计算机科学丛书
点击查看第二章
计算机程序的构造和解释（原书第2版）典藏版
Structure and Interpretation of Computer Programs，Second Edition

哈罗德阿贝尔森（Harold Abelson）
[美] 杰拉尔德杰伊萨斯曼（Gerald Jay Sussman） 著
朱莉萨斯曼（Julie Sussman）
裘宗燕 译

第1章 构造过程抽象

心智的活动，除了尽力产生各种简单的认识之外，主要表现在如下三个方面：1）将若干简单认识组合为一个复合认识，由此产生出各种复杂的认识。2）将两个认识放在一起对照，不管它们如何简单或者复杂，在这样做时并不将它们合而为一。由此得到有关它们的相互关系的认识。3）将有关认识与那些在实际中和它们同在的所有其他认识隔离开，这就是抽象，所有具有普遍性的认识都是这样得到的。
John Locke, An Essay Concerning Human Vnderstanding
（有关人类理解的随笔，1690）

我们准备学习的是有关计算过程的知识。计算过程是存在于计算机里的一类抽象事物，在其演化进程中，这些过程会去操作一些被称为数据的抽象事物。人们创建出一些称为程序的规则模式，以指导这类过程的进行。从作用上看，就像是我们在通过自己的写作魔力去控制计算机里的精灵似的。
一个计算过程确实很像一种神灵的巫术，它看不见也摸不到，根本就不是由物质组成的。然而它却又是非常真实的，可以完成某些智力性的工作。它可以回答提问，可以通过在银行里支付现金或者在工厂里操纵机器人等等方式影响这个世界。我们用于指挥这种过程的程序就像是巫师的咒语，它们是用一些诡秘而深奥的程序设计语言，通过符号表达式的形式精心编排而成，它们描述了我们希望相应的计算过程去完成的工作。
在正常工作的计算机里，一个计算过程将精密而准确地执行相应的程序。这样，初学程序设计的人们就像巫师的徒弟们那样，必须学习如何去理解和预期他们所发出的咒语的效果。程序里即使有一点小错误（常常被称为程序错误（bug）或者故障（glitch）），也可能产生复杂而无法预料的后果。
幸运的是，学习程序的危险性远远小于学习巫术，因为我们要去控制的神灵以一种很安全的方式被约束着。而真实的程序设计则需要极度细心，需要经验和智慧。例如，在一个计算机辅助设计系统里的一点小毛病，就可能导致一架飞机或者一座水坝的灾难性损毁，或者一个工业机器人的自我破坏。
软件工程大师们能组织好自己的程序，使自己能合理地确信这些程序所产生的计算过程将能完成预期的工作。他们可以事先看到自己系统的行为方式，知道如何去构造这些程序，使其中出现的意外问题不会导致灾难性的后果。而且，在发生了这种问题时，他们也能排除程序中的错误。设计良好的计算系统就像设计良好的汽车或者核反应堆一样，具有某种模块化的设计，其中的各个部分都可以独立地构造、替换、排除错误。
用Lisp编程
为了描述这类计算过程，我们需要有一种适用的语言。我们将为此使用程序设计语言Lisp。正如人们每天用自然语言（如英语、法语或日语等）表述自己的想法，用数学形式的记法描述定量的现象一样，我们将要用Lisp表述过程性的思想。Lisp是20世纪50年代后期发明的一种记法形式，是为了能对某种特定形式的逻辑表达式（称为递归方程）的使用做推理。递归方程可以作为计算的模型。这一语言是由John McCarthy设计的，基于他的论文“Recursive Functions of Symbolic Expressions and Their Computation by Machine”（符号表达式的递归函数及其机械计算，McCarthy 1960）。
虽然在开始时，McCarthy是想以Lisp作为一种数学记述形式，但它确实是一种实用的程序设计语言。一个Lisp解释器就像是一台机器，它能实现用Lisp语言描述的计算过程。第一个Lisp解释器是McCarthy在MIT电子研究实验室的人工智能组和MIT计算中心里他的同事和学生的帮助下实现的1。Lisp的名字来自表处理（LISt Processing），其设计是为了提供符号计算的能力，以便能用于解决一些程序设计问题，例如代数表达式的符号微分和积分。它包含了适用于这类目的的一些新数据对象，称为原子和表，这是它与那一时代的所有其他语言之间最明显的不同之处。
Lisp并不是一个刻意的设计努力的结果，它以一种试验性的非正式的方式不断演化，以满足用户的需要和实际实现的各种考虑。Lisp的这种非官方演化持续了许多年，Lisp用户社团具有抵制制定这一语言的“官方”定义企图的传统。这种演化方式以及语言初始概念的灵活和优美，使得Lisp成为今天还在广泛使用的历史第二悠久的语言（只有Fortran比它更老）。这一语言还在不断调整，以便去包容有关程序设计的最新思想。正因为这样，今天的Lisp已经形成了一族方言，它们共享着初始语言的大部分特征，也可能有这样或那样的重要差异。用于本书的Lisp方言名为Scheme2。
由于Lisp的试验性质以及强调符号操作的特点，开始时的这个语言对于数值计算而言是很低效的，至少与Fortran比较时是这样。经过这么多年的发展，人们已经开发出了Lisp编译器，它们可以将程序翻译为机器代码，这样的代码能相当高效地完成各种数值计算。Lisp已经可以非常有效地用于一些特殊的应用领域3。虽然Lisp还没有完全战胜有关它特别低效的诋毁，但它现在已被用于许多性能并不是最重要考虑因素的应用领域。例如，Lisp已经成为操作系统外壳语言的一种选择，作为编辑器和计算机辅助设计系统的扩充语言等等。
既然Lisp并不是一种主流语言，我们为什么要用它作为讨论程序设计的基础呢？这是因为，这一语言具有许多独有的特征，这些特征使它成为研究重要程序的设计、构造，以及各种数据结构，并将其关联于支持它们的语言特征的一种极佳媒介。这些特征之中最重要的就是：计算过程的Lisp描述（称为过程）本身又可以作为Lisp的数据来表示和操作。这一事实的重要性在于，现存的许多威力强大的程序设计技术，都依赖于填平在“被动的”数据和“主动的”过程之间的传统划分。正如我们将要看到的，Lisp可以将过程作为数据进行处理的灵活性，使它成为探索这些技术的最方便的现存语言之一。能将过程表示为数据的能力，也使Lisp成为编写那些必须将其他程序当作数据去操作的程序的最佳语言，例如支持计算机语言的解释器和编译器。除了这些考虑之外，用Lisp编程本身也是极其有趣的。

1.1 程序设计的基本元素

一个强有力的程序设计语言，不仅是一种指挥计算机执行任务的方式，它还应该成为一种框架，使我们能够在其中组织自己有关计算过程的思想。这样，当我们描述一个语言时，就需要将注意力特别放在这一语言所提供的，能够将简单的认识组合起来形成更复杂认识的方法方面。每一种强有力的语言都为此提供了三种机制：

• 基本表达形式，用于表示语言所关心的最简单的个体。
• 组合的方法，通过它们可以从较简单的东西出发构造出复合的元素。
• 抽象的方法，通过它们可以为复合对象命名，并将它们当作单元去操作。

在程序设计中，我们需要处理两类要素：过程和数据（以后读者将会发现，它们实际上并不是这样严格分离的）。非形式地说，数据是一种我们希望去操作的“东西”，而过程就是有关操作这些数据的规则的描述。这样，任何强有力的程序设计语言都必须能表述基本的数据和基本的过程，还需要提供对过程和数据进行组合和抽象的方法。
本章只处理简单的数值数据，这就使我们可以把注意力集中到过程构造的规则方面4。在随后几章里我们将会看到，用于构造过程的这些规则同样也可以用于操作各种数据。

1.1.1 表达式

开始做程序设计，最简单方式就是去观看一些与Lisp方言Scheme解释器交互的典型实例。设想你坐在一台计算机的终端前，用键盘输入了一个表达式，解释器的响应就是将它对这一表达式的求值结果显示出来。
你可以键入的一种基本表达式就是数（更准确地说，你键入的是由数字组成的表达式，它表示的是以10作为基数的数）。如果你给Lisp一个数
486
解释器的响应是打印出
486
可以用表示基本过程的表达形式（例如＋或者 *），将表示数的表达式组合起来，形成复合表达式，以表示求要把有关过程应用于这些数。例如：

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

像上面这样的表达式称为组合式，其构成方式就是用一对括号括起一些表达式，形成一个表，用于表示一个过程应用。在表里最左的元素称为运算符，其他元素都称为运算对象。要得到这种组合式的值，采用的方式就是将由运算符所刻画的过程应用于有关的实际参数，而所谓实际参数也就是那些运算对象的值。
将运算符放在所有运算对象左边，这种形式称为前缀表示。刚开始看到这种表示时会感到有些不习惯，因为它与常规数学表示差别很大。然而前缀表示也有一些优点，其中之一就是它完全适用于可能带有任意个实参的过程，例如在下面实例中的情况：

(+ 21 35 12 7)
75
(* 25 4 12)
1200

在这里不会出现歧义，因为运算符总是最左边的元素，而整个表达式的范围也由括号界定。
前缀表示的第二个优点是它可以直接扩充，允许出现组合式嵌套的情况，也就是说，允许组合式的元素本身又是组合式：

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

原则上讲，对于这种嵌套的深度，以及Lisp解释器可以求值的表达式的整体复杂性，都没有任何限制。倒是我们自己有可能被一些并不很复杂的表达式搞糊涂，例如：

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

对于这个表达式，解释器可以马上求值出57。将上述表达式写成下面的形式有助于阅读：

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

这就是遵循一种称为美观打印的格式规则。按照这种规则，在写一个很长的组合式时，我们令其中的各个运算对象垂直对齐。这样缩格排列的结果能很好地显示出表达式的结构。
即使对于非常复杂的表达式，解释器也总是按同样的基本循环运作：从终端读入一个表达式，对这个表达式求值，而后打印出得到的结果。这种运作模式常常被人们说成是解释器运行在一个读入－求值－打印循环之中。请特别注意，在这里完全没有必要显式地去要求解释器打印表达式的值7。

1.1.2 命名和环境

程序设计语言中一个必不可少的方面，就是它需要提供一种通过名字去使用计算对象的方式。我们将名字标识符称为变量，它的值也就是它所对应的那个对象。
在Lisp方言Scheme里，给事物命名通过define（定义）的方式完成，输入：
(define size 2)
会导致解释器将值2与名字size相关联8。一旦名字size与2关联之后，我们就可以通过这个名字去引用值2了：

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

define是我们所用的语言里最简单的抽象方法，它允许我们用一个简单的名字去引用一个组合运算的结果，例如上面算出的circumference。一般而言，计算得到的对象完全可以具有非常复杂的结构，如果每次需要使用它们时，都必须记住并重复地写出它们的细节，那将是极端不方便的事情。实际上，构造一个复杂的程序，也就是为了去一步步地创建出越来越复杂的计算性对象。解释器使这种逐步的程序构造过程变得非常方便，因为我们可以通过一系列交互式动作，逐步创建起所需要的名字－对象关联。这种特征鼓励人们采用递增的方式去开发和调试程序。在很大程度上，这一情况也出于另一个事实，那就是，一个Lisp程序通常总是由一大批相对简单的过程组成的。
应该看到，我们可以将值与符号关联，而后又能提取出这些值，这意味着解释器必须维护某种存储能力，以便保持有关的名字-值对偶的轨迹。这种存储被称为环境（更精确地说，是全局环境，因为我们以后将看到，在一个计算过程中完全可能涉及若干不同环境）。

1.1.3 组合式的求值

本章的一个目标，就是要把与过程性思维有关的各种问题隔离出来。现在让我们考虑组合式的求值问题。解释器本身就是按照下面过程工作的。

• 要求值一个组合式，做下面的事情：

1) 求值该组合式的各个子表达式。
2) 将作为最左子表达式（运算符）的值的那个过程应用于相应的实际参数，所谓实际参数也就是其他子表达式（运算对象）的值。
即使是一条这样简单的规则，也显示出计算过程里的一些具有普遍性的重要问题。首先，由上面的第一步可以看到，为了实现对一个组合式的求值过程，我们必须先对组合式里的每个元素执行同样的求值过程。因此，在性质上，这一求值过程是递归的，也就是说，它在自己的工作步骤中，包含着调用这个规则本身的需要。
在这里应该特别注意，采用递归的思想可以多么简洁地描述深度嵌套的情况。如果不用递归，我们就需要把这种情况看成相当复杂的计算过程。例如，对下列表达式求值：

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

