CSCI 4430/6430 Programming Languages Fall 2023 Programming Assignment #1

Lambda Calculus Interpreter

The goal of this assignment is to write a lambda calculus interpreter in a functional programming language to reduce lambda calculus expressions in a call-by-name (normal order) manner.

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

<expression> ::= <atom>

|    "\" <atom> "." <expression>

|    "(" <expression> " " <expression> ")"

Your interpreter is expected to take each lambda calculus expression and repeatedly perform beta reduction until no longer possible. It must then perform eta reduction until no longer possible.

In the above grammar, <atom> is deined as a lower case letter followed by a sequence of zero or more alphanumeric characters, excluding Oz language keywords. A full listing of Oz language

keywords can be found at the top of the PA1Helper ile. Your interpreter is to take lambda

calculus expressions from a text ile (one expression per line) and reduce them sequentially. To   enable you to focus on the lambda calculus semantics, a parser is available for both Haskell and Oz, along with supporting code to handle input and output.

Your program must accept two command line arguments. The irst argument is the name of a

ile containing a list of lambda calculus expressions. The second argument is the name of the ile you will write your reduced lambda calculus expressions into.

Your parser should write out the reduced expressions to a ile, again one per line. If something

goes wrong and you cannot reduce an expression, you should write a single new line and then

continue with the next lambda calculus expression. Writing more than one line, or writing nothing at all, will interfere with autograding. Do not write anything else, such as debug printouts, test numbers, etc.

You may (and should!) deine auxiliary procedures for alpha-renaming, beta-reduction, and eta- conversion. For beta reduction, you may want to write an auxiliary procedure that substitutes all  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-name, the argument to a function is not evaluated before the function is called.

You may choose whatever names you wish when alpha-renaming, as long as they do not violate the deinition of <atom>. Your code will be judged correct if we could make your solution match our solution by renaming zero or more of your variable names.

Sample Interpretations

Below are some lambda calculus interpretation test cases:

For your convenience, these have been given in a sample input ile, where each line contains one lambda expression.

Notes for Oz Programmers

You should remove any other Oz installations and use Mozart 2. You can download the binaries from the project's GitHub repository.

Note for Windows users: the interactive Oz editor may fail to launch if you install Mozart on a path containing spaces. It may also fail to launch due to problems with your environment

(causing Mozart to be unable to ind its bundled copy of Emacs). If you are having problems, please post about it on LMS or come to office hours for help.

A parser is provided. Use this starter code and this provided main ile. main.oz receives    command line arguments and invokes PA1Helper's RunProgram procedure, which handles

reading the input and writing output. You will need to implement the ReduceExp method. The

program will write reduced expressions to the output ile and print out both the original and

reduced expressions to stdout. Only the lines written to the ile will be considered when grading.

Sample Interaction

$ cat sample.lambda

(\x.x y)

(\x.\y.(x y) (y w))

$ ozc -c parser.oz

$ ozc -c PA1Helper.oz

$ ozc -c main.oz

$ ozengine main.ozf sample.lambda output.lambda

$ cat output.lambda

y

(y w)

Notes for Haskell Programmers

Use this parser to get a list of lambda calculus expressions from an input ile. See also the

sample main.hs ile (in particular, see the runProgram function.) Speciically, type constructors for the Lexp datatype have been exported from the module. This datatype is used to represent

lambda calculus expressions in Haskell, and the type constructors should be used to pattern

match a lambda expression. Your goal is to create a reducer function that takes an Lexp value as input and returns a Lexp value as output.