《SICP》第1章——构造抽象函数读后感与深入思考

引言：抽象的力量

英国哲学家约翰·洛克曾将人类心智的活动概括为三个方面：（1）将简单概念组合成复杂概念；（2）比对概念以获得它们之间的关系；（3）将概念从具体杂糅中抽离出来，形成普遍的抽象概念。这种对于“抽象”的阐述，恰与程序设计中构造抽象的理念不谋而合。在软件世界里，我们通过程序（一种由符号精心编排的“咒语”）来驱动计算过程，以完成各种复杂任务。要驾驭这些复杂性，程序员必须学会像“巫师的徒弟”那样，充分利用抽象来组织和模块化构造程序，使每个部分各司其职、独立更替，从而控制整体的复杂度。

《计算机程序的构造和解释（JavaScript版）》第一章正是围绕“构造函数抽象”这一主题展开，探讨如何通过函数来构建程序的抽象屏障，管理复杂的计算过程。阅读完本章，我们将对以下内容有系统的理解：

• 程序的基本元素：包括原子表达式（如数字、字符串等基本数据）、组合表达式（通过算符和函数调用构造复杂表达式）、条件判断、函数定义以及名字作用域等。这些构成了一门强大编程语言所必备的基本构件。
• 过程与递归：理解函数执行所产生的计算过程模型，比较递归与迭代两种过程形态以及它们在时间和空间复杂度上的差异，并通过实例（如阶乘、斐波那契、幂运算、最大公约数和素数测试）体会不同算法的效率增长阶。
• 高阶函数与过程抽象：深入讨论如何将函数作为参数和返回值，实现对通用计算模式的抽象。我们将看到如何提炼出求和、求积等通用模式，以及通过引入匿名函数（lambda）和高阶函数构造更高层次的抽象。
• 代换模型与函数的抽象本质：用代换模型理解函数应用的执行机理，在不引入可变状态时将函数调用等价转换，从而加深对递归过程的认知；同时反思“函数即抽象的载体”这一观念——函数在程序设计中不仅是执行操作的实体，更是承载抽象思想的模块化单元，它允许我们以更高层次的思维来组织和复用代码。

接下来，我将按第一章的内容结构，结合个人的理解与反思，对上述各方面逐一展开讨论，并适当引用书中关键代码和练习题进行解析。

程序的基本元素：原子、组合与抽象

程序 = 数据 + 操作。在JavaScript这样的语言中，最基本的程序构件是一些原子表达式，例如数值常量、字符串、布尔值，以及内置的基本运算符和初等函数。这些原子元素提供了最简单的计算语义（例如数字直接表示其值，内置算术运算如+、*直接对应数学运算）。然而，仅有原子操作不足以构成有趣的程序——我们还需要将这些基本元素按照某种结构组合起来，以表达更复杂的运算。

原子表达式与组合表达式

在JavaScript中，我们通过表达式来描述计算。最简单的情况，一个数字常量本身就是一个表达式，其值就是该数字表示的量；一个字符串常量的值就是该字符串自身；一个变量名（标识符）的值则需要由环境（后文详述）来提供绑定。。更复杂的表达式可以由简单表达式组合而成，例如算术组合式 （2 + 3） * 4，这是通过算符将子表达式按照中缀语法组合而成的。当我们求值一个组合表达式时，解释器遵循一定的规则：

1. 求值每个子表达式（包括运算符和操作数）。对于算术组合式，这意味着先求出操作数的值。
2. 将运算符应用于操作数值，得到组合式的结果。

例如，求值表达式 (2 + 4 * 6) * (3 + 12) 时，解释器会先递归地求值子表达式 2 + 4 * 6 和 3 + 12，再将两个结果相乘。事实上，这个过程本身是递归的：子表达式的求值又涉及对更小的组合式的求值，如 4 * 6 等，一直递归下去直到遇到原子表达式（数或变量）为止。这一递归求值过程可以用一棵树来表示，其中内部节点是组合运算，叶节点是原子值；值从叶节点计算并“向上涌现”以组合成更高层次的值。这种结构说明，递归是一种强有力的处理分层结构（如树形表达式）的技术——即使在解释器的求值规则中，我们也看到了递归的身影。

需要注意，当遇到名字（变量）这种原子表达式时，其值是通过查找环境（environment）获得的。环境就是记录了名字与值绑定关系的一种“记忆机制”。在交互式的语言里（例如使用浏览器控制台执行JavaScript），如果没有环境提供变量的含义，像x + 1这样的表达式就无法求值。因此，环境为表达式提供了上下文，它存储着当前已知的名字及其对应的值。可以将环境简单理解为一张表格，记录“名字=对象”的关联。当我们声明一个常量或变量时，就是在当前环境中创建一个绑定关系，以便稍后通过名字引用相应的值。

举例来说，如果执行如下常量声明：

const size = 2;

则解释器会在环境中将标识符size绑定到值2。之后无论何处出现表达式size，都会在当前环境查到它的值2，从而替换计算。使用常量名字来引用值，极大提高了程序的可读性和可维护性——我们可以用有意义的名字代表复杂的计算对象，使得程序就像在处理问题领域的概念而非琐碎的数值。这正是抽象的第一步：用一个简单的代号，来指代一个可能复杂的数据或表达式，从而隐藏细节、凸显意图。

需要留意的是，JavaScript中每条语句也会产生一个值（哪怕有些是undefined），这是语言的约定。而声明语句本身并不被当作一个组合表达式来求值：当我们执行const x = 3;时，解释器的动作不是“取出x的值和数字3，再应用=运算符”，而是将名字x绑定到值3。这里的const是一个关键字，具有特殊语义，不可用于其它用途。不同类别的语句（声明语句、表达式语句、条件语句等）有各自的求值规则，共同构成了语言的语法和执行模型。

函数定义与复合操作的抽象

掌握了基本表达式和组合规则后，我们引入更强大的抽象手段：函数。正如书中总结的，任何强大的程序设计语言都应提供三种机制：

• 基本的数据与操作（如数字和算术运算符）；
• 将简单元素组合成更复杂元素的方法（如嵌套组合表达式）；
• 将一个复杂过程抽象并以名字命名，使之作为一个单位被使用的方法（即定义成函数）。

前两点我们已经了解，第三点——通过函数定义来命名复合操作——是实现过程抽象的关键技术。通过函数，我们可以把一组操作打包并赋予一个名称，以后使用时就无需关心内部如何实现，而只需要知道这个函数的功能。这就像建立了一个“黑箱”，在盒子外我们只需通过接口（函数名和参数）与之交互，而不必了解盒子内的具体细节。

让我们从一个简单的例子开始，看看如何定义函数。在日常语言中，我们可以描述“平方”运算为：“求一个数的平方，就是用它乘以它自己”。用JavaScript语言来表达，就是以下形式：

function square(x) {
    return x * x;
}

在上述函数声明中，square是函数的名称，x是形式参数，函数体通过return语句指定了如何计算结果，即返回x * x。这个定义的求值结果是创建一个以名字square关联的新函数对象。从此，我们就可以使用square来引用这一复合操作，把它当作语言中的基本元素来对待。例如，调用square(21)会得到结果441。函数调用（应用）本身也是一种表达式类型，它的语法形式为：function-expression( argument-expressions )，求值规则与算术组合式类似：先求出函数表达式表示的函数值，以及各个实参表达式的值，然后将函数应用到这些实参。

形式参数与作用域：在function square(x) { ... }的定义中，x称为形式参数（parameter）。形式参数就像数学中的自变量符号，在函数体内充当占位符。当我们实际调用square(5)时，值5被绑定到形式参数x，然后计算函数体x * x得到25并返回。这种将实参值替换形式参数的过程发生在函数调用时。值得强调的是，形式参数仅在函数内部有意义，称为该函数的局部变量。一个函数的局部变量（包括其形式参数及在函数内部声明的变量）与其它函数或全局环境中的同名变量是相互独立、不冲突的。这体现了词法作用域规则：每个函数调用都会创建一个新的本地环境，在其中绑定该函数的局部变量，函数执行完毕后这个环境也随之销毁。

局部变量名的独立性，使函数成为真正的模块化单元。书中通过is_good_enough函数的例子形象地解释了这一点：is_good_enough调用了square函数，并使用了名字x和guess作为参数名。如果square函数内部也用了参数名x（确实如此），两者之间也不会相互干扰——因为square中的x只属于square自身的函数环境，而is_good_enough中的x属于它自己的环境。如果没有这种局部性，模块化将无从谈起：我们在定义或使用一个函数时就不得不考虑其他函数内部用了哪些变量名，这将使程序难以扩展和维护。所幸，在JavaScript等采用词法作用域的语言中，函数的形式参数和内部声明的变量名都是局部的，函数调用时会自动屏蔽掉外部环境中同名的标识符。这确保了我们可以把函数视作一个独立的抽象黑箱来使用——只要了解它实现的功能，而无需关心其内部细节或变量名选择。当我们基于已有函数去构造更复杂的函数时（例如在is_good_enough中调用square），就好比在堆积木：每块木头（函数）都有清晰的接口和边界，不会因为内部实现而相互干扰。这正是**“函数作为黑箱抽象”**的要义。