需要将求值规则应用于4个不同的组合式。如图1-1中所示，我们可以采用一棵树的形式，用图形表示这一组合式的求值过程，其中的每个组合式用一个带分支的结点表示，由它发出的分支对应于组合式里的运算符和各个运算对象。终端结点（即那些不再发出分支的结点）表示的是运算符或者数值。以树的观点看这种求值过程，可以设想那些运算对象的值向上穿行，从终端结点开始，而后在越来越高的层次中组合起来。一般而言，我们应该把递归看作一种处理层次性结构的（像树这样的对象）极强有力的技术。事实上，“值向上穿行”形式的求值形式是一类更一般的计算过程的一个例子，这种计算过程称为树形积累。
进一步的观察告诉我们，反复地应用第一个步骤，总可以把我们带到求值中的某一点，在这里遇到的不是组合式而是基本表达式，例如数、内部运算符或者其他名字。处理这些基础情况的方式如下规定：

• 数的值就是它们所表示的数值。
• 内部运算符的值就是能完成相应操作的机器指令序列。
• 其他名字的值就是在环境中关联于这一名字的那个对象。

我们可以将第二种规定看作是第三种规定的特殊情况，为此只需将像＋和 * 一类的运算符也包含在全局环境里，并将相应的指令序列作为与之关联的“值”。对于初学者，应该指出的关键一点是，环境所扮演的角色就是用于确定表达式中各个符号的意义。在如Lisp这样的交互式语言里，如果没有关于有关环境的任何信息，那么说例如表达式（＋ x 1）的值是毫无意义的，因为需要有环境为符号 x 提供意义（甚至需要它为符号＋提供意义）。正如我们将要在第3章看到的，环境是具有普遍性的概念，它为求值过程的进行提供了一种上下文，对于我们理解程序的执行起着极其重要的作用。
请注意，上面给出的求值规则里并没有处理定义。例如，对（define x 3）的求值并不是将define应用于它的两个实际参数：其中的一个是符号 x 的值，另一个是3。这是因为define的作用就是为 x 关联一个值（也就是说，（define x 3）并不是一个组合式）。

一般性求值规则的这种例外称为特殊形式，define是至今我们已经看到的唯一的一种特殊形式，下面还将看到另外一些特殊形式。每个特殊形式都有其自身的求值规则，各种不同种类的表达式（每种有着与之相关联的求值规则）组成了程序设计语言的语法形式。与大部分其他程序设计语言相比，Lisp的语法非常简单。也就是说，对各种表达式的求值规则可以描述为一个简单的通用规则和一组针对不多的特殊形式的专门规则。

1.1.4 复合过程

我们已经看到了Lisp里的某些元素，它们必然也会出现在任何一种强有力的程序设计语言里。这些东西包括：

• 数和算术运算是基本的数据和过程。
• 组合式的嵌套提供了一种组织起多个操作的方法。
• 定义是一种受限的抽象手段，它为名字关联相应的值。

现在我们来学习过程定义，这是一种威力更加强大的抽象技术，通过它可以为复合操作提供名字，而后就可以将这样的操作作为一个单元使用了。
现在我们要考察如何表述“平方”的想法。我们可能想说“求某个东西的平方，就是用它自身去乘以它自身”。在这个语言里，这件事情应该表述为：

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

可以按如下方式理解这一描述：

这样我们就有了一个复合过程，给它取的名字是square。这一过程表示的是将一个东西乘以它自身的操作。被乘的东西也给定了一个局部名字x，它扮演着与自然语言里代词同样的角色。求值这一定义的结果是创建起一个复合过程，并将它关联于名字square。
过程定义的一般形式是：

其中是一个符号，过程定义将在环境中关联于这个符号。（形式参数）是一些名字，它们用在过程体中，用于表示过程应用时与它们对应的各个实际参数。是一个表达式，在应用这一过程时，这一表达式中的形式参数将用与之对应的实际参数取代，对这样取代后的表达式的求值，产生出这个过程应用的值。和被放在一对括号里，成为一组，就像实际调用被定义过程时的写法。
定义好square之后，我们就可以使用它了：

(square 21)
441
(square (+ 2 5))
49
(square (square 3))
81

我们还可以用square作为基本构件去定义其他过程。例如，x2＋y2可以表述为：

(+ (square x) (square y))

现在我们很容易定义一个过程sum-of-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

复合过程的使用方式与基本过程完全一样。实际上，如果人们只看上面sum-of-squares的定义，根本就无法分辨出square究竟是（像＋和 * 那样）直接做在解释器里呢，还是被定义为一个复合过程。

1.1.5 过程应用的代换模型

为了求值一个组合式（其运算符是一个复合过程的名字），解释器的工作方式将完全按照1.1.3节中所描述的那样，采用与以运算符名为基本过程的组合式一样的计算过程。也就是说，解释器将对组合式的各个元素求值，而后将得到的那个过程（也就是该组合式里运算符的值）应用于那些实际参数（即组合式里那些运算对象的值）。
我们可以假定，把基本运算符应用于实参的机制已经在解释器里做好了。对于复合过程，过程应用的计算过程是：

• 将复合过程应用于实际参数，就是在将过程体中的每个形参用相应的实参取代之后，对这一过程体求值。

为了说明这种计算过程，让我们看看下面组合式的求值：
(f 5)
其中的f是1.1.4节定义的那个过程。我们首先提取出f的体：

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

而后用实际参数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))

使用square的定义又可以将它归约为：

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

通过乘法又能将它进一步归约为：

(+ 36 100)

最后得到：

136

上面描述的这种计算过程称为过程应用的代换模型，在考虑本章至今所定义的过程时，我们可以将它看作确定过程应用的“意义”的一种模型。但这里还需要强调两点：

• 代换的作用只是为了帮助我们领会过程调用中的情况，而不是对解释器实际工作方式的具体描述。通常的解释器都不采用直接操作过程的正文，用值去代换形式参数的方式去完成对过程调用的求值。在实际中，它们一般采用提供形式参数的局部环境的方式，产生“代换”的效果。我们将在第3章和第4章考察一个解释器的细节实现，在那里更完整地讨论这一问题。
• 随着本书讨论的进展，我们将给出有关解释器如何工作的一系列模型，一个比一个更精细，并最终在第5章给出一个完整的解释器和一个编译器。这里的代换模型只是这些模型中的第一个—作为形式化地考虑这种求值过程的起点。一般来说，在模拟科学研究或者工程中的现象时，我们总是从最简单的不完全的模型开始。随着更细致地检查所考虑的问题，这些简单模型也会变得越来越不合适，从而必须用进一步精化的模型取代。代换模型也不例外。特别地，在第3章中，我们将要讨论将过程用于“变化的数据”的问题，那时就会看到替换模型完全不行了，必须用更复杂的过程应用模型来代替它。

应用序和正则序
按照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

这给出了与前面求值模型同样的结果，但其中的计算过程却是不一样的。特别地，在对下面表达式的归约中，对于（＋5 1）和（* 5 2）的求值各做了两次：

(* x x)

其中的x分别被代换为（＋5 1）和（* 5 2）。
这种“完全展开而后归约”的求值模型称为正则序求值，与之对应的是现在解释器里实际使用的“先求值参数而后应用”的方式，它称为应用序求值。可以证明，对那些可以通过替换去模拟，并能产生出合法值的过程应用（包括本书前两章中的所有过程），正则序和应用序求值将产生出同样的值（参见练习1.5中一个“非法”值的例子，其中正则序和应用序将给出不同的结果）。
Lisp采用应用序求值，部分原因在于这样做能避免对于表达式的重复求值（例如上面的（＋5 1）和（* 5 2）的情况），从而可以提高一些效率。更重要的是，在超出了可以采用替换方式模拟的过程范围之后，正则序的处理将变得更复杂。而在另一些方面，正则序也可以成为特别有价值的工具，我们将在第3章和第4章研究它的某些内在性质16。

1.1.6 条件表达式和谓词

至此我们能定义出的过程类的表达能力还非常有限，因为还没办法去做某些检测，而后依据检测的结果去确定做不同的操作。例如，我们还无法定义一个过程，使它能计算出一个数的绝对值。完成此事需要先检查一个数是正的、负的或者零，而后依据遇到的不同情况，按照下面规则采取不同的动作：

这种结构称为一个分情况分析，在Lisp里有着一种针对这类分情况分析的特殊形式，称为cond（表示“条件”）。其使用形式如下：

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

条件表达式的一般性形式为：

这里首先包含了一个符号cond，在它之后跟着一些称为子句的用括号括起的表达式对偶。在每个对偶中的第一个表达式是一个谓词，也就是说，这是一个表达式，它的值将被解释为真或者假。
条件表达式的求值方式如下：首先求值谓词，如果它的值是false，那么就去求值，如果的值是false就去求值。这一过程将继续做下去，直到发现了某个谓词的值为真为止。此时解释器就返回相应子句中的序列表达式的值，以这个值作为整个条件表达式的值。如果无法找到值为真的，cond的值就没有定义。
我们用术语谓词指那些返回真或假的过程，也指那种能求出真或者假的值的表达式。求绝对值的过程abs使用了基本谓词＞、＜和＝，这几个谓词都以两个数为参数，分别检查第一个数是否大于、小于或者等于第二个数，并据此分别返回真或者假。
写绝对值函数的另一种方式是：

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

用自然语言来说，就是“如果x小于0就返回－x，否则就返回x”。else是一个特殊符号，可以用在cond的最后一个子句中的位置，这样做时，如果该cond前面的所有子句都被跳过，它就会返回最后子句中的值。事实上，所有永远都求出真值的表达式都可以用在这个的位置上。
下面是又一种写绝对值函数的方式：

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

这里采用的是特殊形式if，它是条件表达式的一种受限形式，适用于分情况分析中只有两个情况的需要。if表达式的一般形式是：

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

在求值一个if表达式时，解释器从求值其部分开始，如果得到真值，解释器就去求值并返回其值，否则它就去求值并返回其值。
除了一批基本谓词如<、＝和 > 之外，还有一些逻辑复合运算符，利用它们可以构造出各种复合谓词。最常用的三个复合运算符是：

解释器将从左到右一个个地求值，如果某个求值得到假，这一and表达式的值就是假，后面的那些也不再求值了。如果前面所有的都求出真值，这一and表达式的值就是最后那个的值。

解释器将从左到右一个个地求值，如果某个求值得到真，or表达式就以这个表达式的值作为值，后面的那些也不再求值了。如果所有的都求出假值，这一or表达式的值就是假。

如果求出的值是假，not表达式的值就是真；否则其值为假。
注意，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)))

练习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 请将下面表达式变换为前缀形式：

练习1.3 请定义一个过程，它以三个数为参数，返回其中较大的两个数之和。

练习1.4 请仔细考察上面给出的允许运算符为复合表达式的组合式的求值模型，根据对这一模型的认识描述下面过程的行为：

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

练习1.5 Ben Bitdiddle发明了一种检测方法，能够确定解释器究竟采用哪种序求值，是采用应用序，还是采用正则序。他定义了下面两个过程：

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

而后他求值下面的表达式：

(test 0 (p))

如果某个解释器采用的是应用序求值，Ben会看到什么样的情况？如果解释器采用正则序求值，他又会看到什么情况？请对你的回答做出解释。（无论采用正则序或者应用序，假定特殊形式if的求值规则总是一样的。其中的谓词部分先行求值，根据其结果确定随后求值的子表达式部分。）

1.1.7 实例：采用牛顿法求平方根

上面介绍的过程都很像常规的数学函数，它们描述的是如何根据一个或者几个参数去确定一个值。然而，在数学的函数和计算机的过程之间有一个重要差异，那就是，这一过程还必须是有效可行的。
作为目前情况下的一个实例，现在我们来考虑求平方根的问题。我们可以将平方根函数定义为：
＝那样的y，使得y≥0而且y^2＝x
这就描述出了一个完全正统的数学函数，我们可以利用它去判断某个数是否为另一个数的平方根，或根据上面叙述，推导出一些有关平方根的一般性事实。然而，另一方面，这一定义并没有描述一个计算过程，因为它确实没有告诉我们，在给定了一个数之后，如何实际地找到这个数的平方根。即使将这个定义用类似Lisp的形式重写一遍也完全无济于事：

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

