计算机程序的结构与解释, 第2版: 1.1

'⇡'

一种强大的编程语言不仅仅是指示计算机执行任务的手段。该语言还作为一个框架，帮助我们组织关于过程的想法。因此，当我们描述一种语言时，我们应该特别关注该语言提供的将简单想法组合成更复杂想法的手段。每种强大的语言都有三种机制来实现这一点：

• 原始表达式，表示语言所关注的最简单实体，
• 组合方式，通过它可以从简单元素构建复合元素，以及
• 抽象方式，通过它可以将复合元素命名并作为单位进行操作。

在编程中，我们处理两种元素：过程和数据。（稍后我们会发现它们实际上并不是那么不同。）非正式地说，数据是我们想要操作的“东西”，而过程是操作数据的规则的描述。因此，任何强大的编程语言都应该能够描述原始数据和原始过程，并且应该具有组合和抽象过程与数据的方法。

在本章中，我们将仅处理简单的数值数据，以便我们可以专注于构建程序的规则。4 在后面的章节中，我们将看到这些相同的规则也允许我们构建处理复合数据的程序。

开始编程的一个简单方法是检查与Lisp的Scheme方言解释器的一些典型交互。想象一下，你正坐在计算机终端前。你输入一个 表达式，解释器通过显示其 评估 该表达式的结果来回应。

你可能输入的一种原始表达式是一个数字。（更准确地说，你输入的表达式由表示十进制数字的数字符号组成。）如果你向Lisp提供一个数字

解释器将通过打印来响应5

表示数字的表达式可以与表示原始过程的表达式（例如 + 或 *）结合，形成一个复合表达式，该表达式表示将该过程应用于这些数字。例如:

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

像这样的表达式，通过在括号内限定表达式列表以表示过程应用，被称为 组合。列表中最左边的元素称为 运算符，其他元素称为 操作数。组合的值是通过将运算符指定的过程应用于作为操作数值的 参数 来获得的。

将运算符放置在操作数左侧的约定被称为 前缀表示法，起初可能会有些混淆，因为它与传统的数学约定有很大不同。然而，前缀表示法有几个优点。其中之一是它可以容纳可能接受任意数量参数的过程，如以下示例所示:

不会产生歧义，因为运算符始终是最左边的元素，整个组合由括号限定。

前缀表示法的第二个优点是，它以简单明了的方式扩展，允许组合被_嵌套_，即具有其元素本身也是组合的组合：

这样的嵌套深度和Lisp解释器可以评估的表达式的整体复杂性（原则上）没有限制。是我们人类对仍然相对简单的表达式感到困惑，例如

(+ (

• 3 (+ (
• 2 4) (+ 3 5))) (+ (

• 10 7) 6))

解释器会很容易地将其评估为57。我们可以通过将这样的表达式写成以下形式来帮助自己

(+ (

• 3 (+ (
• 2 4) (+ 3 5))) (+ (

• 10 7) 6))

遵循一种称为 pretty-printing 的格式化约定，其中每个长组合的操作数垂直对齐。由此产生的缩进清晰地显示了表达式的结构。6

即使是复杂的表达式，解释器始终在相同的基本循环中运行：它从终端读取一个表达式，评估该表达式，并打印结果。这种操作模式通常用“解释器在 读-评-打印循环 中运行”来表达。特别要注意的是，不需要明确指示解释器打印表达式的值。7

编程语言的一个关键方面是它提供的使用名称来引用计算对象的方式。我们说这个名称标识一个 变量 ，其 值 是该对象。

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

导致解释器将值 2 与名称 size 关联。8 一旦名称 size 与数字 2 关联，我们就可以通过名称引用值 2:

以下是 define 使用的更多示例：

(定义 pi 3.14159) (定义 radius 10) (* pi (* radius radius)) 314.159 (定义 circumference (* 2 pi radius)) circumference 62.8318