条件表达式和谓词

在许多计算过程中，需要依据情况执行不同操作。这就用到了条件表达式和谓词。谓词是返回布尔值的函数或表达式，用于做真/假判断；条件表达式则根据谓词的结果在不同分支间进行选择。在JavaScript中，最常用的条件控制结构是if-else语句，以及三元运算符形式的条件表达式 条件 ? 表达式1 : 表达式2。

例如，我们可以定义一个函数abs(x)返回x的绝对值，它需要判断x是否小于0：

function abs(x) {
    return x >= 0 ? x : -x;
}

这里使用了三元条件运算符：x >= 0是一个比较表达式，作为谓词；若为真，返回x，否则返回-x。条件判断使函数能够对不同情形执行不同计算，以实现正确的逻辑。

需要注意的是，在解释器的求值规则中，不论if语句还是条件表达式，都规定先求值判断部分（谓词），然后根据其布尔结果决定执行哪个分支的代码。特别地，在应用序求值策略下（JavaScript 使用的策略），条件表达式的谓词会被严格求值，而不会存在“不求值某些参数”的情况——除了通过语言规则，比如逻辑运算符&&、||具有短路性质或if语句自身的控制行为。换句话说，除非我们引入特殊的求值策略，否则一般的函数调用和条件计算都遵循确定的顺序求值规则。

函数应用的代换模型

为了理解函数调用的执行过程，书中引入了一个思想工具：代换模型（substitution model）。在暂不考虑副作用（赋值、IO等）的前提下，我们可以将函数应用看作一种符号替换：调用一个函数时，将其形式参数替换为实际参数值，然后计算得到结果。例如，对于递归定义的阶乘函数：

function factorial(n) {
    return n === 1
           ? 1
           : n * factorial(n - 1);
}

如果我们计算factorial(3)，按照代换模型的思路，会经历如下展开和归约过程：

factorial(3)
= 3 * factorial(2)                    // 代换展开
= 3 * (2 * factorial(1))
= 3 * (2 * 1)                         // factorial(1) 展开为 1
= 3 * 2
= 6                                   // 归约完成

在这个过程中，我们将factorial(n)调用展开为n * factorial(n-1)，不断展开直到命中递归基（基例）n === 1，然后再逐步将数值算回去。这种先展开、后收缩的计算过程形状，被称为递归计算过程。从模型上看，递归过程在展开阶段构造出一系列延迟的乘法操作链，收缩阶段再逐一执行这些乘法。在上述例子中，延迟的乘法链长度与n成正比（3展开出2次乘法，n=3），因此阶乘的递归实现需要Θ(n)的步骤和Θ(n)的空间（由于递归需要保存栈帧）。

代换模型提供了一个直观理解递归调用的方法。本章讨论的所有函数（没有副作用且使用严格求值策略）都可以用代换模型来解释其语义。不过需要注意，代换模型是一种帮助思考的简化模型，而非解释器内部的真实工作方式。它忽略了实现细节，以一种接近数学递推的方式诠释函数调用的“含义”。随着我们在后续章节引入可变状态、对象、并发等特性，代换模型将不再充分（例如赋值会破坏简单代换等价性），那时我们需要切换到更复杂的“环境模型”才能正确理解程序行为。尽管如此，在纯函数式计算的范围内，代换模型是非常有用的工具，它让我们聚焦于函数的输入输出映射关系，而暂不必纠结具体的机器实现步骤。

除了揭示递归过程的形状，代换模型还能帮我们区分应用序（applicative order）与正则序（normal order）的求值策略。书中练习1.5设计了一个有趣的试验：通过一个自引用的函数p()和条件函数test(x, y)来测试解释器到底是先计算参数再调用（应用序），还是先代换后计算（正则序）。这个练习结果表明，大多数实际语言采用应用序求值——也就是“先计算参数，再调用函数”。应用序和正则序在纯函数没有副作用时对结果影响不大，但对计算效率和某些特殊程序行为有显著差别。SICP在这里埋下伏笔，提示读者意识到求值策略也是语言设计的维度之一。

实例：牛顿法求平方根

将数学定义转化为计算过程，是本章的一个贯穿示例。其中最经典的莫过于牛顿法近似求平方根。书中通过这个例子，展示了从“说明性知识”到“行动性知识”的转变：数学上平方根√x的定义是“找到非负的y使得y^2 = x”，但直接拿来编程并不能告诉我们如何求解。相反，我们需要找到一个算法来逐步逼近解。牛顿提供的办法是：如果有一个猜测值y，可以通过 (y + x/y) / 2 来得到一个更好的猜测。反复执行这一改进过程，猜测值将收敛于真正的平方根。

书中将上述策略翻译成了递归的程序描述。首先，给出一个函数improve(guess, x)，返回根据牛顿法从当前猜测guess计算出的改进猜测：

function improve(guess, x) {
    return average(guess, x / guess);
}
function average(a, b) {
    return (a + b) / 2;
}

然后，定义一个迭代函数sqrt_iter(guess, x)，它不断改进猜测直到满足终止条件：

function sqrt_iter(guess, x) {
    return is_good_enough(guess, x)
           ? guess
           : sqrt_iter(improve(guess, x), x);
}

这里is_good_enough(guess, x)用于判断当前猜测是否已经“足够好”，如果是则返回结果，否则递归地用改进值调用自身，形成迭代。最后，封装一个对外的接口函数sqrt(x)，它只需调用sqrt_iter(1, x)（以1为初始猜测）即可得到x的平方根近似：

function sqrt(x) {
    return sqrt_iter(1, x);
}

通过这种分解，我们将求平方根的问题拆解为互相协作的几个模块：判断是否足够接近的is_good_enough，计算改进值的improve（以及它用到的average），和驱动迭代的sqrt_iter。每个模块都完成一件清晰的子任务，组合起来便构成了完整的求解过程。这正体现了问题分解和模块抽象的重要性：我们并不是简单地把程序按行切成几段，而是按照逻辑功能拆分成可以清晰说明的片段，使得每个片段都可以独立理解、测试，甚至在其他场合复用。

值得进一步讨论的是终止判断策略is_good_enough的选择。在书中的初版Scheme实现里，is_good_enough可能采用检查连续两次猜测差值很小来判断收敛。但在本书JavaScript版中，作者指出一个简单实现可能对于非常小的数不够敏感、对于非常大的数又因为浮点精度而失效。例如，如果要求一个极小的数的平方根，猜测值的变化可能都小于固定阈值0.001，以致算法过早停止；而对非常大的数，浮点运算误差可能使得微小相对变化无法察觉。这正是练习1.7提出的问题：为什么原始的is_good_enough检测对很小或很大的数不有效？请举例说明，并提出改进策略。通过这道练习，我们反思了算法的鲁棒性：应当根据输入规模动态调整判定条件，例如采用相对误差或监视改进幅度比例的方法。这预示着在实际数值计算中，“什么时候足够近”是一个需慎重对待的问题，往往要结合具体问题和机器精度来设计。

初步实现sqrt函数后，我们可以尝试将其视作一个抽象的函数使用。在is_good_enough的定义中，我们调用了square(guess)而不必关心square如何计算平方；同样，一旦sqrt(x)经过充分测试确保正确，我们在其他地方可以把它当作黑箱来求平方根，而无需每次重复牛顿迭代的细节。这体现了抽象的第二层含义：不仅在代码结构上模块化，更在思想层面把握程序的功能而非具体实现。我们说，一个经过良好封装的函数其实代表了一个抽象的过程：使用者只需了解它做什么，而不必了解它怎么做。

在本章结尾，SICP以“函数作为黑箱抽象”作小结，强调设计良好的函数应该隐藏实现细节，暴露出清晰稳定的接口。例如，不管我们用哪种方式实现square（用乘法还是调用数学库），对is_good_enough而言都无关紧要，只要square正确地返回平方结果即可。同理，我们可以随时替换is_good_enough的判定策略，而不影响sqrt_iter的逻辑。这种抽象屏障思想使得程序的各部分松耦合、易于推理。正如书中所言：“在这一抽象层次上，任何计算平方的函数都同样可以使用”——抽象关注的是行为契约，而不是具体实现。这种理念对构建大型程序至关重要：通过抽象屏障，各模块各司其职、互不干扰，系统才能扩展且可靠。

