7 Control II: Return of the Control🔗

7.1 A ResExn Interpreter [40 Points]🔗

Resumable exceptions are a version of exceptions that allow the programmer to optionally resume computation when an exception is raised using a resume syntactic construct. Resumable exceptions are very similar to effect handlers, a language feature that is becoming increasingly common in modern languages. We will explore this feature in a language called ResExn with the following abstract syntax:

(define-type ResExn

(numE [n : Number])

(addE [e1 : ResExn] [e2 : ResExn])

(identE [id : Symbol])

(appE [e1 : ResExn] [e2 : ResExn])

(lamE [arg : Symbol] [body : ResExn])

(tryE [body : ResExn] [handler : ResExn])

(resumeE [n : Number])

(raiseE))

(define-type ResExnValue

(lamV [id : Symbol] [body : ResExn])

(numV [n : Number]))

The semantics of this language is very similar to Exn from the previous assignment, except for the (resumeE n) construct that immediately jumps back to the point where the exception was raised and replaces (throwE) with n. If a (resumeE) is attempted outside of the handler of a tryE expression, this should raise an invalid-resume runtime error. Consider the following example programs that illustrate the usage of this feature.

Exceptions should continue to work normally just like in the last assignment:

Notice how the same handler can now be invoked multiple times, since the same program can raise multiple exceptions.

Note additionally that the behavior of resumeE is to immediately jump back to the point where the exception was raised. This means that we should discard pending computation in the handler, which the following test illustrates:

Here, the handler contains an addition that is discarded: when the (resumeE 4) expression is encountered during execution, control should immediately jump back to the raiseE expression in the body and replace it with 4.

Here is an example that illustrates how nesting works:

We see that resumeE works in the intuitive way here by jumping back to the point where the exception was raised.

Just like with exceptions, lambdas should "wait to see" which handler they’re called with, which the following test illustrates:

Your task is to design an interpreter interp-resexn of type (ResExn -> ResExnValue) that implements resumable exceptions.

Hint: You will need to add another exception continuation to your interpreter to keep track of where control flow should go if you encounter resumE. The approach here is a bit like combining the return construct and exception constructs (which is why we called this assignment "return of the control"). Go back and look at these interpreters carefully before starting this one.

7.2 Compiling away resumable exceptions [60 Points]🔗

Suppose you want to add resumable exceptions to your favorite language that doesn’t currently have them, like JavaScript. JavaScript doesn’t support resumable exceptions, but it does support function calls, numbers, etc. So, you decide to compile ResExn into the following mini version of JavaScript’s abstract syntax tree:

(define-type Lam

(identL (id : Symbol))

(lamL (arg : Symbol) (body : Lam))

(numL [n : Number])

(addL [e1 : Lam] [e2 : Lam])

(appL (e1 : Lam) (e2 : Lam))

(errorL))

(define-type Value

(lamLV [id : Symbol] [body : Lam])

(numLV [n : Number]))

Design a function compile of type (ResExn -> Lam) that compiles a ResExn program into a Lam program. For instance, the following tests should pass (where interp is a Lam interpreter that we have provided you in the starter code):

Your compiled lambda calculus program should also raise an exception if the original ResExn program would have raised an exception. For instance, the following test should pass:

Your compile function should not invoke the interpreter for ResExn.