这只不过是重新提出了原来的问题。
函数与过程之间的矛盾，不过是在描述一件事情的特征，与描述如何去做这件事情之间的普遍性差异的一个具体反映。换一种说法，人们有时也将它说成是说明性的知识与行动性的知识之间的差异。在数学里，人们通常关心的是说明性的描述（是什么），而在计算机科学里，人们则通常关心行动性的描述（怎么做）。
计算机如何算出平方根呢？最常用的就是牛顿的逐步逼近方法。这一方法告诉我们，如果对x的平方根的值有了一个猜测y，那么就可以通过执行一个简单操作去得到一个更好的猜测：只需要求出y和x/y的平均值（它更接近实际的平方根值）。例如，可以用这种方式去计算2的平方根，假定初始值是1：

继续这一计算过程，我们就能得到对2的平方根的越来越好的近似值。
现在，让我们设法用过程的语言来描述这一计算过程。开始时，我们有了被开方数的值（现在需要做的就是算出它的平方根）和一个猜测值。如果猜测值已经足够好了，有关工作也就完成了。如若不然，那么就需要重复上述计算过程去改进猜测值。我们可以将这一基本策略写成下面的过程：

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

我们还必须说明什么叫作“足够好”。下面的做法只是为了说明问题，它确实不是一个很好的检测方法（参见练习1.7）。这里的想法是，不断改进答案直至它足够接近平方根，使得其平方与被开方数之差小于某个事先确定的误差值（这里用的是0.001）：

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

最后还需要一种方式来启动整个工作。例如，我们可以总用1作为对任何数的初始猜测值：

