The Rules for Evaluation

The overall specification of how the interpreter evaluates a combination remains the same as when we first introduced it in section :

• To evaluate a combination:

• 1.Evaluate the subexpressions of the combination.

• 2.Apply the value of the operator subexpression to the values of the operand subexpressions.

The environment model of evaluation replaces the substitution model in specifying what it means to apply a compound procedure to arguments.

In the environment model of evaluation, a procedure is always a pair consisting of some code and a pointer to an environment. Procedures are created in one way only: by evaluating a lambda expression. This produces a procedure whose code is obtained from the text of the lambda expression and whose environment is the environment in which the lambda expression was evaluated to produce the procedure. For example, consider the procedure definition

(define (square x)
  (* x x))

evaluated in the global environment. The procedure definition syntax is just syntactic sugar for an underlying implicit lambda expression. It would have been equivalent to have used

(define square
  (lambda (x) (* x x)))

which evaluates (lambda (x) (* x x)) and binds square to the resulting value, all in the global environment.

Figure  shows the result of evaluating this define expression. The procedure object is a pair whose code specifies that the procedure has one formal parameter, namely x, and a procedure body (* x x). The environment part of the procedure is a pointer to the global environment, since that is the environment in which the lambda expression was evaluated to produce the procedure. A new binding, which associates the procedure object with the symbol square, has been added to the global frame. In general, define creates definitions by adding bindings to frames.

 

Now that we have seen how procedures are created, we can describe how procedures are applied. The environment model specifies: To apply a procedure to arguments, create a new environment containing a frame that binds the parameters to the values of the arguments. The enclosing environment of this frame is the environment specified by the procedure. Now, within this new environment, evaluate the procedure body.

To show how this rule is followed, figure  illustrates the environment structure created by evaluating the expression (square 5) in the global environment, where square is the procedure generated in figure . Applying the procedure results in the creation of a new environment, labeled E1 in the figure, that begins with a frame in which x, the formal parameter for the procedure, is bound to the argument 5. The pointer leading upward from this frame shows that the frame's enclosing environment is the global environment. The global environment is chosen here, because this is the environment that is indicated as part of the square procedure object. Within E1, we evaluate the body of the procedure, (* x x). Since the value of x in E1 is 5, the result is (* 5 5), or 25.

 

The environment model of procedure application can be summarized by two rules:

• A procedure object is applied to a set of arguments by constructing a frame, binding the formal parameters of the procedure to the arguments of the call, and then evaluating the body of the procedure in the context of the new environment constructed. The new frame has as its enclosing environment the environment part of the procedure object being applied.

• A procedure is created by evaluating a lambda expression relative to a given environment. The resulting procedure object is a pair consisting of the text of the lambda expression and a pointer to the environment in which the procedure was created.

We also specify that defining a symbol using define creates a binding in the current environment frame and assigns to the symbol the indicated value. Finally, we specify the behavior of set!, the operation that forced us to introduce the environment model in the first place. Evaluating the expression (set! variable value) in some environment locates the binding of the variable in the environment and changes that binding to indicate the new value. That is, one finds the first frame in the environment that contains a binding for the variable and modifies that frame. If the variable is unbound in the environment, then set! signals an error.

These evaluation rules, though considerably more complex than the substitution model, are still reasonably straightforward. Moreover, the evaluation model, though abstract, provides a correct description of how the interpreter evaluates expressions. In chapter 4 we shall see how this model can serve as a blueprint for implementing a working interpreter. The following sections elaborate the details of the model by analyzing some illustrative programs.