Define 是我们语言中最简单的抽象手段，因为它允许我们使用简单的名称来指代复合操作的结果，例如上面计算的 circumference。一般来说，计算对象可能具有非常复杂的结构，每次我们想使用它们时，记住并重复它们的细节将极为不便。实际上，复杂程序是通过逐步构建越来越复杂的计算对象而构成的。解释器使这种逐步程序构建特别方便，因为名称-对象关联可以在连续的交互中逐步创建。这个特性鼓励程序的增量开发和测试，并在很大程度上解释了 Lisp 程序通常由大量相对简单的过程组成的事实。

显然，将值与符号关联并随后检索它们的可能性意味着解释器必须维护某种内存，以跟踪名称-对象对。这种内存称为 环境（更准确地说是 全局环境，因为我们稍后会看到，一个计算可能涉及多个不同的环境）。9

本章的目标之一是孤立出关于程序性思维的问题。作为一个例子，让我们考虑在评估组合时，解释器本身也在遵循一个程序。

评估组合，请执行以下操作：

1. 评估组合的子表达式。
2. 将最左边子表达式的值（操作符）所对应的过程应用于其他子表达式的值（操作数）。

即使这个简单的规则也说明了关于过程的一些重要观点。首先，注意到第一步规定，为了完成组合的评估过程，我们必须首先对组合的每个元素执行评估过程。因此，评估规则本质上是_递归_的；也就是说，它包括作为其步骤之一的调用规则本身的需要。10

注意到递归的概念是多么简洁地用于表达在深度嵌套组合的情况下，否则会被视为相当复杂的过程。例如，评估

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

要求将评估规则应用于四种不同的组合。我们可以通过将组合表示为树的形式来获得这个过程的图像，如图 1.1所示。每个组合由一个节点表示，分支对应于从该节点派生的运算符和操作数。终端节点（即没有分支的节点）表示运算符或数字。从树的角度看评估，我们可以想象操作数的值从终端节点向上渗透，然后在更高的层次上结合。一般来说，我们将看到递归是一种处理层次结构、树状对象的非常强大的技术。事实上，“向上渗透值”的评估规则形式是一个被称为_树积累_的通用过程的例子。

图 1.1: 树形表示，显示每个子组合的值。

接下来，注意到第一步的重复应用使我们到达了一个需要评估的点，这里我们需要评估的不是组合，而是原始表达式，例如数字、内置运算符或其他名称。我们通过规定来处理原始情况，

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

我们可以将第二条规则视为第三条规则的一个特例，规定像 + 和 * 这样的符号也包含在全局环境中，并与其“值”的机器指令序列相关联。需要注意的关键点是环境在确定表达式中符号的含义方面的作用。在像 Lisp 这样的交互式语言中，谈论表达式的值，例如 (+ x 1)，而不指定任何关于环境的信息以提供符号 x（甚至符号 +）的含义，是没有意义的。正如我们将在 Chapter 3 中看到的，环境作为提供评估发生的上下文的一般概念将在我们理解程序执行中发挥重要作用。

注意，上述给出的评估规则不处理定义。例如，评估 (define x 3) 并不将 define 应用到两个参数上，其中一个是符号 x 的值，另一个是 3，因为 define 的目的正是将 x 与一个值关联起来。（也就是说，(define x 3) 不是一个组合。）

这样的对一般评估规则的例外被称为 特殊形式。Define 是我们迄今为止见过的唯一一个特殊形式的例子，但我们很快会遇到其他的。每个特殊形式都有其自己的评估规则。各种类型的表达式（每个都有其相关的评估规则）构成了编程语言的语法。与大多数其他编程语言相比，Lisp 具有非常简单的语法；也就是说，表达式的评估规则可以通过一个简单的一般规则以及少数特殊形式的专门规则来描述。11

我们在Lisp中识别出任何强大编程语言中必须出现的一些元素：

• 数字和算术运算是原始数据和过程。
• 组合的嵌套提供了一种组合操作的方法。
• 将名称与值关联的定义提供了一种有限的抽象手段。

现在我们将学习 过程定义，这是一种更强大的抽象技术，通过它可以给复合操作命名，然后作为一个单位进行引用。

我们首先来探讨如何表达“平方”的概念。我们可以说：“要平方某个数，将其乘以自身。”这在我们的语言中表达为