(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

这个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

她很高兴地用自己的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?的另一种策略是监视猜测值在从一次迭代到下一次的变化情况，当改变值相对于猜测值的比率很小时就结束。请设计一个采用这种终止测试方式的平方根过程。对于很大和很小的数，这一方式都能工作吗？

练习1.8 求立方根的牛顿法基于如下事实，如果y是x的立方根的一个近似值，那么下式将给出一个更好的近似值：

请利用这一公式实现一个类似平方根过程的求立方根的过程。（在1.3.4节里，我们将看到如何实现一般性的牛顿法，作为这些求平方根和立方根过程的抽象。）

1.1.8 过程作为黑箱抽象

sqrt是我们用一组手工定义的过程来实现一个计算过程的第一个例子。请注意，在这里sqrt-iter的定义是递归的，也就是说，这一过程的定义基于它自身。能够基于一个过程自身来定义它的想法很可能会令人感到不安，人们可能觉得它不够清晰，这种“循环”定义怎么能有意义呢？是不是完全刻画了一个能够由计算机实现的计算过程呢？在1.2节里，我们将更细致地讨论这一问题。现在首先来看看sqrt实例所显示出的其他一些要点。
可以看到，对于平方根的计算问题可以自然地分解为若干子问题：怎样说一个猜测是足够好了，怎样去改进一个猜测，等等。这些工作中的每一个都通过一个独立的过程完成，整个sqrt程序可以看作一族过程（如图1-2所示），它们直接反映了从原问题到子问题的分解。

这一分解的重要性，并不仅仅在于它将一个问题分解成了几个部分。当然，我们总可以拿来一个大程序，并将它分割成若干部分—最前面10行、后面10行、再后面10行等等。这里最关键的问题是，分解中的每一个过程完成了一件可以清楚标明的工作，这使它们可以被用作定义其他过程的模块。例如，当我们基于square定义过程good-enough?之时，就是将square看作一个“黑箱”。在这样做时，我们根本无须关注这个过程是如何计算出它的结果的，只需要注意它能计算出平方值的事实。关于平方是如何计算的细节被隐去不提了，可以推迟到后来再考虑。情况确实如此，如果只看good-enough?过程，与其说square是一个过程，不如说它是一个过程的抽象，即所谓的过程抽象。在这一抽象层次上，任何能计算出平方的过程都同样可以用。
这样，如果我们只考虑返回值，那么下面这两个求平方的过程就是不可区分的。它们中的每一个都取一个数值参数，产生出这个数的平方作为值25。

(define (square x) (* x x))
(define (square x) 
  (exp (double (log x))))
(define (double x) (+ x x))

由此可见，一个过程定义应该能隐藏起一些细节。这将使过程的使用者可能不必自己去写这些过程，而是从其他程序员那里作为一个黑箱而接受了它。用户在使用一个过程时，应该不需要去弄清它是如何实现的。
局部名
过程用户不必去关心的实现细节之一，就是在有关的过程里面形式参数的名字，这是由实现者所选用的。也就是说，下面两个过程定义应该是无法区分的：

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

这一原则（过程的意义应该不依赖于其作者为形式参数所选用的名字）从表面看起来很明显，但其影响却非常深远。最直接的影响是，过程的形式参数名必须局部于有关的过程体。例如，我们在前面平方根程序中的good-enough?定义里使用了square：

(define (good-enough-  guess x)
  (< (abs (- (square guess) 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也就不是我们所希望的黑箱了。
过程的形式参数在过程体里扮演着一种非常特殊的角色，在这里，形式参数的具体名字是什么，其实完全没有关系。这样的名字称为约束变量，因此我们说，一个过程的定义约束了它的所有形式参数。如果在一个完整的过程定义里将某个约束变量统一换名，这一过程定义的意义将不会有任何改变。如果一个变量不是被约束的，我们就称它为自由的。一个名字的定义被约束于的那一集表达式称为这个名字的作用域。在一个过程定义里，被声明为这个过程的形式参数的那些约束变量，就以这个过程的体作为它们的作用域。
在上面good-enough?的定义中，guess和x是约束变量，而<、-、abs和square则是自由的。要想保证good-enough?的意义与我们对guess和x的名字选择无关，只要求它们的名字与<、-、abs和square都不同就可以了（如果将guess重新命名为abs，我们就会因为捕获了变量名abs而引进了一个错误，因为这样做就把一个原本自由的名字变成约束的了）。good-enough?的意义当然与其中的自由变量有关，显然它的意义依赖于（在这一定义之外的）一些事实：要求符号abs是一个过程的名字，该过程能求出一个数的绝对值。如果我们将good-enough?的定义里的abs换成cos，它计算出的就会是另一个不同函数了。
内部定义和块结构
至今我们才仅仅分离出了一种可用的名字：过程的形式参数是相应过程体里的局部名字。平方根程序还展现出了另一种情况，我们也会希望能控制其中的名字使用。现在这个程序由几个相互分离的过程组成：

(define (sqrt x)
  (sqrt-iter 1.0 x))
(define (sqrt-iter guess x)
  (if (good-enough-  guess x)
      guess
      (sqrt-iter (improve guess x) x)))
(define (good-enough-  guess x)
  (< (abs (- (square guess) x)) 0.001))
(define (improve guess x)
  (average guess (/ x guess)))

问题是，在这个程序里只有一个过程对用户是重要的，那就是，这里所定义的sqrt确实是sqrt。其他的过程（sqrt-iter、good-enough?和improve）则只会干扰他们的思维，因为他们再也不能定义另一个称为good-enough?的过程，作为需要与平方根程序一起使用的其他程序的一部分了，因为现在sqrt需要它。在许多程序员一起构造大系统的时候，这一问题将会变得非常严重。举例来说，在构造一个大型的数值过程库时，许多数值函数都需要计算出一系列的近似值，因此我们就可能希望有一些名字为good-enough?和improve的过程作为其中的辅助过程。由于这些情况，我们也希望将这个种子过程局部化，将它们隐藏到sqrt里面，以使sqrt可以与其他采用逐步逼近的过程共存，让它们中的每一个都有自己的good-enough- 过程。为了使这一方式成为可能，我们要允许一个过程里带有一些内部定义，使它们是局部于这一过程的。例如，在解决平方根问题时，我们可以写：

(define (sqrt x)
  (define (good-enough-  guess x)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess x)
    (average guess (/ x guess)))
  (define (sqrt-iter guess x)
    (if (good-enough-  guess x)
        guess
        (sqrt-iter (improve guess x) x)))
  (sqrt-iter 1.0 x))

这种嵌套的定义称为块结构，它是最简单的名字包装问题的一种正确解决方式。实际上，在这里还潜藏着一个很好的想法。除了可以将所用的辅助过程定义放到内部，我们还可能简化它们。因为x在sqrt的定义中是受约束的，过程good-enough?、improve和sqrt-iter也都定义在sqrt里面，也就是说，都在x的定义域里。这样，显式地将x在这些过程之间传来传去也就没有必要了。我们可以让x作为内部定义中的自由变量，如下所示。这样，在外围的sqrt被调用时，x由实际参数得到自己的值。这种方式称为词法作用域。

(define (sqrt x)
  (define (good-enough-  guess)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (sqrt-iter guess)
    (if (good-enough-  guess)
        guess
        (sqrt-iter (improve guess))))
  (sqrt-iter 1.0))

下面将广泛使用这种块结构，以帮助我们将大程序分解成一些容易把握的片段28。块结构的思想来自程序设计语言Algol 60，这种结构出现在各种最新的程序设计语言里，是帮助我们组织大程序的结构的一种重要工具。

1.2 过程及其产生的计算

我们现在已经考虑了程序设计中的一些要素：使用过许多基本的算术操作，对操作进行组合，通过定义各种复合过程，对复合操作进行抽象。但是，即使是知道了这些，我们还不能说自己已经理解了如何去编程序。我们现在的情况就像是在学下象棋的过程中的一个阶段，此时已经知道了移动棋子的各种规则，但却还不知道典型的开局、战术和策略。就像初学象棋的人们那样，我们还不知道编程领域中各种有用的常见模式，缺少有关各种棋步的价值（值得定义哪些过程）的知识，缺少对所走棋步的各种后果（执行一个过程的效果）做出预期的经验。
能够看清楚所考虑的动作的后果的能力，对于成为程序设计专家是至关重要的，就像这种能力在所有综合性的创造性的活动中的作用一样。要成为一个专业摄影家，必须学习如何去考察各种景象，知道在各种可能的暴光和显影选择条件下，景象中各个区域在影像中的明暗程度。只有在此之后，人才能去做反向推理，对取得所需效果应该做的取景、亮度、曝光和显影等等做出规划。在程序设计里也一样，在这里，我们需要对计算过程中各种动作的进行情况做出规划，用一个程序去控制这一过程的进展。要想成为专家，我们就需要学会去看清各种不同种类的过程会产生什么样的计算过程。只有在掌握了这种技能之后，我们才能学会如何去构造出可靠的程序，使之能够表现出所需要的行为。
一个过程也就是一种模式，它描述了一个计算过程的局部演化方式，描述了这一计算过程中的每个步骤是怎样基于前面的步骤建立起来的。在有了一个刻画计算过程的过程描述之后，我们当然希望能做出一些有关这一计算过程的整体或全局行为的论断。一般来说这是非常困难的，但我们至少还是可以试着去描述过程演化的一些典型模式。
在这一节里，我们将考察由一些简单过程所产生的计算过程的“形状”，还将研究这些计算过程消耗各种重要计算资源（时间和空间）的速率。这里将要考察的过程都是非常简单的，它们所扮演的角色就像是摄影术中的测试模式，是作为极度简化的摄影模式，而其自身并不是很实际的例子。

1.2.1 线性的递归和迭代

首先考虑由下面表达式定义的阶乘函数：

n!＝n·(n－1)·(n－2) …3·2·1

计算阶乘的方式有许多种，一种最简单方式就是利用下述认识：对于一个正整数n，n!就等于n乘以（n－1）!：

n!＝n·[(n－1)·(n－2) …3·2·1]＝n·(n－1)!

这样，我们就能通过算出（n－1）!，并将其结果乘以n的方式计算出n!。如果再注意到1!就是1，这些认识就可以直接翻译成一个过程了：

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

我们可以利用1.1.5节介绍的代换模型，观看这一过程在计算6!时表现出的行为，如图1-3所示。
现在让我们采用另一种不同的观点来计算阶乘。我们可以将计算阶乘n!的规则描述为：先乘起1和2，而后将得到的结果乘以3，而后再乘以4，这样下去直到达到n。更形式地说，我们要维持着一个变动中的乘积product，以及一个从1到n的计数器counter，这一计算过程可以描述为counter和product的如下变化，从一步到下一步，它们都按照下面规则改变：

product ← counter·product 
counter ← counter + 1

可以看到，n!也就是计数器counter超过n时乘积product的值。
我们又可以将这一描述重构为一个计算阶乘的过程：

(define (factorial n)
  (fact-iter 1 1 n))
(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))

与前面一样，我们也可以应用替换模型来查看6!的计算过程，如图1-4所示。

现在对这两个计算过程做一个比较。从一个角度看，它们并没有很大差异：两者计算的都是同一个定义域里的同一个数学函数，都需要使用与n正比的步骤数目去计算出n!。确实，这两个计算过程甚至采用了同样的乘运算序列，得到了同样的部分乘积序列。但另一方面，如果我们考虑这两个计算过程的“形状”，就会发现它们的进展情况大不相同。
考虑第一个计算过程。代换模型揭示出一种先逐步展开而后收缩的形状，如图1-3中的箭头所示。在展开阶段里，这一计算过程构造起一个推迟进行的操作所形成的链条（在这里是一个乘法的链条），收缩阶段表现为这些运算的实际执行。这种类型的计算过程由一个推迟执行的运算链条刻画，称为一个递归计算过程。要执行这种计算过程，解释器就需要维护好那些以后将要执行的操作的轨迹。在计算阶乘n!时，推迟执行的乘法链条的长度也就是为保存其轨迹需要保存的信息量，这个长度随着n值而线性增长（正比于n），就像计算中的步骤数目一样。这样的计算过程称为一个线性递归过程。
与之相对应，第二个计算过程里并没有任何增长或者收缩。对于任何一个n，在计算过程中的每一步，在我们需要保存轨迹里，所有的东西就是变量product、counter和max-count的当前值。我们称这种过程为一个迭代计算过程。一般来说，迭代计算过程就是那种其状态可以用固定数目的状态变量描述的计算过程；而与此同时，又存在着一套固定的规则，描述了计算过程在从一个状态到下一状态转换时，这些变量的更新方式；还有一个（可能有的）结束检测，它描述这一计算过程应该终止的条件。在计算n!时，所需的计算步骤随着n线性增长，这种过程称为线性迭代过程。
我们还可以从另一个角度来看这两个过程之间的对比。在迭代的情况里，在计算过程中的任何一点，那几个程序变量都提供了有关计算状态的一个完整描述。如果我们令上述计算在某两个步骤之间停下来，要想重新唤醒这一计算，只需要为解释器提供有关这三个变量的值。而对于递归计算过程而言，这里还存在着另外的一些“隐含”信息，它们并未保存在程序变量里，而是由解释器维持着，指明了在所推迟的运算所形成的链条里的漫游中，“这一计算过程处在何处”。这个链条越长，需要保存的信息也就越多30。
在做迭代与递归之间的比较时，我们必须当心，不要搞混了递归计算过程的概念和递归过程的概念。当我们说一个过程是递归的时候，论述的是一个语法形式上的事实，说明这个过程的定义中（直接或者间接地）引用了该过程本身。在说某一计算过程具有某种模式时（例如，线性递归），我们说的是这一计算过程的进展方式，而不是相应过程书写上的语法形式。当我们说某个递归过程（例如fact-iter）将产生出一个迭代的计算过程时，可能会使人感到不舒服。然而这一计算过程确实是迭代的，因为它的状态能由其中的三个状态变量完全刻画，解释器在执行这一计算过程时，只需要保持这三个变量的轨迹就足够了。
区分计算过程和写出来的过程可能使人感到困惑，其中的一个原因在于各种常见语言（包括Ada、Pascal和C）的大部分实现的设计中，对于任何递归过程的解释，所需要消耗的存储量总与过程调用的数目成正比，即使它所描述的计算过程从原理上看是迭代的。作为这一事实的后果，要在这些语言里描述迭代过程，就必须借助于特殊的“循环结构”，如do、repeat、until、for和while等等。我们将在第5章里考察的Scheme的实现则没有这一缺陷，它将总能在常量空间中执行迭代型计算过程，即使这一计算是用一个递归过程描述的。具有这一特性的实现称为尾递归的。有了一个尾递归的实现，我们就可以利用常规的过程调用机制表述迭代，这也会使各种复杂的专用迭代结构变成不过是一些语法糖衣了31。
练习1.9 下面几个过程各定义了一种加起两个正整数的方法，它们都基于过程inc（它将参数增加1）和dec（它将参数减少1）。

(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))
(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))

请用代换模型展示这两个过程在求值（＋4 5）时所产生的计算过程。这些计算过程是递归的或者迭代的吗？
练习1.10 下面过程计算一个称为Ackermann函数的数学函数：

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

下面各表达式的值是什么：

(A 1 10)
(A 2 4)
(A 3 3)

请考虑下面的过程，其中的A就是上面定义的过程：

(define (f n) (A 0 n))
(define (g n) (A 1 n))
(define (h n) (A 2 n))
(define (k n) (* 5 n n))

请给出过程f、g和h对给定整数值n所计算的函数的数学定义。例如，（k n）计算的是5n2。

1.2.2 树形递归

另一种常见计算模式称为树形递归。作为例子，现在考虑斐波那契（Fibonacci）数序列的计算，这一序列中的每个数都是前面两个数之和：
0, 1, 1, 2, 3, 5, 8, 13, 21, …
一般说，斐波那契数由下面规则定义：

我们马上就可以将这个定义翻译为一个计算斐波那契数的递归过程：

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

考虑这一计算的模式。为了计算（fib 5），我们需要计算出（fib 4）和（fib 3）。而为了计算（fib 4），又需要计算（fib 3）和（fib 2）。一般而言，这一展开过程看起来像一棵树，如图1-5所示。请注意，这里的每层分裂为两个分支（除了最下面），反映出对fib过程的每个调用中两次递归调用自身的事实。

上面过程作为典型的树形递归具有教育意义，但它却是一种很糟的计算斐波那契数的方法，因为它做了太多的冗余计算。在图1-5中，求（fib 3）差不多是这里的一半工作，这一计算整个地重复做了两次。事实上，不难证明，在这一过程中，计算（fib 1）和（fib 0）的次数（一般说，也就是上面树里树叶的个数）正好是Fib(n＋1)。要领会这种情况有多么糟糕，我们可以证明Fib(n) 值的增长相对于n是指数的。更准确地说（见练习1.13），Fib(n) 就是最接近的整数，其中：

就是黄金分割的值，它满足方程：

这样，该过程所用的计算步骤数将随着输入增长而指数性地增长。另一方面，其空间需求只是随着输入增长而线性增长，因为，在计算中的每一点，我们都只需保存树中在此之上的结点的轨迹。一般说，树形递归计算过程里所需的步骤数将正比于树中的结点数，其空间需求正比于树的最大深度。
我们也可以规划出一种计算斐波那契数的迭代计算过程，其基本想法就是用一对整数a和b，将它们分别初始化为Fib(1)＝1和Fib(0)＝0，而后反复地同时使用下面变换规则：
a←a＋b b←a
不难证明，在n次应用了这些变换后，a和b将分别等于Fib(n＋1) 和Fib(n)。因此，我们可以用下面过程，以迭代方式计算斐波那契数：

(define (fib n)
  (fib-iter 1 0 n))
(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

计算Fib(n)的这种方法是一个线性迭代。这两种方法在计算中所需的步骤上差异巨大—后一方法相对于n为线性的，前一个的增长像Fib(n) 一样快，即使不大的输入也可能造成很大的差异。
但是我们也不应做出结论，说树形递归计算过程根本没有用。当我们考虑的是在层次结构性的数据上操作，而不是对数操作时，将会发现树形递归计算过程是一种自然的、威力强大的工具32。即使是对于数的计算，树形递归计算过程也可能帮助我们理解和设计程序。以计算斐波那契数的程序为例，虽然第一个fib过程远比第二个低效，但它却更加直截了当，基本上就是将斐波那契序列的定义直接翻译为Lisp语言。而要规划出那个迭代过程，则需要注意到，这一计算过程可以重新塑造为一个采用三个状态变量的迭代。
实例：换零钱方式的统计
要想得到一个迭代的斐波那契算法需要一点点智慧。与此相对应，现在考虑下面的问题：给了半美元、四分之一美元、10美分、5美分和1美分的硬币，将1美元换成零钱，一共有多少种不同方式？更一般的问题是，给定了任意数量的现金，我们能写出一个程序，计算出所有换零钱方式的种数吗？
采用递归过程，这一问题有一种很简单的解法。假定我们所考虑的可用硬币类型种类排了某种顺序，于是就有下面的关系：
将总数为a的现金换成n种硬币的不同方式的数目等于

• 将现金数a换成除第一种硬币之外的所有其他硬币的不同方式数目，加上
• 将现金数a－d换成所有种类的硬币的不同方式数目，其中的d是第一种硬币的币值。

要问为什么这一说法是对的，请注意这里将换零钱分成两组时所采用的方式，第一组里都没有使用第一种硬币，而第二组里都使用了第一种硬币。显然，换成零钱的全部方式的数目，就等于完全不用第一种硬币的方式的数目，加上用了第一种硬币的换零钱方式的数目。而后一个数目也就等于去掉一个第一种硬币值后，剩下的现金数的换零钱方式数目。
这样就可以将某个给定现金数的换零钱方式的问题，递归地归约为对更少现金数或者更少种类硬币的同一个问题。仔细考虑上面的归约规则，设法使你确信，如果采用下面方式处理退化情况，我们就能利用上面规则写出一个算法来33：

• 如果a就是0，应该算作是有1种换零钱的方式。
• 如果a小于0，应该算作是有0种换零钱的方式。
• 如果n是0，应该算作是有0种换零钱的方式。

我们很容易将这些描述翻译为一个递归过程：

(define (count-change amount)
  (cc amount 5))
(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

（过程first-denomination以可用的硬币种数作为输入，返回第一种硬币的币值。这里认为硬币已经从最大到最小排列好了，其实采用任何顺序都可以）。我们现在就能回答开始的问题了，下面是换1美元硬币的不同方式数目：

(count-change 100)
292

count-change产生出一个树形的递归计算过程，其中的冗余计算与前面fib的第一种实现类似（它计算出292需要一点时间）。另一方面，要想设计出一个更好的算法，使之能算出同样结果，就不那么明显了。我们将这一问题留给读者作为一个挑战。人们认识到，树形递归计算过程有可能极其低效，但常常很容易描述和理解，这就导致人们提出了一个建议，希望能利用世界上的这两个最好的东西。人们希望能设计出一种“灵巧编译器”，使之能将一个树形递归的过程翻译为一个能计算出同样结果的更有效的过程34。
练习1.11 函数 f 由如下的规则定义：如果n＜3，那么 f(n)＝n；如果n≥3，那么 f(n)＝f(n－1)＋2f(n－2)＋3f(n－3)。请写一个采用递归计算过程计算 f 的过程。再写一个采用迭代计算过程计算 f 的过程。
练习1.12 下面数值模式称为帕斯卡三角形：

三角形边界上的数都是1，内部的每个数是位于它上面的两个数之和35。请写一个过程，它采用递归计算过程计算出帕斯卡三角形。
练习1.13 证明Fib(n) 是最接近的整数，其中。提示：利用归纳法和斐波那契数的定义（见1.2.2节），证明。

1.2.3 增长的阶

前面一些例子说明，不同的计算过程在消耗计算资源的速率上可能存在着巨大差异。描述这种差异的一种方便方式是用增长的阶的记法，以便我们理解在输入变大时，某一计算过程所需资源的粗略度量情况。
令n是一个参数，它能作为问题规模的一种度量，令R(n) 是一个计算过程在处理规模为n的问题时所需要的资源量。在前面的例子里，我们取n为给定函数需要计算的那个数，当然也存在其他可能性。例如，如果我们的目标是计算出一个数的平方根的近似值，那么就可以将n取为所需精度的数字个数。对于矩阵乘法，我们可以将n取为矩阵的行数。一般而言，总存在着某个有关问题特性的数值，使我们可以相对于它去分析给定的计算过程。与此类似，R(n)也可以是所用的内部寄存器数目的度量值，也可能是需要执行的机器操作数目的度量值，或者其他类似东西。在每个时刻只能执行固定数目的操作的计算机里，所需的时间将正比于需要执行的基本机器指令条数。
我们称R(n) 具有Θ(f(n)) 的增长阶，记为R(n)＝Θ(f(n))（读作“f(n) 的theta”），如果存在与n无关的整数k1和k2，使得：

对任何足够大的n值都成立（换句话说，对足够大的n，值R(n) 总位于k1f(n) 和k2f(n) 之间）。
举例来说，在1.2.1节中描述的计算阶乘的线性递归计算过程里，步骤数目的增长正比于输入n。也就是说，这一计算过程所需步骤的增长为Θ(n)，其空间需求的增长也是Θ(n)。对于迭代的阶乘，其步数还是Θ(n) 而空间是Θ(1)，即为一个常数36。树形递归的斐波那契计算需要 步和Θ(n) 空间，这里的f就是1.2.2节中描述的黄金分割率。
增长的阶为我们提供了对计算过程行为的一种很粗略的描述。例如，某计算过程需要n2步，另一计算过程需要1000n2步，还有一个计算过程需要3n2＋10n＋17步，它们增长的阶都是Θ(n^2)。但另一方面，增长的阶也为我们在问题规模改变时，预期一个计算过程的行为变化提供了有用的线索。对于一个Θ(n)（线性）的计算过程，规模增大一倍大致将使它所用的资源增加了一倍。对于一个指数的计算过程，问题规模每增加1都将导致所用资源按照某个常数倍增长。在1.2节剩下的部分，我们将考察两个算法，其增长的阶都是对数型增长的，因此，当问题规模增大一倍时，所需资源量只增加一个常数。
练习1.14 请画出有关的树，展示1.2.2节的过程count-change在将11美分换成硬币时所产生的计算过程。相对于被换现金量的增加，这一计算过程的空间和步数增长的阶各是什么？
练习1.15 在角（用弧度描述）x足够小时，其正弦值可以用sinx≈x计算，而三角恒等式：

可以减小sin的参数的大小（为完成这一练习，我们认为一个角是“足够小”，如果其数值不大于0.1弧度）。这些想法都体现在下述过程中：

(define (cube x) (* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))
(define (sine angle)
   (if (not (> (abs angle) 0.1))
       angle
       (p (sine (/ angle 3.0)))))

a) 在求值（sine 12.15）时，p将被使用多少次？
b) 在求值（sine a）时，由过程sine所产生的计算过程使用的空间和步数（作为a的函数）增长的阶是什么？

1.2.4 求幂

现在考虑对一个给定的数计算乘幂的问题，我们希望这一过程的参数是一个基数b和一个正整数的指数n，过程计算出b^n。做这件事的一种方式是通过下面这个递归定义：

它可以直接翻译为如下过程：

(define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- n 1)))))

