[lambdaheads]Program 5
[Programming][Languages]

Write an eager, lexically-scoped interpreter for the following language. Use data structures, not procedures, to represent closures: 

<L> := <num>
     | <id>
     | (fun (<id>) <L>)
     | (<L> (<L>))
     | (<L> + <L>)
Now CPS the interpreter (i.e., CPS the Scheme program, not <L> programs) using procedures to represent the continuations. For this assignment, you may treat the environment and number manipulation procedures as primitives, i.e., they do not need to be CPSed. You must CPS any other helper functions, such as apply-fun.

To CPS a cases statement, examine the expression on which you are going to split into cases. If this expression does not itself contain any (non-primitive) function calls, then you may leave the cases expression in place and only CPS the expression portions of the branches (like we did with if in the CPSed version of filter). If, however, the branching expression contains a function call, then you need to move the cases into the continuation. That is, 

(cases AFunExp v  ;; where v is a variable reference or constant value
  [numE (n) <exp>0]
  [varE (v) <exp>1])
turns into 
(cases AFunExp v
  [numE (n) ... CPSed version of <exp>0 ...]
  [varE (n) ... CPSed version of <exp>1 ...])
whereas 
(cases AFunExp (f v)
  [numE (n) <exp>0]
  [varE (v) <exp>1])
must transform into 
(f/k v
     (lambda (f-of-v-val)
       (cases AFunExp f-of-v-val
	 [numE (n) ... CPSed version of <exp>0 ...]
	 [varE (n) ... CPSed version of <exp>1 ...])))

Finally, represent the continuations as lists, and convert your CPSed interpreter to register form. Use the conventions adopted for the filter exercise: Push procedures do not need to be transformed (but Pop procedures do). The environment and arithmetic procedures are also exempt from conversion. All other procedures must accept no arguments, communicating instead via global registers. You may use let to allocate temporary registers, as in the filter exercise. cases expressions can remain in the final register form, though their sub-expressions must all be converted.

Turning It In

This assignment is due by 2am on 2000-11-15. You must use handin to turn in your homework code. Run 

/cs/bin/handin -c cs173 program5 <filename>
to turn them in. We would prefer a single Scheme file, but if you want to turn in multiple files, create a tar bundle.

You must provide three functions: main, main/k and main/k/reg. Each procedure accepts one argument, an unparsed <L> program representation, and returns a value (if any) in the format

  • a Scheme number, or
  • the Scheme symbol <closure> (i.e., '<closure>)
as appropriate. The value is that left in the register form's ``return value'' register. main uses the simple interpreter, main/k uses the CPSed interpreter, and main/k/reg uses the register form interpreter to evaluate the program.

Follow this interface, and turn in thoroughly tested programs. We will use a script to test your implementation. If the script fails, you fail!