Saturday, December 11, 2010
Tuesday, October 19, 2010
No office hours today
ITTC is being reviewed today and I will not be available for office hours. Class will meet as usual.
Thursday, October 7, 2010
More on Homework 2
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.
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.
Tuesday, September 28, 2010
Next project
As announced informally in class today, our next homework/project will be a call-by-name DeBrujin interpreter. I strongly suggest using Haskell, ML, or Scheme, but you may use the language of your choice if you don't want to learn a new language. I'll post a more formal description shortly.
- Posted using BlogPress from my iPhone
- Posted using BlogPress from my iPhone
Thursday, September 16, 2010
Homework 1
Your first homework assignment is the following problems from the text:
5.2.4, 5.2.7, 5.2.8, 5.2.10, 5.2.11
I'll post a formal entry on the website shortly.
Tuesday, August 31, 2010
No class this week
Just a quick reminder that there will be no class the week of August 30. I will be traveling, but will be back on Friday afternoon should anyone need anything.
Monday, August 16, 2010
EECS 762 Blog
Welcome to the EECS 762 blog. The purpose of this blog is to allow me to communicate with the entire class concerning projects, exams and adminstrivia concerning the class. The blog is available on blogger.com as well as the website if you prefer to follow it that way. However, please to make sure you check the blog frequently.
Subscribe to:
Posts (Atom)