1.1 编程的要素

1.1 The Elements of Programming

一门强大的编程语言不只是一种指导电脑执行任务的方式。语言也充当的框架，让我们在其中组织有关过程的想法。因此，当我们描述一门语言时，我们应该特别注意这门语言提供的将简单想法组合成复杂想法的方式。每门强大的语言都有三种机制来实现这一目的：

• 基本表达式，用于代表语言关注的最简对象，
• 组合方式，用于将简单元素组合成复合元素，
• 抽象方式，用于命名复合元素并按单元操作它们。

A powerful programming language is more than just a means for instructing a computer to perform tasks. The language also serves as a framework within which we organize our ideas about processes. Thus, when we describe a language, we should pay particular attention to the means that the language provides for combining simple ideas to form more complex ideas. Every powerful language has three mechanisms for accomplishing this:

• primitive expressions, which represent the simplest entities the language is concerned with,
• means of combination, by which compound elements are built from simpler ones, and
• means of abstraction, by which compound elements can be named and manipulated as units.

编程时，我们处理两种元素：程序和数据。（之后我们会发现它们实际上没有那么不同。）不正式地说，数据是我们想要操作的“东西”，程序是对操作数据的规则的描述。因此，任何强大的编程语言都应该有能力描述基本数据和基本程序，还应该有组合和抽象化程序和数据的方法。

In programming, we deal with two kinds of elements: procedures and data. (Later we will discover that they are really not so distinct.) Informally, data is ''stuff'' that we want to manipulate, and procedures are descriptions of the rules for manipulating the data. Thus, any powerful programming language should be able to describe primitive data and primitive procedures and should have methods for combining and abstracting procedures and data.

在这一章中我们只会处理简单的数值数据，因而我们可以专注于建立程序的规则。$$^4$$在之后的章节里我们会看到，相同的规则也能用于操作复合数据。

In this chapter we will deal only with simple numerical data so that we can focus on the rules for building procedures.$$^4$$ In later chapters we will see that these same rules allow us to build procedures to manipulate compound data as well.

1.1.1 表达式

1.1.1 Expressions

开始编程的一种简单方式是和Scheme方言解释器做一些典型的交互。想象你坐在一台计算机终端前。你键入一个表达式，解释器就通过显示那个表达式的求值结果来回应。

One easy way to get started at programming is to examine some typical interactions with an interpreter for the Scheme dialect of Lisp. Imagine that you are sitting at a computer terminal. You type an expression, and the interpreter responds by displaying the result of its evaluating that expression.

一个数字是你可能会键入的一种基本表达式。（更准确地说，你键入的表达式由代表十进制数的数码组成。）如果你给Lisp一个数字

486

解释器就会通过输出$$^5$$

486

加以回应。

One kind of primitive expression you might type is a number. (More precisely, the expression that you type consists of the numerals that represent the number in base 10.) If you present Lisp with a number

486

the interpreter will respond by printing$$^5$$

486

代表数字的表达式可以和代表基本程序的表达式（比如 + 或者 *）组合，用来组成代表程序在数字上应用的表达式。例如：

(+ 137 349)
486
(- 1000 334)
666
(* 5 99)
495
(/ 10 5)
2
(+ 2.7 10)
12.7

Expressions representing numbers may be combined with an expression representing a primitive procedure (such as + or *) to form a compound expression that represents the application of the procedure to those numbers. For example:

(+ 137 349)
486
(- 1000 334)
666
(* 5 99)
495
(/ 10 5)
2
(+ 2.7 10)
12.7

这些由在括号中分隔一列表达式组成的，用来代表程序的应用的表达式叫做组合。列表最左边的元素叫做运算符，其余元素被称为操作数。组合的值是通过将操作符指定的程序应用于实际参数，也就是操作数的值，之上而得到的。

Expressions such as these, formed by delimiting a list of expressions within parentheses in order to denote procedure application, are called combinations. The leftmost element in the list is called the operator, and the other elements are called operands. The value of a combination is obtained by applying the procedure specified by the operator to the arguments that are the values of the operands.

将运算符置于操作数左侧的写法被称为前缀表示法。一开始这可能会有些令人迷惑，因为这与惯常的数学写法不同。然而，前缀表达式有几个好处。其中的一个好处是它能表示那些有任意数量实际参数的程序，例如下面这个例子：

(+ 21 35 12 7)
75

(* 25 4 12)
1200

没有任何歧义，因为运算符总是最左边的元素，而且整个组合被用括号划清界线。

The convention of placing the operator to the left of the operands is known as prefix notation, and it may be somewhat confusing at first because it departs significantly from the customary mathematical convention. Prefix notation has several advantages, however. One of them is that it can accommodate procedures that may take an arbitrary number of arguments, as in the following examples:

(+ 21 35 12 7)
75

(* 25 4 12)
1200

No ambiguity can arise, because the operator is always the leftmost element and the entire combination is delimited by the parentheses.

前缀表达式的第二个好处是它通过一种直白的方式拓展，因而允许组合嵌套，换句话说就是，让组合自己成为组合的元素:

(+ (* 3 5) (- 10 6))
19

