9.2.2 Evaluation rules with state

Introducing mutation requires us to revise the evaluation rule for names, the definition rule, and the application rule for constructed procedures. All of these rules must be adapted to be more precise about how values are associated with names by using places and environments.

Names. The new evaluation rule for a name expression is:

Stateful Evaluation Rule 2: Names. To evaluate a name expression, search the evaluation environment's frame for a place with a name that matches the name in the expression. If such a place exists, the value of the name expression is the value in that place. Otherwise, the value of the name expression is the result of evaluating the name expression in the parent environment. If the evaluation environment has no parent, the name is not defined and the name expression evaluates to an error.

For example, to evaluate the value of the name expression x in Environment B in Figure 9.1, we first look in the frame of Environment B for a place named x. Since there is no place named x in that frame, we follow the parent pointer to Environment A, and evaluate the value of the name expression in Environment A. Environment A's frame contains a place named x that contains the value 7, so the value of evaluating x in Environment B is 7.

The value of the same expression in the Global Environment is 3 since that is the value in the place named x in the Global Environment's frame.

To evaluate the value of y in Environment A, we first look in the frame in Environment A for a place named y. Since no y place exists, evaluation continues by evaluating the expression in the parent environment, which is the Global Environment. The Global Environments frame does not contain a place named y, and the global environment has no parent, so the name is undefined and the evaluation results in an error.

Definition. The revised evaluation rule for a definition is:

Stateful Definition Rule. A definition creates a new place with the definition's name in the frame associated with the evaluation environment. The value in the place is value of the definition's expression. If there is already a place with the name in the current frame, the definition replaces the old place with a new place and value.

The rule for redefinitions means we could use define in some situations to mean something similar to set!. The meaning is different, though, since an assignment finds the place associated with the name and puts a new value in that place. Evaluating an assignment follows the Stateful Evaluation Rule 2 to find the place associated with a name. Hence, (define Name Expression) has a different meaning from (set! Name Expression) when there is no place named Name in the current execution environment. To avoid this confusion, only use define for the first definition of a name and always use set! when the intent is to change the value associated with a name.

Application. The final rule that must change because of mutation is the application rule for constructed procedures. Instead of using substitution, the new application rule creates a new environment with a frame containing places named for the parameters.

Stateful Application Rule 2: Constructed Procedures. To apply a constructed procedure: 1. Construct a new environment, whose parent is the environment of the applied procedure. 2. For each procedure parameter, create a place in the frame of the new environment with the name of the parameter. Evaluate each operand expression in the environment or the application and initialize the value in each place to the value of the corresponding operand expression. 3. Evaluate the body of the procedure in the newly created environment. The resulting value is the value of the application.

Consider evaluating the application expression (bigger 3 4) where bigger is the procedure from Example 3.3: (define (bigger a b) (if (> a b) a b))).

Evaluating an application of bigger involves following the Stateful Application Rule 2. First, create a new environment. Since bigger was defined in the global environment, its environment pointer points to the global environment. Hence, the parent environment for the new environment is the global environment.

Next, create places in the new environment's frame named for the procedure parameters, a and b. The value in the place associated with a is 3, the value of the first operand expression. The value in the place associated with b is 4.

The final step is to evaluate the body expression, (if (> a b) a b), in the newly created environment. Figure 9.2shows the environment where the body expression is evaluated. The values of a and b are found in the application environment.

Figure 9.2: Environment created to evaluate (bigger 3 4).

The new application rule becomes more interesting when we consider procedures that create new procedures. For example, make-adder takes a number as input and produces as output a procedure:

(define (make-adder v) (lambda (n) (+ n v)))

The environment that results from evaluating (define inc (make-adder 1)) is shown in Figure 9.3. The name inc has a value that is the procedure resulting from the application of (make-adder 1). To evaluate the application, we follow the application rule above and create a new environment containing a frame with the parameter name, inc, and its associated operand value, 1.

Figure 9.3: Environment after evaluating (define inc (maker-adder 1)).

The result of the application is the value of evaluating its body in this new environment. Since the body is a lambda expression, it evaluates to a procedure. That procedure was created in the execution environment that was created to evaluate the application of make-adder, hence, its environment pointer points to the application environment which contains a place named inc holding the value 1.

Next, consider evaluating (inc 149). Figure 9.4 illustrates the environment for evaluating the body of the inc procedure. The evaluation creates a new environment with a frame containing the place n and its associated value 149. We evaluate the body of the procedure, (+ n v), in that environment. The value of n is found in the execution environment. The value of v is not found there, so evaluation continues by looking in the parent environment. It contains a place v containing the value 1.

Figure 9.4: Environment for evaluating the boday of (inc 149).

Exercise 9.1. Devise a Scheme expression that could have four possible values, depending on the order in which application subexpressions are evaluated.

Exercise 9.2. Draw the environment that results after evaluating:

> (define alpha 0)
> (define beta 1)
> (define update-beta! (lambda () (set! beta (+ alpha 1)))
> (set! alpha 3)
> (update-beta!)
> (set! alpha 4)

Exercise 9.3. Draw the environment that results after evaluating the following expressions, and explain what the value of the final expression is. (Hint: first, rewrite the let expression as an application.)

> (define (make-applier proc) (lambda (x) (proc x))
> (define p (make-applier (lambda (x) (let ((x 2)) x))))
> (p 4)