过程与算法：递归与迭代

在掌握了基本的过程抽象手段后，SICP第一章接下来讨论函数所描述的计算过程形态以及算法的效率问题。本节通过一系列实例比较递归和迭代两种过程类型，分析它们的时间和空间复杂度（增长阶），并体会算法优化的重要性。

线性递归 vs. 线性迭代

上一节我们用阶乘函数演示了递归过程的展开收缩形态。实际上，阶乘计算还可以用另一种等价的方式实现，即采用迭代的思想。考虑阶乘公式：

$n!=n\times (n-1)\times \cdots \times 2\times 1.$

我们完全可以用一个循环累计乘积来计算 $n!$：从1开始乘2、乘3，一直乘到$n$为止。这可以形式化为保持两个状态变量——当前计数器counter和当前累计积product，然后逐步更新：

• 初始化：counter = 1, product = 1。
• 循环步：若counter <= n，则令product = counter * product，同时counter = counter + 1，重复。
• 直到counter > n时，product即为结果。

用递归方式表达上述迭代过程，我们可以这样实现阶乘：

function factorial(n) {
    return fact_iter(1, 1, n);
}
function fact_iter(product, counter, max_count) {
    return counter > max_count
           ? product
           : fact_iter(counter * product,
                       counter + 1,
                       max_count);
}

在factorial中，我们调用辅助的迭代过程fact_iter，初始参数product=1、counter=1、max_count=n。fact_iter每次递归都会更新product和counter，当counter越过n时结束递归并返回积累的product。这里没有“延迟”的乘法链，每一步计算都会实际进行一次乘法更新状态。这样的过程被称为迭代计算过程：它可以被一组固定数量的状态变量的变化所描述，且每一步变化遵循同样的规则。在上述阶乘例子中，状态由(product, counter, max_count)三个变量构成，状态转移规则由product←counter*product, counter←counter+1给出，一旦counter>max_count即停止。

现在我们有两种实现阶乘的方式：一种是线性递归的（乘法链推迟执行，最后展开），一种是线性迭代的（随算随得，中途不需要保存历史）。尽管它们计算相同的数学函数，在使用相同乘法次数下得到相同结果，但它们对应的计算过程形态截然不同。对比：

• 递归过程：呈现出扩展再收缩的形态，需要保存“尚未完成”的中间计算（如乘法链）。在factorial(6)的递归计算中，我们展开出乘法链6 * 5 * 4 * 3 * 2 * 1，推迟实际计算，直到基例算出1再回溯完成乘法。这个过程中，解释器需要记住还有哪些乘法没做（通过调用栈保存上下文）。因此，递归过程占用的空间随$n$增长而线性增长（需要保存$n$层嵌套调用的栈帧），执行步骤数也线性增长（需要$n-1`次乘法）。
• 迭代过程：没有延期的计算，也不需要保存先前状态链条。对于factorial(6)的迭代实现，解释器在每个调用帧中即可更新product和counter，无需额外空间记录历史。整个计算只使用恒定的空间（即固定的几个变量），步骤数仍然是线性的$n-1`次乘法。当过程停止时，调用栈也随之弹空，不会像递归实现那样还要等待逐层返回。

换言之，递归过程消耗的空间与时间均为Θ(n)，而迭代过程消耗的时间是Θ(n)但空间是Θ(1)。在现代编程语言中，如果支持尾调用优化（Tail-Call Optimization），像fact_iter这样的尾递归函数可在底层以迭代方式实现，从而既保持递归写法的直观，又获得常数空间占用的效率。然而，JavaScript（尤其是ECMAScript标准）对尾调用优化的支持并不完善或一致，所以严格来说，在不考虑引擎优化时，JavaScript中的递归实现仍然会有较高的栈空间开销。因此，在实践中需要根据问题规模选择合适的实现方式。

这里还必须澄清：递归函数和递归过程是相关但不同的概念。一个函数的定义是递归的，并不一定产生递归的过程——如果它通过尾递归优化可以演变为迭代过程。同样，一个迭代过程也可以由递归函数来实现（就像fact_iter），二者并不矛盾。关键区别在于计算过程的动态行为：是否需要保存“未决”的操作。我们应该养成区分这两个概念的习惯，以免误以为“递归函数就是慢的、费空间的”。事实上，通过恰当的优化，递归定义可以表达迭代过程，从而兼顾表达力和效率。

树形递归与增长阶

除线性形态外，还有一种常见的递归模式称为树形递归。树形递归的特征是：函数在定义中可能调用自身不止一次，从而每层调用会产生多个分支。典型例子是计算斐波那契数列：

斐波那契数 $F(n)$的数学定义是：$F(0)=0,F(1)=1$，对于$n\ge 2$有 $F(n)=F(n-1)+F(n-2)$。按照这个定义写出递归程序：

function fib(n) {
    return n === 0 ? 0
         : n === 1 ? 1
         : fib(n - 1) + fib(n - 2);
}

这个fib函数在计算过程中会呈现出树状的递归展开。例如计算fib(5)时，需要fib(4)和fib(3)；而计算fib(4)又需要fib(3)和fib(2)；如此展开下去，我们会得到一棵递归调用树，每个节点对应一次fib调用，节点分支反映函数内部两次递归调用。这棵树的分支数随着 $n$ 增长急剧增多。实际上，计算 fib(n) 所产生的递归调用次数与斐波那契数本身相关：可以证明，fib(n) 的调用次数大约为 $F(n+1)$，其增长是指数级别。更准确地，$F(n)$ 约等于 ${\displaystyle \frac{1}{\sqrt{5}}}{\varphi }^n$（其中 $\varphi \approx 1.618$ 是黄金分割率），因此计算 fib(n) 需要 $\mathrm{\Theta }({\varphi }^n)$ 步骤。即使对于不太大的 $n$，这种指数爆炸也会造成大量冗余计算（例如 fib(3) 在计算 fib(5) 时被重复计算了两次，占总工作量的大约一半）。其空间复杂度则与递归深度线性相关（树的深度为 $n$）。

斐波那契例子表明，直接按照数学递归定义实现，有时会产生非常低效的算法。但我们也能针对这一特定问题设计更高效的解法。例如，可以用迭代过程在线性时间内计算斐波那契数：只需在循环中维护 $(a,b)$ 表示当前的 $(F(k),F(k-1))$，反复应用转换 $a\leftarrow a+b,b\leftarrow a$ 即可。下面是书中给出的迭代实现：

function fib(n) {
    return fib_iter(1, 0, n);
}
function fib_iter(a, b, count) {
    return count === 0
           ? b
           : fib_iter(a + b, a, count - 1);
}

这个实现中，每一步递归将$(a,b)$更新为$(a+b,a)$，并使计数count减1。当count为0时，$b$即为答案。这是一个线性迭代过程，所需步数Θ(n)，空间Θ(1)。与指数时间的递归算法相比，即使对于中等大小的n，效率差别都是天壤之别。

然而，树形递归并非一无是处。在某些问题中，树形递归更自然地匹配问题结构，并且结果规模本身就呈指数增长（例如组合计数问题）。此时树形递归反而是直观且合理的解法。SICP举了一个换零钱的例子：给定几种硬币币值，问用这些硬币凑出指定金额有多少种不同组合。这个问题的解法就很适合用树形递归描述：要么考虑第一种硬币用0枚、要么用1枚、2枚…，将问题分解为子问题递归求解。这种解法虽然也是指数级时间，但对应的问题本身的输出（组合总数）就可能呈指数增长，因此接受指数复杂度是必要的。

更重要的是，清晰和高效往往需要权衡。斐波那契的递归实现虽然低效，却直接对应了斐波那契数列的定义，因而非常直观、容易验证正确性。反之，迭代实现需要我们识别出隐藏的状态规律并引入额外变量才能完成。在复杂问题上，找出等价的迭代算法可能相当困难甚至不切实际。因此，编程时应根据具体需求选择方案：如果问题规模不大或更关注清晰度，递归解法未尝不可；如果规模很大则必须考虑算法改进或优化。有经验的程序员能够以抽象思维发现算法改进之道，将指数级降低为多项式或对数级，从而解决更大规模的问题。

算法的增长阶与示例分析

SICP在1.2.3节专门讨论了计算过程随输入规模增长的复杂度阶（Order of Growth）。增长阶使用Θ符号来粗略描述算法所需资源（时间、空间）相对于输入规模的渐近增长趋势。例如，阶乘的递归过程需要Θ(n)时间和Θ(n)空间，而迭代版本需要Θ(n)时间和Θ(1)空间；斐波那契递归需要Θ(${\varphi }^n$)时间和Θ(n)空间，而斐波那契迭代需要Θ(n)时间和Θ(1)空间。通过这些例子，我们已初步领略算法复杂度分析的意义。