这是一个线性的递归计算过程，需要Θ(n) 步和Θ(n) 空间。就像阶乘一样，我们很容易将其形式化为一个等价的线性迭代：

(define (expt b n)
  (expt-iter b n 1))
(define (expt-iter b counter product)
  (if (= counter 0)
      product
      (expt-iter b
                (- counter 1)
                (* b product))))

这一版本需要Θ(n) 步和Θ(1) 空间。
我们可以通过连续求平方，以更少的步骤完成乘幂计算。例如，不是采用下面这样的方式算b^8：
b·(b·(b·(b·(b·(b·(b·b))))))
而是用三次乘法算出它来：

这一方法对于指数为2的乘幂都可以用。如果采用下面规则，我们就可以借助于连续求平方，去完成一般的乘幂计算：

这一方法可以定义为如下的过程：

(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))

其中检测一个整数是否偶数的谓词可以基于基本过程remainder定义：

(define (even? n)
  (= (remainder n 2) 0))

由fast-expt演化出的计算过程，在空间和步数上相对于n都是对数的。要看到这些情况，请注意，在用fast-expt计算b2n时，只需要比计算bn多做一次乘法。每做一次新的乘法，能够计算的指数值（大约）增大一倍。这样，计算指数n所需要的乘法次数的增长大约就是以2为底的n的对数值，这一计算过程增长的阶为Θ(log n)^37。
随着n变大，Θ(log n) 增长与Θ(n) 增长之间的差异也会变得非常明显。例如对n＝1000，fast-expt只需要14次乘法38。我们也可能采用连续求平方的想法，设计出一个具有对数步数的计算乘幂的迭代算法（见练习1.16）。但是，就像迭代算法的常见情况一样，写出这一算法就不像对递归算法那样直截了当了。
练习1.16 请定义一个过程，它能产生出一个按照迭代方式的求幂计算过程，其中使用一系列的求平方，就像一样fast-expt只用对数个步骤那样。（提示：请利用关系 ＝，除了指数n和基数b之外，还应维持一个附加的状态变量a，并定义好状态变换，使得从一个状态转到另一状态时乘积a b^n不变。在计算过程开始时令a取值1，并用计算过程结束时a的值作为回答。一般说，定义一个不变量，要求它在状态之间保持不变，这一技术是思考迭代算法设计问题时的一种非常强有力的方法。）
练习1.17 本节里的求幂算法的基础就是通过反复做乘法去求乘幂。与此类似，也可以通过反复做加法的方式求出乘积。下面的乘积过程与expt过程类似（其中假定我们的语言只有加法而没有乘法）：

(define (* a b)
  (if (= b 0)
      0
      (+ a (* a (- b 1)))))

这一算法具有相对于b的线性步数。现在假定除了加法之外还有运算double，它能求出一个整数的两倍；还有halve，它将一个（偶数）除以2。请用这些运算设计一个类似fast-expt的求乘积过程，使之只用对数的计算步数。
练习1.18 利用练习1.16和1.17的结果设计一个过程，它能产生出一个基于加、加倍和折半运算的迭代计算过程，只用对数的步数就能求出两个整数的乘积40。
练习1.19 存在着一种以对数步数求出斐波那契数的巧妙算法。请回忆1.2.2节fib-iter计算过程中状态变量a和b的变换规则，a←a＋b和b←a，现在将这种变换称为T变换。通过观察可以发现，从1和0开始将T反复应用n次，将产生出一对数Fib(n＋1) 和Fib(n)。换句话说，斐波那契数可以通过将Tn（变换T的n次方）应用于对偶 (1, 0) 而产生出来。现在将T看作变换族Tpq中p＝0且q＝1的特殊情况，其中Tpq是对于对偶 (a, b) 按照a←bq＋aq＋ap和b←bp＋aq规则的变换。请证明，如果我们应用变换Tpq两次，其效果等同于应用同样形式的一次变换Tp'q'，其中的p'和q'可以由p和q计算出来。这就指明了一条求出这种变换的平方的路径，使我们可以通过连续求平方的方式去计算Tn，就像fast-expt过程里所做的那样。将所有这些集中到一起，就形成了下面的过程，其运行只需要对数的步数：

(define (fib n)
  (fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   <??>      ; compute p'
                   <??>      ; compute q'
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

1.2.5 最大公约数

两个整数a和b的最大公约数（GCD）定义为能除尽这两个数的那个最大的整数。例如，16和28的GCD就是4。在第2章里，当我们要去研究有理数算术的实现时，就会需要GCD，以便能把有理数约化到最简形式（要将有理数约化到最简形式，我们必须将其分母和分子同时除掉它们的GCD。例如，16/28将约简为4/7）。找出两个整数的GCD的一种方式是对它们做因数分解，并从中找出公共因子。但存在着一个更高效的著名算法。
这一算法的思想基于下面的观察：如果r是a除以b的余数，那么a和b的公约数正好也是b的r的公约数。因此我们可以借助于等式：
GCD(a, b)＝GCD(b, r)
这就把一个GCD的计算问题连续地归约到越来越小的整数对的GCD的计算问题。例如：
GCD(206, 40)＝GCD(40, 6) ＝GCD(6, 4) ＝GCD(4, 2) ＝GCD(2, 0) ＝2
将GCD (206, 40) 归约到GCD (2, 0)，最终得到2。可以证明，从任意两个正整数开始，反复执行这种归约，最终将产生出一个数对，其中的第二个数是0，此时的GCD就是另一个数。这一计算GCD的方法称为欧几里得算法42。
不难将欧几里得算法写成一个过程：

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

这将产生一个迭代计算过程，其步数依所涉及的数的对数增长。
欧几里得算法所需的步数是对数增长的，这一事实与斐波那契数之间有一种有趣关系：
Lamé定理：如果欧几里得算法需要用k步计算出一对整数的GCD，那么这对数中较小的那个数必然大于或者等于第k个斐波那契数。
我们可以利用这一定理，做出欧几里得算法的增长阶估计。令n是作为过程输入的两个数中较小的那个，如果计算过程需要k步，那么我们就一定有。这样，步数k的增长就是n的对数（对数的底是φ）。这样，算法的增长阶就是Θ(log n)。
练习1.20 一个过程所产生的计算过程当然依赖于解释器所使用的规则。作为一个例子，考虑上面给出的迭代式gcd过程，假定解释器用第1.1.5节讨论的正则序去解释这一过程（对if的正则序求值规则在练习1.5中描述）。请采用（正则序的）代换方法，展示在求值表达式（gcd 206 40）中产生的计算过程，并指明实际执行的remainder运算。在采用正则序求值（gcd 206 40）中实际执行了多少次remainder运算？如果采用应用序求值呢？

1.2.6 实例：素数检测

本节将描述两种检查整数n是否素数的方法，第一个具有的增长阶，而另一个“概率”算法具有Θ(log n) 的增长阶。本节最后的练习提出了若干基于这些算法的编程作业。
寻找因子
自古以来，数学家就被有关素数的问题所吸引，许多人都研究过确定整数是否素数的方法。检测一个数是否素数的一种方法就是找出它的因子。下面的程序能找出给定数n的（大于1的）最小整数因子。它采用了一种直接方法，用从2开始的连续整数去检查它们能否整除n。

(define (smallest-divisor n)
  (find-divisor n 2))
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b)
  (= (remainder b a) 0))

我们可以用如下方式检查一个数是否素数：n是素数当且仅当它是自己的最小因子：

(define (prime? n)
  (= n (smallest-divisor n)))

find-divisor的结束判断基于如下事实，如果n不是素数，它必然有一个小于或者等于的因子。这也意味着该算法只需在1和之间检查因子。由此可知，确定是否素数所需的步数将具有的增长阶。
费马检查
的素数检查基于数论中著名的费马小定理的结果45。
费马小定理：如果n是一个素数，a是小于n的任意正整数，那么a的n次方与a模n同余。
（两个数称为是模n同余，如果它们除以n的余数相同。数a除以n的余数称为a取模n的余数，或简称为a取模n）。
如果n不是素数，那么，一般而言，大部分的a＜n都将满足上面关系。这就引出了下面这个检查素数的算法：对于给定的整数n，随机任取一个a＜n并计算出an取模n的余数。如果得到的结果不等于a，那么n就肯定不是素数。如果它就是a，那么n是素数的机会就很大。现在再另取一个随机的a并采用同样方式检查。如果它满足上述等式，那么我们就能对n是素数有更大的信心了。通过检查越来越多的a值，我们就可以不断增加对有关结果的信心。这一算法称为费马检查。
为了实现费马检查，我们需要有一个过程来计算一个数的幂对另一个数取模的结果：

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

这个过程很像1.2.4节的fast-expt过程，它采用连续求平方的方式，使相对于计算中指数，步数增长的阶是对数的。
执行费马检查需要选取位于1和n－1之间（包含这两者）的数a，而后检查a的n次幂取模n的余数是否等于a。随机数a的选取通过过程random完成，我们假定它已经包含在Scheme的基本过程中，它返回比其整数输入小的某个非负整数。这样，要得到1和n－1之间的随机数，只需用输入n－1去调用random，并将结果加1：

(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))

下面这个过程的参数是某个数，它将按照由另一参数给定的次数运行上述检查。如果每次检查都成功，这一过程的值就是真，否则就是假：

(define (fast-prime? n times)
  (cond ((= times 0) true)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else false)))

概率方法
从特征上看，费马检查与我们前面已经熟悉的算法都不一样。前面那些算法都保证计算的结果一定正确，而费马检查得到的结果则只有概率上的正确性。说得更准确些，如果数n不能通过费马检查，我们可以确信它一定不是素数。而n通过了这一检查的事实只能作为它是素数的一个很强的证据，但却不是对n为素数的保证。我们能说的是，对于任何数n，如果执行这一检查的次数足够多，而且看到n通过了检查，那么就能使这一素数检查出错的概率减小到所需要的任意程度。
不幸的是，这一断言并不完全正确。因为确实存在着一些能骗过费马检查的整数：某些数n不是素数但却具有这样的性质，对任意整数a＜n，都有an与a模n同余。由于这种数极其罕见，因此费马检查在实践中还是很可靠的。也存在着一些费马检查的不会受骗的变形，它们也像费马方法一样，在检查整数n是否为素数时，选择随机的整数a＜n并去检查某些依赖于n和a的关系（练习1.28是这类检查的一个例子）。另一方面，与费马检查不同的是可以证明，对任意的数n，相应条件对整数a＜n中的大部分都不成立，除非n是素数。这样，如果n对某个随机选出的a能通过检查，n是素数的机会就大于一半。如果n对两个随机选择的a能通过检查，n是素数的机会就大于四分之三。通过用更多随机选择的a值运行这一检查，我们可以使出现错误的概率减小到所需要的任意程度。
能够证明，存在着使这样的出错机会达到任意小的检查算法，激发了人们对这类算法的极大兴趣，已经形成了人所共知称为概率算法的领域。在这一领域中已经有了大量研究工作，概率算法也已被成功地应用于许多重要领域。
练习1.21 使用smallest-divisor过程找出下面各数的最小因子：199、1999、19999。
练习1.22 大部分Lisp实现都包含一个runtime基本过程，调用它将返回一个整数，表示系统已经运行的时间（例如，以微秒计）。在对整数n调用下面的timed-prime-test过程时，将打印出n并检查n是否为素数。如果n是素数，过程将打印出三个星号，随后是执行这一检查所用的时间量。

