When we introduced compound procedures in chapter 1, we used the
substitution model of evaluation
(section ![[*]](../image/cross_ref_motif.gif)
) to define what is meant by
applying a procedure to arguments:
- To apply a compound procedure to arguments, evaluate the body of the procedure with each formal parameter replaced by the corresponding argument.
Once we admit assignment into our programming language, such a
definition is no longer adequate. In particular,
section argued that, in the presence of
assignment, a variable can no longer be considered to be merely a name
for a value. Rather, a variable must somehow designate a ``place'' in
which values can be stored. In our new model of evaluation, these
places will be maintained in structures called
environments.
An environment is a sequence of frames. Each frame is a table (possibly empty) of bindings, which associate variable names with their corresponding values. (A single frame may contain at most one binding for any variable.) Each frame also has a pointer to its enclosing environment, unless, for the purposes of discussion, the frame is considered to be global. The value of a variable with respect to an environment is the value given by the binding of the variable in the first frame in the environment that contains a binding for that variable. If no frame in the sequence specifies a binding for the variable, then the variable is said to be unbound in the environment.
Figure shows a simple environment
structure consisting of three frames, labeled I, II, and III. In the
diagram, A, B, C, and D are pointers to environments. C and D point
to the same environment. The variables z and x are bound
in frame II, while y and x are bound in frame I. The
value of x in environment D is 3. The value of x with
respect to environment B is also 3. This is determined as follows: We
examine the first frame in the sequence (frame III) and do not find a
binding for x, so we proceed to the enclosing environment D and
find the binding in frame I. On the other hand, the value of x
in environment A is 7, because the first frame in the sequence (frame
II) contains a binding of x to 7. With respect to environment
A, the binding of x to 7 in frame II is said to
shadow the
binding of x to 3 in frame I.
The environment is crucial to the evaluation process, because it determines the context in which an expression should be evaluated. Indeed, one could say that expressions in a programming language do not, in themselves, have any meaning. Rather, an expression acquires a meaning only with respect to some environment in which it is evaluated. Even the interpretation of an expression as straightforward as (+ 1 1) depends on an understanding that one is operating in a context in which + is the symbol for addition. Thus, in our model of evaluation we will always speak of evaluating an expression with respect to some environment. To describe interactions with the interpreter, we will suppose that there is a global environment, consisting of a single frame (with no enclosing environment) that includes values for the symbols associated with the primitive procedures. For example, the idea that + is the symbol for addition is captured by saying that the symbol + is bound in the global environment to the primitive addition procedure.