CIS352 Spring 2020 — Final Exam (Part 3)
SU ID: _____________________ Name: ________________________ Links to all parts: Part 1 Part 2 Part 3
Fill out your SU ID and email this part to Kris Micinski (kkmicins@syr.edu) when you finish.
Instructions:
1. This exam has three parts, each consisting of 4 problems.
2. This exam is “open everything except collaboration”
a. You may refer to your old notes
b. You may use DrRacket
c. You may google for anything on demand
d. You may not collaborate with your friends
e. You may not post questions to StackOverflow / freelancr / etc…
3. Please ask us clarification questions, but please do not ask us help questions (e.g., asking help on how to debug your code).
4. Unless specified otherwise, you may use any standard built-in Racket function / form / etc…
5. Each problem is worth 10 points
6. The entire exam is worth 120 points
7. The exam will be graded out of 100 points (no extra credit)
8. Work each part in its corresponding document.
9. Use Google Docs’ “copy” feature to make yourself a copy of the
exam.
10. Fill out your SU ID and name at the top of each part
11. Then email to
a. Part 1 — Jack Vining (jcvining@syr.edu) b. Part 2 — Yihao Sun (ysun67@syr.edu)
c. Part 3 — Kris Micinski (kkmicins@syr.edu)
[10 points] Problem 9 (Higher-Order Function Concepts)
For this problem, recall our definition of number trees:
(define (number-tree? l)
(match l
[’empty #t]
[(? number? n) #t]
[`(,(? number? root) ,(? number-tree? e0) ,(? number-tree? e1)) #t]))
● [10] Write a function, (fold-numtree tree (lambda (n acc) …) i) which folds, in any undefined order (you can do inorder, preorder, postorder, etc… it doesn’t matter) the specified lambda over all of the tree’s numbers. The function should return i for the empty tree.
○ ;; for example, might count nodes in numtree as…
○ (fold-numtree ‘(1 2 3)
(lambda (n acc) (+ 1 acc))
0) ;; 3
[10 points] Problem 10 (Church Encodings)
Consider the following code:
(letrec ([even?
(lambda (x) (cond [(= x 0) #t]
[(= x 1) #f]
[else (odd? (- x 1))]))]
[odd?
(lambda (x) (cond [(= x 0) #f]
[(= x 1) #t]
[else (even? (- x 1))]))])
(odd? 22))
This code implements a very laborious way to implement even? and odd? In terms of each other. Because the code is all placed in one big letrec, each of the functions can refer to each other. In this problem, you will implement this behavior without letrec.
Approach sketch: think about how to modify the U or Y combinator to accept multiple arguments rather than just one. Instead of taking a fixed-point over a single function, you can make a version of Y or U that works with more than one function. You can get mutual recursion by modifying recursive calls (e.g., the call to odd? within even?) and passing them an argument along with the “next copy of yourself.” Realize that you may want to store, for example, a list of functions in your modified Y/U combinator, and may have to modify calls to work as appropriate.
● [10] Translate the above code to use only let, not letrec. As mentioned, the tricky part is the mutually recursive calls. You have to find a version of the Y / U combinator that allows this and update the mutually-recursive calls appropriately.
[10 points] Problem 11 — Store Passing Style
In project a5, we implemented a stack-passing style interpreter. One feature we didn’t talk about during this class was mutable state. It turns out that you can easily-enough modify your interpreter from project a5 to include one more component: a store, which maps variables to (mutable) values. To do so, you would define a function (interp-CESK e env store kont), which accepts an expression, an environment, a store, and a continuation. Consider that we want to interpret the following language:
(define (lang? l)
(match l
[`(store-set! ,(? symbol? x) ,(? symbol? y)) #t]
[`(store-ref ,(? symbol? x)) #t]
[(? boolean?) #t]
[`(lambda (,(? symbol? x)) ,(? lang? e-body)) #t]
[`(,(? lang? e0) ,(? lang? e1)) #t]
[(? symbol? x) #t]))
This language has been extended with two forms, (store-set! x y), which sets the store variable x to the contents of the variable y in the environment. We also add (store-ref x), which looks up a variable from the store. For example:
((lambda (x) (store-ref y)) ((lambda (x) (store-set! y x)) 42)) ;; returns 42
● [10] Starting from the attached starter code, implement a CESK-style interpreter. That is, a store-passing and stack-passing interpreter.
○ Your implementation of (store-set! x y) should (hash-set store x (hash-ref env y)) and (for the purposes of the continuation) return whatever value was stored.
○ Your implementation of (store-ref x) should (hash-ref store x) ○ Hint: because of the we store-ref and store-set! are defined, you don’t
need any special new kinds of continuations. However, you will have to modify calls to interp-CESK to update the store appropriately.
Code follows on next page…
(define (interp-CESK cexp [env (hash)] [store (hash)] [kont ‘halt])
;; May want to modify return as well
(define (return kont v)
(match kont
[`(fn (closure (lambda (,x) ,body) ,env) ,k)
(interp-CESK body (hash-set env x v) store k)]
[`(ar ,e0 ,env ,k)
(interp-CESK e0 env store `(fn ,v ,k))]
[‘halt v]))
(match cexp
[`(store-set! ,(? symbol? x) ,(? symbol? y)) ‘todo]
[`(store-ref ,(? symbol? x)) ‘todo]
[(? boolean? b)
(return kont b)]
[`(lambda (,x) ,body)
(return kont `(closure ,cexp ,env))]
[`(,fun ,arg)
(interp-CESK fun env store `(ar ,arg ,env ,kont))]
[(? symbol? x)
(return kont (hash-ref env x))]))
[10 points] Problem 12 — Course Reflection
Answer both of the following in 2-5 sentences.
● [5] Identify one concept that you learned in CIS 352 that helped you understand programming in a broader way and discuss its impact on your programming style. Have you made any changes or observations about the way you program as a result of taking the course?
● [5] Particular to the course content and mechanics, what is one constructive piece of advice you would give a beginning student in this course early on to set themselves up to succeed later?