1.1.3 Evaluating Combinations

One of our goals in this chapter is to isolate issues about thinking

procedurally. As a case in point, let us consider that, in evaluating

combinations, the interpreter is itself following a procedure.

To evaluate a combination, do the following:

本章的目标之一是将有关过程式思维的问题单独提炼出来加以讨论。就此而言，让我们考虑这样一点：在对组合式求值时，解释器本身也在遵循一个过程。对一个组合式求值，需要执行以下步骤：

Evaluate the subexpressions of the combination.

对组合式的各个子表达式求值。

Apply the procedure that is the value of the leftmost subexpression (the

operator) to the arguments that are the values of the other subexpressions (the

operands).

将最左子表达式（运算符）的值所表示的过程，应用于其余子表达式（运算对象）的值所组成的实际参数。

Even this simple rule illustrates some important points about processes in

general. First, observe that the first step dictates that in order to

accomplish the evaluation process for a combination we must first perform the

evaluation process on each element of the combination. Thus, the evaluation

rule is

recursive in nature; that is, it includes, as one of its

steps, the need to invoke the rule itself.

就是这条简单的规则，也揭示了一些关于计算过程的重要之处。首先，请注意第一步规定：为了对一个组合式完成求值过程，我们必须先对组合式的每个元素执行求值过程。因此，这条求值规则在本质上是递归的 (recursive)，也就是说，它在自身的步骤中包含了调用规则本身的需求。

Notice how succinctly the idea of recursion can be used to express what, in the

case of a deeply nested combination, would otherwise be viewed as a rather

complicated process. For example, evaluating

请注意，递归这一思想被运用得多么简洁——对于深度嵌套的组合式而言，若不借助递归，整个求值过程将显得相当繁复。例如，对

requires that the evaluation rule be applied to four different combinations.

We can obtain a picture of this process by representing the combination in the

form of a tree, as shown in Figure 1.1. Each combination is represented

by a node with branches corresponding to the operator and the operands of the

combination stemming from it. The terminal nodes (that is, nodes with no

branches stemming from them) represent either operators or numbers. Viewing

evaluation in terms of the tree, we can imagine that the values of the operands

percolate upward, starting from the terminal nodes and then combining at higher

and higher levels. In general, we shall see that recursion is a very powerful

technique for dealing with hierarchical, treelike objects. In fact, the

“percolate values upward” form of the evaluation rule is an example of a

general kind of process known as

tree accumulation.

Figure 1.1: Tree representation, showing the value of each subcombination.

求值，需要将求值规则应用于四个不同的组合式。我们可以用树形结构来表示这一组合式，从而得到该计算过程的直观图示，如图 1.1 所示。每个组合式用一个节点表示，从该节点伸出的分支分别对应于组合式的运算符和各运算对象。终端节点（即没有分支从其伸出的节点）表示运算符或数。从树的角度来看待求值过程，可以想象运算对象的值从终端节点开始向上渗透，在越来越高的层次上汇合组合。一般来说，我们将看到递归是处理层次化树形对象的强大技术。事实上，求值规则中"值向上渗透"的形式正是一类称为树形积累 (tree accumulation) 的通用计算过程的一个例子。图 1.1：树形表示，显示了各子组合式的值。

Next, observe that the repeated application of the first step brings us to the

point where we need to evaluate, not combinations, but primitive expressions

such as numerals, built-in operators, or other names. We take care of the

primitive cases by stipulating that

其次，请注意：反复应用第一步，最终会使我们需要对的不再是组合式，而是基本表达式 (primitive expressions)，例如数字字符 (numerals)、内置运算符或其他名字。对于这些基本情形，我们规定：

the values of numerals are the numbers that they name,

数字字符的值是它们所表示的数；

the values of built-in operators are the machine instruction sequences that

carry out the corresponding operations, and

内置运算符的值是执行相应操作的机器指令序列；以及

the values of other names are the objects associated with those names in the

environment.

其他名字的值是环境中与这些名字相关联的对象。

We may regard the second rule as a special case of the third one by stipulating

that symbols such as + and * are also included in the global

environment, and are associated with the sequences of machine instructions that

are their “values.” The key point to notice is the role of the environment

in determining the meaning of the symbols in expressions. In an interactive

language such as Lisp, it is meaningless to speak of the value of an expression

such as (+ x 1) without specifying any information about the environment

that would provide a meaning for the symbol x (or even for the symbol

+). As we shall see in Chapter 3, the general notion of the

environment as providing a context in which evaluation takes place will play an

important role in our understanding of program execution.

我们可以将第二条规则视为第三条规则的特例，方法是规定 + 和 * 这样的符号也被包含在全局环境中，并与作为其"值"的机器指令序列相关联。这里需要注意的关键点是：环境在确定表达式中符号含义方面所起的作用。在 Lisp 这样的交互式语言中，如果不给出关于环境的任何信息，谈论 (+ x 1) 这样的表达式的值是毫无意义的——因为环境才能为符号 x（乃至符号 +）赋予含义。我们将在第 3 章中看到，环境作为求值所在语境这一一般性概念，在我们理解程序执行方面将扮演重要角色。

Notice that the evaluation rule given above does not handle definitions. For

instance, evaluating (define x 3) does not apply define to two

arguments, one of which is the value of the symbol x and the other of

which is 3, since the purpose of the define is precisely to associate

x with a value. (That is, (define x 3) is not a combination.)

请注意，上面给出的求值规则并不处理定义。例如，对 (define x 3) 求值，并非将 define 应用于两个参数——其中一个是符号 x 的值，另一个是 3——因为 define 的目的恰恰是要将 x 与某个值关联起来。（也就是说，(define x 3) 不是一个组合式。）

Such exceptions to the general evaluation rule are called

special forms.

Define is the only example of a special form that we have seen

so far, but we will meet others shortly. Each special form has its own

evaluation rule. The various kinds of expressions (each with its associated

evaluation rule) constitute the syntax of the programming language. In

comparison with most other programming languages, Lisp has a very simple

syntax; that is, the evaluation rule for expressions can be described by a

simple general rule together with specialized rules for a small number of

special forms.

这类对一般求值规则的例外称为特殊形式 (special forms)。define 是我们目前见过的唯一一个特殊形式，但很快我们还会遇到其他特殊形式。每种特殊形式都有其自身的求值规则。各种表达式（每种都有与之关联的求值规则）共同构成了编程语言的语法。与大多数其他编程语言相比，Lisp 拥有非常简单的语法：表达式的求值规则可以用一条简单的通用规则加上少数几种特殊形式的专门规则来完整描述。