Advanced Methods in Programming Languages (201-2-4411-01)
HW Assignment 3 - Spring 2001 - Michael Elhadad

CPS-based Interpreters

Problems for 4 June 2001

CPS Transformation

Implement the full CPS transformation studied in class for the Scheme-like language including the following constructs:
<exp>         ::= <varref>                  varref (var)
               |  <number>                  lit (datum)
               |  (if <exp> <exp> <exp>)    if (test-exp then-exp else-exp)
               |  (proc ({<var>}*) <exp>)   proc (formals body)
               |  (<prim-op> {<exp>}*)      prim-app (prim-rator rands)
               |  (<exp> {<exp>}*)          app (rator rands)
               |  (:= <var> <exp>)          varassign (var exp)
               |  (begin {<exp>}+)          begin (exps)
               |  (let <decls> <exp>)       let (decls body)
               |  (letrec <decls> <exp>)    letrec (decls body)
<decls> ::= ({<decl>}*)
<decl>  ::= (<var> <exp>)                   decl (var exp)
Pay special attention to the "begin" clause which requires a specific treatment, since "begin" does not match the definition of heads/tails we used to characterize the languages to which the CPS transformation applies. The function you must write will be called:
(cps-transform expr)
and it returns a new unparsed expression where the full CPS transformation has been applied to all the lambda expressions in the expression.

CPS-Interpreter and call/cc

Implement an interpreter for the same language as above extended by the call/cc special form. call/cc is defined by the following abstract syntax:
<exp>  ::= (call/cc <proc>)
To implement the interpreter, use a regular interpreter, with the following additions: the expression to be evaluated is first turned into an equivalent CPS expression; this CPS-expression is then evaluated. You must extend the CPS-transformation to support the call/cc form with a special transformation. Verify that the interpreter executes in iterative mode when applied to a form in CPS format.

Interpreter with CPS-transformation

Implement the interpreter using the second strategy which consists of turning the whole interpreter into a CPS expression with explicit continuation support.