#### CSCI.4430/6969 Programming Languages Fall 2006 Programming Assignment #1

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 all the help you need from the TA or the instructor. You are encouraged to use the WebCT Discussions page to post questions so that other students can also answer and see the answers. Students are encouraged to work in pairs. Students working individually will be graded in the same manner as students working in pairs. You are encouraged to post to WebCT if you are unable to find someone to work with.

A Lambda-Calculus Interpreter in Oz

The goal of this assignment is to create a call-by-value lambda-calculus interpreter in Oz.

You are to use the following grammar for the lambda-calculus:

 ::= ::= lambda( ) ::= app( )

Once your interpreter is finished, you should be able to execute statements such as:

```{Browse {Run app(lambda(x x) y)}} % should display y
```

Run is equivalent to applying beta-reduction until no longer possible, then applying eta-reduction until no longer possible.

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.

Extra Credit :

• Create a call-by-name lambda-calculus interpreter.
• Create a lambda calculus interpreter which supports Oz functions (i.e. app(<Oz function> <value>)). Be aware that such an interpreter should always give lambda expressions precedence during evaluation to prevent your functions from taking in lambda expressions as arguments before evaluating such lambda expressions. Provide examples of the usage of this interpreter. The grammar for this interpreter is:
 ::= ::= lambda( ) ::= app( )

For example,
`{Browse {Run app(fun {\$ X} X * X end app(lambda(x x) 5))}} % should display 25`
• See the professor or the TA if you have ideas for other extensions to this assignment and would like extra credit for implementing them.

Due Date:
 Received Time Grade Modification before Thursday, October 5, 11:55PM +5% before Friday, October 6, 11:55PM no modification (on time) before Saturday, October 7, 11:55PM -10% before Monday, October 9, 11:55PM -25% after Monday, October 9, 11:55PM not accepted

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 WebCT 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 WebCT). Please submit your file via WebCT.