Last update: 01/19/00 11:35 PM by Eli
CS212 HandoutsThe substitution model provides us with a means of determining the value of Scheme expressions. In learning and using the substitution model, please keep in mind it is intended as a tool for understanding the evolution of the evaluation of expressions. It is not a direct model of how the computer actually performs the evaluation. We will use some shorthand notation to bury unneeded detail with which you need not be concerned, but which the computer must actually manipulate.
Before we can model the process of evaluating Scheme expressions, we need to develop some notation for differentiating between objects that have already been evaluated (e.g., intermediate values in a computation) and those that have not. In the substitution model we will place braces { } around values in order to distinguish them from objects that have not yet been evaluated. This notation is used to designate the internal representation of an object used by the machine, and implies that no further reduction is possible.
The value of a primitive numeric expression such as 4, -3.1, or 2.71828 is the number that it names. We denote this by placing the number in braces { }. For example, the value of the numeral 5 is the number {5}. This is not what is printed by the computer if you type 5 at it; it is simply a convenient notation for helping us trace the process of evaluation.
The interpreter provides a set of primitive procedures that form the building blocks for our own procedures, including things like addition and multiplication. These are represented by Scheme expressions such as + and *. Thus, the value of the expression + is the addition procedure, which roughly speaking is the code needed to execute the procedure. We will represent these values by braces surrounding some suggestive name; for example,
Compound procedures are created by evaluating a lambda expression, which takes a list of parameters and a body, and creates a procedure object. We will use the special symbol proc and braces to denote the procedure that results from evaluating a lambda expression. We also include the arguments to the procedure and the body of the procedure. For example, the value obtained by evaluating
(lambda (x) (* x x))
is represented by
{proc (x) (* x x)}
The interpreter evaluates compound expressions by the recursive application of two basic rules. These two rules serve to unwind the evaluation of procedures until we get expressions that just involve the application of primitive procedures to primitive values. The resulting values are then substituted for corresponding expression.
The rules for compound expressions are:
Note that this results in an alternation of evaluation and application stages, which continue until reducing the expression to primitives. The rules for primitive expressions are:
To model the evaluation of an expression using these rules, we will use two different notations, one for the evaluation stages and one for the application stages. An expression that is being evaluated will be denoted by parentheses ( ). An expression that denotes the application of a procedure will be represented by square brackets [ ].
To demonstrate the substitution model, we first consider the evaluation of the expression
((lambda (x) (* x x)) 5)
which we know should result in the process of squaring the number 5.
The following table denotes the full evaluation. We will discuss the process by which the evaluation evolves below.
1 ((lambda (x) (* x x)) 5)
2 [{proc (x) (* x x)} {5}]
3 (* {5} {5})
4 [{mult} {5} {5}]
5 {25}
The numbers on the extreme left are simply used to mark lines, so that we can refer to them. They are not part of the substitution model itself.
We begin with line 1. Since this is an evaluation of a compound expression, rule EVAL-C says we must first evaluate the subexpressions. The value obtained by evaluating the lambda expression is a procedure object, denoted by
{proc (x) (* x x)}
and the value of the expression 5 is {5}. Thus, after the first stage of evaluation, our model reduces the evaluation in line 1 to the application of a procedure object to a set of values shown in line 2.
Now, rule APPLY-C reduces this to the evaluation of a simpler expression, namely the body of the procedure with the value of the argument substituted (hence the name of the model) for the formal parameter, as shown in line 3. Note that we have substituted the object {5} directly into the expression.
We now have an evaluation again. Since this is a compound expression, rule EVAL-C applies again. Here, we already have values (or objects) for the second and third subexpressions, as indicated by the braces. Thus rule EVAL-P4 holds, implying that no further evaluation of these expressions is needed. The value of the first subexpression is simply the machine instructions associated with this primitive operation, denoted by {mult}, and is found by using rule EVAL-P3.
Hence, the evaluation of this expression reduces to the application shown in line 4. At this point, we have a primitive built-in operation applied to primitive values. This situation is governed by rule APPLY-P. We just replace the expression with its value, which is the final value given in line 5.
Notice how the process involves the alternation of evaluation and application steps. We will return to this in detail later in the term.
The rules we have described deal with the evaluation of most expressions. There are, however, a small number of special forms that do not obey these rules, and we need to describe a method for dealing with them.
When evaluating a define expression, the rules change slightly. In particular, in evaluating
(define expression-1 expression-2)
we first check that expression-1 is a symbol. Then we evaluate expression-2 using the evaluation rules above and associate the result with the name given in expression-1. Note that only expression-2 is evaluated, not expression-1. We can think of this association occurring by placing the pairing of the name and the value in a lookup table, so that evaluating the name later on allows us to find the associated value. We will ignore some of the details of this process now, and return to them later in the term.
For example, if we evaluate the following expressions:
(define a 2) (define square (lambda (x) (* x x))) (define cube (lambda (x) (* x x x)))
then our table might look something like the following:
Name Value
---------------------------------------
* {mult}
+ {add}
. .
. .
. .
a {2}
square {proc (x) (* x x)}
cube {proc (x) (* x x x)}
Each entry in the table consists of a name and an associated object. Some of these associations are there from the start--for example, the built in primitive operations--and others are added when we evaluate a define expression.
Now consider the evaluation of
(cube (square a))
As in the previous case, we first show the full evolution of the evaluation process, and then describe how we derived it.
1 (cube (square a))
2 ({proc (x) (* x x x)} (square a))
3 (... [{proc (x) (* x x)} {2}])
4 (... (* {2} {2}))
5 (... [{mult} {2} {2}])
6 [{proc (x) (* x x x)} {4}]
7 (* {4} {4} {4})
8 [{mult} {4} {4} {4}]
9 {64}
The evaluation of line 1 first involves the evaluation of each of the two subexpressions, the second of which is itself a compound expression. The details of the process of evaluating the second (compound) subexpression are shown starting at line 3. We have included the details of this evaluation here, but often we may decide to suppress this detail if the evaluation of the expression is apparent. In this case, we could omit the derivations shown, thereby concentrating on the more global evaluation process taking place.
In the first part of line 3, the evaluation of the symbol a and the symbol square involves the rule EVAL-P3, in which we look up the objects or values associated with these names in our lookup table. The rest of the evaluation follows similarly to the example given above.
Suppose we evaluate the following expressions:
(define foo square)
(define do-to-5
(lambda (f) (f 5)))
Evaluation of these expressions associates procedure objects with the names foo and do-to-5. This adds two new pairings to our lookup table:
Name Value
---------------------------------------
* {mult}
+ {add}
. .
. .
. .
a {2}
square {proc (x) (* x x)}
cube {proc (x) (* x x x)}
. .
. .
. .
foo {proc(x) (* x x)}
do-to-5 {proc(f) (f 5)}
Now suppose we want to trace the evaluation of the expression
(do-to-5 foo)
The evaluation evolves in a manner given below:
1 (do-to-5 foo)
2 [{proc (f) (f 5)} {proc (x) (* x x)}]
3 ({proc (x) (* x x)} 5)
4 [{proc (x) (* x x)} {5}]
5 (* {5} {5})
6 [{mult} {5} {5}]
7 {25}
The important point to note here is that procedures, which are objects in their own right, can be directly substituted into the bodies of other procedures. Thus in line 1, we evaluate the subexpressions do-to-5 and foo, each of which has a procedural object associated with it in the lookup table. This is shown in line 2.
Next, we apply the leftmost procedure to the remaining arguments. In this case, the second procedure argument is directly substituted into the body of the first procedure in place of the formal parameter f. This yields line 3. The remainder of the derivation is similar to those above.
Conditional expressions, i.e. those involving if or cond, are also special forms, thus obey slightly different rules than EVAL-C and APPLY-C.
When evaluating an if expression such as
(if predicate consequent alternate)
we first evaluate the expression predicate using the rules we have defined. If the value returned is true (i.e. not false), then we evaluate the expression consequent. Otherwise, we evaluate the expression alternate. We never evaluate both. The value of the entire if expression is the value of consequent or alternate, depending on which one was evaluated. For example, consider
(define abs
(lambda (x)
(if (< x 0) (negative x) x)))
Suppose we later evaluate the expression
(abs -2)
This yields the following evaluation evolution:
1 (abs -2)
2 [{proc (x) (if (< x 0) (negative x) x)} {-2}]
3 (if (< {-2} 0) (negative {-2}) {-2})
4 (if [{less than} {-2} {0}] (negative {-2}) {-2})
5 (if {true} (negative {-2}) {-2})
6 (negative {-2})
7 [{negate} {-2}]
8 {2}
In lines 3-5 we have detailed the evaluation of the predicate clause of the if expression. Note that this evaluation is done before any of the other clauses of the if are evaluated. Based on the result of that evaluation, only one of the other two clauses is evaluated. That is, the special rule for if takes the expression in 5 and reduces it to just the first (as yet unevaluated) clause, which is shown in 6. Also note that we have introduced a special Boolean object {true} that represents truth. This is the same as the value of the Scheme primitive expression #t. A similar object {false} will be used to represent falsity.
The rule for cond is similar. Each test is evaluated until one is true, and the value of the consequent corresponding to the first true test is the value of the entire expression. None of the other consequents are evaluated.
Last update: 01/19/00 11:35 PM
by Eli