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

要对一个运算符指名复合过程的组合式 (combination) 求值，解释器所遵循的过程与运算符指名基本过程时大体相同——我们已在 1.1.3 节描述过后者。也就是说，解释器对组合式的各元素求值，然后将过程（即组合式运算符的值）作用于实际参数（即组合式各运算对象的值）。

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

将复合过程作用于实际参数，就是在过程体 (body) 中用相应的实际参数替换每个形式参数，然后对该过程体求值。为说明这一过程，我们来对以下组合式求值：

where f is the procedure defined in 1.1.4. We begin by

retrieving the body of f:

其中 f 是 1.1.4 节中定义的过程。我们从取出 f 的过程体开始：

Then we replace the formal parameter a by the argument 5:

然后将形式参数 a 替换为实际参数 5：

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

这样，问题就归结为对一个含两个运算对象和运算符 sum-of-squares 的组合式求值。对这个组合式求值涉及三个子问题：我们必须对运算符求值以得到将要应用的过程，并且必须对各运算对象求值以得到实际参数。现在 `(+ 5 1)` 得到 6，`(* 5 2)` 得到 10，因此我们必须将过程 sum-of-squares 作用于 6 和 10。将这两个值代入 sum-of-squares 过程体中的形式参数 x 和 y，将表达式归约为：

If we use the definition of square, this reduces to

若使用 square 的定义，这进一步归约为：

which reduces by multiplication to

经乘法运算归约为：

and finally to

最终得到：

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:

我们刚才描述的过程称为过程应用的代换模型 (substitution model)。就本章所涉及的过程而言，它可以作为确定过程应用"含义"的模型。然而，有两点需要特别强调：

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 Chapter 3 and

Chapter 4 when we examine the implementation of an interpreter in detail.

代换的目的在于帮助我们思考过程应用，而不是描述解释器的实际工作方式。典型的解释器并不通过操纵过程的文本来将形式参数替换为值。在实践中，"代换"是通过为形式参数建立一个局部环境来实现的。我们将在第 3 章和第 4 章详细考察解释器的实现时，对此作更完整的讨论。

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.

Subheading: Applicative order versus normal order

在本书的展开过程中，我们将呈现一系列日益精细的解释器工作模型，最终在第 5 章给出一个完整的解释器与编译器实现。代换模型只是这些模型中的第一个——一种开始形式化思考求值过程的方式。一般而言，在科学与工程中对现象建模时，我们总是从简化的、不完整的模型出发。随着考察的深入，这些简单模型会变得不够用，必须以更精细的模型加以取代。代换模型也不例外。特别是，当我们在第 3 章讨论带"可变数据"的过程时，将会看到代换模型不再成立，必须以更复杂的过程应用模型来替代它。

小节标题：应用序与正则序

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

this method, the evaluation of (f 5) would proceed according to the

sequence of expansions

按照 1.1.3 节给出的求值描述，解释器先对运算符和运算对象求值，再将得到的过程作用于得到的实际参数。但这并非执行求值的唯一方式。另一种求值模型在实际需要某个值之前不对运算对象求值，而是先将运算对象表达式代入参数位置，直到得到一个只含基本运算符的表达式，然后再执行求值。若采用这种方法，`(f 5)` 的求值将按以下展开序列进行：

followed by the reductions

随后进行如下归约：

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

这与前一种求值模型给出相同的答案，但过程有所不同。特别是，`(+ 5 1)` 和 `(* 5 2)` 的求值在此各被执行了两次，对应于将表达式 `(* x x)` 中的 x 分别替换为 `(+ 5 1)` 和 `(* 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 apply” method that the interpreter actually uses, which is called

正则序求值 (normal-order evaluation)，以区别于解释器实际采用的"先求值实参再应用"方法，后者称为

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 “illegitimate” value where

normal-order and applicative-order evaluation do not give the same result.)

应用序求值 (applicative-order evaluation)。可以证明，对于能用代换模型建模的过程应用（包括本书前两章的所有过程）且能产生合法值的情况，正则序求值与应用序求值给出相同的值。（参见练习 1.5，其中有一个"非法"值的实例，正则序与应用序求值不给出相同的结果。）

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 Chapter 3 and Chapter 4.

Lisp 使用应用序求值，部分原因在于避免了对 `(+ 5 1)` 和 `(* 5 2)` 这类表达式的重复求值所带来的额外效率提升；更重要的原因在于，一旦离开能用代换模型建模的过程领域，正则序求值将变得复杂得多，难以处理。另一方面，正则序求值可以是极具价值的工具，我们将在第 3 章和第 4 章考察它的一些影响。