A second advantage of prefix notation is that it extends in a straightforward way to allow combinations to be nested, that is, to have combinations whose elements are themselves combinations:

(+ (* 3 5) (- 10 6))
19

Lisp解释器（在理论上）对这种嵌套的深度和表达式的整体复杂度都没有限制。只有我们人类才会被相对来说仍很简单的表达式迷惑，比如：

(+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6))

解释器能轻而易举地算出它的值是57。我们可以通过将表达式写成下面这种形式来帮助自己：

(+ (* 3
      (+ (* 2 4)
         (+ 3 5)))
   (+ (- 10 7)
      6))

这是遵循一种被称为美观打印的格式化写法写成的。在这种写法中，长的组合中的运算符被垂直对齐。结果产生的缩进清晰地展示出表达式的结构。

There is no limit (in principle) to the depth of such nesting and to the overall complexity of the expressions that the Lisp interpreter can evaluate. It is we humans who get confused by still relatively simple expressions such as

(+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6))

which the interpreter would readily evaluate to be 57. We can help ourselves by writing such an expression in the form

(+ (* 3
      (+ (* 2 4)
         (+ 3 5)))
   (+ (- 10 7)
      6))

following a formatting convention known as pretty-printing, in which each long combination is written so that the operands are aligned vertically. The resulting indentations display clearly the structure of the expression.$$^6$$

即使是在处理复杂表达式时，解释器也总是运行同样的基本循环：它从终端读入一个表达式，对它进行求值，并输出结果。这种运转模式俗称读取-执行-输出 循环。尤其要注意，你不需要显式地命令计算机输出表达式的结果。

Even with complex expressions, the interpreter always operates in the same basic cycle: It reads an expression from the terminal, evaluates the expression, and prints the result. This mode of operation is often expressed by saying that the interpreter runs in a read-eval-print loop. Observe in particular that it is not necessary to explicitly instruct the interpreter to print the value of the expression.$$^7$$

1.1.2 命名和环境

1.1.2 Naming and the Environment

程序语言为计算对象提供名字的方式是一个重要的方面。我们说，名字确定变量，后者的值是对象。

A critical aspect of a programming language is the means it provides for using names to refer to computational objects. We say that the name identifies a variable whose value is the object.

在Lisp的Scheme方言中，我们使用define命名事物。输入

(define size 2)

会让解释器把2这个值和size这个名字联系起来。$$^8$$一旦size和数字2相联系，我们就能通过名字查到2这个值。

size
2
(* 5 size)
10

In the Scheme dialect of Lisp, we name things with define. Typing

(define size 2)

causes the interpreter to associate the value 2 with the name size.$$^8$$ Once the name size has been associated with the number 2, we can refer to the value 2 by name:

size
2
(* 5 size)
10

这里有更多define的用法示例：

(define pi 3.14159)
(define radius 10)
(* pi (* radius radius))
314.159
(define circumference (* 2 pi radius))
circumference
62.8318

Here are further examples of the use of define:

(define pi 3.14159)
(define radius 10)
(* pi (* radius radius))
314.159
(define circumference (* 2 pi radius))
circumference
62.8318

define 是我们语言最简单的抽象方式，因为它允许我们使用简单的名字指代复合操作的结果，例如上面计算过的circumference。一般地，计算对象可能具有非常复杂的结构，因此，记住并在每次用到它们时都重复它们的细节会是极其不便的。确实，复杂的程序是由复杂度一点点增加的计算对象，一步步构建的。解释器让这个一步一步的构造过程变得特别简单，因为名字和对象的联系可以增量地在连续的交互中被创建。这一特性鼓励程序的增量式开发和测试，同时，它也在很大程度上导致了一个Lisp程序通常是由许许多多相对简单的程序组成的这一事实。

Define is our language's simplest means of abstraction, for it allows us to use simple names to refer to the results of compound operations, such as the circumference computed above. In general, computational objects may have very complex structures, and it would be extremely inconvenient to have to remember and repeat their details each time we want to use them. Indeed, complex programs are constructed by building, step by step, computational objects of increasing complexity. The interpreter makes this step-by-step program construction particularly convenient because name-object associations can be created incrementally in successive interactions. This feature encourages the incremental development and testing of programs and is largely responsible for the fact that a Lisp program usually consists of a large number of relatively simple procedures.

将值和符号联系起来的可能性意味着解释器必须保留一定的内存，用来追踪名字－对象对，这应该是很清楚的。这些内存被称为环境（更准确地说是全局环境，因为我们之后会看到，同一个计算过程可能会涉及许多不同的环境）。$$^9$$

It should be clear that the possibility of associating values with symbols and later retrieving them means that the interpreter must maintain some sort of memory that keeps track of the name-object pairs. This memory is called the environment (more precisely the global environment, since we will see later that a computation may involve a number of different environments).$$^9$$

1.1.3 计算组合

1.1.3 Evaluating Combinations

在这章中，我们的目的之一是要分离关于程序化思考的问题。让我们考虑一个很好的例子：在计算组合时，解释器本身就遵循一个程序。

• 要计算一个组合，执行下列操作：
  1. 计算组合中的子表达式。
  2. 将最左边的子表达式（运算符）的值表示的程序应用到其他子表达式（操作数）的值表示的实际参数上。

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:
  1. Evaluate the subexpressions of the combination
  2. 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).

