Part 5 should be completed before class on Thursday, April 27
Final project due Monday, May 8 at noon
If you are still working on Part 4, please let me know if you need help. It is important that you don't fall behind.
To get the code for Part 5 and some wrap-up tests from Part 4, you will first need to run the command update37. Once you have done so, you will have created a new directory (cs37/homework/i-5) which has the new i-tests and interpreter pieces. To join your old code and tests (from cs37/homework/i-4) with the new code and tests in cs37/homework/i-5, run the merge script.
By now, you should be comfortable writing your own wrap-up tests. Your interpreter should successfully run the tests you create in i-tests.ss, but it is strongly recommended that you type some or all of the code in by hand to verify that the interactions are working properly. In particular, i-tests.ss cannot test exit, exit!, or functions that print to the screen (display, newline, etc) properly, so you should try these by hand.
This is a very important section: be sure you understand it before moving to the next section.
In Part 5, we are going to add lambda and let expressions to our interpreter. The focus of Part 5, though, is on lambda. As we have seen in class, and will see in the section for handling let, we can apply a simple syntactic transformation to let expressions that turn them into lambda expressions. In other words, once our interpreter has the ability to handle lambda expressions, we will have written nearly all of the code necessary to handle let expressions too. (And, as you will soon see, let* expressions as well.)
Some of the terminology in this portion of the interpreter may be new to you, and it is important that you read carefully to be sure you don't get the definition of a procedure confused with the evaluation of a procedure, or confused with the application of a procedure. While you work on this portion of the interpreter, it is important to keep these three concepts separate.
Introducing lambda expressions into our interpreter will add complications that we have not had to worry about up to this point. First, let's consider an easy example from Scheme:
(define x 200)
(define y 100)
(define f
(lambda (x)
(+ x y)))
(f 50) ; returns 150
x ; still 200
While it should seem obvious from the above example that the answers
Scheme returns are correct, there are some important details to
notice. First, both x and y are defined in the
environment before f is defined. When we apply the procedure
f to the argument 50, we assign the local parameter
x to be 50 and then evaluate (+ x y). When we
evaluate y, we find that it is bound to 100; when we evaluate
x, we find that it is bound to 50; and so we return 150.
However, when we exit the procedure and evaluate x by itself,
we get 200, not 50. Think how we might do this and then consider the
following code:
(define x 200) ;same as above
(define y 100) ;same as above
(define f ;same as above
(lambda (x)
(+ x y)))
(define g
(lambda (y)
(f y)))
(g 50) ; ???
y ; still 100
Now things have become more interesting. Just before we apply the
procedure g to 50, x and y are still bound
to 200 and 100, respectively. When we apply g to 50, the
local variable y in g gets bound to 50, so (g
50) evaluates to become (f 50) in an environment where
x is 200 and y is now 50. When we apply
f to 50, the local variable x gets bound to 50. So,
what does (+ x y) evaluate to be?
You'll find that Scheme evaluates (+ x y) to be 150. This may seem odd. Why? Well, we know that the local variable x will evaluate to 50, leaving us only to evaluate y. So, what is y? Notice that there are two plausible answers here. If you thought that since y was bound to 50 in g, y should now be 50 in f, then you thought that Scheme uses dynamic scoping. Although some implementations of Lisp, the language that Scheme was derived from, use dynamic scoping, Scheme does not. (One example of a Lisp-based language that does use dynamic scoping is elisp, a language designed so that you can write and install new extensions to emacs, a popular Unix text editor.)
If you thought that (+ x y) should be 150, then you thought that Scheme uses static scoping, and you would be correct. (Most modern programming languages, for example C, C++, Java, and Scheme, all use static scoping.) Static scoping says that the environment where you define a procedure should be the environment in which you apply the procedure. Let's see what that means by taking a look at how we will implement it.
The way that static scoping is implemented is through the creation of a closure. When a procedure, such as (lambda (x) (+ x y)), is defined, we will create a closure which will contain the actual definition of the procedure, as well as the environment in which it is defined.
When we go to define the procedure f, the environment contains a single frame with two bindings (for this example, we will exclude the primitives). So, the environment is represented as: (((y 100) (x 200))). The closure we create will have both the definition of the procedure, and this environment. To help us differentiate between closures and primitives in our interpreter, we will tag the list with the symbol closure. So, the closure we create for this procedure will look like this:
(closure (lambda (x) (+ x y)) (((y 100) (x 200))))
At the start of this portion of the interpreter, I said that it was important to keep the definition, evaluation and application of lambda expressions separate. The code (lambda (x) (+ x y)) is the definition of a procedure that evaluates to be a closure (such as the one above).
If we define a variable to be a procedure, as we do with f when we say (define f (lambda (x) (+ x y))), then we simply add a new binding to our environment which binds f to the closure. (If you go poking around in the details, you'll find that this gives us an odd-looking recursively defined environment because the variable f is stored in the environment as being bound to a closure which itself stores the environment... so you'll see some of that #0= notation which we saw when we created circular lists.)
So, what happens when you type (f 50)? First, Scheme evaluates both f and 50. Scheme will look up f in the environment, finding a closure, and 50 evaluates to itself. Then we apply the closure to 50. To apply a closure to a list of arguments, we do the following: First, the environment, which is saved in the closure, will get temporarily extended to include bindings of each of the procedure's parameters (which is just x in this example) to the values of the arguments (which is 50 here). Then, the lambda expression stored in the closure is evaluated with respect to this extended environment, and the resulting answer will serve as the final answer for the procedure application. So, after we extend the environment (((y 100) (x 200))) to include the new binding (x 50), we evaluate (+ x y) and get 150.
We'll go into details in the next sections.
(You may wish to refer to the summary page.)
As mentioned in the introduction, when we define a lambda expression, we will construct a closure which is a tagged list containing the symbol closure, followed by the lambda expression, followed by the current environment:
(define make-closure
(lambda (lambda-exp env)
(list 'closure lambda-exp env)))
Here is an example of what happens in Scheme when we evaluate a lambda expression:
> (lambda (y) (+ x y)) #<procedure:3:2>What Scheme is actually storing is a closure, though it hides the internal representation from you by reporting only #<procedure:3:2>. When we evaluate a procedure in our interpreter, we get the following:
INTERPRETER> (lambda (y) (+ x y))
(closure
(lambda (y) (+ x y))
(((null ())
(car (primitive car #<procedure car>))
...
))
)
(Notice that it displays the entire environment, including all the
primitive procedure definitions. This will get very tedious. So, we
will soon write i-print which, along with a few other things,
hides the environment when displaying closures.)
When our interpreter encounters a lambda expression, it should create a closure. We can accomplish this by adding the following line to i-eval:
((lambda? exp) (make-closure exp env))Define the tester lambda?, which checks if an expression is a lambda expression.
Now we need to define testers and selectors for closures:
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define closure?
(lambda (closure)
...))
> (closure? (make-primitive '+ +))
#f
> (closure? (make-closure '(lambda (x) (+ x y)) global-env))
#t
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Selects the parameter names from a closure
(define procedure-parameters
(lambda (closure)
...))
> (procedure-parameters (make-closure '(lambda (x z) (+ x y)) global-env))
(x z)
> (procedure-parameters (make-closure '(lambda () (display 5) (newline)) global-env)
()
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Selects the body of the procedure from a closure
(define procedure-body
(lambda (closure)
...))
> (procedure-body (make-closure '(lambda (x z) (+ x y)) global-env))
((+ x y))
> (procedure-body (make-closure '(lambda () (display 5) (newline)) global-env))
((display 5) (newline))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Returns the environment saved in a closure
(define procedure-env
(lambda (closure)
...))
> (procedure-env (make-closure '(lambda () (display 5) (newline)) empty-env))
() ; this is the empty-environment
> (procedure-env (make-closure '(lambda () (display 5) (newline)) global-env))
... ; returns the global environment
All we have to do now is apply our lambda expressions (which are now closures) to a list of arguments. Let's follow this next example step by step. This expression should return 20.
((lambda (x) (+ x 30)) (/ -50 5))First, i-eval will recognize this expression as a procedure application (since it's a list and you wrote application? in Part 2). It will then (recursively) evaluate the operator (lambda (x) (+ x 30)) using the current environment, evaluate the list of operands ((/ -50 5)) using the current environment, and then call i-apply to apply the resulting closure to the list (-10). The closure obtained by evaluating the operator will look like this:
(closure (lambda (x) (+ x 30)) (((null ()) (car (primitive...)) ...)))In i-apply, we will need to add a case to handle closures:
((closure? proc) (apply-closure proc vals))The new procedure apply-closure should implement the steps described above. In particular, apply-closure should first extend the environment stored in the closure using the procedure's parameters bound to the list of values. Then it should evaluate the body of the procedure in the context of that new environment. In this case, a new frame containing the single binding (x -10) will be added to the procedure's environment, and then the sequence of expressions in the body ((+ x 30)) will be evaluated in that new environment, yielding a final result of 20.
Remember that the body of a procedure is a list of expressions to be evaluated, so you cannot use i-eval directly on the body. Instead, you must call i-eval on each expression, in order from first to last. You should be able to handle the evaluation of the procedure body using the eval-begin procedure you wrote in Part 4.
Make sure you clearly understand these steps before you try to update i-apply and write apply-closure. Once you have implemented procedure application in your interpreter, try the test application-test-1 included in i-tests.ss to make sure things are working properly. You may want/need to trace i-eval and i-apply as you try the above examples. As always, be sure to come up with your own tests.
Before we go on to let expressions, first consider what happens when we do the following:
INTERPRETER> (define f (lambda (x) (+ x 1))) f INTERPRETER> fThe define expression binds the symbol f to a closure in the global environment. So evaluating f causes our interpreter to look up the value of this variable in the global environment. That value is a list of the form:
(closure lambda-expression environment)More precisely, it will look like:
#1=(closure
(lambda (x) (+ x 1))
(((f #1#)
(null ())
(car primitive car #<primitive:car>)
...
What happened? We created a circular structure! The symbol
f is bound to the above object in the global environment, but
that object itself includes the global environment as part of its
structure, so Scheme catches this loop (much like it did earlier this
semester when we were playing around with set-cdr!) and
displays the environment using the #1 syntax.
It would be a lot easier to read this if we didn't display the whole closure -- rather, we should just print out the definition of the procedure. Write i-print which, takes one parameter and does the following:
After you have written i-print, substitute the call to pretty-print in read-eval-print-loop with a call to your i-print function.
(You may wish to refer to the summary page.)
A let expression has the following syntax:
(let ((var1 val1) (var2 val2) ... (varn valn)) exp1 exp2 ... expm)As we have seen previously in class, this is simply shorthand for the following:
((lambda (var1 var2 ... varn) exp1 exp2 ... expm) val1 val2 ... valn)Modify your interpreter so that it can recognize and correctly handle let expressions. You should write procedures called let? and let->lambda. The procedure let->lambda should take a let expression and return an equivalent application expression as specified by the above syntactic equivalence rule. When i-eval encounters a let expression, all it needs to do is transform the expression into an equivalent application expression (using let->lambda), and then i-eval will just call itself again on the new expression. Try the tests included in the test file when you are done.
A let* expression has the same syntax as the let expression:
(let* ((var1 val1) (var2 val2) ... (varn valn)) exp1 exp2 ... expm)Here is how the Help Desk in DrScheme explains the let* special form:
Syntax: <Bindings> should have the form ((<variable1> <init1>) ...),
and <body> should be a sequence of one or more expressions.
Semantics: Let* is similar to let, but the bindings are performed sequentially from left to right, and the region of a binding indicated by (
(let ((x 2) (y 3))
(let* ((x 7)
(z (+ x y)))
(* z x))) ===> 70
Like let, the let* expression can be transformed into a expression we already know how to handle. The let* expression does not transform directly to a lambda expression the way a let expression does; rather, let* expressions can be transformed into a series of nested let expressions as follows:
(let ((var1 val1))
(let ((var2 val2))
...
(let ((varn valn))
exp1
exp2
...
expm
)
)
)
Modify your interpreter so that it can recognize and correctly handle
let* expressions. You should write procedures called
let*? and let*->let. The procedure
let*->let should take a let* expression and return
an equivalent let expression. This let expression
should then be evaluated using i-eval. Try the tests
included in the test file when you are done.