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

sqrt 是我们遇到的第一个由一组相互定义的过程所刻画的计算过程的例子。注意，sqrt-iter 的定义是

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 “circular” 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 1.2. But first let’s

consider some other important points illustrated by the sqrt example.

递归的，即这个过程是用它自身来定义的。能够用自身来定义过程这一想法可能令人困惑——如此"循环"的定义究竟能否有意义，更遑论要由计算机执行一个有明确意义的计算过程，这似乎都不清楚。我们将在 1.2 节中更仔细地处理这一问题。但首先，让我们来考察 sqrt 例子所揭示的另外一些重要问题。

Observe that the problem of computing square roots breaks up naturally into a

number of subproblems: how to tell whether a guess is good enough, how to

improve a guess, and so on. Each of these tasks is accomplished by a separate

procedure. The entire sqrt program can be viewed as a cluster of

procedures (shown in Figure 1.2) that mirrors the decomposition of the

problem into subproblems.

Figure 1.2: Procedural decomposition of the sqrt program.

观察可知，计算平方根这个问题自然地分解为若干子问题：如何判断猜测值是否足够好，如何改进猜测值，等等。每一项任务都由一个独立的过程来完成。整个 sqrt 程序可以看作一族过程（如图 1.2 所示），它直接反映了问题向子问题的分解结构。

图 1.2：sqrt 程序的过程式分解。

The importance of this decomposition strategy is not simply that one is

dividing the program into parts. After all, we could take any large program

and divide it into parts—the first ten lines, the next ten lines, the next

ten lines, and so on. Rather, it is crucial that each procedure accomplishes

an identifiable task that can be used as a module in defining other procedures.

For example, when we define the good-enough? procedure in terms of

square, we are able to regard the square procedure as a “black

box.” We are not at that moment concerned with how the procedure

computes its result, only with the fact that it computes the square. The

details of how the square is computed can be suppressed, to be considered at a

later time. Indeed, as far as the good-enough? procedure is concerned,

square is not quite a procedure but rather an abstraction of a

procedure, a so-called

procedural abstraction. At this level of

abstraction, any procedure that computes the square is equally good.

这种分解策略的重要性，并不仅仅在于把程序划分成若干部分。毕竟，我们可以对任何大型程序进行机械切割——前十行、再十行、又十行，如此类推。关键在于，每一个过程必须完成一项可以清晰辨认的任务，并能作为定义其他过程时的一个模块加以使用。例如，当我们用 square 来定义 good-enough? 时，我们就把 square 视为一个"黑箱 (black box)"。在那个时刻，我们并不关心这个过程是如何计算出结果的，只关心它能计算出平方这一事实。square 的计算细节可以被压制下去，留待以后再考虑。事实上，就 good-enough? 而言，square 与其说是一个过程，不如说是对一个过程的抽象，即所谓的过程抽象 (procedural abstraction)。在这一抽象层次上，任何能计算平方的过程都同样适用。

Thus, considering only the values they return, the following two procedures for

squaring a number should be indistinguishable. Each takes a numerical argument

and produces the square of that number as the value.

因此，如果只考虑它们所返回的值，下面两个用于计算一个数之平方的过程应当是无法区分的。它们都接受一个数值参数，并以该数的平方作为返回值。

So a procedure definition should be able to suppress detail. The users of the

procedure may not have written the procedure themselves, but may have obtained

it from another programmer as a black box. A user should not need to know how

the procedure is implemented in order to use it.

Subheading: Local names

因此，过程的定义应当能够隐藏其实现细节。过程的使用者可能并非自己编写了这个过程，而是从另一位程序员那里将其作为黑箱获取的。使用者不需要了解该过程的实现方式就能使用它。

小节标题：局部名字

One detail of a procedure’s implementation that should not matter to the user

of the procedure is the implementer’s choice of names for the procedure’s

formal parameters. Thus, the following procedures should not be

distinguishable:

过程实现中有一个细节对该过程的使用者来说无关紧要，那就是实现者对过程形式参数所选择的名字。因此，下面两个过程应当是无法区分的：

This principle—that the meaning of a procedure should be independent of the

