CSE 526
Spring 2005 Stony Brook |
Principles of Programming Languages
Annie Liu Homework 7 |
Handout H7
Mar. 8, 2005 Due Mar. 15 |

This assignment has two parts, each worth 80% and 20% of the grades, respectively. It is due before class on Tue Mar. 15. Please submit your file(s) as a single attachment (made using tar or zip if necessary) in an email to cse526ATcsDOTsunysbDOTedu.

**Part 1. Implementation.**

This assignment asks you to implement an interpreter for REC+let, i.e., REC extended with let-expressions, based on its call-by-value operational semantics. You need to do two steps to achieve this.

Assume a program in REC+let is an expression to be evaluated plus a
set of function definitions of the form `g_i(x_i_1,...,x_i_j) =
e_i`, where `_` denotes subscript.

**1. Translation**. Translate it into a program that uses
neither let-expressions nor function definitions and applications of
the forms given; instead it uses lambdas of the form `fn x e`,
function definitions of the form `g_i = lambda-forms`, and
applications of the form `(f e)`, where `f` is either
`(fn x e1)`, `g_i`, or `((...((g_i e1) e2) ...)
ek)` for some expressions `e1` to `ek`.

For example, program `g(3,5)` plus `g(x,y) = ifz x then y
else x*g(x-1,y)` is translated into `((g 3) 5)` plus `g
= fn x (fn y (ifz x then y else x*((g (x-1)) y)))`.

Note that a let-expression `let x = e1 in e2` can be
translated into the expression `((fn x e2) e1)`.

**2. Evaluation**. Write an interpreter for the lambda-based
intermediate language based on its call-by-value operational
semantics.

**Part 2. Related requirements**.

**Language**. You must do the implementation using ML.

**Usage**. As in Homework 2, how can anyone take your file(s)
and compile and run your program for tests? You should make this as
simple as possible (e.g., by supplying tests or testing scripts if you
feel necessary).

**Output**. Your program should print the input program, the
lambda-based intermediate program after translation, and the return
value from evaluating the intermediate program. Put as many syntax,
in particular parentheses, as necessary to make your printed programs
unambiguous.