1.1 程序设计的基本元素

一种威力强大的程序设计语言，不仅能作为一种指挥计算机执行任务的方法，还能成为一个框架，使我们能在其中组织自己有关计算过程的思想。这样，当我们说明一种语言时，就应该特别关注该语言所提供的能把简单的概念组合起来形成更复杂概念的方法。每种强有力的语言都为此提供了三种机制：

● 基本表达式 ，用于表示该语言所关注的最简单的个体。

● 组合的方法 ，利用它们可以从较简单的元素出发构造出复合的元素。

● 抽象的方法 ，利用它们可以为复合元素命名，进而把复合元素当作单元去操作。

在程序设计中，我们需要处理的元素有两类：函数和数据（后面我们会发现，实际上它们并非严格分离的）。通俗地说，数据是我们希望去操作的“东西”，而函数就是有关操作这些数据的规则的描述。这样，任何强有力的程序设计语言都必须能表述基本数据和基本函数，还需要提供对函数和数据进行组合和抽象的方法。

本章只处理简单的数值数据，这使我们可以把注意力集中到函数构造的规则方面 。在随后几章里我们将会看到，用于构造函数的规则同样也能用于操作数据。

1.1.1 表达式

开始学习程序设计时，最简单方法就是观察一些与JavaScript语言解释器交互的典型实例。你键入一个 语句 ，解释器的响应就是把它 求值 这个语句的结果显示出来。

你可以键入的一种基本语句就是表达式语句，形式上是一个 表达式 后面跟一个分号。一类最基本的表达式是数（更准确地说，你键入的表达式是一串数字，按照以10为基数的方式表示相应的数值）。如果你输入下面的程序：

解释器的响应是打印出

表示数的表达式可以用运算符（例如+或者*）组合起来，形成复合表达式，表示把相应的基本函数作用于这些数。例如：

上面这样的表达式称为 组合式 ，它们以另一些表达式作为其组成部分。这种组合式的形式是把一个 运算符 符号放在中间，两个 运算对象 表达式分置左右，这种表达式称为 运算符组合式 。得到运算符组合式的值的方法，就是把运算符代表的那个函数应用于给定的 实际参数 （下面常简称为 实参 ），而所谓实际参数就是相应运算对象的值。

把运算符放在两个运算对象之间的约定形式称为 中缀记法 ，这也是常用的数学表示法，这些多半是你早已在小学和日常生活中熟悉了的东西。与在数学中一样，运算符组合式可以 嵌套 ，其中的运算对象本身也可以是运算符组合式：

如常，我们可以用括号在运算符组合式里做分组，以避免歧义。如果忽略括号，JavaScript也遵循常规的规则：乘法和除法运算符的组合力比加减法运算符更强，因此，

表示

对这种情况，我们说*和/具有比+和 -更高的优先级 。加或减的序列从左到右地处理，乘和除的序列也一样。这样，

就表示

对这些情况，我们说运算符+、-、*和/都是 左结合的 。

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

对这样复杂的表达式，解释器马上就能求值得到57。我们帮助自己的方法可能是重写上面的表达式，例如写成下面的形式：

这样就在视觉上区分出了表达式的主要成分。

即使对非常复杂的表达式，解释器也总是按同样的基本循环运作：从终端读入用户键入的一个语句，对该语句求值，然后打印得到的结果。这种运作模式常被说成解释器在运行一个 读入-求值-打印循环 。可以看到，完全不需要明确要求解释器打印语句的值 。

1.1.2 命名和环境

程序设计语言中有一个至关重要的方面，就是需要提供通过名字引用计算对象的方法。第一种方法是声明 常量 。我们说某个名字标识一个常量，就是说它的 值 就是那个对象。

在JavaScript里，我们用 常量声明 来命名常量：

这就导致解释器把值2关联于名字size 。一旦名字size关联于值2，我们就可以通过这个名字去引用值2了：

下面是另外几个使用 const 的例子：