(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (runtime)))
(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (runtime) start-time))))
(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))

请利用这一过程写一个search-for-primes过程，它检查给定范围内连续的各个奇数的素性。请用你的过程找出大于1 000、大于10 000、大于100 000和大于1 000 000的三个最小的素数。请注意其中检查每个素数所需要的时间。因为这一检查算法具有的增长阶，你可以期望在10 000附近的素数检查的耗时大约是在1 000附近的素数检查的倍。你得到的数据确实如此吗？对于100 000和1 000 000得到的数据，对这一预测的支持情况如何？有人说程序在你的机器上运行的时间正比于计算所需的步数，你得到的结果符合这种说法吗？
练习1.23 在本节开始时给出的那个smallest-divisor过程做了许多无用检查：在它检查了一个数是否能被2整除之后，实际上已经完全没必要再检查它是否能被任何偶数整除了。这说明test-divisor所用的值不应该是2，3，4，5，6，...，而应该是2，3，5，7，9，...。请实现这种修改。其中应定义一个过程next，用2调用时它返回3，否则就返回其输入值加2。修改smallest-divisor过程，使它去使用（next test-divisor）而不是（＋test-divisor 1）。让timed-prime-test结合这个smallest-divisor版本，运行练习1.22里的12个找素数的测试。因为这一修改使检查的步数减少一半，你可能期望它的运行速度快一倍。实际情况符合这一预期吗？如果不符合，你所观察到的两个算法速度的比值是什么？你如何解释这一比值不是2的事实？
练习1.24 修改练习1.22的timed-prime-test过程，让它使用fast-prime?（费马方法），并检查你在该练习中找出的12个素数。因为费马检查具有的增长速度，对接近1 000 000的素数检查与接近1000的素数检查作对期望时间之间的比较有怎样的预期？你的数据确实表明了这一预期吗？你能解释所发现的任何不符合预期的地方吗？
练习1.25 Alyssa P. Hacker提出，在写expmod时我们做了过多的额外工作。她说，毕竟我们已经知道怎样计算乘幂，因此只需要简单地写：

(define (expmod base exp m)
  (remainder (fast-expt base exp) m))

她说的对吗？这一过程能很好地用于我们的快速素数检查程序吗？请解释这些问题。
练习1.26 Louis Reasoner在做练习1.24时遇到了很大困难，他的fast-prime?检查看起来运行得比他的prime?检查还慢。Louis请他的朋友Eva Lu Ator过来帮忙。在检查Louis的代码时，两个人发现他重写了expmod过程，其中用了一个显式的乘法，而没有调用square：

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (* (expmod base (/ exp 2) m)
                       (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

“我看不出来这会造成什么不同，”Louis说。“我能看出，”Eva说，“采用这种方式写出该过程时，你就把一个的计算过程变成Θ(n) 的了。”请解释这一问题。
练习1.27 证明脚注47中列出的Carmichael数确实能骗过费马检查。也就是说，写一个过程，它以整数n为参数，对每个a＜n检查a^n是否与a模n同余。用你的过程去检查前面给出的那些Carmichael数。
练习1.28 费马检查的一种不会被欺骗的变形称为Miller-Rabin检查（Miller 1976; Rabin 1980），它来源于费马小定理的一个变形。这一变形断言，如果n是素数，a是任何小于n的整数，则a的 (n－1) 次幂与1模n同余。要用Miller-Rabin检查考察数n的素性，我们应随机地取一个数a＜n并用过程expmod求a的 (n－1) 次幂对n的模。然而，在执行expmod中的平方步骤时，我们需要查看是否遇到了“1取模n的非平凡平方根”，也就是说，是不是存在不等于1或者n－1的数，其平方取模n等于1。可以证明，如果1的这种非平凡平方根存在，那么n就不是素数。还可以证明，如果n是非素数的奇数，那么，至少有一半的数a＜n，按照这种方式计算a^(n-1)，将会遇到1取模n的非平凡平方根。这也是Miller-Rabin检查不会受骗的原因。请修改expmod过程，让它在发现1的非平凡平方根时报告失败，并利用它实现一个类似于fermat-test的过程，完成Miller-Rabin检查。通过检查一些已知素数和非素数的方式考验你的过程。提示：送出失败信号的一种简单方式就是让它返回0。

1.3 用高阶函数做抽象

我们已经看到，在作用上，过程也就是一类抽象，它们描述了一些对于数的复合操作，但又并不依赖于特定的数。例如，在定义：

(define (cube x) (* x x x))

时，我们讨论的并不是某个特定数值的立方，而是对任意的数得到其立方的方法。当然，我们也完全可以不去定义这一过程，而总是写出下面这样的表达式：

(* 3 3 3)
(* x x x)
(* y y y)

并不明确地提出cube。但是，这样做将把自己置于一个非常糟糕的境地，迫使我们永远在语言恰好提供了的那些特定基本操作（例如这里的乘法）的层面上工作，而不能基于更高级的操作去工作。我们写出的程序也能计算立方，但是所用的语言却不能表述立方这一概念。人们对功能强大的程序设计语言有一个必然要求，就是能为公共的模式命名，建立抽象，而后直接在抽象的层次上工作。过程提供了这种能力，这也是为什么除最简单的程序语言外，其他语言都包含定义过程的机制的原因。
然而，即使在数值计算过程中，如果将过程限制为只能以数作为参数，那也会严重地限制我们建立抽象的能力。经常有一些同样的程序设计模式能用于若干不同的过程。为了把这种模式描述为相应的概念，我们就需要构造出这样的过程，让它们以过程作为参数，或者以过程作为返回值。这类能操作过程的过程称为高阶过程。本节将展示高阶过程如何能成为强有力的抽象机制，极大地增强语言的表述能力。

1.3.1 过程作为参数

考虑下面的三个过程，第一个计算从a到b的各整数之和：

(define (sum-integers a b)
  (if (> a b)
      0
      (+ a (sum-integers (+ a 1) b))))

第二个计算给定范围内的整数的立方之和：

(define (sum-cubes a b)
  (if (> a b)
      0
      (+ (cube a) (sum-cubes (+ a 1) b))))

第三个计算下面的序列之和：

它将（非常缓慢地）收敛49到?8：

(define (pi-sum a b)
  (if (> a b)
      0
      (+ (/ 1.0 (* a (+ a 2))) (pi-sum (+ a 4) b))))

可以明显看出，这三个过程共享着一种公共的基础模式。它们的很大一部分是共同的，只在所用的过程名字上不一样：用于从a算出需要加的项的函数，还有用于提供下一个a值的函数。我们可以通过填充下面模板中的各空位，产生出上面的各个过程：

(define (<name> a b)
  (if (> a b)
      0
      (+ (<term> a)
         (<name> (<next> a) b))))

这种公共模式的存在是一种很强的证据，说明这里实际上存在着一种很有用的抽象，在那里等着浮现出来。确实，数学家很早就认识到序列求和中的抽象模式，并提出了专门的“求和记法”，例如：

用于描述这一概念。求和记法的威力在于它使数学家能去处理求和的概念本身，而不只是某个特定的求和—例如，借助它去形式化某些并不依赖于特定求和序列的求和结果。
与此类似，作为程序模式，我们也希望所用的语言足够强大，能用于写出一个过程，去表述求和的概念，而不是只能写计算特定求和的过程。我们确实可以在所用的过程语言中做到这些，只要按照上面给出的模式，将其中的“空位”翻译为形式参数：

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))

请注意，sum仍然以作为下界和上界的参数a和b为参数，但是这里又增加了过程参数term和next。使用sum的方式与其他函数完全一样。例如，我们可以用它去定义sum-cubes（还需要一个过程inc，它得到参数值加一）：

(define (inc n) (+ n 1))
(define (sum-cubes a b)
  (sum cube a inc b))

我们可以用这个过程算出从1到10的立方和：

(sum-cubes 1 10)
3025

利用一个恒等函数帮助算出项值，我们就可以基于sum定义出sum-integers：

(define (identity x) x)
(define (sum-integers a b)
  (sum identity a inc b))

而后就可以求出从1到10的整数之和了：

(sum-integers 1 10)
55

我们也可以按同样方式定义pi-sum50：

(define (pi-sum a b)
  (define (pi-term x)
    (/ 1.0 (* x (+ x 2))))
  (define (pi-next x)
    (+ x 4))
  (sum pi-term a pi-next b))

利用这一过程就能计算出π的一个近似值了:

(* 8 (pi-sum 1 1000))
3.139592655589783

一旦有了sum，我们就能用它作为基本构件，去形式化其他概念。例如，求出函数f在范围a和b之间的定积分的近似值，可以用下面公式完成

其中的dx是一个很小的值。我们可以将这个公式直接描述为一个过程：

(define (integral f a b dx)
  (define (add-dx x) (+ x dx))
  (* (sum f (+ a (/ dx 2.0)) add-dx b)
     dx))
(integral cube 0 1 0.01)
.24998750000000042
(integral cube 0 1 0.001)
.249999875000001

（cube在0和1间积分的精确值是1/4。）
练习1.29 辛普森规则是另一种比上面所用规则更精确的数值积分方法。采用辛普森规则，函数f在范围a和b之间的定积分的近似值是：

其中h＝(b－a)/n，n是某个偶数，而yk＝f(a＋kh)（增大n能提高近似值的精度）。请定义一个具有参数f、a、b和n，采用辛普森规则计算并返回积分值的过程。用你的函数求出cube在0和1之间的积分（用n＝100和n＝1000），并将得到的值与上面用integral过程所得到的结果比较。
练习1.30 上面的过程sum将产生出一个线性递归。我们可以重写该过程，使之能够迭代地执行。请说明应该怎样通过填充下面定义中缺少的表达式，完成这一工作。

(define (sum term a next b)
  (define (iter a result)
    (if <??>
        <??>
        (iter <??> <??>)))
  (iter <??> <??>))

练习1.31 a) 过程sum是可以用高阶过程表示的大量类似抽象中最简单的一个。请写出一个类似的称为product的过程，它返回在给定范围中各点的某个函数值的乘积。请说明如何用product定义factorial。另请按照下面公式计算π的近似值：

b) 如果你的product过程生成的是一个递归计算过程，那么请写出一个生成迭代计算过程的过程。如果它生成一个迭代计算过程，请写一个生成递归计算过程的过程。
练习1.32 a) 请说明，sum和product（练习1.31）都是另一称为accumulate的更一般概念的特殊情况，accumulate使用某些一般性的累积函数组合起一系列项：

(accumulate combiner null-value term a next b)

accumulate取的是与sum和product一样的项和范围描述参数，再加上一个（两个参数的）combiner过程，它描述如何将当前项与前面各项的积累结果组合起来，另外还有一个null-value参数，它描述在所有的项都用完时的基本值。请写出accumulate，并说明我们能怎样基于简单地调用accumulate，定义出sum和product来。
b) 如果你的accumulate过程生成的是一个递归计算过程，那么请写出一个生成迭代计算过程的过程。如果它生成一个迭代计算过程，请写一个生成递归计算过程的过程。
练习1.33 你可以通过引进一个处理被组合项的过滤器（filter）概念，写出一个比accumulate（练习1.32）更一般的版本。也就是说，在计算过程中，只组合起由给定范围得到的项里的那些满足特定条件的项。这样得到的filtered-accumulate抽象取与上面累积过程同样的参数，再加上一个另外的描述有关过滤器的谓词参数。请写出filtered-accumulate作为一个过程，说明如何用filtered-accumulate表达以下内容：
a) 求出在区间a到b中所有素数之和（假定你已经写出了谓词prime?）。
b) 小于n的所有与n互素的正整数（即所有满足GCD(i, n)＝1的整数i＜n）之乘积。

