HW Assignment 3 - Spring 2001 - Michael Elhadad

<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.

<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.