常量声明是在JavaScript语言里做抽象的最简单的方法，它使我们可以用简单的名字引用组合运算的结果，例如上面计算出的circumference。一般而言，计算对象可以有非常复杂的结构，如果每次需要用它们时都必须记住并重复写出它们的细节，那是非常不方便的。实际上，构造一个复杂的程序，也就是为了设法一步一步地创建出越来越复杂的计算对象。解释器使这种一步一步进行的程序构造过程变得非常方便，因为我们可以通过一系列交互操作，逐步建立所需的名字-对象关联。这种特征鼓励人们采用递增的方式开发和调试程序。而且导致了另一个事实：JavaScript程序通常总是由一批相对简单的函数组成的。

应该看到，我们可以把值关联于名字，而后又能重新取出它们，这意味着解释器必须有某种记忆能力，保持有关的名字-值对偶的轨迹。这种记忆称为 环境 （更精确地说，是 程序环境 ，因为我们以后会看到，在一个计算中可能涉及若干不同的环境） 。

1.1.3 运算符组合式的求值

本章的一个目标就是把与过程性思维有关的问题区分出来。作为这方面的第一个情况，现在我们考虑运算符组合式的求值。解释器按下面的过程处理。

求值一个运算符组合式时，按下面的方式工作：

1.求值该组合式的各个子表达式。

2.把运算符指代的那个函数应用于有关的实参，也就是各个运算对象的值。

即使是这样一条简单规则，也显示出一些在计算过程中具有普遍意义的重要问题。首先，上面的第一步说明，为了实现对一个组合式的求值过程，我们必须首先对该组合式的每个运算对象执行这种求值过程。因此，从性质上说，这种求值过程是 递归 的，也就是说，在自己工作的步骤中，又包含了对这个规则本身的使用。

请特别注意，采用递归的思想可以多么简洁地描述深度嵌套的组合式的情况。如果不用递归，我们就需要把这种情况看成很复杂的计算过程。例如，求值：

需要把求值规则应用于4个不同的组合式。我们可以把这个组合式表示为树的形式，得到这个求值过程的图示，如图1.1所示。在这里，每个组合式用一个带分支的结点表示，由它发出的分支对应于组合式的运算符和运算对象。终端结点（那些不再发出分支的结点）表示运算符或者数。用树的观点看求值过程，我们可以设想那些运算对象的值向上穿行，从终端结点开始，在越来越高的层次组合起来。一般而言，我们会看到，递归是处理层次性结构（类似树这样的对象）的特别强有力的技术。事实上，“值向上穿行”形式的求值规则是一类更具普遍意义的计算过程的一个例子，这种计算过程称为 树形积累 。

进一步观察告诉我们，反复应用第一个步骤，总会把我们带到求值中的一点，在这里遇到的不是组合式而是基本表达式，例如数或名字。我们按如下规定处理这些基础情况：

●数的值就是它们所表示的数值。

●名字的值就是在环境中关联于该名字的那个对象。

请注意这里的关键点：环境扮演的角色就是确定表达式中各个名字的意义。在如JavaScript这样的交互式语言里，如果没有环境提供信息，说（例如）表达式x+1的值也毫无意义，因为需要环境为符号x提供意义。正如我们将在第3章里看到的，一般的环境概念为求值的进行提供上下文，对我们理解程序的执行起着非常重要的作用。

请注意，上面给出的求值规则里没有处理声明。举个例子，对 const x=3;求值，并不是把=运算符应用于它的两个实参，其中一个是名字x的值，另一个是3。声明的作用就是为x关联一个值（也就是说， const x=3;不是组合式）。

我们把 const 中的字母写成黑体，就是为表明它是JavaScript语言里的一个 关键字 。每个关键字都有特殊的意义，它们不能当名字使用。关键字或关键字组合要求JavaScript解释器以某种特殊方式处理相应的语句。不同语句形式各有自己的求值规则。各种类别的语句和表达式（每类各有相关的求值规则）组成了程序设计语言的语法。

1.1.4 复合函数

我们已经介绍了JavaScript里的一些元素，它们必然也会出现在任何一种强大的程序设计语言里，包括：

●数和算术运算是基本的数据和函数。

●组合式的嵌套提供了一种把多个操作组织起来的方法。

●常量声明是一种受限的抽象手段，其功能就是为名字关联值。

现在我们来学习 函数声明 ，这是一种威力更强大的抽象技术，通过它可以给复合操作确定一个名字，而后就可以把它作为一个单元来引用。

我们从如何表述“平方”的概念开始。我们可能说“求某个东西的平方，就是用它自身去乘它自身”。在我们的语言里，这件事应该表述为：

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

