丰富的线上&线下活动，深入探索云世界
做任务，得社区积分和周边
最真实的开发者用云体验
让每位学生受益于普惠算力
让创作激发创新
资深技术专家手把手带教
遇见技术追梦人
技术交流，直击现场
海量开发者使用工具、手册，免费下载
极速、全面、稳定、安全的开源镜像
开发手册、白皮书、案例集等实战精华
为开发者定制的Chrome浏览器插件
哈罗德阿贝尔森（HaroldAbelson）[美]杰拉尔德杰伊萨斯曼（GeraldJaySussman）著朱莉萨斯曼（JulieSussman）裘宗燕译
心智的活动，除了尽力产生各种简单的认识之外，主要表现在如下三个方面：1）将若干简单认识组合为一个复合认识，由此产生出各种复杂的认识。2）将两个认识放在一起对照，不管它们如何简单或者复杂，在这样做时并不将它们合而为一。由此得到有关它们的相互关系的认识。3）将有关认识与那些在实际中和它们同在的所有其他认识隔离开，这就是抽象，所有具有普遍性的认识都是这样得到的。JohnLocke,AnEssayConcerningHumanVnderstanding（有关人类理解的随笔，1690）
一个强有力的程序设计语言，不仅是一种指挥计算机执行任务的方式，它还应该成为一种框架，使我们能够在其中组织自己有关计算过程的思想。这样，当我们描述一个语言时，就需要将注意力特别放在这一语言所提供的，能够将简单的认识组合起来形成更复杂认识的方法方面。每一种强有力的语言都为此提供了三种机制：
在程序设计中，我们需要处理两类要素：过程和数据（以后读者将会发现，它们实际上并不是这样严格分离的）。非形式地说，数据是一种我们希望去操作的“东西”，而过程就是有关操作这些数据的规则的描述。这样，任何强有力的程序设计语言都必须能表述基本的数据和基本的过程，还需要提供对过程和数据进行组合和抽象的方法。本章只处理简单的数值数据，这就使我们可以把注意力集中到过程构造的规则方面4。在随后几章里我们将会看到，用于构造过程的这些规则同样也可以用于操作各种数据。
开始做程序设计，最简单方式就是去观看一些与Lisp方言Scheme解释器交互的典型实例。设想你坐在一台计算机的终端前，用键盘输入了一个表达式，解释器的响应就是将它对这一表达式的求值结果显示出来。你可以键入的一种基本表达式就是数（更准确地说，你键入的是由数字组成的表达式，它表示的是以10作为基数的数）。如果你给Lisp一个数486解释器的响应是打印出486可以用表示基本过程的表达形式（例如＋或者*），将表示数的表达式组合起来，形成复合表达式，以表示求要把有关过程应用于这些数。例如：
(+137349)486(-1000334)666(*599)495(/105)2(+2.710)12.7像上面这样的表达式称为组合式，其构成方式就是用一对括号括起一些表达式，形成一个表，用于表示一个过程应用。在表里最左的元素称为运算符，其他元素都称为运算对象。要得到这种组合式的值，采用的方式就是将由运算符所刻画的过程应用于有关的实际参数，而所谓实际参数也就是那些运算对象的值。将运算符放在所有运算对象左边，这种形式称为前缀表示。刚开始看到这种表示时会感到有些不习惯，因为它与常规数学表示差别很大。然而前缀表示也有一些优点，其中之一就是它完全适用于可能带有任意个实参的过程，例如在下面实例中的情况：
(+2135127)75(*25412)1200在这里不会出现歧义，因为运算符总是最左边的元素，而整个表达式的范围也由括号界定。前缀表示的第二个优点是它可以直接扩充，允许出现组合式嵌套的情况，也就是说，允许组合式的元素本身又是组合式：
(+(*35)(-106))19原则上讲，对于这种嵌套的深度，以及Lisp解释器可以求值的表达式的整体复杂性，都没有任何限制。倒是我们自己有可能被一些并不很复杂的表达式搞糊涂，例如：
(+(*3(+(*24)(+35)))(+(-107)6))对于这个表达式，解释器可以马上求值出57。将上述表达式写成下面的形式有助于阅读：
(+(*3(+(*24)(+35)))(+(-107)6))这就是遵循一种称为美观打印的格式规则。按照这种规则，在写一个很长的组合式时，我们令其中的各个运算对象垂直对齐。这样缩格排列的结果能很好地显示出表达式的结构。即使对于非常复杂的表达式，解释器也总是按同样的基本循环运作：从终端读入一个表达式，对这个表达式求值，而后打印出得到的结果。这种运作模式常常被人们说成是解释器运行在一个读入－求值－打印循环之中。请特别注意，在这里完全没有必要显式地去要求解释器打印表达式的值7。
size2(*5size)10下面是另外几个使用define的例子：
(definepi3.14159)(defineradius10)(*pi(*radiusradius))314.159(definecircumference(*2piradius))circumference62.8318define是我们所用的语言里最简单的抽象方法，它允许我们用一个简单的名字去引用一个组合运算的结果，例如上面算出的circumference。一般而言，计算得到的对象完全可以具有非常复杂的结构，如果每次需要使用它们时，都必须记住并重复地写出它们的细节，那将是极端不方便的事情。实际上，构造一个复杂的程序，也就是为了去一步步地创建出越来越复杂的计算性对象。解释器使这种逐步的程序构造过程变得非常方便，因为我们可以通过一系列交互式动作，逐步创建起所需要的名字－对象关联。这种特征鼓励人们采用递增的方式去开发和调试程序。在很大程度上，这一情况也出于另一个事实，那就是，一个Lisp程序通常总是由一大批相对简单的过程组成的。应该看到，我们可以将值与符号关联，而后又能提取出这些值，这意味着解释器必须维护某种存储能力，以便保持有关的名字-值对偶的轨迹。这种存储被称为环境（更精确地说，是全局环境，因为我们以后将看到，在一个计算过程中完全可能涉及若干不同环境）。
本章的一个目标，就是要把与过程性思维有关的各种问题隔离出来。现在让我们考虑组合式的求值问题。解释器本身就是按照下面过程工作的。
1)求值该组合式的各个子表达式。2)将作为最左子表达式（运算符）的值的那个过程应用于相应的实际参数，所谓实际参数也就是其他子表达式（运算对象）的值。即使是一条这样简单的规则，也显示出计算过程里的一些具有普遍性的重要问题。首先，由上面的第一步可以看到，为了实现对一个组合式的求值过程，我们必须先对组合式里的每个元素执行同样的求值过程。因此，在性质上，这一求值过程是递归的，也就是说，它在自己的工作步骤中，包含着调用这个规则本身的需要。在这里应该特别注意，采用递归的思想可以多么简洁地描述深度嵌套的情况。如果不用递归，我们就需要把这种情况看成相当复杂的计算过程。例如，对下列表达式求值：
(*(+2(*46))(+357))需要将求值规则应用于4个不同的组合式。如图1-1中所示，我们可以采用一棵树的形式，用图形表示这一组合式的求值过程，其中的每个组合式用一个带分支的结点表示，由它发出的分支对应于组合式里的运算符和各个运算对象。终端结点（即那些不再发出分支的结点）表示的是运算符或者数值。以树的观点看这种求值过程，可以设想那些运算对象的值向上穿行，从终端结点开始，而后在越来越高的层次中组合起来。一般而言，我们应该把递归看作一种处理层次性结构的（像树这样的对象）极强有力的技术。事实上，“值向上穿行”形式的求值形式是一类更一般的计算过程的一个例子，这种计算过程称为树形积累。进一步的观察告诉我们，反复地应用第一个步骤，总可以把我们带到求值中的某一点，在这里遇到的不是组合式而是基本表达式，例如数、内部运算符或者其他名字。处理这些基础情况的方式如下规定：
我们可以将第二种规定看作是第三种规定的特殊情况，为此只需将像＋和*一类的运算符也包含在全局环境里，并将相应的指令序列作为与之关联的“值”。对于初学者，应该指出的关键一点是，环境所扮演的角色就是用于确定表达式中各个符号的意义。在如Lisp这样的交互式语言里，如果没有关于有关环境的任何信息，那么说例如表达式（＋x1）的值是毫无意义的，因为需要有环境为符号x提供意义（甚至需要它为符号＋提供意义）。正如我们将要在第3章看到的，环境是具有普遍性的概念，它为求值过程的进行提供了一种上下文，对于我们理解程序的执行起着极其重要的作用。请注意，上面给出的求值规则里并没有处理定义。例如，对（definex3）的求值并不是将define应用于它的两个实际参数：其中的一个是符号x的值，另一个是3。这是因为define的作用就是为x关联一个值（也就是说，（definex3）并不是一个组合式）。
我们已经看到了Lisp里的某些元素，它们必然也会出现在任何一种强有力的程序设计语言里。这些东西包括：
现在我们来学习过程定义，这是一种威力更加强大的抽象技术，通过它可以为复合操作提供名字，而后就可以将这样的操作作为一个单元使用了。现在我们要考察如何表述“平方”的想法。我们可能想说“求某个东西的平方，就是用它自身去乘以它自身”。在这个语言里，这件事情应该表述为：
(define(squarex)(*xx))可以按如下方式理解这一描述：
(square21)441(square(+25))49(square(square3))81我们还可以用square作为基本构件去定义其他过程。例如，x2＋y2可以表述为：
(+(squarex)(squarey))现在我们很容易定义一个过程sum-of-squares，给它两个数作为实际参数，让它产生这两个数的平方和：
(define(sum-of-squaresxy)(+(squarex)(squarey)))(sum-of-squares34)25现在我们又可以用sum-of-squares作为构件，进一步去构造其他过程：
(define(fa)(sum-of-squares(+a1)(*a2)))(f5)136复合过程的使用方式与基本过程完全一样。实际上，如果人们只看上面sum-of-squares的定义，根本就无法分辨出square究竟是（像＋和*那样）直接做在解释器里呢，还是被定义为一个复合过程。
为了求值一个组合式（其运算符是一个复合过程的名字），解释器的工作方式将完全按照1.1.3节中所描述的那样，采用与以运算符名为基本过程的组合式一样的计算过程。也就是说，解释器将对组合式的各个元素求值，而后将得到的那个过程（也就是该组合式里运算符的值）应用于那些实际参数（即组合式里那些运算对象的值）。我们可以假定，把基本运算符应用于实参的机制已经在解释器里做好了。对于复合过程，过程应用的计算过程是：
为了说明这种计算过程，让我们看看下面组合式的求值：(f5)其中的f是1.1.4节定义的那个过程。我们首先提取出f的体：
(sum-of-squares(+a1)(*a2))而后用实际参数5代换其中的形式参数：
(sum-of-squares(+51)(*52))这样，问题就被归约为对另一个组合式的求值，其中有两个运算对象，有关的运算符是sum-of-squares。求值这一组合式牵涉三个子问题：我们必须对其中的运算符求值，以便得到应该去应用的那个过程；还需要求值两个运算对象，以得到过程的实际参数。这里的（＋51）产生出6，（*52）产生出10，因此我们就需要将sum-of-squares过程用于6和10。用这两个值代换sum-of-squares体中的形式参数x和y，表达式被归约为：
(+(square6)(square10))使用square的定义又可以将它归约为：
(+(*66)(*1010))通过乘法又能将它进一步归约为：
(+36100)最后得到：
136上面描述的这种计算过程称为过程应用的代换模型，在考虑本章至今所定义的过程时，我们可以将它看作确定过程应用的“意义”的一种模型。但这里还需要强调两点：
应用序和正则序按照1.1.3节给出的有关求值的描述，解释器首先对运算符和各个运算对象求值，而后将得到的过程应用于得到的实际参数。然而，这并不是执行求值的唯一可能方式。另一种求值模型是先不求出运算对象的值，直到实际需要它们的值时再去做。采用这种求值方式，我们就应该首先用运算对象表达式去代换形式参数，直至得到一个只包含基本运算符的表达式，然后再去执行求值。如果我们采用这一方式，对下面表达式的求值：
(f5)将按照下面的序列逐步展开：
(sum-of-squares(+51)(*52))(+(square(+51))(square(*52)))(+(*(+51)(+51))(*(*52)(*52)))而后是下面归约：
(+(*66)(*1010))(+36100)136这给出了与前面求值模型同样的结果，但其中的计算过程却是不一样的。特别地，在对下面表达式的归约中，对于（＋51）和（*52）的求值各做了两次：
(*xx)其中的x分别被代换为（＋51）和（*52）。这种“完全展开而后归约”的求值模型称为正则序求值，与之对应的是现在解释器里实际使用的“先求值参数而后应用”的方式，它称为应用序求值。可以证明，对那些可以通过替换去模拟，并能产生出合法值的过程应用（包括本书前两章中的所有过程），正则序和应用序求值将产生出同样的值（参见练习1.5中一个“非法”值的例子，其中正则序和应用序将给出不同的结果）。Lisp采用应用序求值，部分原因在于这样做能避免对于表达式的重复求值（例如上面的（＋51）和（*52）的情况），从而可以提高一些效率。更重要的是，在超出了可以采用替换方式模拟的过程范围之后，正则序的处理将变得更复杂。而在另一些方面，正则序也可以成为特别有价值的工具，我们将在第3章和第4章研究它的某些内在性质16。
至此我们能定义出的过程类的表达能力还非常有限，因为还没办法去做某些检测，而后依据检测的结果去确定做不同的操作。例如，我们还无法定义一个过程，使它能计算出一个数的绝对值。完成此事需要先检查一个数是正的、负的或者零，而后依据遇到的不同情况，按照下面规则采取不同的动作：
这种结构称为一个分情况分析，在Lisp里有着一种针对这类分情况分析的特殊形式，称为cond（表示“条件”）。其使用形式如下：
(define(absx)(if( (and(>x5)( (define(>=xy)(or(>xy)(=xy)))或者也可以定义为： (define(>=xy)(not( 练习1.3请定义一个过程，它以三个数为参数，返回其中较大的两个数之和。 练习1.4请仔细考察上面给出的允许运算符为复合表达式的组合式的求值模型，根据对这一模型的认识描述下面过程的行为： (define(a-plus-abs-bab)((if(>b0)+-)ab))练习1.5BenBitdiddle发明了一种检测方法，能够确定解释器究竟采用哪种序求值，是采用应用序，还是采用正则序。他定义了下面两个过程： (define(p)(p))(define(testxy)(if(=x0)0y))而后他求值下面的表达式： (test0(p))如果某个解释器采用的是应用序求值，Ben会看到什么样的情况？如果解释器采用正则序求值，他又会看到什么情况？请对你的回答做出解释。（无论采用正则序或者应用序，假定特殊形式if的求值规则总是一样的。其中的谓词部分先行求值，根据其结果确定随后求值的子表达式部分。） (define(sqrt-iterguessx)(if(good-enough-guessx)guess(sqrt-iter(improveguessx)x)))改进猜测的方式就是求出它与被开方数除以上一个猜测的平均值： (define(improveguessx)(averageguess(/xguess)))其中 (define(averagexy)(/(+xy)2))我们还必须说明什么叫作“足够好”。下面的做法只是为了说明问题，它确实不是一个很好的检测方法（参见练习1.7）。这里的想法是，不断改进答案直至它足够接近平方根，使得其平方与被开方数之差小于某个事先确定的误差值（这里用的是0.001）： (define(good-enough-guessx)(<(abs(-(squareguess)x))0.001))最后还需要一种方式来启动整个工作。例如，我们可以总用1作为对任何数的初始猜测值： (define(sqrtx)(sqrt-iter1.0x))如果把这些定义都送给解释器，我们就可以使用sqrt了，就像可以使用其他过程一样： (sqrt9)3.00009155413138(sqrt(+10037))11.704699917758145(sqrt(+(sqrt2)(sqrt3)))1.7739279023207892(square(sqrt1000))1000.000369924366这个sqrt程序也说明，在用于写纯粹的数值计算程序时，至今已介绍的简单程序设计语言已经足以写出可以在其他语言（例如C或者Pascal）中写出的任何东西了。这看起来很让人吃惊，因为这一语言中甚至还没有包括任何迭代结构（循环），它们用于指挥计算机去一遍遍地做某些事情。而另一方面，sqrt-iter展示了如何不用特殊的迭代结构来实现迭代，其中只需要使用常规的过程调用能力24。练习1.6AlyssaP.Hacker看不出为什么需要将if提供为一种特殊形式，她问：“为什么我不能直接通过cond将它定义为一个常规过程呢？”Alyssa的朋友EvaLuAtor断言确实可以这样做，并定义了if的一个新版本： (define(new-ifpredicatethen-clauseelse-clause)(cond(predicatethen-clause)(elseelse-clause)))Eva给Alyssa演示她的程序： (new-if(=23)05)5(new-if(=11)05)0她很高兴地用自己的new-if重写了求平方根的程序： (define(sqrt-iterguessx)(new-if(good-enough-guessx)guess(sqrt-iter(improveguessx)x)))当Alyssa试着用这个过程去计算平方根时会发生什么事情呢？请给出解释。 练习1.7对于确定很小的数的平方根而言，在计算平方根中使用的检测good-enough是很不好的。还有，在现实的计算机里，算术运算总是以一定的有限精度进行的。这也会使我们的检测不适合非常大的数的计算。请解释上述论断，用例子说明对很小和很大的数，这种检测都可能失败。实现good-enough的另一种策略是监视猜测值在从一次迭代到下一次的变化情况，当改变值相对于猜测值的比率很小时就结束。请设计一个采用这种终止测试方式的平方根过程。对于很大和很小的数，这一方式都能工作吗？ 练习1.8求立方根的牛顿法基于如下事实，如果y是x的立方根的一个近似值，那么下式将给出一个更好的近似值： 请利用这一公式实现一个类似平方根过程的求立方根的过程。（在1.3.4节里，我们将看到如何实现一般性的牛顿法，作为这些求平方根和立方根过程的抽象。） sqrt是我们用一组手工定义的过程来实现一个计算过程的第一个例子。请注意，在这里sqrt-iter的定义是递归的，也就是说，这一过程的定义基于它自身。能够基于一个过程自身来定义它的想法很可能会令人感到不安，人们可能觉得它不够清晰，这种“循环”定义怎么能有意义呢？是不是完全刻画了一个能够由计算机实现的计算过程呢？在1.2节里，我们将更细致地讨论这一问题。现在首先来看看sqrt实例所显示出的其他一些要点。可以看到，对于平方根的计算问题可以自然地分解为若干子问题：怎样说一个猜测是足够好了，怎样去改进一个猜测，等等。这些工作中的每一个都通过一个独立的过程完成，整个sqrt程序可以看作一族过程（如图1-2所示），它们直接反映了从原问题到子问题的分解。 (define(squarex)(*xx))(define(squarex)(exp(double(logx))))(define(doublex)(+xx))由此可见，一个过程定义应该能隐藏起一些细节。这将使过程的使用者可能不必自己去写这些过程，而是从其他程序员那里作为一个黑箱而接受了它。用户在使用一个过程时，应该不需要去弄清它是如何实现的。局部名过程用户不必去关心的实现细节之一，就是在有关的过程里面形式参数的名字，这是由实现者所选用的。也就是说，下面两个过程定义应该是无法区分的： (define(squarex)(*xx))(define(squarey)(*yy))这一原则（过程的意义应该不依赖于其作者为形式参数所选用的名字）从表面看起来很明显，但其影响却非常深远。最直接的影响是，过程的形式参数名必须局部于有关的过程体。例如，我们在前面平方根程序中的good-enough定义里使用了square： (define(sqrtx)(sqrt-iter1.0x))(define(sqrt-iterguessx)(if(good-enough-guessx)guess(sqrt-iter(improveguessx)x)))(define(good-enough-guessx)(<(abs(-(squareguess)x))0.001))(define(improveguessx)(averageguess(/xguess)))问题是，在这个程序里只有一个过程对用户是重要的，那就是，这里所定义的sqrt确实是sqrt。其他的过程（sqrt-iter、good-enough和improve）则只会干扰他们的思维，因为他们再也不能定义另一个称为good-enough的过程，作为需要与平方根程序一起使用的其他程序的一部分了，因为现在sqrt需要它。在许多程序员一起构造大系统的时候，这一问题将会变得非常严重。举例来说，在构造一个大型的数值过程库时，许多数值函数都需要计算出一系列的近似值，因此我们就可能希望有一些名字为good-enough和improve的过程作为其中的辅助过程。由于这些情况，我们也希望将这个种子过程局部化，将它们隐藏到sqrt里面，以使sqrt可以与其他采用逐步逼近的过程共存，让它们中的每一个都有自己的good-enough-过程。为了使这一方式成为可能，我们要允许一个过程里带有一些内部定义，使它们是局部于这一过程的。例如，在解决平方根问题时，我们可以写： (define(sqrtx)(define(good-enough-guessx)(<(abs(-(squareguess)x))0.001))(define(improveguessx)(averageguess(/xguess)))(define(sqrt-iterguessx)(if(good-enough-guessx)guess(sqrt-iter(improveguessx)x)))(sqrt-iter1.0x))这种嵌套的定义称为块结构，它是最简单的名字包装问题的一种正确解决方式。实际上，在这里还潜藏着一个很好的想法。除了可以将所用的辅助过程定义放到内部，我们还可能简化它们。因为x在sqrt的定义中是受约束的，过程good-enough、improve和sqrt-iter也都定义在sqrt里面，也就是说，都在x的定义域里。这样，显式地将x在这些过程之间传来传去也就没有必要了。我们可以让x作为内部定义中的自由变量，如下所示。这样，在外围的sqrt被调用时，x由实际参数得到自己的值。这种方式称为词法作用域。 (define(sqrtx)(define(good-enough-guess)(<(abs(-(squareguess)x))0.001))(define(improveguess)(averageguess(/xguess)))(define(sqrt-iterguess)(if(good-enough-guess)guess(sqrt-iter(improveguess))))(sqrt-iter1.0))下面将广泛使用这种块结构，以帮助我们将大程序分解成一些容易把握的片段28。块结构的思想来自程序设计语言Algol60，这种结构出现在各种最新的程序设计语言里，是帮助我们组织大程序的结构的一种重要工具。 首先考虑由下面表达式定义的阶乘函数： 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(factorialn)(if(=n1)1(*n(factorial(-n1)))))我们可以利用1.1.5节介绍的代换模型，观看这一过程在计算6!时表现出的行为，如图1-3所示。现在让我们采用另一种不同的观点来计算阶乘。我们可以将计算阶乘n!的规则描述为：先乘起1和2，而后将得到的结果乘以3，而后再乘以4，这样下去直到达到n。更形式地说，我们要维持着一个变动中的乘积product，以及一个从1到n的计数器counter，这一计算过程可以描述为counter和product的如下变化，从一步到下一步，它们都按照下面规则改变： product←counter·productcounter←counter+1可以看到，n!也就是计数器counter超过n时乘积product的值。我们又可以将这一描述重构为一个计算阶乘的过程： (define(factorialn)(fact-iter11n))(define(fact-iterproductcountermax-count)(if(>countermax-count)product(fact-iter(*counterproduct)(+counter1)max-count)))与前面一样，我们也可以应用替换模型来查看6!的计算过程，如图1-4所示。 (define(+ab)(if(=a0)b(inc(+(deca)b))))(define(+ab)(if(=a0)b(+(deca)(incb))))请用代换模型展示这两个过程在求值（＋45）时所产生的计算过程。这些计算过程是递归的或者迭代的吗？练习1.10下面过程计算一个称为Ackermann函数的数学函数： (define(Axy)(cond((=y0)0)((=x0)(*2y))((=y1)2)(else(A(-x1)(Ax(-y1))))))下面各表达式的值是什么： (A110)(A24)(A33)请考虑下面的过程，其中的A就是上面定义的过程： (define(fn)(A0n))(define(gn)(A1n))(define(hn)(A2n))(define(kn)(*5nn))请给出过程f、g和h对给定整数值n所计算的函数的数学定义。例如，（kn）计算的是5n2。 另一种常见计算模式称为树形递归。作为例子，现在考虑斐波那契（Fibonacci）数序列的计算，这一序列中的每个数都是前面两个数之和：0,1,1,2,3,5,8,13,21,…一般说，斐波那契数由下面规则定义： 我们马上就可以将这个定义翻译为一个计算斐波那契数的递归过程： (define(fibn)(cond((=n0)0)((=n1)1)(else(+(fib(-n1))(fib(-n2))))))考虑这一计算的模式。为了计算（fib5），我们需要计算出（fib4）和（fib3）。而为了计算（fib4），又需要计算（fib3）和（fib2）。一般而言，这一展开过程看起来像一棵树，如图1-5所示。请注意，这里的每层分裂为两个分支（除了最下面），反映出对fib过程的每个调用中两次递归调用自身的事实。 要问为什么这一说法是对的，请注意这里将换零钱分成两组时所采用的方式，第一组里都没有使用第一种硬币，而第二组里都使用了第一种硬币。显然，换成零钱的全部方式的数目，就等于完全不用第一种硬币的方式的数目，加上用了第一种硬币的换零钱方式的数目。而后一个数目也就等于去掉一个第一种硬币值后，剩下的现金数的换零钱方式数目。这样就可以将某个给定现金数的换零钱方式的问题，递归地归约为对更少现金数或者更少种类硬币的同一个问题。仔细考虑上面的归约规则，设法使你确信，如果采用下面方式处理退化情况，我们就能利用上面规则写出一个算法来33： 我们很容易将这些描述翻译为一个递归过程： (define(count-changeamount)(ccamount5))(define(ccamountkinds-of-coins)(cond((=amount0)1)((or( (define(cubex)(*xxx))(define(px)(-(*3x)(*4(cubex))))(define(sineangle)(if(not(>(absangle)0.1))angle(p(sine(/angle3.0)))))a)在求值（sine12.15）时，p将被使用多少次？b)在求值（sinea）时，由过程sine所产生的计算过程使用的空间和步数（作为a的函数）增长的阶是什么？ (define(exptbn)(if(=n0)1(*b(exptb(-n1)))))这是一个线性的递归计算过程，需要Θ(n)步和Θ(n)空间。就像阶乘一样，我们很容易将其形式化为一个等价的线性迭代： 这一方法可以定义为如下的过程： (define(fast-exptbn)(cond((=n0)1)((evenn)(square(fast-exptb(/n2))))(else(*b(fast-exptb(-n1))))))其中检测一个整数是否偶数的谓词可以基于基本过程remainder定义： (define(smallest-divisorn)(find-divisorn2))(define(find-divisorntest-divisor)(cond((>(squaretest-divisor)n)n)((dividestest-divisorn)test-divisor)(else(find-divisorn(+test-divisor1)))))(define(dividesab)(=(remainderba)0))我们可以用如下方式检查一个数是否素数：n是素数当且仅当它是自己的最小因子： (define(expmodbaseexpm)(cond((=exp0)1)((evenexp)(remainder(square(expmodbase(/exp2)m))m))(else(remainder(*base(expmodbase(-exp1)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-testn)(define(try-ita)(=(expmodann)a))(try-it(+1(random(-n1)))))下面这个过程的参数是某个数，它将按照由另一参数给定的次数运行上述检查。如果每次检查都成功，这一过程的值就是真，否则就是假： (define(expmodbaseexpm)(remainder(fast-exptbaseexp)m))她说的对吗？这一过程能很好地用于我们的快速素数检查程序吗？请解释这些问题。练习1.26LouisReasoner在做练习1.24时遇到了很大困难，他的fast-prime检查看起来运行得比他的prime检查还慢。Louis请他的朋友EvaLuAtor过来帮忙。在检查Louis的代码时，两个人发现他重写了expmod过程，其中用了一个显式的乘法，而没有调用square： 我们已经看到，在作用上，过程也就是一类抽象，它们描述了一些对于数的复合操作，但又并不依赖于特定的数。例如，在定义： (define(cubex)(*xxx))时，我们讨论的并不是某个特定数值的立方，而是对任意的数得到其立方的方法。当然，我们也完全可以不去定义这一过程，而总是写出下面这样的表达式： (*333)(*xxx)(*yyy)并不明确地提出cube。但是，这样做将把自己置于一个非常糟糕的境地，迫使我们永远在语言恰好提供了的那些特定基本操作（例如这里的乘法）的层面上工作，而不能基于更高级的操作去工作。我们写出的程序也能计算立方，但是所用的语言却不能表述立方这一概念。人们对功能强大的程序设计语言有一个必然要求，就是能为公共的模式命名，建立抽象，而后直接在抽象的层次上工作。过程提供了这种能力，这也是为什么除最简单的程序语言外，其他语言都包含定义过程的机制的原因。然而，即使在数值计算过程中，如果将过程限制为只能以数作为参数，那也会严重地限制我们建立抽象的能力。经常有一些同样的程序设计模式能用于若干不同的过程。为了把这种模式描述为相应的概念，我们就需要构造出这样的过程，让它们以过程作为参数，或者以过程作为返回值。这类能操作过程的过程称为高阶过程。本节将展示高阶过程如何能成为强有力的抽象机制，极大地增强语言的表述能力。 考虑下面的三个过程，第一个计算从a到b的各整数之和： (define(sum-integersab)(if(>ab)0(+a(sum-integers(+a1)b))))第二个计算给定范围内的整数的立方之和： (define(pi-sumab)(if(>ab)0(+(/1.0(*a(+a2)))(pi-sum(+a4)b))))可以明显看出，这三个过程共享着一种公共的基础模式。它们的很大一部分是共同的，只在所用的过程名字上不一样：用于从a算出需要加的项的函数，还有用于提供下一个a值的函数。我们可以通过填充下面模板中的各空位，产生出上面的各个过程： (define( 用于描述这一概念。求和记法的威力在于它使数学家能去处理求和的概念本身，而不只是某个特定的求和—例如，借助它去形式化某些并不依赖于特定求和序列的求和结果。与此类似，作为程序模式，我们也希望所用的语言足够强大，能用于写出一个过程，去表述求和的概念，而不是只能写计算特定求和的过程。我们确实可以在所用的过程语言中做到这些，只要按照上面给出的模式，将其中的“空位”翻译为形式参数： (define(sumtermanextb)(if(>ab)0(+(terma)(sumterm(nexta)nextb))))请注意，sum仍然以作为下界和上界的参数a和b为参数，但是这里又增加了过程参数term和next。使用sum的方式与其他函数完全一样。例如，我们可以用它去定义sum-cubes（还需要一个过程inc，它得到参数值加一）： (define(incn)(+n1))(define(sum-cubesab)(sumcubeaincb))我们可以用这个过程算出从1到10的立方和： (sum-cubes110)3025利用一个恒等函数帮助算出项值，我们就可以基于sum定义出sum-integers： (define(identityx)x)(define(sum-integersab)(sumidentityaincb))而后就可以求出从1到10的整数之和了： (sum-integers110)55我们也可以按同样方式定义pi-sum50： (define(pi-sumab)(define(pi-termx)(/1.0(*x(+x2))))(define(pi-nextx)(+x4))(sumpi-termapi-nextb))利用这一过程就能计算出π的一个近似值了: (*8(pi-sum11000))3.139592655589783一旦有了sum，我们就能用它作为基本构件，去形式化其他概念。例如，求出函数f在范围a和b之间的定积分的近似值，可以用下面公式完成 其中的dx是一个很小的值。我们可以将这个公式直接描述为一个过程： b)如果你的product过程生成的是一个递归计算过程，那么请写出一个生成迭代计算过程的过程。如果它生成一个迭代计算过程，请写一个生成递归计算过程的过程。练习1.32a)请说明，sum和product（练习1.31）都是另一称为accumulate的更一般概念的特殊情况，accumulate使用某些一般性的累积函数组合起一系列项： (accumulatecombinernull-valuetermanextb)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.1节里用sum时，我们必须定义出一些如pi-term和pi-next一类的简单函数，以便用它们作为高阶函数的参数，这种做法看起来很不舒服。如果不需要显式定义pi-term和pi-next，而是有一种方法去直接刻画“那个返回其输入值加4的过程”和“那个返回其输入与它加2的乘积的倒数的过程”，事情就会方便多了。我们可以通过引入一种lambda特殊形式完成这类描述，这种特殊形式能够创建出所需要的过程。利用lambda，我们就能按照如下方式写出所需的东西： (lambda(x)(+x4))和 (lambda(x)(/1.0(*x(+x2))))这样就可以直接描述pi-sum过程，而无须定义任何辅助过程了： (define(pi-sumab)(sum(lambda(x)(/1.0(*x(+x2))))a(lambda(x)(+x4))b))借助于lambda，我们也可以写出integral过程而不需要定义辅助过程add-dx： (define(integralfabdx)(*(sumf(+a(/dx2.0))(lambda(x)(+xdx))b)dx))一般而言，lambda用与define同样的方式创建过程，除了不为有关过程提供名字之外： (define(plus4x)(+x4))等价于 (defineplus4(lambda(x)(+x4)))我们可以按如下方式来阅读lambda表达式： (lambda(x)(+x4))↑↑↑↑↑该过程以x为参数它加起x和4像任何以过程为值的表达式一样，lambda表达式可用作组合式的运算符，例如： ((lambda(xyz)(+xy(squarez)))123)12或者更一般些，可以用在任何通常使用过程名的上下文中53。用let创建局部变量lambda的另一个应用是创建局部变量。在一个过程里，除了使用那些已经约束为过程参数的变量外，我们常常还需要另外一些局部变量。例如，假定我们希望计算函数： f(x,y)＝x(1＋xy)2＋y(1－y)＋(1＋xy)(1－y)可能就希望将它表述为： 在写计算f的过程时，我们可能希望还有几个局部变量，不只是x和y，还有中间值的名字如a和b。做到这些的一种方式就是利用辅助过程去约束局部变量： (define(fxy)(define(f-helperab)(+(*x(squarea))(*yb)(*ab)))(f-helper(+1(*xy))(-1y)))当然，我们也可以用一个lambda表达式，用以描述约束局部变量的匿名过程。这样，f的体就变成了一个简单的对该过程的调用： (define(fxy)((lambda(ab)(+(*x(squarea))(*yb)(*ab)))(+1(*xy))(-1y)))这一结构非常有用，因此，语言里有一个专门的特殊形式称为let，使这种编程方式更为方便。利用let，过程f可以写为： (define(fxy)(let((a(+1(*xy)))(b(-1y)))(+(*x(squarea))(*yb)(*ab))))let表达式的一般形式是： (let(( 令 ((lambda( (+(let((x3))(+x(*x10)))x)就是38。在这里，位于let体里的x是3，因此这一let表达式的值是33。另一方面，作为最外层的＋的第二个参数的x仍然是5。变量的值是在let之外计算的。在为局部变量提供值的表达式依赖于某些与局部变量同名的变量时，这一规定就起作用了。例如，如果x的值是2，表达式： (let((x3)(y(+x2)))(*xy))将具有值12，因为在这里let的体里，x将是3而y是4（其值是外面的x加2）。有时我们也可以通过内部定义得到与let同样的效果。例如可以将上述f定义为： (define(fxy)(definea(+1(*xy)))(defineb(-1y))(+(*x(squarea))(*yb)(*ab)))当然，在这种情况下我们更愿意用let，而仅将define用于内部过程54。练习1.34假定我们定义了： (define(fg)(g2))而后就有： (fsquare)4(f(lambda(z)(*z(+z1))))6如果我们（坚持）要求解释器去求值（ff），那会发生什么情况呢？请给出解释。 (define(searchfneg-pointpos-point)(let((midpoint(averageneg-pointpos-point)))(if(close-enoughneg-pointpos-point)midpoint(let((test-value(fmidpoint)))(cond((positivetest-value)(searchfneg-pointmidpoint))((negativetest-value)(searchfmidpointpos-point))(elsemidpoint))))))假定开始时给定了函数f，以及使它取值为负和为正的两个点。我们首先算出两个给定点的中点，而后检查给定区间是否已经足够小。如果是的话，就返回这一中点的值作为回答；否则就算出f在这个中点的值。如果检查发现得到的这个值为正，那么就以从原来负点到中点的新区间继续下去；如果这个值为负，就以中点到原来为正的点为新区间并继续下去。还有，也存在着检测值恰好为0的可能性，这时中点就是我们所寻找的根。为了检查两个端点是否“足够接近”，我们可以用一个过程，它与1.1.7节计算平方根时所用的那个过程很类似： (define(close-enoughxy)(<(abs(-xy))0.001))search很难直接去用，因为我们可能会偶然地给了它一对点，相应的f值并不具有这个过程所需的正负号，这时就会得到错误的结果。让我们换一种方式，通过下面的过程去用search，这一过程检查是否某个点具有负的函数值，另一个点是正值，并根据具体情况去调用search过程。如果这一函数在两个给定点的值同号，那么就无法使用折半方法，在这种情况下过程发出错误信号。 (define(half-interval-methodfab)(let((a-value(fa))(b-value(fb)))(cond((and(negativea-value)(positiveb-value))(searchfab))((and(negativeb-value)(positivea-value))(searchfba))(else(error"Valuesarenotofoppositesign"ab)))))下面实例用折半方法求π的近似值，它正好是sinx＝0在2和4之间的根： (half-interval-methodsin2.04.0)3.14111328125这里是另一个例子，用折半方法找出x3－2x－3＝0在1和2之间的根： (half-interval-method(lambda(x)(-(*xxx)(*2x)3))1.02.0)1.89306640625找出函数的不动点数x称为函数f的不动点，如果x满足方程f(x)＝x。对于某些函数，通过从某个初始猜测出发，反复地应用f f(x),f(f(x)),f(f(f(x))),... 直到值的变化不大时，就可以找到它的一个不动点。根据这个思路，我们可以设计出一个过程fixed-point，它以一个函数和一个初始猜测为参数，产生出该函数的一个不动点的近似值。我们将反复应用这个函数，直至发现连续的两个值之差小于某个事先给定的容许值： (definetolerance0.00001)(define(fixed-pointffirst-guess)(define(close-enoughv1v2)(<(abs(-v1v2))tolerance))(define(tryguess)(let((next(fguess)))(if(close-enoughguessnext)next(trynext))))(tryfirst-guess))例如，下面用这一方法求出的是余弦函数的不动点，其中用1作为初始近似值： (fixed-pointcos1.0).7390822985224023类似地，我们也可以找出方程y＝siny＋cosy的一个解： (fixed-point(lambda(y)(+(siny)(cosy)))1.0)1.2587315962971173这一不动点的计算过程使人回忆起1.1.7节里用于找平方根的计算过程。两者都是基于同样的想法：通过不断地改进猜测，直至结果满足某一评价准则为止。事实上，我们完全可以将平方根的计算形式化为一个寻找不动点的计算过程。计算某个数x的平方根，就是要找到一个y使得y2＝x。将这一等式变成另一个等价形式y＝x/y，就可以发现，这里要做的就是寻找函数yx/y的不动点58。因此，可以用下面方式试着去计算平方根： (define(sqrtx)(fixed-point(lambda(y)(/xy))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(sqrtx)(fixed-point(lambda(y)(averagey(/xy)))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.37a)一个无穷连分式是一个如下形式的表达式： 作为一个例子，我们可以证明在所有的Ni和Di都等于1时，这一无穷连分式产生出1/f，其中的f就是黄金分割率（见1.2.2节的描述）。逼近某个无穷连分式的一种方法是在给定数目的项之后截断，这样的一个截断称为k项有限连分式，其形式是： 假定n和d都是只有一个参数（项的下标i）的过程，它们分别返回连分式的项Ni和Di。请定义一个过程cont-frac，使得对（cont-fracndk）的求值计算出k项有限连分式的值。通过如下调用检查你的过程对于顺序的k值是否逼近1/f： (cont-frac(lambda(i)1.0)(lambda(i)1.0)k)你需要取多大的k才能保证得到的近似值具有十进制的4位精度？b)如果你的过程产生一个递归计算过程，那么请写另一个产生迭代计算的过程。如果它产生迭代计算，请写出另一个过程，使之产生一个递归计算过程。练习1.38在1737年，瑞士数学家莱昂哈德·欧拉发表了一篇论文DeFractionibusContinuis，文中包含了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-cfxk），它基于Lambert公式计算正切函数的近似值。k描述的是计算的项数，就像练习1.37一样。 上面的例子说明，将过程作为参数传递，能够显著增强我们的程序设计语言的表达能力。通过创建另一种其返回值本身也是过程的过程，我们还能得到进一步的表达能力。我们将阐释这一思想，现在还是先来看1.3.3节最后描述的不动点例子。在那里我们构造出一个平方根程序的新版本，它将这一计算看作一种不动点搜寻过程。开始时，我们注意到就是函数yx/y的不动点，而后又利用平均阻尼使这一逼近收敛。平均阻尼本身也是一种很有用的一般性技术。很自然，给定了一个函数f之后，我们就可以考虑另一个函数，它在x处的值等于x和f（x）的平均值。我们可以将平均阻尼的思想表述为下面的过程： (define(average-dampf)(lambda(x)(averagex(fx))))这里的average-damp是一个过程，它的参数是一个过程f，返回值是另一个过程（通过lambda产生），当我们将这一返回值过程应用于数x时，得到的将是x和（fx）的平均值。例如，将average-damp应用于square过程，就会产生出另一个过程，它在数值x处的值就是x和x2的平均值。将这样得到的过程应用于10，将返回10与100的平均值55： ((average-dampsquare)10)55利用average-damp，我们可以重做前面的平方根过程如下： (define(sqrtx)(fixed-point(average-damp(lambda(y)(/xy)))1.0))请注意，看看上面这一公式中怎样把三种思想结合在同一个方法里：不动点搜寻，平均阻尼和函数yx/y。拿这一平方根计算的过程与1.1.7节给出的原来版本做一个比较，将是很有教益的。请记住，这些过程表述的是同一计算过程，也应注意，当我们利用这些抽象描述该计算过程时，其中的想法如何变得更加清晰了。将一个计算过程形式化为一个过程，一般说，存在很多不同的方式，有经验的程序员知道如何选择过程的形式，使其特别地清晰且易理解，使该计算过程中有用的元素能表现为一些相互分离的个体，并使它们还可能重新用于其他的应用。作为重用的一个简单实例，请注意x的立方根是函数yx/y^2的不动点，因此我们可以立刻将前面的平方根过程推广为一个提取立方根的过程： (define(cube-rootx)(fixed-point(average-damp(lambda(y)(/x(squarey))))1.0))牛顿法在1.1.7节介绍平方根过程时曾经提到牛顿法的一个特殊情况。如果xg(x)是一个可微函数，那么方程g(x)＝0的一个解就是函数xf(x)的一个不动点，其中： 这里的Dg(x)是g对x的导数。牛顿法就是使用我们前面看到的不动点方法，通过搜寻函数f的不动点的方式，去逼近上述方程的解61。对于许多函数，以及充分好的初始猜测x，牛顿法都能很快收敛到g(x)＝0的一个解62。为了将牛顿方法实现为一个过程，我们首先必须描述导数的思想。请注意，“导数”不像平均阻尼，它是从函数到函数的一种变换。例如，函数xx3的导数是另一个函数x3x2。一般而言，如果g是一个函数而dx是一个很小的数，那么g的导数在任一数值x的值由下面函数（作为很小的数dx的极限）给出: 这样，我们就可以用下面过程描述导数的概念（例如取dx为0.00001）： (define(derivg)(lambda(x)(/(-(g(+xdx))(gx))dx)))再加上定义： (definedx0.00001)与average-damp一样，deriv也是一个以过程为参数，并且返回一个过程值的过程。例如，为了求出函数x->x3在5的导数的近似值（其精确值为75），我们可以求值： (define(cubex)(*xxx))((derivcube)5)75.00014999664018有了deriv之后，牛顿法就可以表述为一个求不动点的过程了： (define(newton-transformg)(lambda(x)(-x(/(gx)((derivg)x)))))(define(newtons-methodgguess)(fixed-point(newton-transformg)guess))newton-transform过程描述的就是在本节开始处的公式，基于它去定义newtons-method已经很容易了。这一过程以一个过程为参数，它计算的就是我们希望去找到零点的函数，这里还需要给出一个初始猜测。例如，为确定x的平方根，可以用初始猜测1，通过牛顿法去找函数y->y2－x的零点63。这样就给出了求平方根函数的另一种形式： (define(sqrtx)(newtons-method(lambda(y)(-(squarey)x))1.0))抽象和第一级过程上面我们已经看到用两种方式，它们都能将平方根计算表述为某种更一般方法的实例，一个是作为不动点搜寻过程，另一个是使用牛顿法。因为牛顿法本身表述的也是一个不动点的计算过程，所以我们实际上看到了将平方根计算作为不动点的两种形式。每种方法都是从一个函数出发，找出这一函数在某种变换下的不动点。我们可以将这一具有普遍性的思想表述为一个函数： (define(fixed-point-of-transformgtransformguess)(fixed-point(transformg)guess))这个非常具有一般性的过程有一个计算某个函数的过程参数g，一个变换g的过程，和一个初始猜测，它返回经过这一变换后的函数的不动点。我们可以利用这一抽象重新塑造本节的第一个平方根计算（搜寻y->x/y在平均阻尼下的不动点），以它作为这个一般性方法的实例： (define(sqrtx)(fixed-point-of-transform(lambda(y)(/xy))average-damp1.0))与此类似，我们也可以将本节的第二个平方根计算（是用牛顿法搜寻yy2－x的牛顿变换的实例）重新描述为： (define(sqrtx)(fixed-point-of-transform(lambda(y)(-(squarey)x))newton-transform1.0))我们在1.3节开始时研究复合过程，并将其作为一种至关重要的抽象机制，因为它使我们能将一般性的计算方法，用这一程序设计语言里的元素明确描述。现在我们又看到，高阶函数能如何去操作这些一般性的方法，以便建立起进一步的抽象。作为编程者，我们应该对这类可能性保持高度敏感，设法从中识别出程序里的基本抽象，基于它们去进一步构造，并推广它们以创建威力更加强大的抽象。当然，这并不是说总应该采用尽可能抽象的方式去写程序，程序设计专家们知道如何根据工作中的情况，去选择合适的抽象层次。但是，能基于这种抽象去思考确实是最重要的，只有这样才可能在新的上下文中去应用它们。高阶过程的重要性，就在于使我们能显式地用程序设计语言的要素去描述这些抽象，使我们能像操作其他计算元素一样去操作它们。一般而言，程序设计语言总会对计算元素的可能使用方式强加上某些限制。带有最少限制的元素被称为具有第一级的状态。第一级元素的某些“权利或者特权”包括： Lisp不像其他程序设计语言，它给了过程完全的第一级状态。这就给有效实现提出了挑战，但由此所获得的描述能力却是极其惊人的66。练习1.40请定义一个过程cubic，它和newtons-method过程一起使用在下面形式的表达式里： (newtons-method(cubicabc)1)能逼近三次方程x3＋ax2＋bx＋c的零点。练习1.41请定义一个过程double，它以一个有一个参数的过程作为参数，double返回一个过程。这一过程将原来那个参数过程应用两次。例如，若inc是个给参数加1的过程，（doubleinc）将给参数加2。下面表达式返回什么值： (((double(doubledouble))inc)5)练习1.42令f和g是两个单参数的函数，f在g之后的复合定义为函数xf(g(x))。请定义一个函数compose实现函数复合。例如，如果inc是将参数加1的函数，那么： ((composesquareinc)6)49练习1.43如果f是一个数值函数，n是一个正整数，那么我们可以构造出f的n次重复应用，将其定义为一个函数，这个函数在x的值是f(f(…(f(x))…))。举例说，如果f是函数xx＋1，n次重复应用f就是函数xx＋n。如果f是求一个数的平方的操作，n次重复应用f就求出其参数的2n次幂。请写一个过程，它的输入是一个计算f的过程和一个正整数n，返回的是能计算f的n次重复应用的那个函数。你的过程应该能以如下方式使用：