为进一步说明改进算法对效率的巨大影响，本章最后给出了两个对数时间的算法示例：幂运算和欧几里得算法，并探讨了素数检测问题中不同算法的效率差异。

幂运算：计算$b^n$，一个朴素的方法是连乘$n$次，这显然是Θ(n)时间的算法。我们可以像对阶乘那样将其改写为迭代形式（将乘法循环累积），空间降为常数但时间仍是线性。不过，存在一种著名的折半算法可以将时间复杂度降低到Θ(log n)：利用指数的二分性质：

• 如果$n$是偶数，$b^n=(b^{n/2}{)}^2$；
• 如果$n$是奇数，$b^n=b\times b^{n-1}$。

据此，我们可以设计一个递归算法，每次将指数减半：

function fast_expt(b, n) {
    return n === 0 ? 1
         : is_even(n) ? square(fast_expt(b, n / 2))
         : b * fast_expt(b, n - 1);
}
function is_even(n) {
    return n % 2 === 0;
}

这个fast_expt在每次递归中把问题规模大致减半，因此乘法次数大约是${\log }_{2}n$次（更准确地说，是$\lfloor {\log }_{2}n\rfloor$次平凡递归加上若干次乘法，与$n$二进制展开中1的个数有关，但仍是Θ(log n)级别）。例如计算$2^{1000}$，朴素算法需要1000次乘法，而快速算法只需大约14次（因为$2^{10}$大约是1024）。这差异是巨大的。我们可以同样采用这种“指数平方法”设计出一个迭代版本（练习1.16要求实现）——尽管迭代实现要比递归实现稍微复杂一些，需要引入不变量来维护状态。无论如何，**指数级改进（将n提高到log n）**充分展示了算法优化的意义。当$n$非常大时，只有对数时间的算法才能应对；线性算法很可能无法在合理时间内完成。例如，SICP打趣道：“或许你会疑惑谁会关心计算某数的1000次方”——但作者马上通过素数检测的例子表明，大数的幂运算在密码学等领域有实际用途（例如实现RSA算法需要快速计算大幂模运算），因此算法效率不是书呆子的空想，而是实实在在的工程问题。

欧几里得算法（求最大公约数）：给定两个正整数$a$和$b$，欧几里得算法基于一个重要性质：如果用$b$去除$a$得到余数$r$，那么$gcd(a,b)=gcd(b,r)$。反复应用这个性质，余数将越来越小，直至变为0，此时另一个数就是最大公约数。例如 $gcd(206,40)$ 的计算过程：

$206,40\to 40,6\to 6,4\to 4,2\to 2,0,$

可见 $gcd(206,40)=2$。用代码实现非常简洁：

function gcd(a, b) {
    return b === 0 ? a : gcd(b, a % b);
}

这个算法每一递归都显著减小问题规模：除法余数$r‘\mathrm{小}\mathrm{于}\mathrm{除}\mathrm{数}$b`。可以证明，欧几里得算法的步骤数增长为Θ(log n)级别（这里$n$可理解为较大输入的数量级）。Lamé定理给出了更精确的描述：若算法进行了$k$步迭代，则较小的初始输入至少大于等于第$k$个斐波那契数。因此最坏情况下步骤$k$大致与斐波那契数迭代到接近$b$同量级，这个$k$是$O(\log b)$的。这意味着，即使输入是非常大的数（例如有几百位十进制数），欧几里得算法也能在极短时间内求出其GCD。

这再次展现了算法威力：同样是求最大公约数，简单的“找出所有因子再求交集”方法在最坏情况下是非常慢的（对大数因数分解本身就是艰深的难题），而欧几里得算法高效优雅。SICP选择在第一章就介绍它，也是为了让读者体会利用数学性质优化算法的艺术。它强调了计算机科学与数学的紧密联系：数学上发现的定理和技巧，往往可以直接转化为高效的计算过程，从而在实践中解决原本难以处理的问题。

练习：素数检测的两种方法

作为对比效率的压轴案例，本章最后探讨了判定素数这一问题，展示如何通过引入随机化算法将一个本需指数时间的问题简化为可行。

判断一个数$n$是否为素数，朴素的方法是尝试除以小于$n$的每个数，看有无整除。实际上不必试到$n$，试到$\sqrt{n}$即可，因为如果存在因子，大的那个因子乘上小的那个不会超过$n$。书中首先实现了一个smallest_divisor(n)函数，找出$n`的最小非1因子：从2开始逐个尝试，如果能整除则返回，不然逐渐递增试探。然后定义：

function is_prime(n) {
    return n === smallest_divisor(n);
}

也就是说，如果一个数的最小因子是它本身，那么它没有更小的因子，只能是素数（当然需排除1的特殊情况）。由于smallest_divisor至多检查到$\sqrt{n}$，该算法的时间复杂度为Θ(√n)。对于10位数（~十亿），√n约是几万；对于20位数（~百万兆），√n约是十亿——后者的数量级已经非常大，不可能枚举。所以朴素试除法对于很大的数是不可行的。

SICP引入了一种概率算法来改进素性测试，基于费马小定理：若$n$是素数，并且$a$是小于$n$的任意正整数，则 $a^n\equiv a(\mathrm{mod}n)$。反过来，如果我们随机选择一些$a$来测试这个同余关系，大多数合数都会不满足，从而可以被识别为合数。具体地，算法为：针对给定的$n$，随机挑选若干$a<n$，计算 $a^{n}modn$（这里需要快速幂取模算法辅助，以提高效率），如果发现对于某个$a$有 $a^n\not\equiv a(\mathrm{mod}n)$，就断定$n$不是素数；如果对许多随机$a$都测试通过，则以极高置信度认为$n$是素数。这样的费马测试不会给出绝对确定性（存在极少数合数对所有$a$都蒙混过关，称为伪素数或卡迈克尔数），但可以将出错概率降到任意低。事实上，连续通过若干次随机测试后，出现错误判定的概率可以比计算机硬件偶然出错的概率还低；在工程上，这已经足够可靠。因此费马测试为判定素数提供了一个高效可行的途径。

更重要的是，费马测试的时间复杂度约为Θ(log n)。原因是：我们可以借助前面讨论的“快速指数模运算”来在Θ(log n)时间内计算 $a^{n}modn$，而测试需要执行常数次（或线性次，但独立于$n$的大小）。因此总体是对数时间的。对比如下：

• 试除法检测：Θ(√n) ~ 指数级别（输入长度为$m$位数时，大致Θ(${10}^{m/2}$)）。
• 费马测试：Θ(log n) ~ 多项式级别（输入长度$m$位时为Θ(m)）。

