CS G111 Machine Problem 5a:
A Lexical-Address Calculator

Out: Tuesday, Oct. 16, 2007

NEW: Only the Java part is due on October 23. The Scheme part is due one week later.

Due: 10/23/2007

Mail messages related to this assignment will be archived here. FAQs for this assignment are collected here. You should check this archive before asking a question.

For this problem, you will complete the lexical-address calculator discussed in lecture 4, /course/csg111/interps/lecture04/lexaddr-lang.

Each problem is worth 5 points.

1. Fill in the remaining definitions in translator.scm to make the tests work.

2. Extend your system to handle "pair" and "unpair" from MP3.

3. Extend your system to handle letrec (Exercise 3.40). 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.

As in the notes, the output of your translator should be a program with no identifiers in it, and your interpreter should be able to evaluate the output of your translator.

Test your solution by running it on the tests in tests.scm, plus the tests you added for "pair" and "unpair" from MP3.

You don't need to write any specification rules for this assignment.

Turn in all these extensions in a single set of modules.

Here comes the Java part which consists of two subparts. The structure-shy interpreters and address calculator in Java using DemeterJ were written by Bryan Chadwick. In the lectures we will go through a sequence of his interpreters.

In this part we pursue again the Elevation problem solving approach
(a term from Minsky)
and write structure-shy interpreters.
This is in preparation of a lexical address
calculator in Java using the structure-shy elevation
approach. The elevation approach is associated with
Polya's inventor's paradox.

Consider the interpreter in mp5/StackAddr_3_b
here. 

Part 1.1 Each operator implementation is worth one point.

The interpreter supports a limited set of operators.
Extend the interpreter so that it handles the following operators:
(Note that Plus and Mult and Eq are already implemented.)

Op: Plus | Minus | Mult | Div |
    Less | Greater | Or | And | Eq |
    Print common implements Val.
Plus = "+".
Minus = "-".
Div = "/".
Mult = "*".
Less = "<".
Greater = ">".
Or = "or".
And = "and".
Eq = "=".
Print = "print".

The operators have the usual meaning. Print returns zero,
so you should use the template:

Print{ {{
    public void apply(ValList vals, EvalVisitor ev){
            // one line 
            ev.push(new NumVal(0));
    }
    void run(Val v){ System.out.println(v.toString()); }
}} }

(Print (+ 1 2) (* 3 4))
should print 3 12 and return 0.

PART 1.2: Worth 5 points.

Extend the class dictionary
from the previous part so that the language
handles lambda and the translation to lexical addresses (deBruijn indices).
Use the following class definitions:

Lambda = "(lambda" *s "("  ArgList ")" *s  E ")".
Var = SymOrAddr.
SymOrAddr : Sym | Addr.
Addr = "["  int "]".

ArgList: ArgCons | ArgEmpty.
ArgCons =  Arg *s  ArgList.
ArgEmpty = .

Arg = *s  Sym .
Sym =  Ident.

Turn in your complete class dictionary, tested with both
nameless lambda expressions (using lexical addresses)
and the corresponding normal lambda expressions.
Use the example on page 89 of EOPL3 (Fig. 3.13)
and its translation to deBruijn indices as test cases.

Put all the data structures that you will need for the complete
implementation of lambda expressions into the class dictionary.
By implementation I mean evaluation as well as translation
to deBruijn indices. Specifically, for the interpreter you
need to represent closures. What do you need for the 
deBruijn indices? Take the Scheme code as a guide.