Project Assignment 3
"Due": Oct 26 (subject to change)
Description of Problem/Process
We'd love it if you could work in looking at/writing an interpreter this week. If it just doesn't fit, don't worry about it, but -- writing a Lisp interpreter in Lisp is a good brain exercise. Futz with the names of things if it helps -- rather than using (if...) to write (if...), call your conditional, oh, say, (suppose...). Again, SICP/Wizard ch 4, or various places on the internet. Katie actually still remembers writing a Scheme interpreter in Common Lisp, going to her with questions is totally acceptable. Tokenizing in other languages like Java or Python is not terribly hard, if you'd rather not use Lisp.
- More details:
You are writing evaluate expression in environment. You will also need apply operation to values (in environment if you're applying lambdas).
- Start with evaluating arithmetic operations.
- Add a conditional.
- Add the ability to look up variables. Note that you will have to manually add these variables to the environment in which you're evaluating.
Adding define requires modifying data structures (specifically the environment). You can learn about set! or set-car!/set-cdr! and do this or skip definitions.
Adding non-recursive lambdas is cool and mind-bending but mostly requires getting apply to work. You don't need define.
Adding recursive lambdas is cool and mind-bending but requires getting define to work or otherwise being able to muck with the environment.
Adding begin allows you to hack define without mutation by evaluating subsequent expressions in the environment left by earlier expressions.
- By now you've more than used up your week!
Final goal
Write eval:
- Interpret nested arithmetic expressions
Further: add names(define) and/or conditionals(if, cond)
Further: build procedures (w/ or w/o define) (also requires apply)