The Substitution Model for Procedure Application

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

(sum-of-squares (+ a 1) (* a 2))Then we replace the formal parameter

(sum-of-squares (+ 5 1) (* 5 2))Thus the problem reduces to the evaluation of a combination with two operands and an operator

(+ (square 6) (square 10))If we use the definition of

(+ (* 6 6) (* 10 10))which reduces by multiplication to

(+ 36 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.

^{}

Applicative order versus normal order

According to the description of evaluation given in section , 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 perform the evaluation. If we used this method, the evaluation of

(f 5)would proceed according to the sequence of expansions

(sum-of-squares (+ 5 1) (* 5 2))followed by the reductions(+ (square (+ 5 1)) (square (* 5 2)) )

(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))

(+ (* 6 6) (* 10 10))This gives the same answer as our previous evaluation model, but the process is different. In particular, the evaluations of(+ 36 100)

136

(* x x)with

This alternative ``fully expand and then reduce'' evaluation method is
known as
*normal-order evaluation*, in contrast to the ``evaluate
the arguments and then apply'' 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 for an instance of
an ``illegitimate'' 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 1)` 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.^{}