即使这个规则很简单，它仍能说明一些有关一般过程的要点。首先，我们观察到，为了完成一个组合的求值过程，第一步要求我们先完成组合中每个元素的求值过程。因此，这套求值规则实际上是递归的。这也就是说，它的一个步骤包含调用它本身的需要。$$^{10}$$

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.$$^{10}$$

请注意递归的概念可以多么简洁地表达，就深度嵌套的组合而言，原本看起来相当复杂的过程。比如说：

(* (+ 2 (* 4 6))
   (+ 3 5 7))

要求求值规则被应用到四个不同的组合上。通过以树的形式表现这一过程，我们可以得到图1.1。每个组合都被以一个节点表示，节点的分支与组合的运算符和操作数相对应。终端节点（也就是没有分支的节点）代表运算符或者操作数。从树的方面看求值过程，我们可以想象操作数的值逐级向上传递——从终端节点开始，在更高的地方合并。一般地，我们应该将递归视为一种用来处理阶层式的、树状对象的非常强大技巧。事实上，求值规则“向上传值”的形式是一类被称为树状积累的过程中的一个例子。

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

(* (+ 2 (* 4 6))
   (+ 3 5 7))

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.

图1.1： 树状表示，显示出每个子组合的值。

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

其次，我们观察到第一部的重复执行最终使我们需要计算基本表达式，例如数码、内置运算符、或者其他名字，而不是组合的值。为了处理这些基本的情况，我们规定：

• 数码的值是它们表示的数字，
• 内置运算符的值是执行对应操作的机器指令序列，以及
• 其他名字的值是在环境中和这些名字相关联的对象。

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

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

我们可以将第二条规则看做第三条的特例，因为诸如+和*的符号是包括在全局环境中的，也是和它们“值”里的机器指令序列相关联的。要注意的关键是环境在决定表达式中符号的意义中发挥的作用。在Lisp之类的交互型语言里，不指定为符号x（甚至是符号+）提供意义的环境的任何信息，而谈论类似(+ x 1)的表达式的值是没有意义的。就像我们将在第三章里看到的那样，环境为求值提供背景的一般概念会对我们对程序执行的理解起到重要作用。

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.

