lec07.dvi
CS 450
Lecture 7: The Environment Model
Carl D. Offner
1 Environments
An environment is a tree of environment frames.
A frame is
• a (possibly empty) table of variables and their associated values (i.e., bindings), together with
• a pointer to its parent in the tree of environment frames. This parent is called the enclosing
environment. Of course there is one exception: the root frame, which is also called the global
environment has no parent, and so has no such pointer.
At each point during execution of a program, we have a current environment. This is one of the
frames in the tree.
2 Evaluating a variable
The value of a variable is found by starting with the current environment and walking up the tree
until the variable is found. Figure 1 shows how this works.
x: 3
y: 5
z: 6
x: 7
m: 1
y: 2
Figure 1: x may have the value 7 or 3, depending on the current environment; similarly for y.
1
2 4 EVALUATING A (USER-DEFINED) PROCEDURE CALL
3 Evaluating a lambda expression
To evaluate a lambda expression, create a procedure object consisting of
• the text of the procedure. This in turn consists of
– the formal parameters of the procedure, and
– the body of the procedure.
It is important to remember that this is just copied textually—nothing in the text of the
procedure is evaluated at this point.
• a pointer (or more accurately, a reference) to the environment in which the lambda expression
was evaluated.
This procedure object is what the lambda expression evaluates to.
current
environment
parameters : x
body : (* x x)
Figure 2: Evaluation of the lambda expression (lambda(x) (* x x))
4 Evaluating a (user-defined) procedure call
To evaluate a procedure call (where the procedure is user-defined, and hence evaluates to a procedure
object),
1. Evaluate the first expression in the list. This is the procedure itself, and so it evaluates to a
procedure object, as above.
2. Evaluate the rest of the expressions of the list—these are the actual arguments to the procedure—
in the current environment.
3. Construct a new frame containing the bindings of the formal parameters of the procedure to
the corresponding values just produced in step 2.
The enclosing environment of this frame is the environment part of the procedure object
produced in step 1.
4. Evaluate the body of the procedure in this new environment.
3
current
environment
parameters : x
body : (* x x)
x : 5
Figure 3: Applying a lambda expression: ((lambda(x) (* x x)) 5).
current
environment
(look here for y)
parameters : x
body : (* x y)
x : 5
Figure 4: Applying a lambda expression (a second example): ((lambda(x) (* x y)) 5).
Note the convention I am using for these pictures:
Frames are represented by rectangles. Frames are the only nodes in the environment
tree.
The parent-child relation between frames is represented by a solid arrow.
Procedure objects are represented by ovals. This is to emphasize that procedure objects
are not nodes in the environment tree. Each procedure object, however, does point to
a node (i.e., a frame) in the environment tree. This frame is called the “environment of
the procedure object”. It is not, however, the “parent” of the procedure object, since the
procedure object is not a node in the tree. For this reason,
The arrow from a procedure object to its environment frame is dotted. This is to
reinforce the fact that the arrow does not represent a parent-child relation.
4 5 EVALUATING DEFINE AND SET!
5 Evaluating define and set!
environment
(before)
environment
(after)
aa : 12
bc : -5
x : 466
aa : 12
bc : -5
x : 466
p : 45
q : 7
p : 45
q : 7
x : 5
Figure 5: To evaluate (define x
environment
(before)
environment
(after)
aa : 12
bc : -5
x : 466
aa : 12
bc : -5
x : 5
p : 45
q : 7
p : 45
q : 7
Figure 6: To evaluate (set! x
change the value bound to x. Thus, (set! x 5) changes the binding of x in the first frame in
which x is found.
5
square :
parameters: x
body: (* x x)
Figure 7:
(define (square x) (* x x))
which is the same as
(define square (lambda (x) (* x x)))
6 6 SOME LARGER EXAMPLES
6 Some larger examples
make-withdraw :
parameters: balance
body: (lambda (amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
“Insufficient funds.”))
(define (make-withdraw balance)
(lambda (amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
“Insufficient funds.”)))
This is equivalent to
(define make-withdraw
(lambda (balance)
(lambda (amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
“Insufficient funds.”))))
Figure 8: Definition of make-withdraw. If we then (define W1 (make-withdraw 100)), we get
Figure 9.
7
make-withdraw :
W1 :
parameters: balance
body: (lambda (amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
“Insufficient funds.”))
parameters: amount
body: (if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
“Insufficient funds.”)
balance : 100
Figure 9: Evaluation of (define W1 (make-withdraw 100))
8 6 SOME LARGER EXAMPLES
new-withdraw :
parameters: balance
body: (lambda (amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
“Insufficient funds.”))
parameters: amount
body: (if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
“Insufficient funds.”)
(define new-withdraw
(let ((balance 100))
(lambda (amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
“Insufficient funds.”))))
This is immediately turned internally into
(define new-withdraw
((lambda (balance)
(lambda (amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
“Insufficient funds.”)))
100)
)
Figure 10: new-withdraw
balance : 45
9
sqrt :
parameters: x
body: (define good-enough?
(lambda (guess)
(< (abs (- (square guess) x)) 0.001)))
(define improve
(lambda (guess)
(average guess (/ x guess))))
(define sqrt-iter
(lambda (guess)
(if (good-enough? guess)
guess
(sqrt-iter (improve guess)))))
(sqrt-iter 1.0)
x : 2
good-enough? :
improve :
sqrt-iter :
parameters: guess
body: (< (abs (- (square guess) x)) 0.001)))
parameters: guess
body: (average guess (/ x guess))))
parameters: guess
body: (if (good-enough? guess)
guess
(sqrt-iter (improve guess)))
guess : 1
call to sqrt-iter
guess : 1
call to good-enough?
(define sqrt
(lambda (x)
(define (good-enough? guess)
(< (abs (- (square guess) x)) 0.001))
(define improve
(lambda (guess)
(average guess (/ x guess))))
(define sqrt-iter
(lambda (guess)
(if (good-enough? guess)
guess
(sqrt-iter (improve guess)))))
(sqrt-iter 1.0)))
Figure 11: Evaluating (sqrt 2). Only the first few steps of the computation are shown.