3.2.1 The Rules for Evaluation - SICP Comparison Edition

Permalink copied!

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

To evaluate a combination: an application:
1. Evaluate the subexpressions of the combination.[1] application.[2]
2. Apply the value of the operator function subexpression to the values of the operand argument subexpressions.

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

Original		Python
		Before applying these rules, we need to say in which environment the statements of a program are evaluated. It is not the built-in environment of section 3.2: that frame is reserved for Python's built-in functions and values, and a program never adds bindings to it. Instead, the interpreter evaluates a program in a global environment, which consists of a single global frame whose enclosing environment is the built-in environment. Every definition and assignment at the top level of a program adds or changes a binding in the global frame, whereas the built-in frame supplies the names that the program does not define itself. Looking up `print` in the global environment therefore finds no binding in the global frame and proceeds to the built-in frame, while a name defined by the program is found in the global frame itself.

In the environment model of evaluation, a procedure function 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. Functions are created in two ways: by evaluating a function definition or a lambda expression. This produces a procedure In both cases, the result is a function whose code is obtained from the text of the lambda expression program text and whose environment is the environment in which the lambda function definition or lambda expression was evaluated to produce the procedure. function. For example, consider the procedure definition function definition

Original	Python
`(define (square x) (* x x))`	`def square(x): return x * x`

evaluated in the global environment. The procedure definition syntax is just syntactic sugar for an underlying implicit lambda 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. As far as the environment model is concerned, the function definition statement behaves like a declaration assignment of a lambda expression (section 1.3.2). It would have been equivalent to have used square = lambda x: x * x which evaluates lambda x: x * x and binds square to the resulting function value, all in the global environment.

Figure 3.3 Figure 3.4 shows the result of evaluating this define expression. function definition. The procedure function object is a pair whose code specifies that the procedure function has one formal parameter, namely x, and a procedure function body (* x x). return x * x. The environment part of the procedure function is a pointer to the global environment, since that is the environment in which the lambda lambda expression was evaluated to produce the procedure. function. A new binding, which associates the procedure function object with the symbol name square, has been added to the global frame.

Original		Python
In general, `define` creates definitions by adding bindings to frames.

Original		Python
Figure 3.3 Environment structure produced by evaluating `(define (square x) (* x x))` in the global environment.		Figure 3.4 Environment structure produced by evaluating `def square(x): return x * x` in the global environment.

Now that we have seen how procedures functions are created, we can describe how procedures functions are applied. So far, the environment model specifies: To apply a Here is the first version of a rule for applying a procedure function 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. function. Now, within Within this new environment, evaluate the procedure function body. (We will refine this in section 3.2.3.)

To show how this rule is followed, figure 3.5 figure 3.6 illustrates the environment structure created by evaluating the expression (square 5) square(5) in the global environment, where square is the procedure function generated in figure 3.3. figure 3.4. Applying the procedure function 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, function, 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 function object. Within E1, we evaluate the body of the procedure, function, (* x x). return x * x. Since the value of x in E1 is 5, the result is (* 5 5), 5 * 5, or 25.

Original		Python
Figure 3.5 Environment created by evaluating `(square 5)` in the global environment.		Figure 3.6 Environment created by evaluating `square(5)` in the global environment.

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

A procedure function object is applied to a set of arguments by constructing a frame, binding the formal parameters of the procedure binding the parameters of the function to the arguments of the call, and then evaluating the body of the procedure function in the context of the new environment constructed. The new frame has as its enclosing environment the environment part of the procedure function object being applied. The result of the application is the result of evaluating the return expression of the first return statement encountered while evaluating the function body.
A procedure function is created by evaluating a lambda expression function definition or lambda expression relative to a given environment. The resulting procedure function object is a pair consisting of the text of the lambda expression function body and a pointer to the environment in which the procedure function was created.

Original		Python
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.[3]

Original		Python
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! )`		Finally, we specify the behavior of assignment (declaration assignment or reassignment). It was reassignment that forced us to introduce the environment model in the first place. Evaluating the assignment $name$ `=` $value$

in some environment locates the binding of the variable in the environment. For this, 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

Original		Python
, then `set!` signals an error.		and the environment is the global environment, the assignment adds a binding to the global environment. If the variable is unbound in the environment and the environment is not the global environment, then the assignment 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 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.

[1] Assignment introduces a subtlety into step 1 of the evaluation rule. As shown in exercise 3.8, the presence of assignment allows us to write expressions that will produce different values depending on the order in which the subexpressions in a combination are evaluated. Thus, to be precise, we should specify an evaluation order in step 1 (e.g., left to right or right to left). However, this order should always be considered to be an implementation detail, and one should never write programs that depend on some particular order. For instance, a sophisticated compiler might optimize a program by varying the order in which subexpressions are evaluated. The ECMAScript standard specifies evaluation of subexpressions from left to right.

[2] Reassignment introduces a subtlety into step 1 of the evaluation rule. As shown in exercise 3.8, the presence of reassignment allows us to write expressions that will produce different values depending on the order in which the subexpressions in a combination are evaluated. To eliminate such ambiguities, Python specifies left-to-right evaluation of the subexpressions of combinations and of the argument expressions of applications.

[3] If there is already a binding for the variable in the current frame, then the binding is changed. This is convenient because it allows redefinition of symbols; however, it also means that define can be used to change values, and this brings up the issues of assignment without explicitly using set!. Befcause of this, some people prefer redefinitions of existing symbols to signal errors or warnings.

< Previous

Next >

3.2.1 The Rules for Evaluation