CSE 341, Spring 07 Assignment 3 Due May 11 1. OVERVIEW Over the next two assignments you'll be implementing a Scheme interpreter for a significant portion of the language. You'll start with the file meta-eval.scm. This is a working Scheme evaluator that supports a very small subset of the language: number, string, and boolean literals, and 'if' expressions. Your job in assignment 3 is to add the following language features: - defining new variables with the 'define' form - accessing variables in the current frame - mutating variables with the 'set!' form - calling built-in procedures, such as '+', 'eq?', 'cons', 'cdr', etc. - executing a sequence of statements with 'begin' User defined procedures will be left until next week. 2. PROVIDED CODE The interpreter is run through the Read-Eval-Print-Loop. Look over this section of the code to understand how it works, but there's no need to modify it. Your job starts at the eval function. 'eval' takes as arguments a Scheme expression and an environment. For this assignment an environment is just an association list of variable names and their values. 'eval' evaluates the given Scheme expression, making any necessary changes to the environment, and returns a value. Note that 'eval' is recursive--Scheme expressions are composed of smaller Scheme expressions, each of which is evaluated with 'eval'. The simplest expressions are literals--they evaluate to themselves. Next come the special forms. We could list out each special form in the 'cond' expression in 'eval', but we've chosen to use a style called data-directed programming. Rather than hard-code the special forms into eval, we use an association list to associate special form evaluation procedures with their Scheme reserved words. Be sure to understand the example for 'if' and 'quote' expressions before writing your own special forms. 3. FRAMES For this assignment we'll use the term frame and environment interchangeably since there is only one frame in our environment. You are required to represent frames as the symbol 'frame, followed by an association list, where each element consists of a symbol and a value. You will need to write the following functions for manipulating frames: 1. 'lookup-in-frame' takes a symbol and a frame, and returns the value of the given symbol in the frame. 2. 'set-frame-var!' takes a symbol, a value, and a frame, and sets the value of the symbol in the frame to the given value. You may assume that the symbol exists in the frame. 3. 'add-in-frame!' takes a symbol, a value, and a frame, and associates the symbol with the value in the frame. Here's a sample interaction: > (define f '(frame)) > (add-in-frame! 'x 4 f) > f (frame (x 4)) > (add-in-frame! 'y #t f) > f (frame (y #t) (x 4)) > (lookup-in-frame 'x f) 4 > (set-frame-var! 'y #f f) > f (frame (y #f) (x 4)) It's worth understanding why we put the 'frame symbol in front of the association list. Try writing these methods without it, and see what trouble you run into. HINT: Make sure these methods work correctly before moving on to the next part. Debugging an interpreter can be hard! Feel free to use the built in 'assoc' function when appropriate. 4. DEFINE, SET!, and variable access Write two new special case evaluators: 'eval-define', 'eval-set!'. Add these to your list of syntactic forms. Implement variable access. Can you handle variable access via the syntactic forms list? Where does it need to go instead? 5. BUILT-IN PROCEDURES So far our only data types are numbers, strings and booleans, and we represented them by Scheme's underlying data types. Procedures will require a little more structure. A procedure value in your interpreter will look like: ('primitive ) That is, the addition function could be built by saying (list 'primitive +) We need the 'primitive symbol to distinguish the built in procedures from the user-defined procedures we'll implement in the next assignment. Before you can call a primitive procedure, you need to give it a name. Primitive procedures are variables in the frame, just like any user defined variable. We think of them as 'built-in' because they come predefined when we launch the interpreter. Implement this by creating a variable called 'initial-frame'. Bind each of your primitive procedure values to their appropriate names. Then use 'initial-frame' as the initial frame when the interpreter is launched. For built in procedures, include at least the following: - arithmetic: +, -, /, *, <, >, = - equality testing with eq? - list operations cons, car, and cdr Once you've installed these in the initial frame, you should be able to run your interpreter and get the following interaction: ;;; M-Eval input: + ;;; M-Eval value: (primitive #) The next step is to add an 'eval-procedure-call' evaluator. Again, can this be added as a special form? Where do you need to put it? Remember, in Scheme ANY list that doesn't start with a special form is assumed to be a procedure call. 6. BEGIN Add 'begin' as a syntactic form. This should be easy by now! 7. TESTING Include in comments at the end of your file a copy of some interactions with your interpreter showing that each of the features you implemented works correctly. 8. FEEDBACK Also in a comment at the end of your code tell us approximately how many hours it took you to do this assignment. It won't effect your grade, we're just curious. A FINAL HINT: If you get stuck on one part, or your code is looking ugly, take a step back and think about your approach. Ask us questions. The longest procedure in my solution is 4 lines long; most are only 1 line.