parameter names used by its author—seems on the surface to be self-evident,

but its consequences are profound. The simplest consequence is that the

parameter names of a procedure must be local to the body of the procedure. For

example, we used square in the definition of good-enough? in our

square-root procedure:

这一原则——过程的含义应当与其作者所用的参数名无关——表面上似乎不言而喻，但其推论却意义深远。最直接的推论是：过程的参数名必须是该过程体的局部变量。例如，在我们的开平方过程中，我们在定义 good-enough? 时用到了 square：

The intention of the author of good-enough? is to determine if the

square of the first argument is within a given tolerance of the second

argument. We see that the author of good-enough? used the name

guess to refer to the first argument and x to refer to the second

argument. The argument of square is guess. If the author of

square used x (as above) to refer to that argument, we see that

the x in good-enough? must be a different x than the one

in square. Running the procedure square must not affect the

value of x that is used by good-enough?, because that value of

x may be needed by good-enough? after square is done

computing.

good-enough? 的作者的意图是：判断第一个参数的平方与第二个参数之差是否在给定容差范围之内。我们看到，good-enough? 的作者用名字 guess 指代第一个参数，用 x 指代第二个参数，而 square 的参数则是 guess。如果 square 的作者（如上所述）用 x 来指代那个参数，那么 good-enough? 中的 x 必定与 square 中的 x 是两个不同的 x。运行过程 square 不能影响 good-enough? 所使用的 x 的值，因为 square 计算完毕后，good-enough? 可能还需要用到那个 x 的值。

If the parameters were not local to the bodies of their respective procedures,

then the parameter x in square could be confused with the

parameter x in good-enough?, and the behavior of

good-enough? would depend upon which version of square we used.

Thus, square would not be the black box we desired.

如果参数对各自过程的体来说不是局部的，那么 square 中的参数 x 就可能与 good-enough? 中的参数 x 相混淆，good-enough? 的行为也将取决于我们所使用的是哪个版本的 square。这样，square 就不再是我们所期望的那个黑箱了。

A formal parameter of a procedure has a very special role in the procedure

definition, in that it doesn’t matter what name the formal parameter has. Such

a name is called a

bound variable, and we say that the procedure

definition

binds its formal parameters. The meaning of a procedure

definition is unchanged if a bound variable is consistently renamed throughout

the definition. If a variable is not bound, we say that it is

free.

The set of expressions for which a binding defines a name is called the

过程定义中，形式参数 (formal parameter) 具有非常特殊的地位——形式参数叫什么名字并不重要。这样的名字被称为约束变量 (bound variable)，我们说过程定义约束 (binds) 了它的形式参数。如果在定义中将某个约束变量一致地重命名，过程定义的含义不会改变。如果一个变量不是被约束的，我们就说它是自由的 (free)。绑定 (binding) 所定义的名字适用的表达式集合被称为

scope of that name. In a procedure definition, the bound variables

declared as the formal parameters of the procedure have the body of the

procedure as their scope.

该名字的作用域 (scope)。在过程定义中，被声明为形式参数的约束变量，其作用域就是该过程的体。

In the definition of good-enough? above, guess and x are

bound variables but , -, abs, and square are free.

The meaning of good-enough? should be independent of the names we choose

for guess and x so long as they are distinct and different from

, -, abs, and square. (If we renamed guess

to abs we would have introduced a bug by

capturing the

variable abs. It would have changed from free to bound.) The meaning

of good-enough? is not independent of the names of its free variables,

however. It surely depends upon the fact (external to this definition) that

the symbol abs names a procedure for computing the absolute value of a

number. Good-enough? will compute a different function if we substitute

cos for abs in its definition.

Subheading: Internal definitions and block structure

在上面的 good-enough? 定义中，guess 和 x 是约束变量，而 、-、abs 和 square 则是自由变量。good-enough? 的含义应当与我们为 guess 和 x 所选择的名字无关，只要它们互不相同，并且与 、-、abs 和 square 不同即可。（如果我们把 guess 改名为 abs，就会因为捕获 (capturing) 了变量 abs 而引入一个错误——该变量将从自由变量变成约束变量。）然而，good-enough? 的含义并不独立于其自由变量的名字。它显然依赖于一个（在此定义之外的）事实：符号 abs 命名了一个计算数的绝对值的过程。如果我们在定义中把 abs 替换为 cos，good-enough? 就会计算出一个完全不同的函数。