请注意，上面给出的求值规则并不能处理定义。例如，计算(define x 3)并不是把define应用于两个实际参数上：其中一个是符号x的值，另一个是3。这是因为define的意义是精确地把x和一个值关联起来。（这也就是说，(define 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是我们目前唯一看到的特殊形式的例子，但我们很快就会遇到其他的。每种特殊类型都有它自己的求值规则。不同的表达式（每种都有相关的求值规则）组成了编程语言的语法。和其他大部分编程语言相比，Lisp的语法相当简单，也就是说，表达式的求值规则可以用一个简单的一般规则连同少量特殊形式的特别规则来描述。$$^{11}$$

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.$$^{11}$$

1.1.4 复合程序

1.1.4 Compound Procedures

我们已经在Lisp中看到了一些强大的编程语言的必备元素：

• 数字和算数操作是基本数据和程序。
• 组合嵌套提供了一种把操作组合起来的方式。
• 使值与名字相关联的定义提供了一种有限的抽象方式。

We have identified in Lisp some of the elements that must appear in any powerful programming language:

• Numbers and arithmetic operations are primitive data and procedures.
• Nesting of combinations provides a means of combining operations.
• Definitions that associate names with values provide a limited means of abstraction.

现在我们将学习程序定义，一种强大得多的抽象技巧。通过使用这种技巧，我们可以为复杂的操作取一个名字，并把它视为一个单元。

Now we will learn about procedure definitions, a much more powerful abstraction technique by which a compound operation can be given a name and then referred to as a unit.

我们从考察如何表示“平方”的概念开始。我们也许会说，“要平方什么，就乘它以它自己。”在我们的语言中，这被表示为：

(define (square x) (* x x))

We begin by examining how to express the idea of ''squaring.'' We might say, ''To square something, multiply it by itself.'' This is expressed in our language as

(define (square x) (* x x))

我们可以这么理解它：

(define (square  x)        (*         x     x))  
 要      平方     什么，    就乘         它 以  它自己。

We can understand this in the following way:

(define (square  x)        (*         x     x))  
 To      square something, multiply   it by itself.

在这里我们有一个复合程序，它被命名为平方。这一程序代表乘某个东西以它自己。被乘的东西被以一个局部名字x命名，x的作用就像自然语言里的代词一样。对这个定义进行求值会产生这个复合程序，并把它和平方这个名字相关联。$$^{12}$$

We have here a compound procedure, which has been given the name square. The procedure represents the operation of multiplying something by itself. The thing to be multiplied is given a local name, x, which plays the same role that a pronoun plays in natural language. Evaluating the definition creates this compound procedure and associates it with the name square.$$^{12}$$

程序定义的一般形式是：

(define (<name> <formal parameters>) <body>)

<name>是在环境中要与程序定义相关联的记号。$$^{13}$$<formal parameters>是在程序体中用于指代相应实际参数的名字。<body>是一个表达式，当程序应用于的实际参数代替形式参数后，它会产生程序应用的值。$$^{14}$$<name>和<formal parameters>被括号包起来，就像它们在对被定义程序的实际调用中一样。

The general form of a procedure definition is

(define (<name> <formal parameters>) <body>)

The <name> is a symbol to be associated with the procedure definition in the environment.$$^{13}$$ The <formal parameters> are the names used within the body of the procedure to refer to the corresponding arguments of the procedure. The <body> is an expression that will yield the value of the procedure application when the formal parameters are replaced by the actual arguments to which the procedure is applied.$$^{14}$$ The <name> and the <formal parameters> are grouped within parentheses, just as they would be in an actual call to the procedure being defined.

在定义了square之后，我们现在可以使用它了：

(square 21)
441

(square (+ 2 5))
49

(square (square 3))
81

Having defined square, we can now use it:

(square 21)
441

(square (+ 2 5))
49

(square (square 3))
81

我们也可以把square当作定义其他程序的砖块。例如，$$x^2 + y^2$$可以被表示成

(+ (square x) (square y))

We can also use square as a building block in defining other procedures. For example, $$x^2 + y^2$$ can be expressed as

(+ (square x) (square y))

我们可以轻易地定义一个叫sum-of-squares的程序，对于任何两个作为参数的数，计算出它们的平方和：

(define (sum-of-squares x y)
  (+ (square x) (square y)))

(sum-of-squares 3 4)
25

We can easily define a procedure sum-of-squares that, given any two numbers as arguments, produces the sum of their squares:

(define (sum-of-squares x y)
  (+ (square x) (square y)))

(sum-of-squares 3 4)
25

现在我们又可以把sum-of-squares用作构建进一步的程序的砖块：

(define (f a)
  (sum-of-squares (+ a 1) (* a 2)))

(f 5)
 136

Now we can use sum-of-squares as a building block in constructing further procedures:

(define (f a)
  (sum-of-squares (+ a 1) (* a 2)))

(f 5)
 136

复合程序和基本程序的用法完全一样。事实上，通过观察上面给出的对sum-of-squares的定义，你并不能知道square是像+和*一样内置于解释器内的，还是一个被定义的复合过程。

Compound procedures are used in exactly the same way as primitive procedures. Indeed, one could not tell by looking at the definition of sum-of-squares given above whether square was built into the interpreter, like + and *, or defined as a compound procedure.

1.1.5 程序应用的替代模型

1.1.5 The Substitution Model for Procedure Application

解释器计算一个运算符是复合程序名字的组合的过程和计算那些运算符是基本程序名字的组合的过程在很大程度上是一致的，我们在1.1.3节中已经对后者有过描述，即，解释器计算组合的元素，并把程序（组合中运算符的值）应用于参数（组合中操作数的值）上。

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.

为了说明清楚这一点，我们来计算这个组合：

(f 5)

其中f是定义在1.1.4节中的程序。首先，我们来回忆一下f的本体：

(sum-of-squares (+ a 1) (* a 2))

然后，我们用参数5替换掉形式参数：

(sum-of-squares (+ 5 1) (* 5 2))

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

因此这个问题就被化简为对一个具有两个操作数和一个运算符sum-of-squares的组合的求值了。计算这一组合包含三个子问题。我们必须计算运算符以获得要被应用的过程；我们必须计算操作数以获得参数。现在(+ 5 1)产生了6，而(* 5 2)产生了10，因此我们必须把sum-of-squares程序应用到6和10上。这些值取代了sum-of-squares本体中的形式参数x和y，将表达式化简为：

(+ (square 6) (square 10))

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

如果我们使用square的定义，这又会被化简为：

(+ (* 6 6) (* 10 10))

乘法可以把这化简为：

(+ 36 100)

最终我们得到：

136

If we use the definition of square, this reduces to

(+ (* 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:

• 替代的目的是帮助我们理解程序应用，而不是为了描述解释器实际上是如何工作的。典型的解释器不会通过操作程序文本来把形式参数替换成值，并以此计算程序应用。实际上，“替代”是通过使用一个对形式参数的本地环境实现的。在第3和第4章中，当我们仔细探究解释器的实现的时候，我们会对此展开完整的讨论。

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

• 在本书中，我们会呈现一系列越来越精致的模型来说明解释器是如何工作的，并以第5章中对解释器和编译器的详细解释告终。替代模型只是这些模型中的第一个——一种开始正式地思考求值过程的方式。一般地，当我们在科学和工程学中建模时，我们从简化的、不完整的模型开始。当我们更细致地考察事物时，这些简单模型就不充分了，所以他们必须被更精细的模型取代。替代模型也不例外。特别地，当我们在第三章中使用“可变数据”说明程序的用法时，我们会看到替代模型将不再成立，因此它必须被一种更复杂的过程应用的模型取代。$$^{15}$$

• 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

根据1.1.3节中给出的对于求值的描述，解释器首先对运算符和操作数求值，然后再把产生的程序应用到产生的参数上。这不是执行计算的唯一途径。另一个可选的求值模型不会对操作数进行求值，直到我们需要他们的值。相反，它首先把形式参数替换成操作数表达式，直到获得一个只含基本运算符的表达式，然后再执行求值。如果我们使用这种方法，

(f 5)

的求值过程就会按照一系列的展开进行

(sum-of-squares (+ 5 1) (* 5 2))

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

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

接着是化简

(+         (* 6 6)             (* 10 10))

(+           36                   100)

                    136

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

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

答案与我们先前的求值模型相同，但过程不同。特别地，(+ 5 1)和(* 5 2)的求值过程在这里都被执行了两次。这就相当于表达式

(* x x)

的化简，其中的x被(+ 5 1)和(* 5 2)分别替换。

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

这一另外的“完全展开再化简”的求值方法被称为正常次序求值，与之相对的是“对实际参数求值在应用”这一解释器实际采用的，被称为应用次序求值的方法。可以证明，对于那些可以用替代对其建模（本书前两章中的所有程序都是如此）、且产生合法值的程序应用，正常次序求值和应用次序求值产生的结果是相同的。（练习1.5中有一个正常次序求值和应用次序求值给出不同结果的“非法值”的例子。）

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 1.5 for an instance of an ''illegitimate'' value where normal-order and applicative-order evalLispuation do not give the same result.)

Lisp采用应用次序求值，这部分是因为避免对类似之前提到的(+ 5 1)和(* 5 2)的表达式进行多次求值可以产生额外的效率，更重要的是因为，当我们离开能通过替代建模的程序的领域之后，正常次序求值会变得难处理得多。反过来，正常次序求值也可以是极有价值的工具，我们将在第3和第4章中探讨它的一些影响。$$^{16}$$

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.$$^{16}$$

1.1.6 条件表达式和谓词

1.1.6 Conditional Expressions and Predicates

我们现在能定义的这类程序的表现力是十分有限的，因为我们无法做测试，并根据测试的结果执行不同的操作。比如，我们不能定义一个计算绝对值的程序，通过测试一个数是正数、负数还是零，并根据下列规则对不同的情况采取不同的行动：

The expressive power of the class of procedures that we can define at this point is very limited, because we have no way to make tests and to perform different operations depending on the result of a test. For instance, we cannot define a procedure that computes the absolute value of a number by testing whether the number is positive, negative, or zero and taking different actions in the different cases according to the rule

这个结构被称为情况分析，在Lisp中有一种特殊的形式用来代表这样的情况分析。它被称为cond（代表“条件的”（''conditional''——译按）），用法如下：

(define (abs x)
  (cond ((> x 0) x)
        ((= x 0) 0)
        ((< x 0) (- x))))

This construct is called a case analysis, and there is a special form in Lisp for notating such a case analysis. It is called cond (which stands for ''conditional''), and it is used as follows:

(define (abs x)
  (cond ((> x 0) x)
        ((= x 0) 0)
        ((< x 0) (- x))))

条件表达式的一般形式是：

(cond (<p1> <e1>)
      (<p2> <e2>)

      (<pn> <en>))

它由符号cond和紧接着的名叫子句的被括号包裹起来的表达式对(<p> <e>)组成。每对中的第一个表达式是谓词，就是指值被解释执行成真或者假的表达式。

The general form of a conditional expression is

(cond (<p1> <e1>)
      (<p2> <e2>)

      (<pn> <en>))

consisting of the symbol cond followed by parenthesized pairs of expressions (<p> <e>) called clauses. The first expression in each pair is a predicate -- that is, an expression whose value is interpreted as either true or false.$$^{17}$$

条件表达式是这么被求值的：谓词<p1>首先被求值。如果它的值是假，那<p2>就被求值。如果<p2>的值也是假，那<p3>就被求值。这个过程一直持续到找到一个值为真谓词为止，在这种情况下，解释器会返回该分句相应的结果表达式的值作为条件表达式的值。如果没有找到值为真的<p>，cond的值就是未定义的。

Conditional expressions are evaluated as follows. The predicate <p1> is evaluated first. If its value is false, then <p2> is evaluated. If <p2>'s value is also false, then <p3> is evaluated. This process continues until a predicate is found whose value is true, in which case the interpreter returns the value of the corresponding consequent expression <e> of the clause as the value of the conditional expression. If none of the <p>'s is found to be true, the value of the cond is undefined.

谓词这个被用于返回真或假的程序，以及求值结果为真或假的表达式。绝对值程序abs使用了基本谓词>，<和=。$$^{18}$$它们有两个实际参数，并测试第一个数相对于第二个数是大于、小于或者等于，并据此返回真或假。

The word predicate is used for procedures that return true or false, as well as for expressions that evaluate to true or false. The absolute-value procedure abs makes use of the primitive predicates >, <, and =.$$^{18}$$ These take two numbers as arguments and test whether the first number is, respectively, greater than, less than, or equal to the second number, returning true or false accordingly.

绝对值程序的另一种写法是

(define (abs x)
  (cond ((< x 0) (- x))
        (else x)))

用中文（原文为“英语” ——译按）说就是“如果x小于0，就返回- x；否则就返回x。”Else是一个可以用在cond中最后一句子句的位置的特殊符号。在先前所有字句都被绕过的情况下，它会让cond返回它对应的<e>的值。事实上，任何计算结果总为真的表达式都能作这里的<p>。

Another way to write the absolute-value procedure is

(define (abs x)
  (cond ((< x 0) (- x))
        (else x)))

which could be expressed in English as ''If x is less than zero return - x; otherwise return x.'' Else is a special symbol that can be used in place of the <p> in the final clause of a cond. This causes the cond to return as its value the value of the corresponding <e> whenever all previous clauses have been bypassed. In fact, any expression that always evaluates to a true value could be used as the <p> here.

绝对值程序还有一种写法：

(define (abs x)
  (if (< x 0)
      (- x)
      x))

Here is yet another way to write the absolute-value procedure:

(define (abs x)
  (if (< x 0)
      (- x)
      x))

这里使用了特殊形式if，条件式的一种受限类型，当情况分析中恰有两种情况时可以用它。if表达式的一般形式是

(if <predicate> <consequent> <alternative>)

This uses the special form if, a restricted type of conditional that can be used when there are precisely two cases in the case analysis. The general form of an if expression is

(if <predicate> <consequent> <alternative>)

要计算一个if表达式，解释器首先计算表达式的<predicate>部分。如果<predicate>的结果是真，解释器就接着对<consequent>求值并返回它的值。否则，它就对<alternative>求值并返回这个值。

To evaluate an if expression, the interpreter starts by evaluating the <predicate> part of the expression. If the <predicate> evaluates to a true value, the interpreter then evaluates the <consequent> and returns its value. Otherwise it evaluates the <alternative> and returns its value.$$^{19}$$

出了<，=和>这样的基本谓词，还有逻辑组合运算，它们使我们得以构建复合谓词。这里是最常用的三个：

• (and <e1> ... <en>)

• 解释器从左到右一个个对表达式<e>求值。如果任何一个<e>的值是假，这个and表达式的值就是假，其余的<e>不会被求值。如果所有<e>的值都为真，and表达式的值就是最后一个<e>的值。

• (and <e1> ... <en>)

• 解释器从左到右一个个对表达式<e>求值。如果任何一个<e>的值是真，它的值就被返回，作为这个or表达式的值，其余的<e>不会被求值。如果所有<e>的值都为假，or表达式的值为假。

• (not <e>)

• 当<e>表达式的值为假，not表达式的值就为真，否则为假。

In addition to primitive predicates such as <, =, and >, there are logical composition operations, which enable us to construct compound predicates. The three most frequently used are these:

• (and <e1> ... <en>)
• The interpreter evaluates the expressions <e> one at a time, in left-to-right order. If any <e> evaluates to false, the value of the and expression is false, and the rest of the <e>'s are not evaluated. If all <e>'s evaluate to true values, the value of the and expression is the value of the last one.

• (or <e1> ... <en>)
• The interpreter evaluates the expressions <e> one at a time, in left-to-right order. If any <e> evaluates to a true value, that value is returned as the value of the or expression, and the rest of the <e>'s are not evaluated. If all <e>'s evaluate to false, the value of the or expression is false.

• (not <e>)
• The value of a not expression is true when the expression <e> evaluates to false, and false otherwise.

请注意，and and or是特殊形式，而不是程序，因为子表达式不一定都会被求值。Not是一个普通程序。

举个例子来说明如何使用它们：数字x在范围$$5 < x < 10$$中的条件可以被表示成

(and (> x 5) (< x 10))

作为另一个例子，我们可以这样定义一个用来测试一个数是否大于等于另一个数的谓词

(define (>= x y)
  (or (> x y) (= x y)))

也可以把它写成

(define (>= x y)
  (not (< x y)))

Notice that and and or are special forms, not procedures, because the subexpressions are not necessarily all evaluated. Not is an ordinary procedure.

As an example of how these are used, the condition that a number x be in the range $$5 < x < 10$$ may be expressed as

(and (> x 5) (< x 10))

As another example, we can define a predicate to test whether one number is greater than or equal to another as

(define (>= x y)
  (or (> x y) (= x y)))

or alternatively as

(define (>= x y)
  (not (< x y)))

练习1.1. 下面有一列表达式。解释器输出的每个表达式的结果是什么？假设这列表达式的求值顺序与显示顺序相同。

Exercise 1.1. Below is a sequence of expressions. What is the result printed by the interpreter in response to each expression? Assume that the sequence is to be evaluated in the order in which it is presented.

10
(+ 5 3 4)
(- 9 1)
(/ 6 2)
(+ (* 2 4) (- 4 6))
(define a 3)
(define b (+ a 1))
(+ a b (* a b))
(= a b)
(if (and (> b a) (< b (* a b)))
    b
    a)
(cond ((= a 4) 6)
      ((= b 4) (+ 6 7 a))
      (else 25))
(+ 2 (if (> b a) b a))
(* (cond ((> a b) a)
         ((< a b) b)
         (else -1))
   (+ a 1))

练习 1.2. 将下列表达式翻译成前缀形式

Exercise 1.2. Translate the following expression into prefix form

练习 1.3. 定义一个以三个数字作为实际参数的程序，返回较大的两个数的平方和。

Exercise 1.3. Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers.

练习 1.4. 观察到我们的求值模型允许复合表达式作为组合的运算符。使用这一结论，描述下列程序的行为：

(define (a-plus-abs-b a b)
  ((if (> b 0) + -) a b))

Exercise 1.4. Observe that our model of evaluation allows for combinations whose operators are compound expressions. Use this observation to describe the behavior of the following procedure:

(define (a-plus-abs-b a b)
  ((if (> b 0) + -) a b))

练习 1.5. 小明发明了一种用于判断解释器使用的是应用次序求值还是正常顺序求值的测试。他定义了下列两个程序：

(define (p) (p))

(define (test x y)
  (if (= x 0)
      0
      y))

然后他对这个表达式求值：

(test 0 (p))

小明会在一个使用应用次序求值的解释器上看到什么呢？他在一个使用正常次序求值的解释器上又会看到什么呢？请解释你的答案。（假设，无论解释器使用应用次序求值还是正常次序求值，特殊形式if的求值规则都是这样的：谓词表达式首先被求值，再用它的结果决定是对结果表达式求值还是对替代表达式求值。）

Exercise 1.5. Ben Bitdiddle has invented a test to determine whether the interpreter he is faced with is using applicative-order evaluation or normal-order evaluation. He defines the following two procedures:

(define (p) (p))

(define (test x y)
  (if (= x 0)
      0
      y))

Then he evaluates the expression

(test 0 (p))

What behavior will Ben observe with an interpreter that uses applicative-order evaluation? What behavior will he observe with an interpreter that uses normal-order evaluation? Explain your answer. (Assume that the evaluation rule for the special form if is the same whether the interpreter is using normal or applicative order: The predicate expression is evaluated first, and the result determines whether to evaluate the consequent or the alternative expression.)

1.1.7 实例：牛顿法求平方根

1.1.7 Example: Square Roots by Newton's Method

程序，如同上面介绍的那样，很像普通的数学函数。它们根据一个或多个参数指定一个值。但是数学函数和计算机程序有一个重要的不同。程序必须有效。

Procedures, as introduced above, are much like ordinary mathematical functions. They specify a value that is determined by one or more parameters. But there is an important difference between mathematical functions and computer procedures. Procedures must be effective.

作为一个很好的例子，考虑计算平方根的问题。我们可以这么定义平方根

这描述了一个完美合法的数学函数。我们可以用它来判断一个数是否是另一个数的平方根，或者推导出有关平方根的一般事实。但在另一方面，这个定义并没有描述一个过程。事实上，他几乎没有没有告诉我们到底如何才能找到一个数的平方根。用伪Lisp重新表述这个定义并没有意义：

(define (sqrt x)
  (the y (and (>= y 0)
              (= (square y) x))))

这仅仅是在回避问题。

As a case in point, consider the problem of computing square roots. We can define the square-root function as

This describes a perfectly legitimate mathematical function. We could use it to recognize whether one number is the square root of another, or to derive facts about square roots in general. On the other hand, the definition does not describe a procedure. Indeed, it tells us almost nothing about how to actually find the square root of a given number. It will not help matters to rephrase this definition in pseudo-Lisp:

(define (sqrt x)
  (the y (and (>= y 0)
              (= (square y) x))))

This only begs the question.

函数和程序之间的反差反映了描述事物的性质和描述如何做事之间的一般区别，这有时候也会被称为陈述性知识和祈使性知识的区别。在数学中，我们通常关心陈述性（是什么）描述，然而在计算机科学中我们通常关心祈使性（怎么做）描述。$$^{20}$$

The contrast between function and procedure is a reflection of the general distinction between describing properties of things and describing how to do things, or, as it is sometimes referred to, the distinction between declarative knowledge and imperative knowledge. In mathematics we are usually concerned with declarative (what is) descriptions, whereas in computer science we are usually concerned with imperative (how to) descriptions.$$^{20}$$

一个人要如何计算平方根呢？最平常的方法是使用牛顿的连续逼近法，这就是说每当我们猜测$$y$$是一个数$$x$$的平方根，我们可以进行一部简单的操作，即取$$y$$和$$x/y$$的平均数，来获得更好（更接近实际平方根）的猜测。比如，我们可以按下列方法计算2的平方根。假定我们一开始的猜想是1:

继续这个过程，我们就能获得对平方根越来越好的近似。

How does one compute square roots? The most common way is to use Newton's method of successive approximations, which says that whenever we have a guess $$y$$ for the value of the square root of a number $$x$$, we can perform a simple manipulation to get a better guess (one closer to the actual square root) by averaging $$y$$ with $$x/y$$.$$^{21}$$ For example, we can compute the square root of 2 as follows. Suppose our initial guess is 1:

Continuing this process, we obtain better and better approximations to the square root.

现在让我们站在程序的角度对这个过程进行形式化。开始时我们有一个被开放数（我们要计算平方根的那个数）和一个猜测的数。如果这一猜测足以达成我们的目的，我们就完成了；如果不够，我们必须以一个改善过的猜想重复这个过程。我们把这个基本策略写成一个程序：

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
                 x)))

