For Homework 2 I have asked you to write an interpreter for lambda calculus using call-by-name interpretation semantics. Here's a bit more detail about what that involves.
1. Design a data structure for representing the abstract syntax of lambda calculus. If you're writing Haskell this is an algebraic type, for Scheme used the define-type extension, for Java or C++ use a tree class. This is the data structure that will represent your expressions. There should be one definition for each language term type - variables, lambdas and apps. Because lambdas and apps contain terms, they will cause the data structure to be a tree.
2. Define the shift and substitute functions that Pierce defines in the text. If you define these correctly, then the interpreter is just the proper composition of the two. You'll need to represent the context of your interpreter to do this. Use a list to do this as described below.
3. Define DeBrujin interpreter that is simply a function that will manipulate the tree. Note that it should have two arguments - context and expression. The context will keep track of assignments to variables. My suggestion is to use a list for this where the list index is the DeBrujin number and the list contents are bindings of values to those numbers.
4. Define and execute a collection of test cases. You should be able to get plenty from your text. One of the more interesting text cases would be a Y combinator that allows you to write recursive functions. Church Booleans, Church Numbers and pairs would also be good test cases.
I'll move all this to the main website, but for now this will get you started.
No comments:
Post a Comment