这样我们就有了一个 复合函数 ，它还被命名为square。这个函数表示把一个东西乘以其自身的操作。被乘的东西给定了一个局部名x，它扮演着与自然语言里的代词同样的角色。求值这一声明的结果就是创建出一个复合函数，并把它关联于名字square 。

最简单的函数声明的形式是：

其中的 name 是一个名字，函数的定义将在环境中关联于这个名字 ^[1] 。 parameters （形式参数）是一些名字，它们被用在函数体里，表示要求引用在应用这个函数时提供的各个实参。这些 parameters 写在一对括号里，用逗号分隔，就像所声明的函数被实际调用时的写法。在最简单的形式里，这里的 body 就是一个 返回语句 ，由关键字 return 和一个 返回表达式 构成 。在函数应用时，声明中的形式参数被与之对应的实参取代，返回表达式的执行生成函数应用的值。与常量声明和表达式语句一样，返回语句最后也需要有分号。

声明了square之后，我们就可以在 函数应用 表达式里使用它。我们可以给这种表达式加上分号，将其转变为一个语句：

除了运算符组合式，函数应用是我们遇到的第二种组合表达式，它们同样可用于构造更大的表达式。函数应用的一般形式是：

应用中的 function-expression （函数表达式）描述希望应用的函数，要求将其应用于逗号分隔的那些 argument-expression （实参表达式）。在求值一个函数应用式时，解释器将按下面的过程工作，类似于1.1.3节描述的运算符组合式的求值过程：

需要求值一个函数应用式时，按下面的方式工作：

1.求值应用式中的各个子表达式，即其中的函数表达式和各个实参表达式。

2.把得到的函数（也就是函数表达式的值）应用于那些实参表达式的值。

这里的实参表达式本身又是组合式，即为运算符组合式2+5。

很自然，实参表达式同样也可以是函数应用表达式。

我们还可以用square作为基本构件去声明其他函数。举例说， x ² + y ² 可以描述为：

现在我们很容易声明一个函数sum_of_squares ，给它两个数作为实参，它就能给出这两个数的平方和：

现在我们又可以用sum_of_squares作为构件，进一步去构造其他函数了：

除了复合函数之外，每个JavaScript环境都提供了一些基本函数，它们被构筑在解释器里，或者可以从函数库装入。除了为各个运算符提供相应的基本函数，本书使用的JavaScript环境还包括了另外一些基本函数，例如函数math_log，它计算实参的自然对数值 。基本函数的使用方式与复合函数一样，math_log（1）将得到数值0。实际上，如果只看上面给出的sum_of_squares的声明，我们根本没办法分辨其中的square究竟是直接构筑在解释器里，或是从程序库装入，还是通过声明定义的复合函数。

1.1.5 函数应用的代换模型

在求值函数应用时，解释器完全按1.1.4节描述的过程工作。也就是说，解释器首先求值应用表达式的各个元素，而后把得到的函数（也就是该应用式中的函数表达式的值）应用于那些实际参数（它们就是应用式中的那些实参表达式的值）。

我们可以假定，基本函数的应用已经在解释器或库里做好了。对于复合函数，这种应用的计算过程是：

把一个复合函数应用于一些实际参数，就是在把该函数的返回表达式中的每个形参用相应的实参取代后，求值得到的结果表达式 。

为了展示这个计算过程，让我们求值下面的应用式：

其中的f就是1.1.4节声明的那个函数。我们首先提取出f的返回表达式：

而后用实参5代换其中的形式参数：

这样，问题归约为对另一个应用式的求值，它有两个实参，函数表达式是sum_of_squares。求值这一应用式牵涉下面三个子问题：我们必须求值其中的函数表达式，得到应该去应用的函数；还要求值那些实参表达式，得到函数应用的实际参数。这里的5+1产生6，5 * 2产生10，因此我们需要把sum_of_squares函数应用于6和10。用这两个值代换sum_of_squares的返回表达式里的形式参数x和y，该表达式就归约为：

我们使用square的声明，又可以把它归约为：

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

最后就得到了：

上面描述的计算过程称为函数应用的 代换模型 。在考虑本章到目前为止所关注的函数时，我们可以把它看作确定函数应用的“意义”的模型。但是，这里还需要强调两点：