1.3.2 用lambda构造过程

在1.3.1节里用sum时，我们必须定义出一些如pi-term和pi-next一类的简单函数，以便用它们作为高阶函数的参数，这种做法看起来很不舒服。如果不需要显式定义pi-term和pi-next，而是有一种方法去直接刻画“那个返回其输入值加4的过程”和“那个返回其输入与它加2的乘积的倒数的过程”，事情就会方便多了。我们可以通过引入一种lambda特殊形式完成这类描述，这种特殊形式能够创建出所需要的过程。利用lambda，我们就能按照如下方式写出所需的东西：

(lambda (x) (+ x 4))

和

(lambda (x) (/ 1.0 (* x (+ x 2))))

这样就可以直接描述pi-sum过程，而无须定义任何辅助过程了：

(define (pi-sum a b)
  (sum (lambda (x) (/ 1.0 (* x (+ x 2))))
       a
       (lambda (x) (+ x 4))
       b))

借助于lambda，我们也可以写出integral过程而不需要定义辅助过程add-dx：

(define (integral f a b dx)
  (* (sum f
          (+ a (/ dx 2.0))
          (lambda (x) (+ x dx))
          b)
     dx))

一般而言，lambda用与define同样的方式创建过程，除了不为有关过程提供名字之外：

(lambda (\<formal-parameters>) \<body>)

这样得到的过程与通过define创建的过程完全一样，仅有的不同之处，就是这种过程没有与环境中的任何名字相关联。事实上，

(define (plus4 x) (+ x 4))

等价于

(define plus4 (lambda (x) (+ x 4)))

我们可以按如下方式来阅读lambda表达式：

    (lambda    (x)    (+    x        4))
    ↑    ↑    ↑    ↑        ↑
    该过程    以x为参数    它加起    x    和    4

像任何以过程为值的表达式一样，lambda表达式可用作组合式的运算符，例如：

((lambda (x y z) (+ x y (square z))) 1 2 3)
12

或者更一般些，可以用在任何通常使用过程名的上下文中53。
用let创建局部变量
lambda的另一个应用是创建局部变量。在一个过程里，除了使用那些已经约束为过程参数的变量外，我们常常还需要另外一些局部变量。例如，假定我们希望计算函数：

f(x, y)＝x(1＋xy)2＋y(1－y)＋(1＋xy)(1－y)

可能就希望将它表述为：

在写计算 f 的过程时，我们可能希望还有几个局部变量，不只是x和y，还有中间值的名字如a和b。做到这些的一种方式就是利用辅助过程去约束局部变量：

(define (f x y)
  (define (f-helper a b)
    (+ (* x (square a))
       (* y b)
       (* a b)))
  (f-helper (+ 1 (* x y)) 
            (- 1 y)))

当然，我们也可以用一个lambda表达式，用以描述约束局部变量的匿名过程。这样，f的体就变成了一个简单的对该过程的调用：

(define (f x y)
  ((lambda (a b)
     (+ (* x (square a))
        (* y b)
        (* a b)))
   (+ 1 (* x y))
   (- 1 y)))

这一结构非常有用，因此，语言里有一个专门的特殊形式称为let，使这种编程方式更为方便。利用let，过程f可以写为：

(define (f x y)
  (let ((a (+ 1 (* x y)))
        (b (- 1 y)))
    (+ (* x (square a))
       (* y b)
       (* a b))))

let表达式的一般形式是：

(let ((<var1> <exp1>)
      (<var2> <exp2>)
      
      (<varn> <expn>))
   <body>)

可以将它读作：

令 <var1> 具有值 <exp1> 而且
     <var2> 具有值 <exp2> 而且

     <varn> 具有值 <expn>
在 <body> 中

let表达式的第一部分是个名字-表达式对偶的表，当let被求值时，这里的每个名字将被关联于对应表达式的值。在将这些名字约束为局部变量的情况下求值let的体。这一做法正好使let表达式被解释为替代如下表达式的另一种语法形式：

((lambda (<var1> ...<varn>)
    <body>)
 <exp1>
 
 <expn>)

这样，解释器里就不需要为提供局部变量增加任何新机制。let表达式只是作为其基础的lambda表达式的语法外衣罢了。
根据这一等价关系，我们可以认为，由let表达式描述的变量的作用域就是该let的体，这也意味着：
?let使人能在尽可能接近其使用的地方建立局部变量约束。例如，如果x的值是5，下面表达式

     (+ (let ((x 3))
          (+ x (* x 10)))
        x)

就是38。在这里，位于let体里的x是3，因此这一let表达式的值是33。另一方面，作为最外层的＋的第二个参数的x仍然是5。
?变量的值是在let之外计算的。在为局部变量提供值的表达式依赖于某些与局部变量同名的变量时，这一规定就起作用了。例如，如果x的值是2，表达式：

     (let ((x 3)
           (y (+ x 2)))
       (* x y))

将具有值12，因为在这里let的体里，x将是3而y是4（其值是外面的x加2）。
有时我们也可以通过内部定义得到与let同样的效果。例如可以将上述f定义为：

     (define (f x y)
       (define a (+ 1 (* x y)))
       (define b (- 1 y))
       (+ (* x (square a))
          (* y b)
          (* a b)))

当然，在这种情况下我们更愿意用let，而仅将define用于内部过程54。
练习1.34 假定我们定义了：

(define (f g)
  (g 2))

而后就有：

(f square)
4
(f (lambda (z) (* z (+ z 1))))
6

如果我们（坚持）要求解释器去求值（f f），那会发生什么情况呢？请给出解释。

1.3.3 过程作为一般性的方法

我们在1.1.4节里介绍了复合过程，是为了作为一种将若干操作的模式抽象出来的机制，使所描述的计算不再依赖于所涉及的特定的数值。有了高阶过程，例如1.3.1节的integral过程，我们开始看到一种威力更强大的抽象，它们也是一类方法，可用于表述计算的一般性过程，与其中所涉及的特定函数无关。本节将讨论两个更精细的实例—找出函数零点和不动点的一般性方法，并说明如何通过过程去直接描述这些方法。
通过区间折半寻找方程的根
区间折半方法是寻找方程 f(x)＝0根的一种简单而又强有力的方法，这里的 f 是一个连续函数。这种方法的基本想法是，如果对于给定点a和b有 f(a)＜0＜f(b)，那么 f 在a和b之间必然有一个零点。为了确定这个零点，令x是a和b的平均值并计算出 f(x)。如果 f(x)＞0，那么在a和x之间必然有的一个 f 的零点；如果 f(x)＜0，那么在x和b之间必然有的一个 f 的零点。继续这样做下去，就能确定出越来越小的区间，且保证在其中必然有 f 的一个零点。当区间“足够小”时，就结束这一计算过程了。因为这种不确定的区间在计算过程的每一步都缩小一半，所需步数的增长将是Q(log(L/T))，其中L是区间的初始长度，T是可容忍的误差（即认为“足够小”的区间的大小）。下面是一个实现了这一策略的过程：

(define (search f neg-point pos-point)
  (let ((midpoint (average neg-point pos-point)))
    (if (close-enough? neg-point pos-point)
        midpoint
        (let ((test-value (f midpoint)))
          (cond ((positive? test-value)
                 (search f neg-point midpoint))
                ((negative? test-value)
                 (search f midpoint pos-point))
                (else midpoint))))))

假定开始时给定了函数 f，以及使它取值为负和为正的两个点。我们首先算出两个给定点的中点，而后检查给定区间是否已经足够小。如果是的话，就返回这一中点的值作为回答；否则就算出 f 在这个中点的值。如果检查发现得到的这个值为正，那么就以从原来负点到中点的新区间继续下去；如果这个值为负，就以中点到原来为正的点为新区间并继续下去。还有，也存在着检测值恰好为0的可能性，这时中点就是我们所寻找的根。
为了检查两个端点是否“足够接近”，我们可以用一个过程，它与1.1.7节计算平方根时所用的那个过程很类似：

(define (close-enough? x y)
  (< (abs (- x y)) 0.001))

search很难直接去用，因为我们可能会偶然地给了它一对点，相应的 f 值并不具有这个过程所需的正负号，这时就会得到错误的结果。让我们换一种方式，通过下面的过程去用search，这一过程检查是否某个点具有负的函数值，另一个点是正值，并根据具体情况去调用search过程。如果这一函数在两个给定点的值同号，那么就无法使用折半方法，在这种情况下过程发出错误信号。

(define (half-interval-method f a b)
  (let ((a-value (f a))
        (b-value (f b)))
    (cond ((and (negative? a-value) (positive? b-value))
           (search f a b))
          ((and (negative? b-value) (positive? a-value))
           (search f b a))
          (else
           (error "Values are not of opposite sign" a b)))))

下面实例用折半方法求π的近似值，它正好是sin x＝0在2和4之间的根：

(half-interval-method sin 2.0 4.0)
3.14111328125

这里是另一个例子，用折半方法找出x3－2x－3＝0在1和2之间的根：

(half-interval-method (lambda (x) (- (* x x x) (* 2 x) 3))
                      1.0
                      2.0)
1.89306640625

找出函数的不动点
数x称为函数 f 的不动点，如果x满足方程 f(x)＝x。对于某些函数，通过从某个初始猜测出发，反复地应用 f

f(x), f( f(x)), f( f( f(x))), . . .

直到值的变化不大时，就可以找到它的一个不动点。根据这个思路，我们可以设计出一个过程fixed-point，它以一个函数和一个初始猜测为参数，产生出该函数的一个不动点的近似值。我们将反复应用这个函数，直至发现连续的两个值之差小于某个事先给定的容许值：

(define tolerance 0.00001)
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

例如，下面用这一方法求出的是余弦函数的不动点，其中用1作为初始近似值：

(fixed-point cos 1.0)
.7390822985224023

类似地，我们也可以找出方程y＝sin y＋cos y的一个解：

(fixed-point (lambda (y) (+ (sin y) (cos y)))
             1.0)
1.2587315962971173

这一不动点的计算过程使人回忆起1.1.7节里用于找平方根的计算过程。两者都是基于同样的想法：通过不断地改进猜测，直至结果满足某一评价准则为止。事实上，我们完全可以将平方根的计算形式化为一个寻找不动点的计算过程。计算某个数x的平方根，就是要找到一个y使得y2＝x。将这一等式变成另一个等价形式y＝x/y，就可以发现，这里要做的就是寻找函数yx/y的不动点58。因此，可以用下面方式试着去计算平方根：

(define (sqrt x)
  (fixed-point (lambda (y) (/ x y))
               1.0))

遗憾的是，这一不动点搜寻并不收敛。考虑某个初始猜测y1，下一个猜测将是y2＝x/y1，而再下一个猜测是y3＝x/y2＝x/(x/y1)＝y1。结果是进入了一个无限循环，其中没完没了地反复出现两个猜测y1和y2，在答案的两边往复振荡。
控制这类振荡的一种方法是不让有关的猜测变化太剧烈。因为实际答案总是在两个猜测y和x/y之间，我们可以做出一个猜测，使之不像x/y那样远离y，为此可以用y和x/y的平均值。这样，我们就取y之后的下一个猜测值为 (1/2)(y＋x/y) 而不是x/y。做出这种猜测序列的计算过程也就是搜寻y (1/2)(y＋x/y) 的不动点：

(define (sqrt x)
  (fixed-point (lambda (y) (average y (/ x y)))
               1.0))

（请注意，y＝(1/2)(y＋x/y) 是方程y＝x/y经过简单变换的结果，导出它的方式是在方程两边都加y，然后将两边都除以2。）
经过这一修改，平方根过程就能正常工作了。事实上，如果我们仔细分析这一定义，那么就可以看到，它在求平方根时产生的近似值序列，正好就是1.1.7节原来那个求平方根过程产生的序列。这种取逼近一个解的一系列值的平均值的方法，是一种称为平均阻尼的技术，它常常用在不动点搜寻中，作为帮助收敛的手段。
练习1.35 请证明黄金分割率f（1.2.2节）是变换x1＋1/x的不动点。请利用这一事实，通过过程fixed-point计算出f的值。
练习1.36 请修改fixed-point，使它能打印出计算中产生的近似值序列，用练习1.22展示的newline和display基本过程。而后通过找出xlog(1000)/log(x) 的不动点的方式，确定xx＝1000的一个根（请利用Scheme的基本过程log，它计算自然对数值）。请比较一下采用平均阻尼和不用平均阻尼时的计算步数。（注意，你不能用猜测1去启动fixed-point，因为这将导致除以log(1)＝0。）
练习1.37 a) 一个无穷连分式是一个如下形式的表达式：

