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

Translating and Interpreting Recursive Functions.

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.