(定义 (平方 x) (* x x))

我们可以这样理解：

(define (square x) ( x x)) | | | | | | 要平方某个东西，将其乘以自身。

我们这里有一个 复合过程，它被命名为 square。这个过程表示将某物与其自身相乘的操作。要被相乘的东西被赋予一个局部名称 x，它在这里扮演着类似于自然语言中代词的角色。评估定义会创建这个复合过程，并将其与名称 square 关联。12

过程定义的一般形式是

(定义 (⟨名称⟩ ⟨形式参数⟩) ⟨主体⟩)

⟨名称⟩是与环境中的过程定义相关联的符号。13 ⟨形式参数⟩是在过程主体中用于引用相应过程参数的名称。⟨主体⟩是一个表达式，当形式参数被实际应用于过程的实际参数替换时，将产生过程应用的值。14 ⟨名称⟩和⟨形式参数⟩被括在括号内，就像在对被定义的过程的实际调用中一样。

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

(平方 21) 441 (平方 (+ 2 5)) 49 (平方 (平方 3)) 81

我们还可以将 square 作为构建其他过程的基础。例如，x 2 + y 2 可以表示为

(+ (平方 x) (平方 y))

我们可以很容易地定义一个过程 sum-of-squares，它接受任意两个数字作为参数，产生它们平方的和：

(定义 (平方和 x y) (+ (平方 x) (平方 y))) (平方和 3 4) 25

现在我们可以将 sum-of-squares 作为构建进一步程序的基础模块：

(定义 (f a) (平方和 (+ a 1) (

• a 2))) (f 5) 136

复合过程的使用方式与原始过程完全相同。实际上，仅通过查看上面给出的sum-of-squares的定义，无法判断square是像+和*那样内置于解释器中，还是定义为复合过程。

要评估一个操作符名称为复合过程的组合，解释器遵循与我们在 1.1.3 中描述的操作符名称为原始过程的组合几乎相同的过程。也就是说，解释器评估组合的元素，并将过程（即组合操作符的值）应用于参数（即组合操作数的值）。

我们可以假设将原始过程应用于参数的机制是内置于解释器中的。对于复合过程，应用过程如下：

将复合过程应用于参数时，用相应的参数替换每个形式参数，评估过程的主体。

为了说明这个过程，让我们评估组合

其中 f 是在 1.1.4 中定义的过程。我们首先检索 f 的主体:

(平方和 (+ a 1) (

• a 2))

然后我们用参数 5 替换形式参数 a:

(平方和 (+ 5 1) (

• 5 2))

因此，问题简化为对两个操作数和一个运算符 sum-of-squares 的组合进行评估。评估这个组合涉及三个子问题。我们必须评估运算符以获取要应用的过程，并且我们必须评估操作数以获取参数。现在 (+ 5 1) 产生 6，而 (* 5 2) 产生 10，因此我们必须将 sum-of-squares 过程应用于 6 和 10。这些值被替换为 sum-of-squares 主体中的形式参数 x 和 y，将表达式简化为

(+ (平方 6) (平方 10))

如果我们使用 square 的定义，这将简化为

通过乘法减少为

最后到

我们刚刚描述的过程称为_替代模型_，用于过程应用。它可以被视为一个模型，确定过程应用的“意义”，就本章所涉及的过程而言。然而，有两点需要强调：

• 替换的目的是帮助我们思考过程应用，而不是提供解释器实际工作的描述。典型的解释器并不是通过操纵过程的文本来替换形式参数的值来评估过程应用。在实践中，“替换”是通过为形式参数使用局部环境来实现的。我们将在第3章和第4章中更全面地讨论这一点，当我们详细检查解释器的实现时。
• 在本书的过程中，我们将呈现一系列越来越复杂的解释器工作模型，最终在第5章中给出一个完整的解释器和编译器的实现。替换模型只是这些模型中的第一个——一种开始正式思考评估过程的方法。一般来说，在科学和工程中建模现象时，我们从简化、不完整的模型开始。当我们更详细地检查事物时，这些简单模型变得不够，必须被更精细的模型所取代。替换模型也不例外。特别是，当我们在第3章中讨论使用“可变数据”的过程时，我们将看到替换模型崩溃，必须被更复杂的过程应用模型所取代。15