Now let's formalize the process in terms of procedures. We start with a value for the radicand (the number whose square root we are trying to compute) and a value for the guess. If the guess is good enough for our purposes, we are done; if not, we must repeat the process with an improved guess. We write this basic strategy as a procedure:

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
                 x)))

我们可以改善一个猜想，方法是对它和被开放数与旧猜想的比值取平均：

(define (improve guess x)
  (average guess (/ x guess)))

其中

(define (average x y)
  (/ (+ x y) 2))

A guess is improved by averaging it with the quotient of the radicand and the old guess:

(define (improve guess x)
  (average guess (/ x guess)))

where

(define (average x y)
  (/ (+ x y) 2))

我们还得说明“足够好”是什么意思。以下是解释，但它实际上并不是一个太好的测试。（见练习1.7.）我们想法是一直改善答案，直到它接近到它的平方与被平方数的差小于一个事先确定的容差（这里用的是0.001）：$$^{22}$$

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

We also have to say what we mean by ''good enough.'' The following will do for illustration, but it is not really a very good test. (See exercise 1.7.) The idea is to improve the answer until it is close enough so that its square differs from the radicand by less than a predetermined tolerance (here 0.001):$$^{22}$$

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

最后，我们需要一种开始的方法。例如，我们可以始终猜想任何数的平方根都是1:$$^{23}$$