差别不可谓不巨大。书中练习1.22让我们用smallest_divisor方案实际测量若干位数素数检测的运行时间，验证其随着$n`增大呈现约10倍的增长。而练习1.24则要求改用费马测试，比较对1000左右的数和百万量级的数检测时间，应该可以发现后者相对前者增加极小。这组练习旨在让读者以实验支撑理论：随机化算法在判定素数问题上将指数难题降为了多项式时间。实际上，1970年代发现的这些随机素性测试（如Solovay–Strassen、Miller–Rabin等，费马测试是Miller–Rabin的基础）奠定了现代密码学的基础。RSA算法的安全性依赖于大整数分解的困难，但我们又需要快速判断一个大整数是否素数来挑选密钥，概率算法正好解决了这个矛盾。在2021年之前，判断任意大数素性的最快方法几乎都是基于这些随机算法。计算的惊人表现力由此可见一斑：仅用简单的算术和随机取样，我们就在几秒内完成了对一个300位（上百位十进制）大数素性的判断——这是朴素方法在宇宙寿命内都无法做到的。

总之，通过素数检测的例子，我们体会到选择适当的算法和利用巧妙的抽象（如将素性判定问题转化为幂同余测试）能够极大提升效率。计算机科学不仅关心程序能否正确计算出结果，还关心计算是否在合理时间内完成。第一章借由这些例子向我们初步展示了算法分析的思路：用增长阶粗略估计性能，并通过数学推导或实验验证来理解算法的行为。更深层地，这些内容也引出了后续章节的话题，比如惰性求值（为什么费马测试选择随机$a$而不穷举？我们允许一定概率失败换来平均性能提升）、数学与计算的结合（数论定理指导算法设计）等等。对于初学者而言，这些例子强调了：写程序不只是让计算机“会做”某事，还要让它“做好”某事——找到好的过程抽象和算法，是程序设计的核心竞争力之一。

用高阶函数构造抽象

在第一章的最后一节，SICP介绍了另一种强大的过程抽象手段：高阶函数（Higher-Order Function），即可以接受函数作为参数或将函数作为返回值的函数。高阶函数使我们能够抽象出很多通用的计算模式，并极大提高了语言的表达能力。本节通过几个范例说明如何利用高阶函数来构造抽象，包括将计算过程参数化、提炼通用模式，以及构造返回函数的工厂等。

提炼通用模式：以求和函数为例

回顾我们前面的编程练习，会发现许多函数在结构上是类似的。书中先举了三个求和函数的例子：

1. 求整数和：计算从整数$a$到$b$的和。
2. 求立方和：计算给定范围内所有整数的立方的和。
3. 计算一个序列的求和：具体例子是计算序列 $1/1\cdot 3+1/5\cdot 7+1/9\cdot 11+\cdots$ 的和（这个序列会收敛到 $\pi /8$）。

对应的代码分别可能是：

function sum_integers(a, b) {
    return a > b ? 0 : a + sum_integers(a + 1, b);
}
function sum_cubes(a, b) {
    return a > b ? 0 : cube(a) + sum_cubes(a + 1, b);
}
function pi_sum(a, b) {
    return a > b ? 0 : 1/(a * (a + 2)) + pi_sum(a + 4, b);
}

细心观察可以发现，这三个函数共享了非常相似的结构——它们只有两处有所不同：

• 求和的具体项如何计算：整数和直接取a，立方和取cube(a)，序列和取1/(a*(a+2))。
• 下一次迭代如何前进：整数和和立方和都是a+1，而序列和则步进4（因为序列项每次增加4）。

除此之外，递归模式都是：“如果$a > b`则返回0，否则计算当前项加上递归调用求和”。这种高度一致性暗示我们可以提炼出一个通用的求和抽象，将可变的部分参数化。

数学家早已发明了“∑”符号来表达求和的抽象概念，例如：

$\sum _{n=a}^{b}f(n)=f(a)+f(a+1)+\cdots +f(b)$

这个符号的威力在于，它使我们能够直接处理“求和”这个概念本身，而不是具体的某个求和实例。同样地，作为程序设计者，我们希望语言足够强大，能让我们写出“求和”这种高阶概念的函数。幸运的是，通过允许函数作为参数，我们正可以做到这一点。

我们构造一个高阶函数sum，令其接受几个参数：term（一个函数，用于计算求和项）、next（一个函数，用于生成下一个自变量的值）、以及上下界a和b。sum的逻辑即为前述递归模板的抽象版：

function sum(term, a, next, b) {
    return a > b
           ? 0
           : term(a) + sum(term, next(a), next, b);
}

现在，sum函数本身没有固定要做“整数和”或“立方和”——这些细节通过参数传入。我们填入不同的参数组合，就可以实例化出不同的求和函数。例如：

• 整数求和可以通过sum(identity, a, inc, b)来实现，其中identity(x) = x是恒等函数，inc(x) = x+1是递增函数：

  function identity(x) { return x; }
  function inc(n) { return n + 1; }
  function sum_integers(a, b) {
      return sum(identity, a, inc, b);
  }

  调用sum_integers(1, 10)将计算$1+2+\cdots +10$并得到55。

• 立方和可以通过sum(cube, a, inc, b)构造，其中cube(x)计算$x^3`：

  function sum_cubes(a, b) {
      return sum(cube, a, inc, b);
  }

  例如sum_cubes(1, 10)会得到$1^3+\cdots +{10}^3=3025$。

• 序列和可以通过提供特定的term和next来实现，例如：

  function pi_sum(a, b) {
      function pi_term(x) { return 1/(x * (x + 2)); }
      function pi_next(x) { return x + 4; }
      return sum(pi_term, a, pi_next, b);
  }

  那么8 * pi_sum(1, 1000)将计算上述序列1000项的和，再乘以8，得到对$\pi$的近似。

通过这样一次抽象，我们消除了大量重复的模式化代码，把注意力从“怎么遍历相加”转移到了“定义项和步进方式”上。这体现了高阶函数的价值——将过程一般化，变成一种可参数化的模板。现在，如果我们想要计算“从a到b以步长n累加某函数”的结果，不用每次重写递归，只需调用sum并提供对应的term和next即可。就像数学家运用$\sum$符号能推导出许多不依赖特定求和实例的结论一样，程序员运用sum这样的高阶过程也能轻松构造出各种新的运算。

书中还展示了用sum进一步构造抽象的例子：定积分的数值近似。定积分的定义（黎曼和）其实就是求和的极限形式。譬如，用宽度为dx的矩形近似积分：

${\int }_a^{b}f(x)dx\approx \sum _{k=1}^{n}f(a+k\cdot dx)\cdot dx,$

其中 $dx=\frac{b-a}{n}$。我们可以直接利用sum实现一个积分求近似的函数：

function integral(f, a, b, dx) {
    function add_dx(x) { return x + dx; }
    return sum(f, a + dx/2, add_dx, b) * dx;
}

这里选择取每个小区间的中点 (a + dx/2, a + 3dx/2, ... ) 来估计，提高精度。有了它，我们可算例如 ${\int }_0^1{x}^{3}dx$ 的近似值：integral(cube, 0, 1, 0.001)，结果约0.24999987，与真实值1/4非常接近。

练习1.29更进一步，引入辛普森规则这种更高精度的积分方法，让读者实现一个带参数$f,a,b,n$的simpson函数，并比较用simpson和integral计算结果的差别。辛普森规则用二次插值多项式达到更高阶误差项抵消，其公式比矩形法复杂一些，但练习的本质仍是让我们将公式翻译成程序。这道题也印证了高阶过程的灵活性——即使公式复杂，我们仍不过是在描述“对$f$进行一系列固定加权的求和”。如果需要，我们甚至可以再次利用sum来组织辛普森求和的实现：只不过term将涉及$f‘\mathrm{在}\mathrm{不}\mathrm{同}\mathrm{分}\mathrm{点}\mathrm{的}\mathrm{值}，‘next\text{`}\mathrm{步}\mathrm{长}\mathrm{是}$h$的一倍或两倍交替等等。当然，在实际编码中直接写循环也许更方便，但抽象的思路是贯通的。

在练习1.30～1.33中，SICP进一步引导读者思考如何进一步抽象sum这样的模式。比如：

• 练习1.31要求实现一个类似sum的高阶函数product，返回区间内一系列项的乘积。并让我们用product去定义阶乘（验证product(n, 1, inc, n)等价于n!）以及计算某个π的近似公式（Wallis乘积公式）。
• 练习1.32指出，sum和product其实是更一般的累积（accumulation）操作的特例。如果引入一个参数combiner（如加法或乘法）和一个null_value（加法的零元0，乘法的单位元1），就可以把sum和product统一为一个更通用的高阶函数accumulate(combiner, null_value, term, a, next, b)。我们只需调用accumulate((x,y)=>x+y, 0, term, a, next, b)就能完成求和，调用accumulate((x,y)=>x*y, 1, term, a, next, b)就能完成求积。
• 练习1.33则更进一步，要求实现一个带过滤（filter）功能的累积，即在累积前先对项进行筛选，只累加或累乘满足条件的项。比如可以用filtered_accumulate求出某范围内素数的和，或与给定$n$互素的数的乘积等。

这些练习旨在让我们体会：通过恰当的抽象，我们可以将一些看似完全不同的操作统一起来，从而以极高的思维层次去设计程序。当然，作者也提醒读者，目前我们缺乏操作通用数据序列的手段，这些抽象在第2章介绍序列后会更有用武之地。即便如此，此处的训练已经体现出高阶函数的威力：程序语言本身为我们提供了抽象手段，我们可以像对待数据一样将过程本身作为操作对象来组合和变换，从而创造出更高级别的过程抽象。

匿名函数与本地函数

上一小节，我们定义sum时不得不为每种求和模式显式声明辅助函数（如pi_term、pi_next），有时显得冗长。有没有办法直接在函数调用的参数位置描述需要的函数，而不必提前起名字呢？答案就是使用匿名函数（anonymous function），也称lambda表达式。JavaScript在ES2015中引入了箭头函数语法，可以方便地创建匿名函数。例如：

• 一个返回其输入值加4的函数可写作 x => x + 4；
• 一个返回$\frac{1}{x(x+2)}$的函数可写作 x => 1 / (x * (x + 2))。

这样，我们就不需要声明pi_term和pi_next，可以直接将它们作为参数传给sum：

function pi_sum(a, b) {
    return sum(x => 1/(x * (x + 2)),
               a,
               x => x + 4,
               b);
}

