When we introduced compound functions in chapter 1, we used the substitution model of evaluation (section 1.1.5) to define what is meant by applying a function to arguments:

• To apply a compound function to arguments, evaluate the return expression of the function (more generally, the body) with each parameter replaced by the corresponding argument.

Once we admit assignment into our programming language, such a definition is no longer adequate. In particular, section 3.1.3 argued that, in the presence of assignment, a name cannot be considered to be merely representing a value. Rather, a name 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 names with their corresponding values. (A single frame may contain at most one binding for any name.) 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 name with respect to an environment is the value given by the binding of the name in the first frame in the environment that contains a binding for that name. If no frame in the sequence specifies a binding for the name, then the name is said to be unbound in the environment.

Figure 3.2 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 names 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 display(1) depends on an understanding that one is operating in a context in which the name display refers to the primitive function that displays a value. 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 names associated with the primitive functions. For example, the idea that display is the name for the primitive display function is captured by saying that the name display is bound in the global environment to the primitive display function.

Before we evaluate a program, we extend the global environment with a new frame, the program frame, resulting in the program environment. We will add the names that are declared at the top level of the program, outside of any block, to this frame. The given program is then evaluated with respect to the program environment.