●这里的代换只是为帮助我们思考函数调用的情况，而不是对解释器实际工作方式的具体说明。典型的解释器都不采用直接操作函数正文、以值代换形式参数的方式完成对函数调用的求值。实际的求值器通常采用为形式参数建立局部环境的方式产生“代换”的效果。我们将在第3章和第4章考察解释器的实现细节，更完整地讨论这个问题。

●随着本书的进展，我们将展示一系列有关解释器如何工作的模型，一个比一个更精细，并最终在第5章给出一个解释器和一个编译器的完整实现。代换模型只是这些模型中的第一个——作为形式化地思考求值过程的起点。一般而言，在模拟科学研究或者工程中的现象时，我们总是从简化的不完整的模型开始。随着更细致地检查所考虑的问题，这些简单模型也会变得越来越不合适，从而必须用进一步精化的模型取代。这里的代换模型也不例外。特别地，我们将要在第3章讨论把函数用于“变动数据”的问题，那时就会看到代换模型完全不行了，必须用更复杂的函数应用模型取代 。

应用序和正则序

按1.1.4节给出的有关求值过程的描述，解释器首先求值函数和各个实参表达式，而后把得到的函数应用于得到的实际参数。然而，这并不是执行求值的唯一可能方式。另一种求值模型是先不求出实参表达式的值，直到实际需要它们的值的时候再求值。采用这种求值方式，我们就应该首先用实参表达式代换形式参数，直至得到一个只包含运算符和基本函数的表达式，然后再执行求值。如果我们采用这种方式，对下面这个表达式求值：

将会形成下面的逐步展开序列：

然后是下面的归约：

这样做也给出了与前面求值模型同样的结果，但计算过程却是不同的。特别地，对5+1和5 * 2的求值各做了两次，它们都出自对下面表达式的归约：

其中的x分别被代换为5+1和5 * 2。

这种“完全展开而后归约”的求值模型称为 正则序求值 ，与之相对的是解释器实际使用的方式，“先求出实参而后应用”，这称为 应用序求值 。可以证明，对于可以用代换来模拟，并能产生合法值的那些函数应用（包括本书前两章的所有函数），正则序和应用序求值将产生同样的值（参看练习1.5中“非法”值的例子，正则序和应用序会给出不同的结果）。

JavaScript采用应用序求值，部分原因在于这样做能避免对表达式的重复求值（如上面的5+1和5 * 2的情况所示），从而可以提高一点效率。更重要的是，在超出了可以用代换方式模拟的函数的范围后，正则序的处理将变复杂许多。而在另一些方面，正则序也可以成为特别有价值的工具，我们将在第3章和第4章研究它的某些内在性质 。

1.1.6 条件表达式和谓词

至此，我们能描述的函数类的表达能力还非常有限，因为还没办法先做检测，然后根据检测结果执行不同操作。例如，我们还无法声明一个函数，使它能算出一个数的绝对值。完成此事需要先检查这个数是否非负，然后按下面的规则对不同情况采用不同的动作：

这种结构称为 分情况分析 ，在JavaScript里可以用 条件表达式 写出来：

这个条件表达式可以用自然语言读为“如果 x 大于等于0就返回 x ，否则返回 -x 。”条件表达式的一般形式是：

条件表达式以 predicate 开头（下面有时称为“谓词部分”“谓词表达式”，或直接说“谓词”），这是一个值为 真 或 假 的表达式。 真 和 假 是JavaScript里的两个 布尔 值，对基本布尔表达式 true 和 false 求值将直接得到布尔值真和假。在谓词之后是一个问号，然后是 consequent-expression （下面称为“后继部分”或“后继表达式”）、一个冒号和 alternative-expression （下面称为“替代部分”或“替代表达式”）。

求值条件表达式时，解释器首先求值表达式中的 predicate ，如果它的值是真，那么就去求值 consequent-expression ，并以其值作为这个条件表达式的值。如果 predicate 的值是假，就去求值 alternative-expression ，并以其值作为条件表达式的值 ^[2] 。

术语 谓词 （ predicate ）指返回真或假的运算符或函数，以及求值结果为真或假的表达式。绝对值函数abs里使用了基本谓词>=，这是一个运算符，它以两个数作为参数，检查第一个数是否大于或等于第二个数，并据此分别返回真或假。