(define (sqrt x)
  (sqrt-iter 1.0 x))

Finally, we need a way to get started. For instance, we can always guess that the square root of any number is 1:$$^{23}$$

(define (sqrt x)
  (sqrt-iter 1.0 x))

如果我们把这些定义输入解释器，我们就可以像使用任何程序一样使用sqrt：

(sqrt 9)
3.00009155413138
(sqrt (+ 100 37))
11.704699917758145
(sqrt (+ (sqrt 2) (sqrt 3)))
1.7739279023207892
(square (sqrt 1000))
1000.000369924366

If we type these definitions to the interpreter, we can use sqrt just as we can use any procedure:

(sqrt 9)
3.00009155413138
(sqrt (+ 100 37))
11.704699917758145
(sqrt (+ (sqrt 2) (sqrt 3)))
1.7739279023207892
(square (sqrt 1000))
1000.000369924366

sqrt程序也显示我们介绍了这么多的这个简单的程序化语言足以编写任何能用，比如说，C或者Pascal编写的纯数学程序。这看起来也许很令人惊讶，因为我们的语言还没有包含指导计算机一遍遍重复做事情的迭代（循环）结构。Sqrt-iter，在另一方面，展示了如何不用除了调用程序的普通能力之外的特殊结构实现迭代。$$^{24}$$