根据在 1.1.3 中给出的评估描述，解释器首先评估操作符和操作数，然后将结果程序应用于结果参数。这并不是执行评估的唯一方法。另一种评估模型是在需要操作数的值之前不进行评估。相反，它会首先将操作数表达式替换为参数，直到获得仅涉及原始操作符的表达式，然后再进行评估。如果我们使用这种方法，(f 5) 的评估将按照扩展的顺序进行。

(平方和 (+ 5 1) (

• 5 2)) (+ (平方 (+ 5 1)) (平方 (
• 5 2))) (+ (
• (+ 5 1) (+ 5 1)) (
• (
• 5 2) (
• 5 2)))}

随后是减少

(+ (

• 6 6) (
• 10 10)) (+ 36 100) 136

这给出了与我们之前的评估模型相同的答案，但过程是不同的。特别是，(+ 5 1) 和 (* 5 2) 的评估在这里各执行了两次，分别对应于将表达式 (* x x) 中的 x 替换为 (+ 5 1) 和 (* 5 2) 的简化过程。

这种替代的“完全展开然后缩减”评估方法被称为 正常顺序评估，与解释器实际使用的“评估参数然后应用”方法相对，该方法称为 应用顺序评估。可以证明，对于可以使用替换建模的过程应用（包括本书前两章中的所有过程）并且产生合法值的情况，正常顺序和应用顺序评估产生相同的值。（参见 练习 1.5 以获取一个“非法”值的实例，其中正常顺序和应用顺序评估未给出相同的结果。）

Lisp 使用应用顺序求值，部分原因是通过避免对如 (+ 5 1) 和 (* 5 2) 这样的表达式进行多次求值而获得的额外效率，更重要的是，当我们离开可以通过替换建模的过程领域时，正常顺序求值变得更加复杂。另一方面，正常顺序求值可以是一个极其有价值的工具，我们将在第 3 章和第 4 章中探讨它的一些影响。16

