CS 441 Assignment 5: Continuation-passing Interpreters

This assignment is due Thursday March 15 at 10:30am by electronic submission.

Read this entire assignment before beginning work.

Read EOPL Chapters 8 and 9 for background.

Part 1: Interpreting Scheme Again

Add letrec, begin, and set! to the interpreter from part 1 of assignment 3. That is, support the following subset of Scheme: 
 e ::= n                  
     | #t                 
     | #f                 
     | ()                 
     | (quote x)          
     | x                  
     | (if e e e)         
     | (lambda (x ...) e) 
     | (let ((x e) ...) e)
     | (let* ((x e) ...) e)
     | (letrec ((x f) ...) e)
     | (set! x e)
     | (begin e e ...)
     | (e e ...)
where n is a number, x is a variable, and ... means zero or more of the previous parenthesis-balanced item. Primitives should include 
+ * - / = not eq? symbol? number? cons car cdr pair?
as before. Your interpreter should be meta-circular and direct style, ie., not first-order, not CPS. But do not use Scheme's letrec to implement letrec. Environments should map variables to boxes. You may start from my solution if you wish.

Part 2: Interpreting Scheme in Continuation-passing Style

Perform the CPS transform on your interpreter from part 1. You do not need to CPS the parser nor the environment functions.

Part 3: Control Operators

Add abort and let/cc with semantics as we discussed in class. (My parser has been extended if you are using it.)

EXTRA CREDIT: Dynamic Assignment

Add dynamic-let that interacts correctly with abort and let/cc. That is, using abort or let/cc to throw out of a dynamic-let should restore the old value of the binding. Capturing a continuation, throwing out from a dynamic-let (which restores the old value), then throwing back into the dynamic-let should restore the temporary value.

What to hand in

Turn in a single file that uses no load's other than cs441-load's and has no syntax errors. This file should define a function eval that takes an expression, parses it, and evaluates it in an appropriate initial continuation. Be sure that it works with the product function from class that performs no multiplies if there is a zero in the list.