CS212 Handouts
The Environment Model
An environment is an association of names with values. To
understand how Scheme resolves variable names, we must understand how
environments are created and used.
A binding is an association of a single name (a variable) with
a value. We denote such a binding by name:value.
A frame is an unordered set of bindings, no two of which bind
the same name. For example, a frame might consist of the bindings
x:10, y:15, z:(4 5 6).
An environment consists of an ordered sequence of one or more
frames. The frames are arranged in a linear order starting from the
"youngest'' frame, the one associated with the procedure currently
running, back to the "oldest'' frame. Different frames can bind
different sets of names, and two frames in an environment may have
different bindings for the same name.
The environment consisting of the oldest frame alone is called the
global environment. It contains the bindings of the Scheme language primitives such as + and
lambda. It is
always there from the time of system startup and never disappears.
When searching an environment for a given name, Scheme starts at the
youngest frame and continues searching older and older frames until a
binding with that name is found. If there is no binding in any frame
for that name, a special value is returned indicating that the name is
not bound to anything in the environment. This procedure is called
lookup.
When an expression is evaluated, it is always evaluated in the context
of some environment. The appropriate evaluation rule is determined by
the type of expression that is being evaluated.
The value of an identifier with respect to a given environment is the
value given by the first frame containing a binding for that
variable in the lookup order as described above. The value is
undefined if there is no frame containing a binding for that name.
This rule is often referred to as the lookup rule. In other
words, look in the youngest frame of the environment for a binding of
the given name. If there is no binding in this frame, go on to the
next frame and look there. Continue in this fashion until a binding
for the name is found, or until the frames are exhausted. Return the
value that is found.
Evaluating a define expression always adds a binding to the
oldest (global) frame, bypassing all other frames in the environment.
Thus all bindings done with define are global definitions.
If there are bindings for the name in younger frames, they are
ignored. The new binding associates the given name
with the value that results from evaluating the given expression in
the whole environment. No useful value is returned. Recall that this does not
apply to an internal define, since internal defines are just another way of
representing letrec.
Evaluating (set! var expr) in a given environment uses
the lookup rule to find the first binding of the variable var, then changes that binding to a new value. The new value is the result of evaluating expr in the given environment. Thus the environment structure is changed by changing the value of the first binding found for the
given name. No useful value is returned.
The result of evaluating a lambda expression with respect
to a given environment is to create a new procedure object consisting
of
- The formal parameters of the lambda.
- The body of the lambda.
- A pointer to the environment in which the lambda
expression was evaluated.
This is called a closure. Conceptually, a procedure object is just the text of the
lambda expression together with a pointer to the
environment where the lambda expression was evaluated.
That is, the procedure object stores the parameters and the code
(which were both part of the lambda expression) along with
the environment where the lambda expression was evaluated
(which was not part of the lambda expression). Note that evaluating a lambda expression just creates a procedure object; it does
not evaluate the body of the lambda at that point!
That happens only later, when the procedure gets applied. This is
essentially the same as the evaluation of lambda
expressions in the substitution model, only here there is additionally
an environment pointer.
The reason the environment pointer is included in closures is that we need a means of resolving identifiers that occur in the body of the method that are not parameters. We would like the values of these identifiers to be the ones in effect when the method was created, not when it is called.
Evaluating a let expression
(let ((name1 exp1)
(name2 exp2)
...
(namek expk)) body)
in an environment creates a single frame that binds each expi. This
single frame is created after evaluating each expi, and the frame holds all the
bindings namei:expi. The body is then evaluated in the context of this new
environment that starts at this single frame. Evaluating a let statement is
essentially the same as applying a procedure (see below).
On the other hand, evaluating a let* expression
(let* ((name1 exp1)
(name2 exp2)
...
(namek expk)) body)
in an environment creates a sequence of new frames with the specified
bindings. Each successive expi is evaluated in the
environment containing the new frames created by the first i-1
bindings. A new frame is then created with the single binding
namei:expi and appended to the front of the
environment. Finally the body is evaluated in the
environment with the k new frames.
This is not quite equivalent to creating a procedure object with
one parameter for each name (see the Application Rule below), since here the bindings are done sequentially and k different frames are created, whereas in the case of procedures, only one new frame is created with all the bindings.
Lastly, evaluating a letrec expression
(letrec ((name1 exp1)
(name2 exp2)
...
(namek expk)) body)
in an environment creates a new frame and temporarily binds each namei
to a null value. Each expi is then evaluated in this
environment. After all expis are evaluated, the null values
are replaced such that there exists a binding for each namei:expi.
It is important that each expi be a lambda statement, since
looking up another namej while evaluating expi
before it is bound would cause unpredictable results.
To evaluate a compound expression in some environment, first
evaluate all the subexpressions in that environment, and then
apply the value of the first to the remaining values. The
value of the first had better be a function, or an error results.
To apply a compound procedure to a list of values, i.e. to call a
procedure with a specified set of values for the parameters:
- Create a new frame containing a binding for each formal parameter
of the procedure bound to the corresponding argument value. Add this
new frame to the front of the environment in the closure of the
procedure being applied. This is the environment in which the
procedure object was created, as discussed above under the evaluation of method expressions; it is
not the environment in which the application takes place!
Note that the only operations that create frames are the
application of a procedure and let and its variants.
- Evaluate the body of the procedure with respect to the new
environment created in step 1.
Application of primitive procedures is done directly by Scheme.
When reasoning using the environment model, we handle application of
primitive procedures the same way as we did in the substitution model:
just substitute the value.
![](../images/home.gif)
Last Modified: 3/23/99 by Brandon Bray