The sqrt program also illustrates that the simple procedural language we have introduced so far is sufficient for writing any purely numerical program that one could write in, say, C or Pascal. This might seem surprising, since we have not included in our language any iterative (looping) constructs that direct the computer to do something over and over again. Sqrt-iter, on the other hand, demonstrates how iteration can be accomplished using no special construct other than the ordinary ability to call a procedure.$$^{24}$$

练习 1.7. 在计算很小的数字的平方根时，good-enough?测试不会很有效。同时，在真实的计算机上，算术操作的精度几乎总是有限的。这就让我们的测试不足以应对大数字。解释这些结论，举例说明为什么测试无法处理小数字和大数字。另一种实现good-enough?的策略是观察guess在两次迭代间的变化，并在变化只占猜想很小部分的时候停止。定义一个用这种终止测试的平方根程序。这个作品能更好地处理小数字和大数字吗？

Exercise 1.7. The good-enough? test used in computing square roots will not be very effective for finding the square roots of very small numbers. Also, in real computers, arithmetic operations are almost always performed with limited precision. This makes our test inadequate for very large numbers. Explain these statements, with examples showing how the test fails for small and large numbers. An alternative strategy for implementing good-enough? is to watch how guess changes from one iteration to the next and to stop when the change is a very small fraction of the guess. Design a square-root procedure that uses this kind of end test. Does this work better for small and large numbers?