如果我们愿意把0作为另一种情况处理，也可以要求这个函数按另一种方式计算数值的绝对值：

在JavaScript里，我们经常用到在一个条件表达式的 alternative-expression 部分嵌套另一个条件表达式的语句形式，用于描述包含多种不同情况的分情况分析：

在嵌套的表达式x===0?0:-x周围不需要加括号，这是因为条件表达式是右结合的。为了提高可读性，这里加入了一些空格和换行，把分情况分析里的各个?和:都与第一个谓词对齐。解释器会忽略这些空格和换行。分情况分析的一般形式是：

我们把谓词 p _i 和随后的 e _i 一起称为一个 子句 ，这样，分情况分析结构就可以看作子句的序列，最后跟着一个表示其他情况的表达式。按条件表达式的求值规则，求值这种结构时，解释器首先求值谓词 p ₁ ，如果其值是假就求值 p ₂ ，如果其值还是假就求值 p ₃ 。这一过程持续到求值某个谓词得到真，这时解释器就求值该子句的 e ，并将其值作为整个分情况分析的值。如果所有的 p 求出值都不是真，这个分情况分析的值就是最后那个其他情况表达式的值。

除了可以应用于数值的基本谓词如>=、>、<、<=、===和!==之外 ，还有几个逻辑复合运算符，利用它们可以构造出各种复合谓词。最常用的三个复合运算符是：

● expression ₁ && expression ₂

这个运算描述 逻辑合取 ，其意义大致相当于自然语言的“并且”。这一语法形式实际上是 expression ₁ ? expression ₂ :false的语法包装（加了 语法糖衣 ）。

● expression ₁ || expression ₂

这个运算描述 逻辑析取 ，其意义大致相当于自然语言的“或者”。这一语法形式实际上是 expression ₁ ? true: expression ₂ 的语法包装。

●! expression

这个运算描述 逻辑否定 ，其意义大致相当于自然语言的“非”。如果 expression 求出的值是假，整个表达式的值就是真；如果 expression 的值为真，整个表达式的值就是假。

注意，&&和||都只是语法形式而不是运算符，它们右边的子表达式不一定求值。另一方面，!是一个运算符，遵循1.1.3节说明的求值规则。这是一个 一元 运算符，也就是说它只有一个运算对象，而至今我们讨论的算术运算符和基本函数都是 二元 的，都要求两个参数。运算符!应该放在其运算对象前面，因此称为 前缀运算符 。另一个前缀运算符是算术的求负运算符，前面abs函数里的表达式-x就是使用它的例子。

作为使用这些谓词的例子，数 x 的值位于区间5< x <10中的条件可以表述为：

语法形式&&的优先级低于比较运算符>和<。另一方面，条件表达式语法形式…?…:…的优先级低于我们遇到过的所有运算符。前面的abs函数里已经用到这个性质。

作为另一个例子，我们可以声明一个谓词，它检测某个数是否大于或等于另一个：

或者也可以写成：

把函数greater_or_equal应用于两个数，其行为就像运算符>=。一元运算符的优先级高于二元运算符，因此，后一例子里的括号是必需的。

练习1.1 下面是一系列语句。对这里的每个语句，解释器将输出什么结果？假定这一语句序列按我们展示的顺序求值。

在最后两个例子里，围绕条件表达式的括号都是必需的，因为条件表达式语法形式的优先级低于运算符+和*。

练习1.2 请把下面这个表达式翻译为JavaScript表达式：

练习1.3 请声明一个函数，它以三个数为参数，返回其中较大的两个数的平方和。

练习1.4 应该注意，我们的求值模型允许函数应用中的函数表达式又是复合表达式，请根据这一认识说明函数a_plus_abs_b的行为：

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

而后他求值下面的语句：

如果解释器采用应用序求值，Ben会看到什么样的情况？如果解释器采用正则序求值，他又会看到什么情况？请解释你的回答。（在这里我们假设：无论解释器实际使用的是正则序还是应用序，条件表达式的求值规则总是一样的，其中的谓词部分先行求值，再根据其结果确定随后求值的子表达式部分。）

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

上面介绍的函数很像常规的数学函数，它们描述的都是根据一个或几个参数确定一个值。然而，在数学的函数和计算机的函数之间有一个重要的差异，那就是，计算机的函数还必须是有效可行的。

