Save a copy of the Part 5 code before you begin.
In our interpreter, the evaluation of a lambda expression in
an environment will consist of constructing a tagged list containing
the symbol lambda-procedure (so that we can distinguish it from a
primitive procedure), followed by the lambda expression itself,
followed by the environment used to evalute the lambda expression.
The following procedure will do this for us:
Here is an example of what happens in Scheme when we evaluate a
lambda expression:
Introduction
When Scheme evaluates an expression like (lambda (x y) (+ x y
a)), it creates a procedure, which can be applied later to some
arguments. This procedure contains two pieces of information: (a) the
original lambda expression from which it was created, and (b)
the environment in which it was created. Should the procedure ever
get applied to some arguments (10 and 20, let's say), two things will
happen:
For example, suppose we do the following:
MINI-EVAL> (define a 100)
a
MINI-EVAL> (define proc (lambda (x y) (+ x y a)))
proc
This will create a procedure (called proc) that contains the
lambda expression itself and an environment. This
environment contains a binding for a (to the value 100). If
we then apply proc to 10 and 20 by evaluating the application
expression (proc 10 20), the bindings (x . 10) and
(y . 20) will be added temporarily to the environment and the
expression (+ x y a) will be evaluated with respect to this
new environment (which now includes bindings for all of the symbols
x,
y, and a). Evaluating (+ x y a) will in turn cause the evaluator to
recursively call itself, until eventually the primitive + procedure is
applied and the value 130 is returned as the final result.
Handling lambda expressions
;;; Constructor for procedures created with lambda:
(define make-lambda-procedure
(lambda (lambda-exp env)
(list 'lambda-procedure lambda-exp env)))
> (lambda (x y) (+ x y a))
#[procedure]
Although we can't see it, this procedural object actually contains
within it a representation for the environment in which the
lambda expression was evaluated. For comparison, here is
what should happen when we use our own mini-evaluator:
MINI-EVAL> (lambda (x y) (+ x y a))
(lambda-procedure
(lambda (x y) (+ x y a))
(((car primitive car #[procedure car]) ...)))
Every time our interpreter evaluates a lambda expression, it
should create a lambda procedure represented as a list of
three items like that shown above. We can accomplish this by adding
the following line to mini-eval:
((lambda? exp) (make-lambda-procedure exp env))
Define the tester lambda?, which checks if an expression is a
lambda expression. Next, we need some helper funtions for
dealing with lambda procedures. It is very important to keep
in mind the distinction between a lambda expression
such as (lambda (x y) (+ x y a)) and a lambda
procedure, which is an object created by the evaluator as the
result of evaluating a lambda expression. Define the
following four testers and selectors for lambda procedures:
;;; Distinguishes between primitive procedures and lambda
;;; procedures by looking at the tag at the front of the object.
(define lambda-procedure?
(lambda (proc)
...))
> (lambda-procedure? '(primitive car #[procedure car]))
#f
> (lambda-procedure? '(lambda-procedure (lambda (x) (+ x 2)) global-environment)
#t
;;; Returns a lambda procedure's list of parameter names.
(define procedure-parameters
(lambda (proc)
...))
> (procedure-parameters '(lambda-procedure (lambda (x y) (+ x y)) global-environment)
(x y)
> (procedure-parameters '(lambda-procedure (lambda () 'hello) global-environment)
()
;;; Returns a list of all the expressions in the body of the
;;; procedure's lambda expression:
(define procedure-body
(lambda (proc)
...))
> (procedure-body '(lambda-procedure (lambda (x y) (+ x y)) global-environment))
((+ x y))
> (procedure-body '(lambda-procedure (lambda () (display "hi") (newline)) global-environment))
((display "hi") (newline))
;;; Returns the environment saved in a lambda procedure:
(define procedure-env
(lambda (proc)
...))
> (procedure-env '(lambda-procedure (lambda (x y) (+ x y)) ()))
()
Handling lambda applications
Now we have to make sure that we apply these lambda
procedures correctly. Go back and re-read the description of
procedure application in the Introduction.
Let's go through this process again step by step, using a different example. Consider the process of evaluating the following expression which should return 0.
((lambda (x) (+ 10 x)) (* -1 10))First, mini-eval will recognize this expression as a procedure application. It will then (recursively) evaluate the operator (lambda (x) (+ 10 x)) using the current environment, evaluate the list of operands ((* -1 10)) using the current environment, and then call mini-apply to apply the resulting lambda procedure to the list (-10). The procedure obtained by evaluating the operator will look like this:
(lambda-procedure (lambda (x) (+ 10 x)) (((car primitive ...))))In mini-apply, we will need to include a new cond clause to handle the case of applying a lambda. The new line should look like this:
((lambda-procedure? proc) (apply-lambda-procedure proc vals))The new procedure apply-lambda-procedure should implement the steps described above. In particular, apply-lambda-procedure should first extend the environment stored in the procedure using the procedure's parameters and 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 ((+ 10 x)) will be evaluated in that new context, yielding a final result of 0.
Remember that the body of a procedure is a list of expressions to be evaluated, so you cannot use mini-eval directly on the body. Instead, you must call mini-eval on each expression, in order from first to last. In the above example, the body contains just one expression, but it is still a list. The result of evaluating the last expression in the list should serve as the result of evaluating the body. You should be able to handle the evaluation of the procedure body in the same way that you handled evaluating the expressions in a begin in Part 4.
Make sure you clearly understand these steps before you try to update mini-apply and write apply-lambda-procedure. Once you have implemented lambda procedure application in your interpreter, try the following tests to see if things are working properly:
MINI-EVAL> (define animal 'dog)
animal
MINI-EVAL> ((lambda (new)
(display "original animal was ")
(display animal)
(newline)
(set! animal new)
(display "updated animal to ")
(display animal)
(newline)
'done)
'cat)
original animal was dog
updated animal to cat
done
MINI-EVAL> animal
cat
MINI-EVAL> (define count-down
(lambda (n)
(if (= n 0)
'boom!
(begin
(display n)
(newline)
(count-down (- n 1))))))
count-down
MINI-EVAL> (count-down 5)
5
4
3
2
1
boom!
Trace mini-eval and mini-apply as you try the above
examples. Also try a number of your own examples, such as
factorial, square, and so on.
Before we go on to let expressions, first consider what happens when we do the following:
MINI-EVAL> (define myadd1 (lambda (x) (+ x 1))) myadd1 MINI-EVAL> myadd1 ?The define expression binds the symbol myadd1 to a lambda procedure in the global environment. So evaluating myadd1 causes our evaluator to look up the value of this variable in the global environment. That value is a list of the form:
(lambda-procedure lambda-expression environment)More precisely, it will look like:
(lambda-procedure (lambda (x) (+ x 1)) (((myadd1 lambda-procedure (lambda (x) (+ x 1)) (((myadd1 ...)Try this in your evaluator and watch what happens (if necessary, use the stop button to interrupt the result). What's the problem? We've created a circular structure! The symbol myadd1 is bound to the above object in the global environment, but that object itself includes the global environment as part of its structure, so in some versions of Scheme we get into an infinite loop just by trying to print it out.
Since our users should be able to evaluate a lambda expression and see the result without worrying about infinite loops, we need to work around this problem. Change driver-loop so that instead of calling pretty-print on the result of mini-eval, it calls the new procedure safe-print, which you will write. The procedure safe-print should check if the object to be printed is a lambda procedure, and if so, it should print only the procedure's parameters and body, but not its environment. If the object to be printed is a primitive procedure, it should avoid printing the primitive's internal implementation procedure. For all other types of objects, safe-print should just call pretty-print on the object. Write this procedure now. Below are some examples of how it should work:
MINI-EVAL> (define myadd1 (lambda (x) (+ x 1))) myadd1 MINI-EVAL> myadd1 [lambda-procedure (x) ((+ x 1))] MINI-EVAL> (define smaller (lambda (x y) (if (< x y) x y))) smaller MINI-EVAL> smaller [lambda-procedure (x y) ((if (< x y) x y))] MINI-EVAL> car [primitive-procedure car] MINI-EVAL> 'hello helloFor a more rigorous test of our evaluator's ability to handle procedures, we can try out some of the object-oriented code from Chapter 3 of the textbook:
MINI-EVAL> (define make-withdraw
(lambda (balance)
(lambda (amount)
(if (> balance amount)
(begin
(set! balance (- balance amount))
balance)
"Insufficient funds"))))
make-withdraw
MINI-EVAL> (define w1 (make-withdraw 50))
w1
MINI-EVAL> (w1 70)
"Insufficient funds"
MINI-EVAL> (w1 30)
20
MINI-EVAL> (define w2 (make-withdraw 100))
w2
MINI-EVAL> (w2 70)
30
A let expression has the following syntax:
(let ((var1 val1) (var2 val2) ... (varn valn)) exp1 exp2 ... expm)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 mini-eval encounters a let expression, all it needs to do is transform the expression into an equivalent application expression (using let->lambda), and then just call itself again on the new expression. Try the following tests when you are done:
MINI-EVAL> (let ((a 10))
(let ((b (lambda (x) (+ x a))))
(let ((a 500))
(b a))))
510
MINI-EVAL> (let ((f car))
(let ((f (lambda (y) (f y))))
(f '(apple banana cherry))))
apple
MINI-EVAL> (define x 1)
x
MINI-EVAL> (let ((x 0) (y 2) (z x))
(set! x 10)
(+ x y z))
13
MINI-EVAL> x
1
MINI-EVAL> (let ((z (* x -1)))
(if (> z 0) 'positive 'negative))
negative
MINI-EVAL> z
*** ERROR -- unbound variable z