6.001 Recitation #11 – March
14, 2003
RI: Konrad Tollmar
www.ai.mit.edu/~konrad/6001
•Environment Model
•Diagram Components
•Rules
•Some examples
• Frames: We draw a frame as a box. In the
box go bindings. Every frame (except the frame representing the global
environment) needs to have a link to exactly one other frame.
• Bindings: A binding is an association
between an identifier (or symbol) to a value.
• Procedure Objects: These are special
objects (symbolized by the double bubble) created by evaluating a lambda
expression as described below.
• Looking up a name - (+ x 10)
1. Look for a value in the current
frame.
2. If there is no value for that identifier
in the current frame, follow the link from the current frame to the one that it
is linked from.
3. Continue until we find a binding for the identifier we're looking up or until we run out of frames in our chain of links. If there's no binding in the GE, the identifier we're looking up is an unbound variable.
• Define - (define var
expression)
1. Evaluates the expression with respect to
the current environment.
2. Adds a binding to the frame in which it is evaluated.
• Set - (set! var
expression)
1. Evaluates the expression with respect to
the current environment.
2. Lookup the identifier in the current
environment
3. Rebind the identifier in the frame it was found to the value of the expression.
• Lambda - (lambda
(parameters) body)
1. Evaluating a lambda expression will result
in a two-part procedure object (two circles next to each other -- the double
bubble).
2. The pointer of the left circle points down
to a list of the parameters and the body of the procedure.
3. The pointer of the right circle points up
to the environment frame in which the lambda expression was evaluated. Note
that nothing else happens until we apply the procedure.
• Combination / Procedure
application
To evaluate a combination with respect to an
environment, first evaluate the subexpressions with respect to the environment
and then apply the value of the
operator subexpression to the values of the operand subexpressions.
1. Draw a new environment frame.
2. Link the new environment frame to the
environment frame pointed to by the right circle of the procedure object.
3. Bind the parameters to their values in
this new environment frame.
4. Evaluate the body of the procedure in this
new environment frame.
1. MyFirst Environment Diagram
Evaluate the expressions below, draw the corresponding environment diagram and following the rules of the environment model.
(define
foo
(lambda (x) (+ a x)))
(define
a 5)
(foo
4)
2. A recursive case
Once again… evaluate the expressions below, draw the corresponding environment diagram and following the rules of the environment model.
(define
(fact n)
(if (= n 1)
1
(* n (fact (- n 1)))))
(define
n 6)
(fact
2)
3. A let example
Desugar the let–expression,
(let
((n v)…) body) ==> ((l (n …) body) v … )
and draw the corresponding environment diagram.
(define (adder y)
(let ((inc y))
(lambda (x)
(+ inc x)))
use that to evaluate
(define add3 (adder 3))
(add3 4)
4. Procedural abstraction
Draw the corresponding environment diagram for:
(define F
(lambda (a b c)
(define G
(lambda (b a)
(-
a b)))
(define H
(lambda (a x)
(*
a b)))
(+ (G a b)
(H b a))))
(F 2 3 4)