作为实例，现在考虑计算平方根的问题。我们可以把平方根函数定义为：

得到那样的 y ，能使得 y ≥0而且 y ² = x

这句话描述了一个完全合法的数学函数，我们可以根据它去判断某个数是否为另一个数的平方根，或根据它推导出一些有关平方根的一般性事实。然而，在另一方面，这个定义并没有描述计算机函数，因为它确实没有告诉我们，在拿到一个数之后，如何实际地找出这个数的平方根。即使采用类似JavaScript的形式重写一遍这个定义也无济于事：

这只不过是重述了原来的问题。

数学函数与计算机的函数之间的明显对比，不过是描述事物的特征，与描述如何去做出这一事物之间的普遍性差异的一个具体反映。换一种说法，人们有时也把它说成是说明性的知识与行动性的知识之间的差异。在数学里，我们通常关心的是说明性的描述（是什么），而在计算机科学里，人们则通常关心行动性的描述（怎么做） 。

怎样才能计算出平方根呢？最常用的就是牛顿的逐步逼近方法。这一方法告诉我们，如果对 x 的平方根值有了一个猜测 y ，那么就可以通过执行一个简单操作，得到一个更好的猜测（它更接近实际平方根的值）：只需要求出 y 和 x / y 的平均值 。例如，我们可以用这种方式计算2的平方根，假定初始值是1：

继续这一计算过程，我们就能得到2的平方根的越来越好的近似值。

现在，让我们用函数的语言来描述这一计算过程。开始时，我们有被开方的数值（要做的就是计算它的平方根）和一个猜测值。如果猜测值对我们的用途而言已经足够好，工作就完成了。如若不然，就需要重复上述计算过程去改进这个猜测值。我们可以把这一基本策略写成下面的函数：

改进猜测值的方法，就是求出它与被开方数除以这个旧猜测的平均值：

其中

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

最后，还需要一种方法启动整个工作。例如，对任何数，我们都可以猜其平方根为1：

如果把这些声明都送给解释器，我们就可以像使用其他函数一样使用sqrt了：

这个sqrt程序也说明，至今已经介绍的这个简单的函数式语言，已经足以写出可以用其他语言（例如C或Pascal）写出的任何纯粹数值计算的程序了。这件事看起来可能很让人吃惊，因为在我们的语言里甚至没有包括任何迭代结构（循环，它们可用于指挥计算机去一遍遍地做某些事情）。而在另一方面，sqrt_iter展示了如何不用特殊的迭代结构来实现迭代，其中只需要使用常规的函数调用能力 。

练习1.6 Alyssa P.Hacker不喜欢条件表达式的语法，因为其中涉及符号?和:。她问：“为什么我不能直接声明一个常规的条件函数，其应用的工作方式就像条件表达式呢？” Alyssa的朋友Eva Lu Ator断言确实可以这样做，并声明了一个名为conditional的函数：

Eva给Alyssa演示了她的程序：

她很高兴地用自己的conditional函数重写了求平方根的程序：

当Alyssa试着用这个函数去计算平方根时会发生什么情况？请给出解释。

练习1.7 在计算很小的数的平方根时，用is_good_enough检测不是很有效。还有，在实际计算机里，算术运算总以一定的有限精度进行。这会使我们的检测不适合用于对很大的数的计算。请解释上述论断，并用例子说明对很小的和很大的数，这种检测都可能失效。实现is_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定义函数is_good_enough时，就是把square看作“黑箱”。我们暂时不关心这个函数如何得到结果，而是只注意它能计算平方值的事实。如何计算平方的细节被隐去不提，推迟到以后再考虑。确实如此，如果只看is_good_enough函数，与其说square是函数，不如说它是一个函数的抽象，即所谓 函数抽象 。在这一抽象层次上，任何计算平方的函数都同样可以使用。

这样，如果只考虑返回值，下面这两个求数值平方的函数并无差别。两者都以一个数值作为参数，产生这个数的平方作为函数值 。

由此可见，一个函数应该能隐藏一些细节。这使该函数的使用者有可能不必自己写这些函数，而是从其他程序员那里作为黑箱接受它。在使用一个函数时，用户应该不需要知道它是如何实现的。