我们在这一点上可以定义的过程类的表达能力非常有限，因为我们没有办法进行测试并根据测试结果执行不同的操作。例如，我们无法定义一个通过测试一个数字是正数、负数还是零来计算绝对值的过程，并根据规则 | x | = { x 如果 x > 0 , 0 如果 x = 0 , − x 如果 x < 0 在不同情况下采取不同的行动。这个构造被称为 case analysis，在 Lisp 中有一种特殊的形式用于表示这样的 case analysis。它被称为 cond（代表“条件”），用法如下:

(定义 (绝对值 x) (条件 ((> x 0) x) ((= x 0) 0) ((< x 0) (- x))))

条件表达式的一般形式是

(cond (⟨p₁⟩ ⟨e₁⟩) (⟨p₂⟩ ⟨e₂⟩) … (⟨pₙ⟩ ⟨eₙ⟩))

由符号 cond 及其后带有括号的表达式对组成

称为 clauses。每对中的第一个表达式是 predicate——即一个其值被解释为真或假的表达式。17

条件表达式的评估如下。首先评估谓词 ⟨ p 1 ⟩。如果其值为假，则评估 ⟨ p 2 ⟩。如果 ⟨ p 2 ⟩ 的值也为假，则评估 ⟨ p 3 ⟩。这个过程持续进行，直到找到一个值为真的谓词，在这种情况下，解释器返回该子句对应的 结果表达式 ⟨ e ⟩ 的值作为条件表达式的值。如果没有找到任何值为真的 ⟨ p ⟩，则 cond 的值是未定义的。

单词 predicate 用于返回真或假的过程，以及评估为真或假的表达式。绝对值过程 abs 使用了原始谓词 >、< 和 =。18 这些谓词接受两个数字作为参数，并测试第一个数字是否分别大于、小于或等于第二个数字，返回相应的真或假。

另一种写绝对值过程的方法是

(定义 (绝对值 x) (条件 ((< x 0) (- x)) (其他 x)))

可以用英语表达为 “如果 x 小于零则返回 − x ; 否则返回 x .” Else 是一个特殊符号，可以在 cond 的最后一个子句中替代 ⟨ p ⟩。这使得 cond 在所有先前的子句都被跳过时返回相应的 ⟨ e ⟩ 的值。实际上，任何始终评估为真值的表达式都可以在这里用作 ⟨ p ⟩。

这里还有另一种编写绝对值过程的方法：

(定义 (绝对值 x) (如果 (< x 0) (- x) x))

这使用了特殊形式 if，一种限制类型的条件语句，当在案例分析中恰好有两种情况时可以使用。if 表达式的一般形式是

(如果 ⟨谓词⟩ ⟨结果⟩ ⟨替代⟩)

要评估一个 if 表达式，解释器首先评估表达式的 ⟨谓词⟩ 部分。如果 ⟨谓词⟩ 评估为真值，解释器接着评估 ⟨结果⟩ 并返回其值。否则，它评估 ⟨替代⟩ 并返回其值。19

除了原始谓词如 <、= 和 > 之外，还有逻辑组合操作，这使我们能够构造复合谓词。最常用的三种是：

• `(和 ⟨e₁⟩

…

⟨eₙ⟩)`

解释器按从左到右的顺序逐个评估表达式 ⟨e⟩。如果任何 ⟨e⟩ 的值为假，则 and 表达式的值为假，其余的 ⟨e⟩ 不会被评估。如果所有 ⟨e⟩ 的值都为真，则 and 表达式的值为最后一个的值。

• `(或 ⟨e₁⟩

…

⟨eₙ⟩)`

解释器按从左到右的顺序逐个评估表达式 ⟨e⟩。如果任何 ⟨e⟩ 评估为真值，则该值作为 or 表达式的值返回，其余的 ⟨e⟩ 不再评估。如果所有 ⟨e⟩ 评估为假，则 or 表达式的值为假。

• (不是 ⟨e⟩)

not 表达式的值在表达式 ⟨e⟩ 计算为假时为真，否则为假。

注意到 and 和 or 是特殊形式，而不是过程，因为子表达式不一定全部被求值。Not 是一个普通的过程。

作为这些如何使用的一个例子，数字 x 在范围 5 < x < 10 的条件可以表示为

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

(定义 (">= x y) (或 ("> x y) (\

或作为

(定义 (">= x y) (不 (< x y)))

练习 1.1: 以下是一系列表达式。解释器对每个表达式的响应结果是什么？假设该序列按呈现的顺序进行评估。

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: 将以下表达式翻译成前缀形式： 5 + 4 + ( 2 − ( 3 − ( 6 + 4 5 ) ) ) 3 ( 6 − 2 ) ( 2 − 7 ) .

练习 1.3: 定义一个过程，该过程接受三个数字作为参数，并返回两个较大数字的平方和。

练习 1.4: 注意到我们的评估模型允许操作符为复合表达式的组合。利用这一观察来描述以下过程的行为：

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

练习 1.5: Ben Bitdiddle 发明了一种测试，以确定他所面对的解释器是使用应用顺序求值还是正常顺序求值。他定义了以下两个过程：

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

然后他评估表达式

使用应用顺序求值的解释器，Ben 会观察到什么行为？使用正常顺序求值的解释器，他会观察到什么行为？请解释你的答案。（假设特殊形式 if 的求值规则无论解释器使用正常还是应用顺序都是相同的：谓词表达式首先被求值，结果决定是否求值结果或替代表达式。）

如上所述，过程很像普通的数学函数。它们指定一个由一个或多个参数决定的值。但数学函数和计算机过程之间有一个重要的区别。过程必须是有效的。

作为一个例子，考虑计算平方根的问题。我们可以将平方根函数定义为 x = y，使得 y ≥ 0 且 y² = x。这描述了一个完全合法的数学函数。我们可以用它来识别一个数字是否是另一个数字的平方根，或者推导关于平方根的一般事实。另一方面，这一定义并没有描述一个过程。实际上，它几乎没有告诉我们如何实际找到给定数字的平方根。将这个定义用伪Lisp重新表述也无济于事：

这只会引发问题。

函数和过程之间的对比反映了描述事物属性与描述如何做事之间的一般区别，或者有时称之为声明性知识与命令性知识之间的区别。在数学中，我们通常关注声明性（是什么）描述，而在计算机科学中，我们通常关注命令性（如何做）描述。20

如何计算平方根？最常见的方法是使用牛顿的逐次逼近法，它表示每当我们对一个数字 x 的平方根值有一个猜测 y 时，我们可以通过将 y 与 x / y 平均来进行简单的操作，以获得一个更好的猜测（更接近实际平方根）。21 例如，我们可以如下计算 2 的平方根。假设我们的初始猜测是 1:

猜测 商 平均值

1 (2/1) = 2 ((2 + 1)/2) = 1.5

1.5 (2/1.5) ((1.3333 + 1.5)/2) = 1.3333 = 1.4167

1.4167 (2/1.4167) ((1.4167 + 1.4118)/2) = 1.4118 = 1.4142

1.4142 ... ...

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

现在让我们将这个过程形式化为程序。我们从一个被开方数的值（我们试图计算其平方根的数字）和一个猜测值开始。如果这个猜测对我们的目的足够好，我们就完成了；如果不够好，我们必须用一个改进的猜测重复这个过程。我们将这个基本策略写成一个程序：

(定义 (sqrt-iter 猜测 x) (如果 (足够好? 猜测 x) 猜测 (sqrt-iter (改进 猜测 x) x))

通过将猜测与被开方数和旧猜测的商进行平均，可以改善猜测：

(定义 (改进 猜测 x) (平均 猜测 (/ x 猜测)))

哪里

(定义 (平均 x y) (/ (+ x y) 2))

我们还必须说明我们所说的“足够好”是什么意思。以下内容可以用作说明，但实际上这并不是一个很好的测试。(见 练习 1.7。) 这个想法是改进答案，直到它足够接近，以至于它的平方与被开方数的差异小于预定的容差（这里是 0.001）：22

(定义 (足够好吗? 猜测 x) (< (绝对值 ( (平方 猜测) x)) 0.001))

最后，我们需要一个开始的方法。例如，我们总是可以猜测任何数字的平方根是 1:23

(定义 (平方根 x) (平方根-迭代 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

sqrt 程序还说明了我们迄今为止介绍的简单过程语言足以编写任何纯数值程序，这些程序在 C 或 Pascal 中也可以编写。这可能看起来令人惊讶，因为我们在语言中没有包含任何指示计算机重复执行某些操作的迭代（循环）结构。另一方面，Sqrt-iter 演示了如何仅使用调用过程的普通能力来实现迭代。 24

练习 1.6: Alyssa P. Hacker 不明白为什么 if 需要作为一种特殊形式提供。她问：“我为什么不能仅仅将其定义为一个普通的程序，基于 cond？”Alyssa 的朋友 Eva Lu Ator 声称这确实可以做到，并且她定义了一个新的 if 版本：

(define (new-if predicate then-clause else-clause) (cond (predicate then-clause) (else else-clause)))

Eva 向 Alyssa 演示了这个程序：

(new-if ( = 2 3) 0 5) 5 (new-if ( = 1 1) 0 5) 0

高兴的 Alyssa 使用 new-if 重写了平方根程序：

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

当 Alyssa 尝试使用这个来计算平方根时会发生什么？解释。

练习 1.7: 用于计算平方根的 good-enough? 测试对于寻找非常小的数字的平方根效果不佳。此外，在真实的计算机中，算术运算几乎总是以有限的精度进行。这使得我们的测试对于非常大的数字也不够充分。解释这些陈述，并举例说明测试如何在小数字和大数字上失败。实现 good-enough? 的另一种策略是观察 guess 从一个迭代到下一个迭代的变化，并在变化是猜测的一个非常小的分数时停止。设计一个使用这种结束测试的平方根程序。这对于小数字和大数字的效果更好吗？

练习 1.8: 牛顿法求立方根的基础在于，如果 y 是 x 的立方根的近似值，那么更好的近似值由值 x / y ² + 2 y ³ 给出。使用这个公式实现一个类似于平方根程序的立方根程序。（在 1.3.4 中，我们将看到如何将牛顿法作为这些平方根和立方根程序的抽象进行实现。）

Sqrt 是我们第一个通过一组相互定义的过程来定义的过程的例子。注意，sqrt-iter 的定义是 递归的；也就是说，该过程是通过自身来定义的。能够通过自身定义一个过程的想法可能令人不安；这样的“循环”定义似乎不清楚如何能够有意义，更不用说指定一个由计算机执行的明确定义的过程了。这将在 1.2 中更仔细地讨论。但首先，让我们考虑一些通过 sqrt 示例所说明的其他重要点。

注意到计算平方根的问题自然分解为多个子问题：如何判断一个猜测是否足够好，如何改进一个猜测，等等。每个任务都是通过一个单独的过程来完成的。整个 sqrt 程序可以被视为一组过程的集合（如 图 1.2 所示），它反映了将问题分解为子问题的过程。

图 1.2: sqrt 程序的过程分解。

这种分解策略的重要性不仅在于将程序划分为多个部分。毕竟，我们可以将任何大型程序分成几个部分——前十行，接下来的十行，再接下来的十行，等等。更重要的是，每个过程都必须完成一个可识别的任务，这个任务可以作为定义其他过程的模块。例如，当我们根据square定义good-enough?过程时，我们能够将square过程视为一个“黑箱”。在那一刻，我们并不关心_如何_计算结果，只关心它计算平方这一事实。平方的计算细节可以被压制，留待以后考虑。实际上，就good-enough?过程而言，square并不完全是一个过程，而是一个过程的抽象，所谓的_过程抽象_。在这个抽象层次上，任何计算平方的过程都是同样有效的。

因此，仅考虑它们返回的值，以下两种平方数的过程应该是不可区分的。每个过程都接受一个数值参数，并将该数字的平方作为值。25

(定义 (平方 x) (* x x)) (定义 (平方 x) (exp (双倍 (log x)))) (定义 (双倍 x) (+ x x))

因此，过程定义应该能够抑制细节。过程的用户可能并没有自己编写该过程，而是可能从其他程序员那里以黑箱的形式获得它。用户在使用该过程时不需要知道它是如何实现的。

程序实现的一个细节，用户不应该关心的是实现者为程序的形式参数选择的名称。因此，以下程序不应可区分:

(定义 (平方 x) (* x x)) (定义 (平方 y) (* y y))

这个原则——一个过程的意义应该独立于其作者使用的参数名称——表面上看似显而易见，但其后果却是深远的。最简单的后果是，一个过程的参数名称必须局限于该过程的主体。例如，我们在平方根过程的 good-enough? 定义中使用了 square：

(定义 (足够好吗? 猜测 x) (< (绝对值 ( (平方 猜测) x)) 0.001))

good-enough? 的作者意图是确定第一个参数的平方是否在第二个参数的给定容差范围内。我们看到 good-enough? 的作者使用了名称 guess 来指代第一个参数，使用 x 来指代第二个参数。square 的参数是 guess。如果 square 的作者使用 x（如上所述）来指代该参数，我们看到 good-enough? 中的 x 必须与 square 中的 x 不同。运行过程 square 不能影响 good-enough? 使用的 x 的值，因为在 square 完成计算后，good-enough? 可能需要该值的 x。

如果参数不局限于各自过程的主体，那么 square 中的参数 x 可能会与 good-enough? 中的参数 x 混淆，并且 good-enough? 的行为将取决于我们使用的是哪个版本的 square。因此，square 将不是我们所期望的黑箱。

过程的形式参数在过程定义中具有非常特殊的角色，因为形式参数的名称并不重要。这样的名称被称为 绑定变量，我们说过程定义 绑定 其形式参数。如果在整个定义中一致地重命名一个绑定变量，过程定义的含义不会改变。26 如果一个变量没有被绑定，我们称之为 自由。绑定定义名称的表达式集合称为该名称的 范围。在过程定义中，作为过程的形式参数声明的绑定变量的范围是过程的主体。

在上面的 good-enough? 的定义中，guess 和 x 是绑定变量，但 <、-、abs 和 square 是自由变量。good-enough? 的含义应该独立于我们为 guess 和 x 选择的名称，只要它们是不同的，并且与 <、-、abs 和 square 不同。（如果我们将 guess 重命名为 abs，我们就会通过 捕获 变量 abs 引入一个错误。它将从自由变量变为绑定变量。）然而，good-enough? 的含义并不独立于其自由变量的名称。它确实依赖于一个事实（与此定义无关），即符号 abs 命名了一个计算数字绝对值的过程。如果我们在其定义中将 abs 替换为 cos，Good-enough? 将计算一个不同的函数。

到目前为止，我们有一种名称隔离可用：过程的形式参数在过程体内是局部的。平方根程序说明了我们希望控制名称使用的另一种方式。现有程序由独立的过程组成：

(定义 (平方根 x) (平方根-迭代 1.0 x)) (定义 (平方根-迭代 猜测 x) (如果 (足够好? 猜测 x) 猜测 (平方根-迭代 (改进 猜测 x) x))) (定义 (足够好? 猜测 x) (< (绝对值 ( (平方 猜测) x)) 0.001)) (定义 (改进 猜测 x) (平均 猜测 (/ x 猜测))

这个程序的问题在于，用户使用 sqrt 时唯一重要的过程是 sqrt。其他过程（sqrt-iter、good-enough? 和 improve）只会让他们的思维变得混乱。他们可能不会在另一个程序中定义任何其他名为 good-enough? 的过程，以便与平方根程序一起工作，因为 sqrt 需要它。这个问题在许多独立程序员构建大型系统时尤其严重。例如，在构建一个大型数值过程库时，许多数值函数作为连续近似计算，因此可能会有名为 good-enough? 和 improve 的过程作为辅助过程。我们希望将子过程局部化，将它们隐藏在 sqrt 内部，以便 sqrt 可以与其他连续近似共存，每个都有自己私有的 good-enough? 过程。为了实现这一点，我们允许一个过程具有对该过程局部的内部定义。例如，在平方根问题中，我们可以写

(定义 (平方根 x) (定义 (足够好? 猜测 x) (< (绝对值 ( (平方 猜测) x)) 0.001)) (定义 (改进 猜测 x) (平均 猜测 (/ x 猜测))) (定义 (平方根-迭代 猜测 x) (如果 (足够好? 猜测 x) 猜测 (平方根-迭代 (改进 猜测 x) x))) (平方根-迭代 1.0 x))

这种定义的嵌套，称为 块结构，基本上是解决最简单名称包装问题的正确方案。但这里潜藏着一个更好的想法。除了将辅助过程的定义内部化，我们还可以简化它们。由于 x 在 sqrt 的定义中被绑定，因此在 sqrt 内部定义的过程 good-enough?、improve 和 sqrt-iter 都在 x 的作用域内。因此，不必将 x 显式传递给这些过程中的每一个。相反，我们允许 x 在内部定义中作为自由变量，如下所示。然后，x 从调用封闭过程 sqrt 时传入的参数中获取其值。这种规则称为 词法作用域。27

(定义 (平方根 x) (定义 (足够好? 猜测) (< (绝对值 ( (平方 猜测) x)) 0.001)) (定义 (改进 猜测) (平均 猜测 (/ x 猜测))) (定义 (平方根-迭代 猜测) (如果 (足够好? 猜测) 猜测 (平方根-迭代 (改进 猜测)))) (平方根-迭代 1.0))

我们将广泛使用块结构来帮助我们将大型程序分解为可处理的部分。28 块结构的概念源于编程语言Algol 60。它出现在大多数高级编程语言中，是帮助组织大型程序构建的重要工具。