小节标题：内部定义与块结构

We have one kind of name isolation available to us so far: The formal

parameters of a procedure are local to the body of the procedure. The

square-root program illustrates another way in which we would like to control

the use of names. The existing program consists of separate procedures:

到目前为止，我们只有一种可用的名字隔离手段：过程的形式参数是该过程体的局部变量。开平方程序展示了另一种我们希望对名字的使用加以控制的方式。现有程序由若干独立的过程组成：

The problem with this program is that the only procedure that is important to

users of sqrt is sqrt. The other procedures (sqrt-iter,

good-enough?, and improve) only clutter up their minds. They may

not define any other procedure called good-enough? as part of another

program to work together with the square-root program, because sqrt

needs it. The problem is especially severe in the construction of large

systems by many separate programmers. For example, in the construction of a

large library of numerical procedures, many numerical functions are computed as

successive approximations and thus might have procedures named

good-enough? and improve as auxiliary procedures. We would like

to localize the subprocedures, hiding them inside sqrt so that

sqrt could coexist with other successive approximations, each having its

own private good-enough? procedure. To make this possible, we allow a

procedure to have internal definitions that are local to that procedure. For

example, in the square-root problem we can write

这个程序存在的问题是：对 sqrt 的用户来说，唯一重要的过程是 sqrt 本身，其余过程（sqrt-iter、good-enough? 和 improve）只会徒增他们的思维负担。他们可能无法在另一个与开平方程序协同工作的程序中定义任何名为 good-enough? 的过程，因为 sqrt 需要用到它。在由众多程序员分别构建的大型系统中，这一问题尤为严峻。例如，在构建一个大型数值过程库时，许多数值函数都是通过逐步逼近的方式来计算的，因此可能都有名为 good-enough? 和 improve 的辅助过程。我们希望将这些子过程局部化，把它们隐藏在 sqrt 内部，这样 sqrt 就可以与其他逐步逼近过程共存，每个过程都拥有自己私有的 good-enough? 过程。为此，我们允许一个过程拥有对该过程来说是局部的内部定义。例如，在开平方问题中，我们可以这样写：

Such nesting of definitions, called

block structure, is basically the

right solution to the simplest name-packaging problem. But there is a better

idea lurking here. In addition to internalizing the definitions of the

auxiliary procedures, we can simplify them. Since x is bound in the

definition of sqrt, the procedures good-enough?, improve,

and sqrt-iter, which are defined internally to sqrt, are in the

scope of x. Thus, it is not necessary to pass x explicitly to

each of these procedures. Instead, we allow x to be a free variable in

the internal definitions, as shown below. Then x gets its value from the

argument with which the enclosing procedure sqrt is called. This

discipline is called

lexical scoping.

这种定义的嵌套，称为块结构 (block structure)，基本上是解决最简单的名字打包问题的正确方案。但这里还潜藏着一个更好的想法。除了将辅助过程的定义内部化之外，我们还可以对它们加以简化。由于 x 在 sqrt 的定义中是被约束的，在 sqrt 内部定义的过程 good-enough?、improve 和 sqrt-iter 都处于 x 的作用域之内。因此，不必将 x 显式地传递给每一个过程。我们可以让 x 在内部定义中作为自由变量，如下所示——这样 x 的值就来自于调用外层过程 sqrt 时所传入的参数。这种规则被称为词法作用域 (lexical scoping)。

We will use block structure extensively to help us break up large

programs into tractable pieces.

The idea of block structure originated with the programming language

Algol 60. It appears in most advanced programming languages and is an

important tool for helping to organize the construction of large

programs.

我们将广泛运用块结构来帮助我们将大型程序分解为易于处理的片段。块结构的思想起源于编程语言 Algol 60，并在大多数高级程序设计语言中得到了体现，是组织构建大型程序的一个重要工具。