To evaluate a combination whose operator names a compound procedure,
the interpreter follows much the same process as for combinations
whose operators name primitive procedures, which we described in
section 1.1.3.
That is, the interpreter evaluates the elements of the combination and
applies the procedure (which is the value of the operator of the
combination) to the arguments (which are the values of the operands of
the combination).
We can assume that the mechanism for applying primitive procedures to
arguments is built into the interpreter. For compound procedures, the
application process is as follows:
To apply a compound procedure to arguments, evaluate the body of
the procedure with each formal parameter replaced by the corresponding
argument.
To illustrate this process, let's evaluate the combination
(f 5)
where f is the procedure defined in section 1.1.4. We begin by
retrieving the body of f:
(sum-of-squares (+ a 1) (
a 2))
Then we replace the formal parameter a by the argument 5:
(sum-of-squares (+ 5 1) ( 5 2))
Thus the problem reduces to the evaluation of a combination with two
operands and an operator sum-of-squares. Evaluating this
combination involves three subproblems. We must evaluate the operator
to get the procedure to be applied, and we must evaluate the operands
to get the arguments. Now (+ 5 1) produces 6 and ( 5 2) produces 10, so we must apply the
sum-of-squares procedure to 6 and 10. These values are
substituted for the formal parameters x and y in
the body of sum-of-squares, reducing the expression to
(+ (square 6) (square 10))
If we use the definition of square, this reduces to
(+ ( 6 6) ( 10 10))
which reduces by multiplication to
(+ 32 100)
and finally to
(136)
The process we have just described is called the substitution
model for procedure application. It can be taken as a model that
determines the "meaning" of procedure application, insofar as the
procedures in this chapter are concerned. However, there are two
points that should be stressed:
The purpose of the substitution is to help us think about procedure
application, not to provide a description of how the interpreter
really works. Typical interpreters do not evaluate procedure
applications by manipulating the text of a procedure to substitute
values for the formal parameters. In practice, the "substitution" is
accomplished by using a local environment for the formal
parameters. We will discuss this more fully in chapters 3 and 4 when
we examine the implementation of an interpreter in detail.
Over the course of this book, we will present a sequence of
increasingly elaborate models of how interpreters work, culminating
with a complete implementation of an interpreter and compiler in
chapter 5. The substitution model is only the first of these models
a way to get started thinking formally about the evaluation
process. In general, when modeling phenomena in science and
engineering, we begin with simplified, incomplete models. As we
examine things in greater detail these simple models become inadequate
and must be replaced by more refined models. The substitution model is
no exception. In particular, when we address in chapter 3 the use of
procedures with "mutable data," we will see that the substitution
model breaks down and must be replaced by a more complicated model of
procedure application. 15
Applicative order versus normal order
According to the description of evaluation given in section 1.1.3, the
interpreter first evaluates the operator and operands and then applies
the resulting procedure to the resulting arguments. This is not the
only way to perform evaluation. An alternative evaluation model would
not evaluate the operands until their values were needed. Instead it
would first substitute operand expressions for parameters until it
obtained an expression involving only primitive operators, and would
then perfom the evaluation. If we used this method, the evaluation of
(f 5)
would proceed according to the sequence of expressions
(sum-of-squares (+ 5 1) ( 5 2))
(+ (square (+ 5 1)) (square ( 5 2)) )
(+ ( (+ 5 1) (+ 5 1)) ( ( 5 2) ( 5 2)))
followed by the reductions
(+ ( 6 6) ( 10 10))
(+ 36 100)
136
This gives the same answer as our previous evaluation model, but the
process is different. In particular, the evaluations of (+ 5
1) and ( 5 2) are each performed
twice here, corresponding to the reduction of the expression
( x x)
with x replaced respectively by (+ 5 1) and ( 5 2).
This alternative "fully expand and then reduce" evaluation method is
known as normal-order evaluation, in contrast to the
"evaluate the arguments and then appply" method that the interpreter
actually uses, which is called applicative-order
evaluation. It can be shown that, for procedure applications that
can be modeled using substitution (including all the procedures in the
first two chapters of this book) and that yield legitimate values,
normal-order and applicative-order evaluation produce the same
value. (See exercise 1.5 for an instance of an "illigitimate" value
where normal-order and applicative-order evaluation do not give the
same result.)
Lisp uses applicative-order evaluation, partly because of the
additional efficiency obtained from avoiding multiple evaluations of
expressions such as those illustrated with (+ 5 2) and
( 5 2) above and, more significantly,
because normal-order evaluation becomes much more complicated to deal
with when we leave the realm of procedures that can be modeled by
substitution. On the other hand, normal-order evaluation can be an
extremely valuable tool, and we will investigate some of its
implications in chapters 3 and 4. 16
