Assignment 7: More Continuations

Instructions:

• Due date: Tuesday, Nov. 26
• Upload your solutions to gradescope as assignment-7.rkt.
• Ask questions on Piazza or during office hours.
• Perform all the work for this project by yourself. You may discuss with your classmates, but you must write your own code and solve your own exercises.
• Starter code: here

Problem 1: Fix the Code [15 Points]

In class we did not have quite enough time to finish the implementation of compiling away exceptions. Here is what we finished: link

This implementation is almost correct, but not quite. Identify all the bugs in this implementation. Refer to specific line numbers, and briefly explain how each of the bugs should be fixed if there is more than 1 bug. You can feel free to refer to the solution in the notes. Put your solution in the problem1 definition in the starter code.

Problem 2: Compiling away Return [85 Points]

Recall the small language from class that makes use of return from Lecture 17. Let’s consider an extended version of this language with lambdas:

(struct rnum (n) #:transparent
  #:guard (struct-guard/c number?))
(struct radd (e1 e2) #:transparent
  #:guard (struct-guard/c (recursive-contract rexpr/c) (recursive-contract rexpr/c)))
(struct rret (e) #:transparent
  #:guard (struct-guard/c (recursive-contract rexpr/c)))
(struct rlam (id body) #:transparent
  #:guard (struct-guard/c string? (recursive-contract rexpr/c)))
(struct rapp (e1 e2) #:transparent
  #:guard (struct-guard/c (recursive-contract rexpr/c) (recursive-contract rexpr/c)))
(struct rident (id) #:transparent
  #:guard (struct-guard/c string?))

(define rexpr/c (or/c rnum? radd? rret? rlam? rapp? rident?))

Problem 2a: A RetLang Interpreter [45 Points]

First we will implement an interpreter (rinterp e) for retlang. Your interpreter should have the following semantics. This language behaves is very similar to the lambda calculi we’ve been seeing so far in class, but with the addition of a rret expression for returning expressions from within functions.

radd is evaluated right to left. This means that (radd e1 e2) first evaluates e2, then it evaluates e1.

Applications (rapp e1 e2) are evaluated using the call-by-value semantics, where e2 is evaluated first, then e1.

(rret e) behaves similar to return in languages like Python and Java: it immediately terminates running the currently executing function, and returns whatever e evaluates to. If rret is called at the top level (i.e., not as part of a lambda), then it should immediately halt execution and return what e evaluates to. Here are some example evaluations. Look at them carefully to get a good understanding for how rret is supposed to work.

> (rinterp (rret (rnum 10)))
(rnum 10)
> (rinterp (radd (rret (rnum 10)) (rnum 30)))
(rnum 10)
> (rinterp (rapp (rlam "x" (rret (rnum 30))) (rnum 10)))
(rnum 30)
> (rinterp (radd 
              (rapp (rlam "x" (radd (rret (rnum 30)) (rnum 40))) (rnum 10)) 
              (rnum 10)))
(rnum 40) 
> (rinterp (rapp
            (rapp (rlam "x" (radd (rret (rlam "y" (rident "y"))) (rnum 30))) (rnum 30))
            (rnum 40)))
(rnum 40)

Problem 2b: Compiling RetLang into the Lambda Calculus [40 Points]

Following the example we saw from class, implement the compile function that compiles RetLang into the lambda calculus, using the provided lambda calculus interpreter. Your compiler should not make use of rinterp or otherwise evaluate RetLang programs.

For example, the following tests should pass:

(check-equal? (compile-and-run (rapp (rlam "x" (rret (rnum 10))) (rnum 30))) (lnum 10))