同样，前面的integral函数也可以省去辅助的add_dx函数，通过箭头函数内联：

function integral(f, a, b, dx) {
    return sum(f,
               a + dx/2,
               x => x + dx,
               b) * dx;
}

可以看到，箭头函数让我们直接将过程作为“一等公民”在表达式中使用：我们编写x => ...就像编写数字或字符串字面量一样，将一个过程直接嵌入到更大的组合表达式里。上面的例子甚至出现了这样的形式：sum(x => 1/(x * (x + 2)), ...)，即函数的某个实参本身又是一个函数应用（这里是箭头函数表达式）。这在语法上是完全合法的，也充分体现了高阶函数的用法。

值得注意箭头函数的语法和作用范围规则：箭头函数 (parameters) => expression 等价于一个匿名函数，其参数列表和返回值由箭头两侧指定。在箭头函数内部可以直接使用外部环境中的变量（静态/词法作用域依然适用），但如果定义了同名的参数或局部变量则会遮蔽外部的同名变量。当需要编写多行函数体时，可以用括号包裹表达式改写成块语句（ES2015之后也支持箭头函数有块体）。另外要小心箭头函数的优先级比函数调用运算符低，因此有时需要用括号括起箭头函数再调用。例如，前述匿名求和例子如果少了外层括号写成 ((x,y,z) => x + y + square(z))(1,2,3) 是必要的，否则会被解析错误。

引入匿名函数还有一个显著益处：可以方便地创建本地函数，从而简化封装。想象我们有一个函数需要一些辅助手段处理中间结果。过去我们可能通过在函数内部声明一个子函数（命名函数）或在外部定义一个工具函数，然后在内部调用。但这增加了名字管理的负担。利用匿名函数，我们可以在需要的时候立即构造并调用它，从而在函数内部引入局部名字。例如书中讨论的例子：定义一个函数 $f(x,y)=(1+x\ast y{)}^2+y\ast (1-y)+(1+x\ast y)(1-y)$（这个例子实际来自书中1.3.2节插入的一个数学公式，意在说明如何在函数内便利地引入局部变量）。为了计算这个表达式，我们希望复用中间结果 $a=1+x\ast y$ 和 $b=1-y$。可以有几种方法：

• 使用内部命名的辅助函数：将$a$和$b$当作参数传递：

  function f(x, y) {
      function f_helper(a, b) {
          return x * square(a) + y * b + a * b;
      }
      return f_helper(1 + x * y, 1 - y);
  }

这样f_helper为局部函数，引入了局部名字a、b，起到了在f内部定义局部变量的作用。然f_helper这个名字本身其实并不需要对外可见，仅用于包裹计算。

• 使用立即调用的匿名函数：我们可以用一个箭头函数来扮演f_helper，在定义的同时就用(1 + x*y, 1 - y)调用它：

  function f_2(x, y) {
      return ((a, b) => x * square(a) + y * b + a * b)(1 + x * y, 1 - y);
  }

这里 ((a, b) => ...)(expr1, expr2) 等价于定义了一个匿名函数并立刻以expr1和expr2为参数调用它。这样一来，我们无需命名f_helper，仍然达到了引入局部名字a和b的目的。

• 使用块作用域的常量声明：其实ES2015进一步提供了let和const来声明块级局部变量，更为直接。上述函数可用块内const来实现：

  function f_3(x, y) {
      const a = 1 + x * y;
      const b = 1 - y;
      return x * square(a) + y * b + a * b;
  }

这里 a 和 b 仅在函数f_3的块作用域内有效。相较前两种方法，这种写法可能更清晰直观（它本质相当于语法糖——代替我们手动创建并调用匿名函数来绑定局部名）。SICP强调了，块内用const引入名字其作用域为所在块，而且在声明之前不可使用该名字（即所谓的暂时性死区）。这一点在多层嵌套时需要小心，以避免误用外部同名变量或在声明前就引用。

需要说明的是，尽管JS箭头函数和const很方便，但在SICP的思想体系中，它们只是辅助我们进行函数式抽象的工具。本质上，我们关心的是如何正确抽象和封装计算过程，至于用匿名函数、内部函数还是局部变量，只是实现上的选择。本书选择在1.3.2节就介绍lambda表达式的用法，并非要求初学者马上习惯这种写法，而是为了揭示：命名和函数其实可以解耦。我们完全可以创建不带名字的函数，也可以给已有函数赋予一个名字。正如脚注6所提示的，这是两个概念：创建函数和命名函数。理解这一点很重要，因为在后面的内容里，高阶函数的组合会经常产生临时的函数对象，我们不会为它们命名，而是直接将它们当作值来传递。匿名函数让我们以更简洁的方式写出高阶函数调用，使抽象更贴近我们思维的描述。例如看到sum(x => x*x, 1, x => x+1, 5)，很清楚地表明了我们在求 $\sum _{x=1}^5{x}^2$。

通用过程抽象：寻找根与不动点

高阶函数不仅可以抽象简单的循环模式，还能帮助我们描述通用的计算方法。书中1.3.3节通过两个例子——区间折半法和不动点迭代法，展示如何使用高阶函数来表达一般的求解策略，使之适用于各种具体问题。

区间折半法求方程根：给定连续函数$f(x)$，如果在区间$[a,b]$两端函数值异号，即 $f(a)<0\text{<}f(b)$，那么根据介值定理，在$(a,b)$之间必有$f(x)=0$的根。折半法（又称二分法）利用此性质逼近根：反复将区间二分，取中点$m=(a+b)/2$计算$f(m)$，然后根据$f(m)$的正负决定舍弃哪一半区间，使新区间依然两端异号。如此迭代直到区间足够小，中点近似解就是方程根。折半法每一步将区间长度减半，因此需要的迭代步数大致是${\log }_2((b-a)/T)$，其中$T$是容许误差阈值。时间复杂度为Θ(log((b-a)/T))，收敛相当快且保证收敛（前提是函数连续且初始区间确有异号根）。

我们可以实现一个通用的折半查找函数search(f, neg_point, pos_point)，接受函数f及一个已知$f$值为负的点和一个$f$值为正的点，然后递归地缩小区间：

function search(f, neg_point, pos_point) {
    const midpoint = average(neg_point, pos_point);
    if (close_enough(neg_point, pos_point)) {
        return midpoint;
    } else {
        const test_value = f(midpoint);
        return positive(test_value)
               ? search(f, neg_point, midpoint)
               : negative(test_value)
               ? search(f, midpoint, pos_point)
               : midpoint;
    }
}

这个实现中，用close_enough(x,y)判定当前区间是否已经足够小，可以复用之前求平方根时的类似判断方法（例如差距小于0.001为足够小）。positive和negative是用于判断符号的辅助函数。需要特别处理的是如果f(midpoint)恰好为0则直接返回中点作为根。有了search这个通用过程后，我们再包装一个函数half_interval_method(f, a, b)用于检查给定区间端点符号并调用search：

function half_interval_method(f, a, b) {
    const a_value = f(a);
    const b_value = f(b);
    return negative(a_value) && positive(b_value)
           ? search(f, a, b)
           : negative(b_value) && positive(a_value)
           ? search(f, b, a)
           : error("values are not of opposite sign");
}

这样，我们就得到了一个通用的求根方法。不论$f(x)$是什么具体函数，只要能提供区间$[a,b]$符号相反，我们就可以用half_interval_method逼近它的一个零点。举例：

• half_interval_method(Math.sin, 2, 4) 会找到$\sin x=0$在区间$(2,4)$的根，结果应接近$\pi \approx 3.14159$。
• half_interval_method(x => x*x*x - 2*x - 3, 1, 2) 会找到方程 $x^3-2x-3=0$ 在$(1,2)$的根，结果约1.893。

可以看到，我们通过高阶函数将“折半求根”这一方法抽象出来。half_interval_method就像一个通用的算法模块，参数化了具体的函数$f$。这体现了SICP一直强调的理念：将“如何做”的部分分离出来，上升为独立的概念。在这里，“如何找根”被浓缩成了search，而与具体函数的关联仅通过参数发生。结果就是一个高度通用、可复用的过程抽象。

不动点迭代法：另一个通用方法是不动点(fixed-point)搜索。不动点指的是一个值$x$满足 $f(x)=x$。许多方程求解问题可以转化为寻找某个迭代函数的固定点。例如，求方程$g(x)=0$的解，可以写成寻找$f(x)$的不动点，其中 $f(x)=x-\frac{g(x)}{Dg(x)}$（这正是牛顿迭代的函数形式，我们稍后讨论）。固定点迭代法的一般思想是，从某个初始猜测$x_0$出发，不断计算$x_{n+1}=f(x_n)$，希望序列$x_n$能收敛到$f$的不动点。我们需要一个终止判定，当连续两次迭代结果足够接近时，就认为达到了不动点近似。

