CSCI 4430/6430 Programming Languages
Fall 2019
Programming Assignment #1
Due Date: 7:00 PM September 26 (Thursday)
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 mentors, TAs, or the instructor. You are encouraged to use the Submitty Discussion Forum to post problems so that other students can also answer/see the answers.
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:
::=
|
“\”
|
“(”
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,
Your program must accept two command line arguments. The first argument is the name of a file containing a list of lambda calculus expressions. The second argument is the name of the file you will write your reduced lambda calculus expressions into.
Your parser should write out the reduced expressions to a file, 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!) define 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 definition of
Sample Interpretations
Below are some lambda calculus interpretation test cases:
Expression
Result
Comment
(\x.\y.(y x) (y w))
\z.(z (y w))
Avoid capturing the free variable y in (y w)
(\x.\y.(x y) (y w))
(y w)
Avoid capturing the free variable y in (y w), and perform eta reduction
(\x.x y)
y
Identity combinator
\x.(y x)
y
Eta reduction
((\y.\x.(y x) \x.(x x)) y)
(y y)
Application combinator
(((\b.\t.\e.((b t) e) \x.\y.x) x) y)
x
If-then-else combinator
\x.((\x.(y x) \x.(z x)) x)
(y z)
Eta reductions
(\y.(\x.\y.(x y) y) (y w))
(y w)
Alpha renaming, beta reduction and eta reduction all involved
For your convenience, these have been given in a sample input file, 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 find its bundled copy of Emacs). If you are having problems, please post about it on Submitty or come to office hours for help.
A parser is provided. Use this starter code and this provided main file. 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 file and print out both the original and reduced expressions to stdout. Only the lines written to the file 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 file. See also the sample main.hs file (in particular, see the runProgram function.) Specifically, 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.
The provided helper code will both write to stdout and to the output file. The former is inteded to help you during the development process. Only the lines written to the file will matter when the assignment is graded.
Note: Please name your main file ‘main.hs’. It should accept two arguments when compiled and executed. The provided main.hs has this functionality provided.
Sample Interaction
$ cat sample.lambda
(\x.x y)
(\x.\y.(x y) (y w))
$ runghc main.hs sample.lambda output.lambda
$ cat output.lambda
y
(y w)
If you get an error about Text.Parsec being undefined, run stack install parsec (or cabal install parsec)
Further Haskell Hints: It may be useful to consider Map and Set, which can be found in the Data.Map and Data.Set modules, respectively. It is also recommended to use Hoogle, a search engine for looking up Haskell documentation.
If you use an unusual library, you will need to contact the course TAs to have them installed on the Submitty server. Otherwise, your solution will not compile.
Grading: The assignment will be graded mostly on correctness, but code clarity / readability will also be a factor. If something is unclear, explain it with comments!
Correctness is judged by testing if your lambda calculus expressions are alpha-equivalent to the expected expressions. Therefore, your choice of names when performing alpha renaming will not affect correctness, as long as your chosen names are valid (i.e. lowercase alphanumeric strings that start with a letter and are not Oz keywords).
Submission Requirements: You will submit your code via Submitty. Include all source files need to run your program, as well as a README file. We will not automatically include any provided code. In the README file, place the names of each group member (up to two). Your README file should also have a list of specific features/bugs in your solution. If you are working with another student, then only one member of the team needs to submit.
Working alone/in pairs: You may work alone, or with one other student. To work alone, simply create a new team on Submitty with only yourself in it. To work with a partner, either invite them to your team, or join their team.