CIS352 Spring 2020 — Final Exam (Part 2)
SU ID: _____________________ Name: ________________________ Links to all parts: Part 1 Part 2 Part 3
Fill out your SU ID and email this part to Yihao Sun (ysun67@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 5 (call/cc)
Consider the following code:
(define (protect x)
(if (< x 0)
(error "bad")
x))
(define (my-fun x)
(call/cc
(λ (y)
(protect x)
(protect (call/cc (λ (z) (+ 1 'todo)))))))
● [4] In the above code, what can replace ‘todo to make it so that my-fun returns the value 0 no matter what the argument is given as x?
Consider the following code, which uses a let-bound call/cc form as a loop:
(define (foo input bound)
(let ([loop-info (call/cc (lambda (k) (cons input k)))])
(if (> (car loop-info) bound)
(car loop-info)
(begin
(pretty-print loop-info)
((cdr loop-info)
(cons (* (car loop-info) (car loop-info)) (cdr loop-info))))))
● [3] Explain in about a sentence or two (perhaps using some math) what the above code is computing.
● [3] Using big-O notation, give a bound on maximum stack size incurred while executing the above loop, in terms of input and bound.
[10 points] Problem 6 (church encoding)
Errata in RED: the U combinator was incorrect at first.
In this problem, you may assume that the variable U is defined as the U combinator (lambda (x) (x x)). Consider the following code:
(let ([f (U (lambda (f) (f f)))]) (f f))
● [7] Assuming the existence of a variable U bound to the U combinator, translate the above code using the church encodings discussed in class.
● [3] If you attempted to continually -reduce the term in your answer just above, would you eventually arrive at some normal form?
[10 points] Problem 7 (lambdas, closures, and laziness)
For the purposes of this problem, we will call functions streams when they:
● Are nullary-argument lambdas
● Return a cons cell consisting of some value and another stream
Streams specifically are not lists. They are lazy lists. We treat them accordingly. We define (take-n s n), which returns the first n elements from the stream s as a list: (define (take-n s n)
(if (= n 0) ‘()
(let* ([forced (s)]
[next-elt (car forced)]
[next-stream (cdr forced)])
(cons next-elt (take-n next-stream (- n 1))))))
Using this setup, we can model infinite data. For example, consider the stream which counts up from some input n:
(define (counter n)
(lambda ()
(cons n (counter (+ n 1)))))
(take-n (counter 0) 5) ;; ‘(0 1 2 3 4)
● [5] Write a function (double s), which both accepts a stream and returns a stream. The return stream should double each element of the input stream. For example:
(take-n (double (counter 0)) 5) ;; ‘(0 2 4 6 8)
● [5] Write a function (stream-map s f), which returns a stream such that each element of the resulting stream will be (f x), where x is the corresponding element of the input stream s
(take-n (stream-map (counter 0) (lambda (x) (* x 2))) 5)
;; ‘(0 2 4 6 8)
[10 points] Problem 8 (continuation-passing style)
Consider the following piece of code, which implements the factorial function:
(define (factorial n)
(if (= n 0)
1
(* n (factorial (- n 1)))))
In this problem, you will use the concept of continuation-passing style to create a CPS version of the factorial function, (factorial-cps n k), which takes a number n and an initial continuation k and computes the factorial of n, invoking k on that result.
For example:
(factorial-cps 10 (lambda (x) x)) ;; returns 3628800
To define your function, you will need the following CPS-based version of the following operators:
(define (=k n0 n1 k) (k (= n0 n1))) ;; (=k 2 3 (lambda (x) x)) ;; #ff (define (-k n0 n1 k) (k (- n0 n1))) ;; (-k 1 2 (lambda (x) (+ x 1))) ;; 0 (define (*k n0 n1 k) (k (* n0 n1))) ;; (*k 2 3 (lambda (x) (/ x 2))) ;; 3
● [10] Implement (factorial-cps n k), a CPS-based version of the factorial function. Note that every call in your function must be a tail call, including calls to builtins. To be even more specific, solutions that use * or = rather than (for example) *k or =k will not receive credit (or will receive reduced credit).