书中实现了一个高阶函数fixed_point(f, first_guess)，通过迭代逼近$f$的不动点：

const tolerance = 0.00001;
function fixed_point(f, first_guess) {
    function close_enough(x, y) {
        return abs(x - y) < tolerance;
    }
    function try_with(guess) {
        const next = f(guess);
        return close_enough(guess, next)
               ? next
               : try_with(next);
    }
    return try_with(first_guess);
}

可以看出，这和前面的sqrt_iter逻辑很相似，只是判定条件和迭代函数变成了通用的形式。fixed_point接受一个函数f和一个初始猜测值，不关心$f的具体含义，只要我们能实现它，fixed_point`就能帮我们找到 $f(x)=x$ 的解（前提是迭代确实收敛）。

举几个例子：

• 寻找 $\cos (x)=x$ 的解。由于 $\cos (x)$ 的图像与 $y=x$ 有交点，这实际上是在求解 $\cos (x)-x=0$。调用 fixed_point(Math.cos, 1) 可以逼近此不动点，结果约为0.73908（这就是著名的戴维南常数）。
• 求解方程 $y=\sin y+\cos y$。这可以转化为寻找函数 $f(y)=\sin y+\cos y$ 的不动点。调用 fixed_point(y => Math.sin(y) + Math.cos(y), 1)，得到约1.25873。

这些例子表明，fixed_point 是一个相当通用的求解器——我们只需定义好迭代函数 $f$，就能尝试找到满足 $f(x)=x$ 的值。

现在，回到我们之前实现的平方根问题。注意到，当时我们说平方根问题可以表述为求$y$使 $y^2=x$，即 $y=x/y$。这正是函数 $g(y)=x/y$ 的不动点条件。于是，一个天真的想法是直接用fixed_point求函数 $y\mapsto x/y$ 的不动点，期望迭代序列收敛。然而，实践会发现这次迭代会在两个值之间来回震荡，而无法收敛。例如求$\sqrt{4}$时，若初始猜测1，那么序列将是1 → 4 → 2 → 2 → 2 → ...，实际落入了循环（对于一般$x$则是在两个近似值之间来回震荡）。问题在于迭代步幅太大：$f(y)=x/y$把猜测从一边拉到了另一边，却没有渐进缩小距离。

为了解决此问题，我们采用了一种常用技巧：平均阻尼（average damping）。就是将迭代函数稍作修改，取$f(y)$和$y$的平均值作为新猜测，从而减缓变化幅度，确保单调收敛。对于 $y=x/y$，加入平均阻尼得到新的迭代函数 $y\mapsto \frac{1}{2}(y+x/y)$。事实证明，这正对应了牛顿法，我们前面以特殊方式实现的improve函数就是做这个事。而现在，用高阶函数的方法，我们可以直接通过组合已有抽象来得到这个改进：

书中定义了一个高阶函数average_damp, 它接受一个函数$f$，返回一个新的函数，其值是 $x$ 和 $f(x)$ 的平均值：

function average_damp(f) {
    return x => average(x, f(x));
}

这个average_damp本身就是一个返回函数的高阶函数，它将“平均阻尼”这一操作抽象成了可以套用在任何函数上的变换。例如，average_damp(Math.sqrt) 将返回一个函数，其输出是 $(x+\sqrt{x})/2$。将其应用于$x=10$会得到 $(10 + \sqrt{10})/2 ≈ 5.74:contentReference[oaicite:234]{index=234}:contentReference[oaicite:235]{index=235}。现在，我们可以利用average_damp`改进平方根的求解：

function sqrt(x) {
    return fixed_point(average_damp(y => x / y), 1);
}

这个新版的sqrt用一行代码清晰地结合了三个思想：不动点搜寻、平均阻尼以及特定的迭代函数 $y\mapsto x/y$。相比我们在1.1.7节写的原始版本，这个抽象版本更凸显出计算的数学原理：它直接表达了“平方根是$y\mapsto x/y$在平均阻尼下的不动点”。通过对比两种写法，我们体会到，将想法抽象化为组合的高阶函数，可以让程序更接近人类对问题的思考方式。在这个例子中，我们通过fixed_point和average_damp这样高度抽象的模块，把求平方根这一特定问题的一般模式提炼了出来，使得程序读起来几乎就是对算法的自然语言描述。

进一步的好处是抽象的复用：既然平方根计算被视为一种不动点问题的特例，那么求立方根等也可以套用类似方法。书中指出，$y^3=x$ 可转化为 $y=x/y^2$，所以立方根就是函数 $y\mapsto x/y^2$ 的不动点，也需要平均阻尼才能收敛。因此，只需修改迭代函数，我们立即得到：

function cube_root(x) {
    return fixed_point(average_damp(y => x / square(y)), 1);
}

这样，通过构造通用抽象，我们避免了为立方根问题从零开始设计算法——直接复用了平方根求解的模式。抽象使知识可以迁移和重组，正如数学中一旦我们掌握某种方法，就可以举一反三解决一类问题。

牛顿法的一般形式：前面提到，不动点迭代可以描述牛顿法。牛顿法用于求解 $g(x)=0$，基本迭代公式是：

$x_{n+1}=x_n-\frac{g(x_n)}{g^{\prime }(x_n)}.$

可将其封装为函数：$N(g)(x)=x-\frac{g(x)}{g^{\prime }(x)}$。那么方程$g(x)=0$的解就是$N(g)$的不动点。在代码中，我们可以先实现一个高阶函数deriv(g)来返回$g$的导数函数的近似：

const dx = 0.00001;
function deriv(g) {
    return x => (g(x + dx) - g(x)) / dx;
}

这里用了微小增量dx（1e-5）计算差商，作为导数的近似。然后定义newton_transform(g)返回$N(g)$函数：

function newton_transform(g) {
    return x => x - g(x) / deriv(g)(x);
}

最后，定义newtons_method(g, guess)为在给定初始猜测下对$N(g)$求不动点：

function newtons_method(g, guess) {
    return fixed_point(newton_transform(g), guess);
}

现在，newtons_method可以用来求解很多方程。比如，我们可以重新定义平方根为寻找 $y^2-x=0$ 的正根：

function sqrt(x) {
    return newtons_method(y => square(y) - x, 1);
}

同样，可以用一行通过newtons_method定义立方根。这样得到的结果与前面的fixed_point方法是一致的，只是Newton方法收敛更快。Newton每次迭代通常能将有效精度加倍，所以它比折半法还要快（局部二次收敛）。

通过引入newton_transform，我们把牛顿法本身也变成了一个可传递给fixed_point的“变换”参数。而看到fixed_point和newtons_method这两个定义，我们可以再做一次抽象：二者其实都是“寻找某个变换下的函数不动点”。也就是说，可以抽象出：

function fixed_point_of_transform(g, transform, guess) {
    return fixed_point(transform(g), guess);
}

这样，之前的平方根解法1（平均阻尼版）和解法2（牛顿法版）可以统一表示为：

function sqrt(x) {
    return fixed_point_of_transform(y => x / y, average_damp, 1);
}
function sqrt(x) {
    return fixed_point_of_transform(y => square(y) - x, newton_transform, 1);
}

二者本质上都是在求某个特定变换下的函数不动点，只是一个变换是平均阻尼套用原函数，另一个是Newton变换套用原函数。通过fixed_point_of_transform，我们进一步提升了抽象层次——不光强调过程，还抽象了对过程所做的变换。这样的抽象思路在第二章数据抽象中也会大量出现（如将不同数据表示通过变换归一）。

这一连串推演充分体现了SICP的编程观念：不断寻找程序中的抽象模式，加以命名封装，并尝试进一步泛化。在这个过程中，高阶函数是我们的利器，因为它使得过程也能像数据一样被传递、被操作，从而能够直接表达这些抽象概念。正如书中所总结的：“高阶函数的重要性就在于它使我们能够将这些抽象用程序设计语言的元素明确地描述出来，并使它们像其他计算元素一样可以作为操作的对象”。换句话说，JavaScript把函数提升为“一等公民”，赋予其与数字、字符串等平等的地位，我们才能如此自由地构造和组合函数抽象。

函数的第一等地位

在本章的结尾，作者讨论了“一等公民”（First-class）概念：在一门编程语言里，具有最少限制、享有完全使用权限的元素，被称为具有第一等地位。通常判断某类对象是否为一等公民，可以看它是否具备如下权利：

