CS 7400 Machine Problem 4: Big-Step Semantics, Environments

Out: Thursday, 10/8/09

Due: Thursday, 10/15/09

For this problem, you will complete the lexical-address calculator discussed in lecture 4, lexaddr-lang.

1. (5 points) Fill in the remaining definitions in translator.scm to make the tests work.
2. (5 points) Extend your system to handle EOPL Exercise 3.18 (unpacking lists) from MP3.
3. (10 points) Extend your system to handle letrec. You will have to add both letrec-exp and nameless-letrec-exp. You will have to write something like extend-nameless-env-recursively, and in this procedure you may use the same kinds of Scheme primitives that were used for this in the lecture notes.
4. (10 points) Add let* to the language. It should have the same scoping behavior as in Scheme, but its syntax should be compatible with the rest of the language.

   Here are some tests to make sure you have the right behavior

   let x=1 in let* x=0 y=x in y       => 0
   let x=1 in let* y=x x=0 in y       => 1
   let x=1 in let* x=+(x,1) y=x in y  => 2
   let* x=2 x=+(x, 1) in x            => 3
   

5. (10 points, extra credit) Extend your system to handle multiple arguments. This should include:
   • Multiple-argument procedures and procedure calls
   • Multiple-declaration lets
   • Letrecs that declare multiple procedures of multiple arguments
6. (10 points, extra credit) Modify your system to use a vector representation of environments, as discussed in class, so that variable reference is a single vector-ref, and therefore takes constant time. You needn't make this fancy (eg, by having the environment only include the variables that actually occur in the procedure body, or by special-casing the formal parameter of a procedure. However, if you do this for the multiple-argument language of the preceding question, please arrange things so that a variable reference still takes only a single vector-ref.

As before, you should turn in your solution as a single set of PLT Scheme modules. So if you do multiple arguments, you don't need to turn in a separate solution for the one-argument case; if you do the vector representation of environments, you don't have to turn in a separate solution using the naive data-structure representation.