局部名

函数的用户不必关心的实现细节之一，就是实现者为函数所选用的形式参数的名字，也就是说，下面两个函数应该是不可区分的：

这一原则（函数的意义不依赖于其作者为形式参数选用的名字）从表面看是自明的，但其影响却很深远。最直接的影响是，函数的形式参数名必须局部于有关的函数体。例如，我们在前面平方根函数的is_good_enough声明里用到名字square：

is_good_enough作者的意图是确定第一个参数的平方是否位于第二个参数的给定误差的范围内。可以看到，is_good_enough的作者用名字guess表示其第一个参数，用x表示第二个参数，而square的实际参数就是guess。如果square的作者也用x（例中确实如此）表示参数，可以想到，is_good_enough里的x必须与square里的x不同。运行函数square绝不应该影响is_good_enough里用的那个x的值，因为在square完成计算后，is_good_enough可能还需要x的值。

如果参数不是局部于它们所在的函数体，那么square里的参数x就会与is_good_enough里的参数x相互干扰。如果这样，is_good_enough的行为方式就依赖我们所用的square的具体版本，square也就不是我们希望的黑箱了。

函数的形式参数在函数声明里扮演着非常特殊的角色，形式参数的具体名字其实并不重要，这样的名字称为是 约束的 。因此我们说，函数声明约束了它的所有形式参数。如果在一个函数声明里把某个约束名统一换名，该函数声明的意义不变 。如果一个名字不是约束的，我们就说它是 自由的 。一个名字的声明被约束的那一集语句称为这个名字的 作用域 。在一个函数声明里，被声明为函数形式参数的约束名都以该函数的体为作用域。

在上面is_good_enough的声明里，guess和x是约束的名字，而abs和square是自由的。要保证is_good_enough的意义与我们对名字guess和x的选择无关，只需要求这些名字都与abs和square不同（如果我们把guess重命名为abs，就会因为捕获了名字abs而引进一个错误，因为这样做把一个原来自由的名字变成约束的了）。is_good_enough的意义当然与其中自由名字的选择有关，这个意义显然依赖于（这个声明之外的）一些事实：名字abs引用一个函数，该函数能求出数值的绝对值。如果我们把is_good_enough声明里的abs换成math_cos（基本余弦函数），它计算的就是另一个不同的函数了。

内部声明和块结构

到现在为止，我们只分离出了一种可用的名字：函数的形式参数是其函数体里的局部名字。这个平方根程序还表现了另一种情况，我们也会希望能控制其中名字的使用。目前这个程序由几个相互独立的函数组成：

问题是，在这个程序里，只有一个函数对sqrt的用户是重要的，那就是这里的sqrt。其他函数（sqrt_iter、is_good_enough和improve）只会干扰用户的思维，因为在需要与平方根程序一起使用的其他程序里，它们再不能声明另一个名为is_good_enough的函数作为程序的一部分了，因为在sqrt里用了这个名字。当许多分别工作的程序员一起构造大型系统时，这一问题就会变得非常严重。举例说，在构造一个大型数值函数库时，许多数值函数都需要计算一系列近似值，因此它们都可能需要名字为is_good_enough和improve的函数作为辅助函数。由于这些情况，我们自然会希望把子函数也局部化，把它们隐藏到sqrt里面，使sqrt可以与其他同样采用逐步逼近方法的函数共存，即使它们中每一个都有自己的is_good_enough函数。为使这件事成为可能，我们允许在一个函数声明里包含一些局部于这个函数的内部声明。例如，在解决平方根问题时，我们可以写：

任意一对匹配的花括号表示一个 块 ，块内部的声明局部于这个块。这种嵌套的声明结构称为 块结构 ，这是最简单的名字包装问题的正确处理方法。实际上，这里还潜藏着一个很好的情况：除了可以内部化辅助函数的声明，我们还可能简化它们。因为x在sqrt的声明中是受约束的，函数is_good_enough、improve和sqrt_iter也都声明在sqrt内部，也就是在x的定义域里。这样，明确地把x在这些函数之间传来传去就没有必要了。我们可以让x作为这些内部声明里的自由变量，如下所示。这样，在外围的sqrt被调用时，x由其实际参数得到自己的值。这种做法称为 词法作用域 。

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