CSCI.4430/6969 Programming Languages Spring 2010
Programming Assignment #2

This assignment is to be done either individually or in pairs. Do not show your code to any other group and do not look at any other group's code. Do not put your code in a public directory or otherwise make it public. However, you may get help from the TAs or the instructor. You are encouraged to use the RPILMS Discussions page to post questions so that other students can also answer and see the answers.

An interpreter for a subset of Scheme in Oz

The goal of this assignment is to write an interpreter in Oz for a restricted version of Scheme. The interpreter should be able to reduce Scheme expressions that correspond to the lambda calculus in a call-by-value (applicative order) manner.

The input to your interpreter will be a sequence of lambda calculus expressions separated by ";", each expression in the concrete Scheme-like syntax:

e :==  v

|      (lambda(v) e)

|      (e e)

For your convenience, we have provided an Oz parser to parse the Scheme-like syntax into an Oz list of records, each record representing a lambda calculus expression. Please follow the provided readme file for instructions on using the parser.

Your interpreter is expected to take each of these lambda calculus expressions and perform repeatedly beta reduction until no longer possible (a value expression that can no longer be beta-reduced) and then eta reduction until no longer possible.

An example follows. The parser takes an input file 'Lambda.in', where ‘Lambda.in’ contains Scheme-like lambda calculus expressions separated by ";" for example:
------------
% some input to test the lambda calculus interpreter
((lambda (x) y) z);
(((lambda (x) x) (lambda (y) y)) x);
((lambda (x) x) z)
------------
The parser (using the given parser code) will produce the following Oz list:
------------
[apply(lambda(x y) z)
apply(apply(lambda(x x) lambda(y y)) x)
apply(lambda(x x) z)]
------------

Now, your task is to evaluate the list of expressions, one by one. When correctly evaluated the above list of (three) expressions will print the following final result:
------------
[y x z]
------------

Hints: You may define auxiliary procedures for alpha-renaming, beta-reduction, and eta-reduction. For beta reduction, you may want to write an auxiliary procedure that substitutes all free occurrences of a variable in an expression for another expression. Be sure that the replacing expression does not include free variables that would become captured in the substitution. Remember that in call-by-value, the argument to a function is evaluated before the function is called.

10% Extra Credit:

Create a call-by-name (normal order evaluation) restricted Scheme interpreter.

See the professor if you have ideas for other extensions to this assignment and would like extra credit for implementing them.

Due Date:

The assignment will be graded mostly on correctness, but code clarity / readability will also be a factor (comment, comment, comment!). Be sure your solutions are robust.

Submission Requirements: Your code should consist of an Oz file, plus a README file. Combine these files into a single ZIP file with your LMS user name(s) as the filename, either userid1.zip or userid1_userid2.zip. Only submit one assignment per pair (the other does not need to submit anything via RPILMS). Please submit your file via RPILMS.