练习 1.8. 牛顿法求立方根是基于这样一个事实的：如果$$y$$是对$$x$$的立方根的近似，一个更好的近似的值就会是

$$\frac{\frac{x}{y^2}+2y}{3}$$

类比平方根程序，使用这个公式实现一个立方根过程。（在1.3.4节中我们将看到如何把牛顿法作为这些平方根和立方根程序的抽象，一般地实现。）

Exercise 1.8. Newton's method for cube roots is based on the fact that if $$y$$ is an approximation to the cube root of $$x$$, then a better approximation is given by the value

$$\frac{\frac{x}{y^2}+2y}{3}$$

Use this formula to implement a cube-root procedure analogous to the square-root procedure. (In section 1.3.4 we will see how to implement Newton's method in general as an abstraction of these square-root and cube-root procedures.)

1.1.8 把程序作为黑盒抽象

1.1.8 Procedures as Black-Box Abstractions

Sqrt is our first example of a process defined by a set of mutually defined procedures. Notice that the definition of sqrt-iter is recursive; that is, the procedure is defined in terms of itself. The idea of being able to define a procedure in terms of itself may be disturbing; it may seem unclear how such a ''ircular'' definition could make sense at all, much less specify a well-defined process to be carried out by a computer. This will be addressed more carefully in section 1.2. But first let's consider some other important points illustrated by the sqrt example.