CSE 341, Spring 07 Assignment 4 Due May 21 1. OVERVIEW In this assignment we'll add user defined procedures to our simple interpreter. By the end of this assignment you will have implemented the major functionality of a real Scheme interpreter. With a few minor additions most, if not all, of the Scheme programs you've seen in class should be able to run in your interpreter. 2. ENVIRONMENTS In the last assignment we treated frames and environments as the same thing. Now we'll make a distinction. The association list structure from last assignment is a frame. An environment is a list of frames. With the exception of the initial frame, the only way frames are created is through procedure calls. When a procedure is invoked, a new frame is created with the procedure's arguments bound to the values passed in, and that frame is added to the environment in which the procedure was defined. (This is very important--procedure calls extend the environment in which the procedure was defined, not the environment in which it was called. What kind of scoping would we have if we did it the other way?) You'll need several new procedures for dealing with environments. Write lookup-in-environment and set-environment-var! procedures. They should return/set the innermost instance of the given variable (the one nearest the front of the environment list). For concreteness, say we had (define x 42) (define (foo x y) (+ x y)) When evaluating the call (foo 2 4) the environment should look like: ((frame (x 2) (y 4)) (frame (foo (user-proc (x y) )) (x 42) )) And the call evaluates to 6, not 46. Note: We don't need to write an add-in-environment! procedure, because definitions always get added to the current frame. Lookups and mutations, on the other hand, might have to look at enclosing frames. 3. PROCEDURE DATA TYPE A user-defined procedure consists of four pieces - the symbol 'user-proc, to distinguish it from primitives - a list of argument names - a list of expressions in the body - the environment in which it was defined Recall from section that even though Scheme doesn't have an explicit mechanism for creating abstract data types, it is good style to hide the implementation of your data types. Since procedures are relatively complicated objects, we'll write a constructor and accessor procedures. You should write a make-user-proc procedure that takes the argument list, a list of expressions, and an environment. Also write is-user-proc? and is-primitive-proc?. Write accessor methods for the three components of a user-defined procedure. Note: The name of the procedure is not a part of the procedure. Names only get associated with procedure values through define, let, etc. 4. LAMBDA Write and install an eval-lambda procedure. There's nothing fancy to do here. Just package everything up with a call to make-user-proc and return that value. 5. APPLYING USER DEFINED PROCEDURES In your eval-procedure-call procedure, add a new case for user-defined procedures. Again, there's nothing fancy going on here. Just call eval on the body of the procedure. The environment is the environment where the procedure was defined, extended with a new frame containing the arguments bound to their values. You'll probably find it helpful to write a procedure make-frame that takes a list of names and a list of values and turns that into an association list. You saw one way to do this in section a couple weeks ago. Note: In Scheme the body of a lambda expression is implicitly inside a begin form. That is, (lambda () (set! x (+ x 1)) x) is really interpreted as (lambda () (begin (set! x (+ x 1)) x)). You can add the begin either in make-procedure, or when evaluating the call to the procedure. 6. PROCEDURE DEFINITION SYNTACTIC SUGAR Recall that (define (square x) (* x x)) is really syntactic sugar for (define square (lambda (x) (* x x))). Implement this with a procedure proc-define->lambda. This procedure takes in a definition like the former and returns a definition like the later. Note that there's no evaluation going on here, it's just transforming the syntax. Now go back to eval-define and add a check for whether the second element of the define expression is a list. If so, run your proc-define->lambda procedure and evaluate the result. 7. LET SYNTACTIC SUGAR Recall that (let ((x 1) (y 2)) (+ x y)) is just shorthand for ((lambda (x y) (+ x y)) 1 2). [This was not quite true in ML because of some restrictions of the type system, but it is true in Scheme; it's *defined* this way.] Just as you did for the procedure definition shorthand, write a procedure let->lambda that transforms a let expression into the equivalent lambda expression. Now write and install an eval-let procedure that just calls eval on the result of let->lambda. 8. TEST CASES As before, you should write and include test code to convince yourself and us that everything works. Include some more complicated stuff with lambdas, like higher order function, or local state. 9. EXTRA CREDIT Implement some or all of cond, list, let*, letrec. "Inner" defines (not at top level) are only allowed in certain contexts and are to be treated as letrecs. Read the Scheme spec to understand the rules and implement it, and/or try to write an explanation of *why* they wrote the rules this way. E.g., are there subtle problems introduced into the language definition if inner defines act more like top-level defines or vice versa? 10. FINAL THOUGHTS Make sure your implementation from HW3 works. If you're unsure of your implementation, you're welcome to start from our solutions rather than your own. Also, tell us how many hours the assignment took you. It won't affect your grade. A last hint: as always, the solution is short and uncomplicated. Procedures like map can be used in most cases to avoid having to iterate through lists yourself. Spending a couple more hours up front understand what's required will save you time in the long run. And a word about context: with completion of this project you've built a powerful programming language, hopefully in about 250 lines of code. It's not very efficient, especially due to linear time environment searches for names, but don't assume all languages are that bad or that they're all equal. Obviously, there's quite a bit of room for optimization, subject to the constraints of the language definition (and CSE 401 will have a lot more to say about this). But, hopefully, it shows you quite a lot about what goes on behind the scenes in any compiler or interpreter.