• 能够在程序中命名（赋值给变量或以常量出现）；
• 能作为参数传递给函数；
• 能作为返回值从函数返回；
• 能被包含在数据结构中。

在JavaScript等高级语言中，函数具备以上所有权利。我们可以把函数赋给变量（如 const f = x => x * x;），可以将函数传递给另一个函数（正如sum, fixed_point等所做的），可以从函数返回一个函数（如average_damp(f)返回一个新函数)，也可以将函数存储在数组、对象等数据结构里。函数的这种第一等地位极大增强了语言的表达力，也正是SICP选择Scheme（在JavaScript版中为JS）的原因之一。像C语言这种早期的过程式语言，函数并非一等公民，不能在运行时动态创建和操作函数；而在Lisp、Scheme以及现代JavaScript、Python等语言中，函数本质上是值，我们可以像操作整数一样操作函数。这开启了编程范式的新天地，使得“将函数作为抽象载体”成为可能。

反过来说，如果没有一等函数，高阶函数将难以实现，很多抽象也无法直观地表达。试想若JavaScript不允许函数作为参数，我们就不得不用宏展开或手动写出每一种求和，无法用sum这样的通用过程；没有匿名函数，我们封装抽象时要想办法避开命名问题，或者求助于面向对象的绕行（比如用对象封装行为）。因此，一等函数奠定了整本SICP很多思想的基石。

当然，实现一等函数对语言的底层而言是有挑战的，需要处理诸如闭包、垃圾回收、栈帧生命周期等问题。但这些由语言和编译器/解释器的设计者去解决，赋予了程序员极大的自由。而这份自由带来的抽象能力则是惊人的：我们可以写出函数产生函数、函数改造函数这样的代码，程序的结构不再局限于静态的层次，而可以动态地构建过程网络。正如Alan Perlis所戏言：“Lisp（函数式编程）程序员知道所有东西的价值，却不知道它们的代价”——因为可以随意创建嵌套的函数对象，初学者往往不关心性能负担（不过SICP通过分析增长阶，让我们也开始“知道代价”）。但从抽象角度看，这赋予了编程语言一种近乎元编程的能力。

综合以上讨论，我们可以理解**“函数即抽象的载体”**这一命题：函数不仅是执行计算的工具，更是封装思想和意图的容器。通过函数，我们把一段逻辑赋予一个名称或直接当作值传递，从而隔离了使用者与实现者之间的细节，实现抽象屏障。通过高阶函数，我们将通用的计算模式提升为可复用的模块，使程序的结构映射出问题的结构。当函数可以自由地传递和返回时，我们甚至可以在运行时动态生成所需的过程，这给予程序一种自描述和自构造的能力。这些特性结合起来，使得程序设计语言成为真正的“思维工具”——程序员能够用它直接表达抽象的解决方案，而非纠结在低层次的反复细节中。

余论：抽象之道

阅读《构造和解释计算机程序》第一章，我们完成了一次从具体到抽象的思维旅程。一开始，我们关注如何用基本元素编写正确的计算过程（如牛顿法求平方根）；随后，我们学习分析过程的行为和代价（递归vs迭代，算法的复杂度）；最后，我们探索将过程本身作为操作对象进行抽象，建立起更高层的过程组合（高阶函数应用于各种通用方法）。这不仅仅是几种编程技巧，而是一种思维方式的培养。

首先，抽象要求我们发现共性。当面对数个类似的问题或模式，我们应该敏锐地识别出它们的共同结构，并尝试将这些结构提炼出来。例如在求和、求积例子中，不同函数其实只有很小的差异，我们抓住这些可变之处，将其参数化，就得到了通用的sum、product高阶函数。又如在平方根和立方根问题中，Newton法和平均阻尼作为通用技巧被分离出来，一次实现，多处使用。通过抽象，我们消除了重复代码，使知识得以模块化重组。这不仅减少了编码量，更降低了出错概率并提高了程序可维护性——因为一个抽象方案解决了一类问题，当需求变化时我们只需调整抽象层而非众多具体实现。

其次，抽象要求我们忽略细节。这听起来与程序员追求精确的职责相悖，其实是就不同层次而言的：在高层我们刻意不去管底层的实现细枝末节，而只关注抽象接口和行为契约。在第一章中，多次强调“黑箱”概念：一旦我们确信某个函数正确工作，就可以将其视为黑箱使用，不必每次用到都展开其内部逻辑。例如，我们在实现is_good_enough时，把square当成黑箱调用；在实现fixed_point时，把传入的函数f看作黑箱迭代。只要接口契约（输入输出关系）满足，我们就可以高枕无忧地组合这些模块。这体现了一种工程哲学：屏蔽复杂性，分而治之。大型软件无不以分层抽象来管理复杂性，没有人能把所有细节同时装在脑中。通过抽象屏蔽，每层只需关注与自己相关的事物，大大减轻理解和推理负担。这和洛克所说第（3）点完全一致：“将关注的概念与其他无关概念隔离开”即是抽象的过程。

再次，抽象意味着通用化和可迁移。当我们把一种方法抽象出来后，它往往能运用到更多情境中。高阶函数让我们写出与具体业务无关的通用过程，如search用于任何连续函数求根，fixed_point用于任何不动点问题，accumulate用于各种聚合计算。写出这样的抽象需要一定的总结和概括能力，但一旦写出，其应用范围和重用价值极高。这有点类似数学上从具体定理总结出公理体系，可以衍生出无数定理结果。在编程中，这种通用化体现为库和框架的设计：抽象程度越高，库函数就越灵活，用户可以用更少的代码做更多的事。当然，要抽象得恰到好处并不容易。好的抽象应该不多不少：多了，会增加不必要的复杂性；少了，又无法覆盖足够的场景。SICP通过练习（如1.31-1.33）一步步引导读者去体验如何扩大抽象的泛用性，同时保持接口简洁。这种训练有助于培养良好的抽象能力，即抓住本质、滤除冗余的能力。

最后，抽象还需要合适的语言机制来支撑。没有语言层面的first-class函数和闭包，我们就很难写出高阶函数；没有词法作用域和块结构，我们难以管理复杂程序中的名字和状态。本章在介绍概念的同时，也凸显了JavaScript（及其源头Scheme）的语言特性：一等函数、动态类型、词法作用域、lambda表达式等等。这些特性并非为了炫技，而是服务于更高层次的程序设计思想。本章通过这些机制让我们初步领略了“程序即计算过程的抽象描述”这一观点。当函数可以指代一个过程并被命名或传递时，我们确实是在用符号操纵“过程”本身——仿佛这些过程是实实在在的对象。这种抽象能力正是计算机科学的魅力之一。

Alan J. Perlis在本书开篇寄语中说：“计算机程序设计思想的实质是改变了人们的思考方式”。通过第一章的学习，我们体会到了这一点：我们学会将重复的具体操作上升为一般性的过程，并用函数加以封装；学会站在更高维度看待程序，将函数视为可以操作的实体，从而在过程之上再抽象过程；学会用数学和逻辑的眼光审视程序的运行性能，以更理性地选择实现。可以说，我们不只是掌握了几段代码，而是领略了一种思维模式——抽象化思维。这种思维并非只适用于编程，在工程、科学乃至日常问题求解中都大有裨益：懂得抽象的人，往往更善于发现问题的模式、抓住关键，设计出简洁而优雅的解决方案。

当然，抽象并不是程序设计的终点。正如洛克所言，除了组合与抽象，人类心智还有“将两个概念并置以考察其关系”这一能力。在编程中，抽象模块之间的接口契约与关系，同样需要认真对待。随着系统规模增长，我们还会遇到状态变化、时间顺序、并发交互等复杂问题，那时单纯的函数抽象将不再够用。本书后续章节将逐步引入赋值、对象、流、非确定性等概念，讨论抽象在更广阔背景下的应用和演变。

但无论如何，第一章打下的基石——过程抽象的理念——将始终贯穿其中。当我们阅读后续内容或日后从事软件开发时，回想这一章的收获，就会明白为何计算机科学家如此强调抽象的重要性。正如本章结尾所倡导的：作为程序员，我们应当对程序中的基本抽象保持高度敏感，努力去构造它们、推广它们，以创建更强大优美的抽象。只有具备抽象思维，我们才能在复杂的问题领域中发现简洁的模型，在瞬息万变的技术浪潮中举重若轻地复用已有成果。归根结底，计算机程序=过程的抽象，学会构造抽象，就学会了以计算机科学的视角去看待和征服问题。第一章的学习只是一个开始，但已足以让我们感受到抽象之美，也为更深入的编程探究铺平了道路。

参考文献：

• Abelson, Sussman 等，《计算机程序的构造和解释：JavaScript版》，第1章，机械工业出版社，2023。