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.

In the environment model of evaluation, a procedure function is always a pair consisting of some code and a pointer to an environment. Procedures Functions are created in one way only: by evaluating a lambda lambda expression. This produces a procedure function whose code is obtained from the text of the lambda lambda expression and whose environment is the environment in which the lambda 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 program environment. The procedure definition function definition syntax is just syntactic sugar for equivalent to an underlying implicit lambda lambda expression. It would have been equivalent to have used[3]

Original	Python
`(define square (lambda (x) (* x x)))`	`square = lambda x: x * x`

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

Figure 3.3 Figure 3.4 shows the result of evaluating this define expression. declaration statement.

Original		Python
		The global environment encloses the program environment. To reduce clutter, after this figure we will not display the global environment (as it is always the same), but we are reminded of its existence by the pointer from the program environment upward.

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 program 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 program 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 program environment.

Original		Python
		In general, function definitions and declaration assignments add bindings to frames. Assignment is forbidden on constants, so our environment model needs to distinguish names that refer to constants from names that refer to variables. We indicate that a name is a constant by writing an equal sign after the colon that follows the name. We consider function definitions as equivalent to constant declarations;[4] observe the equal signs after the colons in figure 3.4.

Now that we have seen how procedures functions are created, we can describe how procedures functions are applied. The environment model specifies: To apply 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 this new environment, evaluate the procedure function body.

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 program 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. Note that name x in environment E1 is followed by a colon with no equal sign, which indicates that the parameter x is treated as a variable.[5] The pointer leading upward from this frame shows that the frame's enclosing environment is the global program environment. The global program 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 program 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 lambda expression relative to a given environment. The resulting procedure function object is a pair consisting of the text of the lambda lambda expression 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.		We leave this out of the Python version, because it is discussed in more detail in section 3.2.4.

Original		Python
Evaluating the expression `(set!` variable 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, then `set!` signals an error.		Finally, we specify the behavior of reassignment, the operation that forced us to introduce the environment model in the first place. Evaluating the reassignment statement $name$ `=` $value$ in some environment locates the binding of the name in the environment. That is, one finds the first frame in the environment that contains a binding for the name and changes that binding to reflect the new value of the variable. If the name is unbound in the environment, then the assignment signals a `"variable undeclared"` 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.

[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] 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. To eliminate such ambiguities, Python specifies left-to-right evaluation of the subexpressions of combinations and of the argument expressions of applications.

[3] Footnote in chapter 1 mentions subtle differences between the two in full Python, which we will ignore in this book.

[4] We mentioned in footnote in chapter 1 that the full Python language allows assignment to names that are declared with function definitions.

[5] This example does not make use of the fact that the parameter x is a variable, but recall the function make_withdraw in section 3.1.1, which relied on its parameter being a variable.

< Previous

Next >

3.2.1 The Rules for Evaluation