作为一个例子，我们可以证明在所有的Ni和Di都等于1时，这一无穷连分式产生出1/f，其中的f就是黄金分割率（见1.2.2节的描述）。逼近某个无穷连分式的一种方法是在给定数目的项之后截断，这样的一个截断称为k项有限连分式，其形式是：

假定n和d都是只有一个参数（项的下标i）的过程，它们分别返回连分式的项Ni和Di。请定义一个过程cont-frac，使得对（cont-frac n d k）的求值计算出k项有限连分式的值。通过如下调用检查你的过程对于顺序的k值是否逼近1/f：

(cont-frac (lambda (i) 1.0)
           (lambda (i) 1.0)
           k)

你需要取多大的k才能保证得到的近似值具有十进制的4位精度？
b) 如果你的过程产生一个递归计算过程，那么请写另一个产生迭代计算的过程。如果它产生迭代计算，请写出另一个过程，使之产生一个递归计算过程。
练习1.38 在1737年，瑞士数学家莱昂哈德·欧拉发表了一篇论文De Fractionibus Continuis，文中包含了e－2的一个连分式展开，其中的e是自然对数的底。在这一分式中，Ni全都是1，而Di依次为1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, …。请写出一个程序，其中使用你在练习1.37中所做的cont-frac过程，并能基于欧拉的展开式求出e的近似值。
练习1.39 正切函数的连分式表示由德国数学家J.H. Lambert在1770年发表：

其中的x用弧度表示。请定义过程（tan-cf x k），它基于Lambert公式计算正切函数的近似值。k描述的是计算的项数，就像练习1.37一样。

1.3.4 过程作为返回值

上面的例子说明，将过程作为参数传递，能够显著增强我们的程序设计语言的表达能力。通过创建另一种其返回值本身也是过程的过程，我们还能得到进一步的表达能力。
我们将阐释这一思想，现在还是先来看1.3.3节最后描述的不动点例子。在那里我们构造出一个平方根程序的新版本，它将这一计算看作一种不动点搜寻过程。开始时，我们注意到就是函数yx/y的不动点，而后又利用平均阻尼使这一逼近收敛。平均阻尼本身也是一种很有用的一般性技术。很自然，给定了一个函数 f 之后，我们就可以考虑另一个函数，它在x处的值等于x和 f（x）的平均值。
我们可以将平均阻尼的思想表述为下面的过程：

(define (average-damp f)
  (lambda (x) (average x (f x))))

这里的average-damp是一个过程，它的参数是一个过程f，返回值是另一个过程（通过lambda产生），当我们将这一返回值过程应用于数x时，得到的将是x和（f x）的平均值。例如，将average-damp应用于square过程，就会产生出另一个过程，它在数值x处的值就是x和x2的平均值。将这样得到的过程应用于10，将返回10与100的平均值55：

((average-damp square) 10)
55

利用average-damp，我们可以重做前面的平方根过程如下：

(define (sqrt x)
  (fixed-point (average-damp (lambda (y) (/ x y)))
               1.0))

请注意，看看上面这一公式中怎样把三种思想结合在同一个方法里：不动点搜寻，平均阻尼和函数yx/y。拿这一平方根计算的过程与1.1.7节给出的原来版本做一个比较，将是很有教益的。请记住，这些过程表述的是同一计算过程，也应注意，当我们利用这些抽象描述该计算过程时，其中的想法如何变得更加清晰了。将一个计算过程形式化为一个过程，一般说，存在很多不同的方式，有经验的程序员知道如何选择过程的形式，使其特别地清晰且易理解，使该计算过程中有用的元素能表现为一些相互分离的个体，并使它们还可能重新用于其他的应用。作为重用的一个简单实例，请注意x的立方根是函数yx/y^2的不动点，因此我们可以立刻将前面的平方根过程推广为一个提取立方根的过程：

(define (cube-root x)
  (fixed-point (average-damp (lambda (y) (/ x (square y))))
               1.0))

牛顿法
在1.1.7节介绍平方根过程时曾经提到牛顿法的一个特殊情况。如果xg(x) 是一个可微函数，那么方程g(x)＝0的一个解就是函数x f(x) 的一个不动点，其中：

这里的Dg(x) 是g对x的导数。牛顿法就是使用我们前面看到的不动点方法，通过搜寻函数 f 的不动点的方式，去逼近上述方程的解61。对于许多函数，以及充分好的初始猜测x，牛顿法都能很快收敛到g(x)＝0的一个解62。
为了将牛顿方法实现为一个过程，我们首先必须描述导数的思想。请注意，“导数”不像平均阻尼，它是从函数到函数的一种变换。例如，函数x x3的导数是另一个函数x 3x2。一般而言，如果g是一个函数而dx是一个很小的数，那么g的导数在任一数值x的值由下面函数（作为很小的数dx的极限）给出:

这样，我们就可以用下面过程描述导数的概念（例如取dx为0.00001）：

(define (deriv g)
  (lambda (x)
    (/ (- (g (+ x dx)) (g x))
       dx)))

再加上定义：

(define dx 0.00001)

与average-damp一样，deriv也是一个以过程为参数，并且返回一个过程值的过程。例如，为了求出函数x->x3在5的导数的近似值（其精确值为75），我们可以求值：

(define (cube x) (* x x x))
((deriv cube) 5)
75.00014999664018

有了deriv之后，牛顿法就可以表述为一个求不动点的过程了：

(define (newton-transform g)
  (lambda (x)
    (- x (/ (g x) ((deriv g) x)))))
(define (newtons-method g guess)
  (fixed-point (newton-transform g) guess))

newton-transform过程描述的就是在本节开始处的公式，基于它去定义newtons-method已经很容易了。这一过程以一个过程为参数，它计算的就是我们希望去找到零点的函数，这里还需要给出一个初始猜测。例如，为确定x的平方根，可以用初始猜测1，通过牛顿法去找函数y->y2－x的零点63。这样就给出了求平方根函数的另一种形式：

(define (sqrt x)
  (newtons-method (lambda (y) (- (square y) x))
                  1.0))

抽象和第一级过程
上面我们已经看到用两种方式，它们都能将平方根计算表述为某种更一般方法的实例，一个是作为不动点搜寻过程，另一个是使用牛顿法。因为牛顿法本身表述的也是一个不动点的计算过程，所以我们实际上看到了将平方根计算作为不动点的两种形式。每种方法都是从一个函数出发，找出这一函数在某种变换下的不动点。我们可以将这一具有普遍性的思想表述为一个函数：

(define (fixed-point-of-transform g transform guess)
  (fixed-point (transform g) guess))

这个非常具有一般性的过程有一个计算某个函数的过程参数g，一个变换g的过程，和一个初始猜测，它返回经过这一变换后的函数的不动点。
我们可以利用这一抽象重新塑造本节的第一个平方根计算（搜寻y->x/y在平均阻尼下的不动点），以它作为这个一般性方法的实例：

(define (sqrt x)
  (fixed-point-of-transform (lambda (y) (/ x y))
                            average-damp
                            1.0))

与此类似，我们也可以将本节的第二个平方根计算（是用牛顿法搜寻y y2－x的牛顿变换的实例）重新描述为：

(define (sqrt x)
  (fixed-point-of-transform (lambda (y) (- (square y) x))
                            newton-transform
                            1.0))

我们在1.3节开始时研究复合过程，并将其作为一种至关重要的抽象机制，因为它使我们能将一般性的计算方法，用这一程序设计语言里的元素明确描述。现在我们又看到，高阶函数能如何去操作这些一般性的方法，以便建立起进一步的抽象。
作为编程者，我们应该对这类可能性保持高度敏感，设法从中识别出程序里的基本抽象，基于它们去进一步构造，并推广它们以创建威力更加强大的抽象。当然，这并不是说总应该采用尽可能抽象的方式去写程序，程序设计专家们知道如何根据工作中的情况，去选择合适的抽象层次。但是，能基于这种抽象去思考确实是最重要的，只有这样才可能在新的上下文中去应用它们。高阶过程的重要性，就在于使我们能显式地用程序设计语言的要素去描述这些抽象，使我们能像操作其他计算元素一样去操作它们。
一般而言，程序设计语言总会对计算元素的可能使用方式强加上某些限制。带有最少限制的元素被称为具有第一级的状态。第一级元素的某些“权利或者特权”包括：

• 可以用变量命名；
• 可以提供给过程作为参数；
• 可以由过程作为结果返回；
• 可以包含在数据结构中65。

Lisp不像其他程序设计语言，它给了过程完全的第一级状态。这就给有效实现提出了挑战，但由此所获得的描述能力却是极其惊人的66。
练习1.40 请定义一个过程cubic，它和newtons-method过程一起使用在下面形式的表达式里：

(newtons-method (cubic a b c) 1)

能逼近三次方程x3＋ax2＋bx＋c的零点。
练习1.41 请定义一个过程double，它以一个有一个参数的过程作为参数，double返回一个过程。这一过程将原来那个参数过程应用两次。例如，若inc是个给参数加1的过程，（double inc）将给参数加2。下面表达式返回什么值：

(((double (double double)) inc) 5)

练习1.42 令 f 和g是两个单参数的函数，f 在g之后的复合定义为函数x f(g(x))。请定义一个函数compose实现函数复合。例如，如果inc是将参数加1的函数，那么：

((compose square inc) 6)
49

练习1.43 如果 f 是一个数值函数，n是一个正整数，那么我们可以构造出 f 的n次重复应用，将其定义为一个函数，这个函数在x的值是 f( f(…( f(x))…))。举例说，如果 f 是函数x x＋1，n次重复应用 f 就是函数x x＋n。如果 f 是求一个数的平方的操作，n次重复应用 f 就求出其参数的2n次幂。请写一个过程，它的输入是一个计算 f 的过程和一个正整数n，返回的是能计算 f 的n次重复应用的那个函数。你的过程应该能以如下方式使用：

((repeated square 2) 5)
625

提示：你可能发现使用练习1.42的compose能带来一些方便。
练习1.44 平滑一个函数的想法是信号处理中的一个重要概念。如果 f 是一个函数，dx是某个很小的数值，那么 f 的平滑也是一个函数，它在点x的值就是 f(x－dx)、f(x) 和 f(x＋dx) 的平均值。请写一个过程smooth，它的输入是一个计算 f 的过程，返回一个计算平滑后的 f 的过程。有时可能发现，重复地平滑一个函数，得到经过n次平滑的函数（也就是说，对平滑后的函数再做平滑，等等）也很有价值。说明怎样利用smooth和练习1.43的repeated，对给定的函数生成n次平滑函数。
练习1.45 在1.3.3节里，我们看到企图用朴素的方法去找y->x/y的不动点，以便计算平方根的方式不收敛，这个缺陷可以通过平均阻尼的方式弥补。同样方法也可用于找立方根，将它看作平均阻尼后的y->x/y^2的不动点。遗憾的是，这一计算过程对于四次方根却行不通，一次平均阻尼不足以使对y->x/y^3的不动点搜寻收敛。而另一方面，如果我们求两次平均阻尼（即，用y->x/y^3的平均阻尼的平均阻尼），这一不动点搜寻就会收敛了。请做一些试验，考虑将计算n次方根作为基于y->x/yn－1的反复做平均阻尼的不动点搜寻过程，请设法确定各种情况下需要做多少次平均阻尼。并请基于这一认识实现一个过程，它使用fixed-point、average-damp和练习1.43的repeated过程计算n次方根。假定你所需要的所有算术运算都是基本过程。
练习1.46 本章描述的一些数值算法都是迭代式改进的实例。迭代式改进是一种非常具有一般性的计算策略，它说的是：为了计算出某些东西，我们可以从对答案的某个初始猜测开始，检查这一猜测是否足够好，如果不行就改进这一猜测，将改进之后的猜测作为新的猜测去继续这一计算过程。请写一个过程iterative-improve，它以两个过程为参数：其中之一表示告知某一猜测是否足够好的方法，另一个表示改进猜测的方法。iterative-improve的返回值应该是一个过程，它以某一个猜测为参数，通过不断改进，直至得到的猜测足够好为止。利用iterative-improve重写1.1.7节的sqrt过程和1.3.3节的fixed-point过程。