计算机程序的构造和解释

正如我们所看到的，序对提供了一种原始的"胶水"，我们可以用它来构造复合数据对象。图 2.2 展示了一种可视化序对的标准方式——这里展示的是由 (cons 1 2) 构成的序对。在这种称为盒指针表示法的表示中，每个对象显示为一个指向盒子的指针。基本对象的盒子中包含该对象的表示。例如，数字的盒子中包含一个数字。序对的盒子实际上是一个双格盒子，左半部分包含序对 car 的（指针），右半部分包含 cdr 的（指针）。

我们已经看到，cons 不仅可以用来组合数字，也可以用来组合序对。（在完成练习 2.2 和 2.3 时，你已经使用或应当使用过这一事实。）因此，序对提供了一种通用的构建块，我们可以用它来构造各种数据结构。图 2.3 展示了使用序对组合数字 1、2、3 和 4 的两种方式。

创建其元素本身也是序对的序对的能力，是表结构作为表示工具的重要性的本质所在。我们将这种能力称为 cons 的 闭包性质。一般而言，如果通过某个操作组合数据对象得到的结果本身也可以使用同一操作进行组合，那么这个组合数据对象的操作就满足闭包性质。⁶ 闭包是任何组合方式强大能力的关键，因为它允许我们创建 层次性结构——即由部分组成的结构，而这些部分本身又由更小的部分组成，以此类推。

从第 1 章开始，我们在处理过程时就已经大量使用了闭包，因为除了最简单的程序之外，所有程序都依赖于这样一个事实：组合的元素本身也可以是组合。在本节中，我们将讨论闭包对复合数据的影响。我们将描述一些使用序对表示序列和树的传统技术，并展示一种以生动方式体现闭包思想的图形语言。⁷

2.2.1 序列的表示

我们可以用序对构建的一种有用结构是序列——数据对象的有序集合。当然，用序对表示序列有很多种方法。一种特别直观的表示如图 2.4 所示，其中序列 1, 2, 3, 4 被表示为一个序对链。每个序对的 car 是链中对应的元素，序对的 cdr 是链中的下一个序对。最后一个序对的 cdr 通过指向一个不是序对的特殊值来标记序列的结束，在盒指针图中用对角线表示，在程序中用变量 nil 的值表示。整个序列通过嵌套的 cons 操作构造：

这种由嵌套的 cons 形成的序对序列称为表（list），Scheme 提供了一个名为 list 的基本过程来帮助构造表。⁸ 上述序列可以通过 (list 1 2 3 4) 产生。一般来说，

Lisp 系统通常用括号括起元素序列的方式来打印表。因此，图 2.4 中的数据对象被打印为 (1 2 3 4)：

请注意不要将表达式 (list 1 2 3 4) 与表 (1 2 3 4) 混淆，后者是表达式求值后得到的结果。试图对表达式 (1 2 3 4) 求值会导致错误，因为解释器会尝试将过程 1 应用于参数 2、3 和 4。

我们可以将 car 看作是选取表中的第一个元素，而 cdr 则是选取除去第一个元素后剩余元素组成的子表。car 和 cdr 的嵌套应用可以用来提取表中的第二个、第三个以及后续的元素。⁹ 构造函数 cons 可以构造一个与原始表相似的表，但在开头增加了一个额外的元素。

(car one-through-four) 1 (cdr one-through-four) (2 3 4) (car (cdr one-through-four)) 2 (cons 10 one-through-four) (10 1 2 3 4) (cons 5 one-through-four) (5 1 2 3 4)

The value of nil, used to terminate the chain of pairs, can be thought of as a sequence of no elements, the empty list. The word nil is a contraction of the Latin word nihil, which means ``nothing.''¹⁰

表操作

用序对将元素序列表示为表的做法，伴随着一套传统的编程技术，即通过依次 "cdr 向下遍历"表来操作表。例如，过程 list-ref 接受一个表和一个数字 n 作为参数，返回表的第 n 个元素。习惯上，表的元素从 0 开始编号。计算 list-ref 的方法如下：

(define (list-ref items n) (if (= n 0) (car items) (list-ref (cdr items) (- n 1)))) (define squares (list 1 4 9 16 25)) (list-ref squares 3) 16

通常我们会 cdr 向下遍历整个表。为了辅助这一操作，Scheme 提供了一个基本谓词 null?，它检查其参数是否为空表。过程 length 返回表中元素的个数，展示了这种典型的使用模式：

(define (length items) (if (null? items) 0 (+ 1 (length (cdr items))))) (define odds (list 1 3 5 7)) (length odds) 4

(define (length items) (define (length-iter a count) (if (null? a) count (length-iter (cdr a) (+ 1 count)))) (length-iter items 0))

另一种传统的编程技术是在 cdr 向下遍历一个表的同时 "cons 向上"构造一个结果表，过程 append 就是这样的例子，它接受两个表作为参数，将它们的元素组合成一个新表：

(append squares odds) (1 4 9 16 25 1 3 5 7) (append odds squares) (1 3 5 7 1 4 9 16 25)

Append 也是用递归规划实现的。要将表 list1 和 list2 进行 append，执行以下步骤：

(define (append list1 list2) (if (null? list1) list2 (cons (car list1) (append (cdr list1) list2))))

练习 2.17. 定义一个过程 last-pair，它返回只包含给定（非空）表的最后一个元素的表：

练习 2.18. 定义一个过程 reverse，它接受一个表作为参数，返回一个元素顺序相反的同样元素的表：

练习 2.19. 考虑第 1.2.2 节中的换零钱程序。如果能够方便地更改程序使用的货币种类，例如计算兑换一英镑的方法数，那就太好了。按照目前的写法，货币的知识一部分分布在了过程 first-denomination 中，另一部分分布在过程 count-change 中（它知道有五种美国硬币）。如果能提供一个用于换零钱的硬币列表，那就更好了。

我们希望重写过程 cc，使其第二个参数是一个待使用的硬币面值列表，而不是一个指定使用哪种硬币的整数。然后我们可以用表来定义每种货币：

(define us-coins (list 50 25 10 5 1)) (define uk-coins (list 100 50 20 10 5 2 1 0.5))

要做到这一点，需要稍微修改程序 cc。它仍然具有相同的形式，但将以不同的方式访问其第二个参数，如下所示：

(define (cc amount coin-values) (cond ((= amount 0) 1) ((or (< amount 0) (no-more? coin-values)) 0) (else (+ (cc amount (except-first-denomination coin-values)) (cc (- amount (first-denomination coin-values)) coin-values)))))

用表结构的基本操作定义过程 first-denomination、except-first-denomination 和 no-more?。表 coin-values 的顺序是否会影响 cc 产生的答案？为什么会影响或为什么不会影响？

练习 2.20. 过程 +、* 和 list 可以接受任意数量的参数。定义这类过程的一种方法是使用带有点尾记法的 define。在过程定义中，如果在最后一个参数名之前有一个点，则表示当过程被调用时，前面的参数（如果有的话）将像往常一样取前面实参的值，但最后一个参数的值将是所有剩余实参构成的表。例如，给定以下定义

那么在 f 的体中，x 为 1，y 为 2，z 为表 (3 4 5 6)。给定定义

使用这种记法来编写一个过程 same-parity，它接受一个或多个整数，并返回一个表，其中包含所有与第一个参数奇偶性相同的参数。例如，

表的映射

一种非常有用的操作是对表中的每个元素应用某种变换，并生成结果构成的表。例如，以下过程将表中的每个数按给定的因子进行缩放：

(define (scale-list items factor) (if (null? items) nil (cons (* (car items) factor) (scale-list (cdr items) factor)))) (scale-list (list 1 2 3 4 5) 10) (10 20 30 40 50)

我们可以抽象出这一通用思想，并将其捕获为一个以高阶过程表达的通用模式，就像第 1.3 节中那样。这里的高阶过程叫做 map。Map 接受一个单参数过程和一个表作为参数，返回将该过程应用于表中每个元素后产生的结果构成的表：¹²

(define (map proc items) (if (null? items) nil (cons (proc (car items)) (map proc (cdr items))))) (map abs (list -10 2.5 -11.6 17)) (10 2.5 11.6 17) (map (lambda (x) (* x x)) (list 1 2 3 4)) (1 4 9 16)

Map 是一个重要的构造，不仅因为它捕获了一种通用模式，而且因为它为处理表建立了更高层次的抽象。在 scale-list 的原始定义中，程序的递归结构将注意力引向了表的逐元素处理。而用 map 定义 scale-list 则抑制了这种细节层次，并强调了缩放是将元素列表转换为结果列表。两种定义之间的区别不在于计算机执行的过程不同（它并没有不同），而在于我们对过程的思考方式不同。实际上，map 帮助建立了一个抽象屏障，将转换表的过程的实现与表中元素如何被提取和组合的细节隔离开来。就像图 2.1 中展示的屏障一样，这种抽象使我们能够灵活地改变序列实现的底层细节，同时保持将序列转换为序列的操作的概念框架。第 2.2.3 节将进一步展开这种将序列作为组织程序的框架的用法。

练习 2.21. 过程 square-list 接受一个数字表作为参数，返回这些数的平方构成的表。

以下是 square-list 的两种不同定义。通过填入缺失的表达式来完成它们：

(define (square-list items) (if (null? items) nil (cons <??> <??>))) (define (square-list items) (map <??> <??>))

练习 2.22. Louis Reasoner 尝试重写练习 2.21 中第一个 square-list 过程，使其演化为一个迭代过程：

(define (square-list items) (define (iter things answer) (if (null? things) answer (iter (cdr things) (cons (square (car things)) answer)))) (iter items nil))

不幸的是，这样定义 square-list 产生的答案列表的顺序与期望的顺序相反。为什么？

(define (square-list items) (define (iter things answer) (if (null? things) answer (iter (cdr things) (cons answer (square (car things)))))) (iter items nil))

练习 2.23. 过程 for-each 与 map 类似。它接受一个过程和一个元素表作为参数。然而，与形成结果表不同的是，for-each 只是从左到右依次将过程应用于每个元素。将过程应用于元素后返回的值完全不被使用——for-each 用于执行动作的过程，例如打印。例如，

调用 for-each 返回的值（上面没有展示）可以是任意的，例如 true。请给出 for-each 的一个实现。

2.2.2 层次性结构

The representation of sequences in terms of lists generalizes naturally to represent sequences whose elements may themselves be sequences. For example, we can regard the object ((1 2) 3 4) constructed by

看作是一个包含三个元素的表，其中第一个元素本身也是一个表 (1 2)。事实上，解释器打印结果的形式也暗示了这一点。图 2.5 展示了用序对表示的这种结构。

另一种看待元素本身也是序列的序列的方式是将其视为树。序列的元素是树的分支，而本身也是序列的元素则是子树。图 2.6 将图 2.5 中的结构看作一棵树。

递归是处理树结构的自然工具，因为我们经常可以将对树的操作归约为对其分支的操作，而这些分支操作又归约为对分支的分支的操作，以此类推，直到到达树的叶子。作为例子，比较第 2.2.1 节中的 length 过程与 count-leaves 过程，后者返回一棵树的总叶子数：

(define x (cons (list 1 2) (list 3 4))) (length x) 3 (count-leaves x) 4 (list x x) (((1 2) 3 4) ((1 2) 3 4)) (length (list x x)) 2 (count-leaves (list x x)) 8

但在归约步骤中，当我们剥离表的 car 时，我们必须考虑到 car 本身可能是一棵需要计算叶子的树。因此，适当的归约步骤是

最后，通过取 car，我们会到达实际的叶子，因此我们需要另一个基例：

为了帮助编写关于树的递归过程，Scheme 提供了基本谓词 pair?，它测试其参数是否是一个序对。以下是完整的过程：¹³

(define (count-leaves x) (cond ((null? x) 0) ((not (pair? x)) 1) (else (+ (count-leaves (car x)) (count-leaves (cdr x))))))

练习 2.24. 假设我们求值表达式 (list 1 (list 2 (list 3 4)))。给出解释器打印的结果、相应的盒指针结构，以及将其解释为一棵树（如图 2.6 所示）。

练习 2.25. 给出能从以下每个表中取出 7 的 car 和 cdr 组合：

练习 2.27. 修改练习 2.18 中的 reverse 过程，生成一个 deep-reverse 过程，它接受一个表作为参数，返回其元素反转后的表，并且所有子表也都被深度反转。例如，

(define x (list (list 1 2) (list 3 4))) x ((1 2) (3 4)) (reverse x) ((3 4) (1 2)) (deep-reverse x) ((4 3) (2 1))

练习 2.28. 编写一个过程 fringe，它接受一棵树（用表表示）作为参数，返回一个表，其元素是树中所有按从左到右顺序排列的叶子。例如，

(define x (list (list 1 2) (list 3 4))) (fringe x) (1 2 3 4) (fringe (list x x)) (1 2 3 4 1 2 3 4)

练习 2.29. 一个二叉活动体由两个分支组成，即左分支和右分支。每个分支是一根特定长度的杆，上面悬挂着一个重物或另一个二叉活动体。我们可以用复合数据来表示二叉活动体，即用两个分支来构造它（例如，使用 list）：

一个分支由 length（必须是一个数）和 structure 构成，其中 structure 可以是一个数（表示简单重物）或另一个活动体：

a. 写出相应的选择函数 left-branch 和 right-branch，它们返回活动体的两个分支；以及 branch-length 和 branch-structure，它们返回分支的组成部分。

b. 使用你的选择函数，定义一个过程 total-weight，它返回一个活动体的总重量。

c. 如果一个活动体的左上分支施加的扭矩等于右上分支施加的扭矩（即左杆的长度乘以其悬挂重物的积等于右边相应的积），并且悬挂在其分支上的每个子活动体都是平衡的，则称该活动体是平衡的。设计一个谓词来测试一个二叉活动体是否平衡。

(define (make-mobile left right) (cons left right)) (define (make-branch length structure) (cons length structure))

树的映射

正如 map 是处理序列的强大抽象一样，map 与递归结合是处理树的强大抽象。例如，scale-tree 过程类似于第 2.2.1 节中的 scale-list，它接受一个数值因子和一棵叶子是数字的树作为参数。它返回一棵形状相同的树，其中每个数字都乘以该因子。scale-tree 的递归规划与 count-leaves 的类似：

(define (scale-tree tree factor) (cond ((null? tree) nil) ((not (pair? tree)) (* tree factor)) (else (cons (scale-tree (car tree) factor) (scale-tree (cdr tree) factor))))) (scale-tree (list 1 (list 2 (list 3 4) 5) (list 6 7)) 10) (10 (20 (30 40) 50) (60 70))

实现 scale-tree 的另一种方法是将树看作子树的序列并使用 map。我们映射整个序列，依次缩放每个子树，并返回结果的列表。在基例中，当树是叶子时，我们只需乘以因子：

(define (scale-tree tree factor) (map (lambda (sub-tree) (if (pair? sub-tree) (scale-tree sub-tree factor) (* sub-tree factor))) tree))

练习 2.30. 定义一个过程 square-tree，它类似于练习 2.21 中的 square-list 过程。也就是说，square-tree 的行为应如下所示：

(square-tree (list 1 (list 2 (list 3 4) 5) (list 6 7))) (1 (4 (9 16) 25) (36 49))

请用两种方式定义 square-tree：直接定义（即不使用任何高阶过程），以及使用 map 和递归定义。

练习 2.31. 将你对练习 2.30 的解答进行抽象，生成一个过程 tree-map，使得 square-tree 可以定义为

练习 2.32. 我们可以用一个由不同元素组成的表来表示一个集合，并可以用表的表来表示一个集合的所有子集的集合。例如，如果集合是 (1 2 3)，那么所有子集的集合是 (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))。完成下面生成集合的所有子集的过程定义，并清楚地解释它为什么能工作：

(define (subsets s) (if (null? s) (list nil) (let ((rest (subsets (cdr s)))) (append rest (map <??> rest)))))

2.2.3 序列作为一种约定的接口

在处理复合数据时，我们强调了数据抽象如何使我们能够设计程序而不陷入数据表示的细节之中，以及抽象如何为我们保留了尝试不同表示的灵活性。在本节中，我们介绍另一种处理数据结构的强大设计原则——使用约定的接口。

在第 1.3 节中，我们看到以高阶过程实现的程序抽象如何能够捕获处理数值数据的程序中的通用模式。我们能否为处理复合数据制定类似的操作，关键在于我们操作数据结构的方式。例如，考虑以下过程，它类似于第 2.2.2 节中的 count-leaves 过程，接受一棵树作为参数，计算其中奇数叶子的平方和：

(define (sum-odd-squares tree) (cond ((null? tree) 0) ((not (pair? tree)) (if (odd? tree) (square tree) 0)) (else (+ (sum-odd-squares (car tree)) (sum-odd-squares (cdr tree))))))

从表面上看，这个过程与下面这个构造所有偶数斐波那契数 Fib(k)（其中 k 小于或等于给定整数 n）的表的过程非常不同：

(define (even-fibs n) (define (next k) (if (> k n) nil (let ((f (fib k))) (if (even? f) (cons f (next (+ k 1))) (next (+ k 1)))))) (next 0))

尽管这两个过程在结构上非常不同，但对这两个计算更抽象的描述揭示了大量的相似之处。第一个程序

信号处理工程师会自然地用信号流经一系列阶段的方式来概念化这些过程，每个阶段实现程序计划的一部分，如图 2.7 所示。在 sum-odd-squares 中，我们从一个枚举器开始，它生成一个由给定树的叶子组成的"信号"。这个信号通过一个过滤器，它消除所有非奇数元素。得到的信号再通过一个映射，它是一个将 square 过程应用于每个元素的"转换器"。映射的输出随后送入一个累积器，它用 + 组合元素，从初始值 0 开始。even-fibs 的计划是类似的。

不幸的是，上面的两个过程定义未能展现出这种信号流结构。例如，如果我们检查 sum-odd-squares 过程，我们会发现枚举部分由 null? 和 pair? 测试实现，部分由过程的树递归结构实现。类似地，累积部分既体现在测试中，也体现在递归中使用的加法中。一般而言，这两个过程中没有对应于信号流描述中各个元素的独立部分。我们的两个过程以不同的方式分解了计算，将枚举分散在程序中，并将其与映射、过滤和累积混合在一起。如果我们能够组织程序，使信号流结构在编写的过程中显现出来，这将增加最终代码的概念清晰度。

序列操作

组织程序使其更清晰地反映信号流结构的关键在于，集中关注从一个处理阶段流向下一个阶段的"信号"。如果我们将这些信号表示为表，那么我们就可以使用表操作来实现每个阶段的处理。例如，我们可以使用第 2.2.1 节中的 map 过程来实现信号流图中的映射阶段：

过滤一个序列以选出满足给定谓词的元素可以通过以下过程完成：

(define (filter predicate sequence) (cond ((null? sequence) nil) ((predicate (car sequence)) (cons (car sequence) (filter predicate (cdr sequence)))) (else (filter predicate (cdr sequence)))))

(define (accumulate op initial sequence) (if (null? sequence) initial (op (car sequence) (accumulate op initial (cdr sequence))))) (accumulate + 0 (list 1 2 3 4 5)) 15 (accumulate * 1 (list 1 2 3 4 5)) 120 (accumulate cons nil (list 1 2 3 4 5)) (1 2 3 4 5)

要实现信号流图，剩下的工作就是枚举要处理的元素序列。对于 even-fibs，我们需要生成给定范围内的整数序列，这可以通过以下方式实现：

(define (enumerate-interval low high) (if (> low high) nil (cons low (enumerate-interval (+ low 1) high)))) (enumerate-interval 2 7) (2 3 4 5 6 7)

(define (enumerate-tree tree) (cond ((null? tree) nil) ((not (pair? tree)) (list tree)) (else (append (enumerate-tree (car tree)) (enumerate-tree (cdr tree)))))) (enumerate-tree (list 1 (list 2 (list 3 4)) 5)) (1 2 3 4 5)

现在我们可以按照信号流图重新表述 sum-odd-squares 和 even-fibs。对于 sum-odd-squares，我们枚举树的叶子序列，过滤此序列以只保留奇数，对每个元素求平方，然后求和结果：

(define (sum-odd-squares tree) (accumulate + 0 (map square (filter odd? (enumerate-tree tree)))))

对于 even-fibs，我们枚举从 0 到 n 的整数，为每个整数生成斐波那契数，过滤结果序列以只保留偶数元素，并将结果累积到一个表中：

(define (even-fibs n) (accumulate cons nil (filter even? (map fib (enumerate-interval 0 n)))))

将程序表示为序列操作的价值在于，这有助于我们设计出模块化的程序，即由相对独立的部分组合而成的设计。我们可以通过提供标准组件库以及用于灵活连接组件的约定接口来鼓励模块化设计。

模块化构造是控制工程设计复杂性的一种强大策略。例如，在实际的信号处理应用中，设计师通常通过级联从标准化的滤波器和转换器系列中选择的元件来构建系统。类似地，序列操作提供了一组标准程序元素的库，我们可以混合搭配使用。例如，我们可以在一个构造前 n + 1 个斐波那契数的平方表的程序中重用 sum-odd-squares 和 even-fibs 过程中的片段：

(define (list-fib-squares n) (accumulate cons nil (map square (map fib (enumerate-interval 0 n))))) (list-fib-squares 10) (0 1 1 4 9 25 64 169 441 1156 3025)

我们可以重新排列这些片段，并将它们用于计算序列中奇数整数的乘积：

(define (product-of-squares-of-odd-elements sequence) (accumulate * 1 (map square (filter odd? sequence)))) (product-of-squares-of-odd-elements (list 1 2 3 4 5)) 225

我们也可以用序列操作来表述常规的数据处理应用。假设我们有一个人事记录序列，我们想找出薪资最高的程序员的薪资。假设我们有一个选择函数 salary 返回一条记录的薪资，还有一个谓词 programmer? 测试一条记录是否属于程序员。那么我们可以这样写：

(define (salary-of-highest-paid-programmer records) (accumulate max 0 (map salary (filter programmer? records))))

这些例子只是能用序列操作表示的众多操作中的冰山一角。¹⁵

序列（在这里以表的形式实现）作为一种约定接口，使我们能够组合处理模块。此外，当我们统一地将结构表示为序列时，我们就把程序中的数据结构依赖性局部化到了少量的序列操作上。通过改变这些操作，我们可以在保持程序整体设计不变的情况下尝试不同的序列表示方式。我们将在第 3.5 节中利用这一能力，届时我们将推广序列处理范式以支持无穷序列。

练习 2.33. 填入缺失的表达式，完成以下将一些基本表操作定义为累积的定义：

(define (map p sequence) (accumulate (lambda (x y) <??>) nil sequence)) (define (append seq1 seq2) (accumulate cons <??> <??>)) (define (length sequence) (accumulate <??> 0 sequence))

练习 2.34. 在 x 的给定值处求多项式在 x 处的值可以表述为一种累积。我们求值多项式

换句话说，我们从 a_n 开始，乘以 x，加上 a_n-1，乘以 x，以此类推，直到到达 a₀。¹⁶ 填入下面的模板，生成一个使用霍纳规则求多项式值的过程。假设多项式的系数按从 a₀ 到 a_n 的顺序排列在一个序列中。

(define (horner-eval x coefficient-sequence) (accumulate (lambda (this-coeff higher-terms) <??>) 0 coefficient-sequence))

练习 2.35. 将第 2.2.2 节中的 count-leaves 重新定义为一个累积：

练习 2.36. 过程 accumulate-n 与 accumulate 类似，不同之处在于它的第三个参数是一个序列的序列，假定其中所有序列都有相同数量的元素。它将指定的累积过程应用于组合所有序列的第一个元素、所有序列的第二个元素，以此类推，并返回一个结果序列。例如，如果 s 是一个包含四个序列的序列 ((1 2 3) (4 5 6) (7 8 9) (10 11 12))，那么 (accumulate-n + 0 s) 的值应该是序列 (22 26 30)。填入下面 accumulate-n 定义中缺失的表达式：

(define (accumulate-n op init seqs) (if (null? (car seqs)) nil (cons (accumulate op init <??>) (accumulate-n op init <??>))))

练习 2.37. 假设我们将向量 v = (v_i) 表示为数的序列，将矩阵 m = (m_ij) 表示为向量（矩阵的行）的序列。例如，矩阵

表示为序列 ((1 2 3 4) (4 5 6 6) (6 7 8 9))。使用这种表示，我们可以用序列操作简洁地表达基本的矩阵和向量操作。这些操作（在任何矩阵代数教材中都有描述）如下：

填入以下计算其他矩阵操作的过程中缺失的表达式。（过程 accumulate-n 在练习 2.36 中定义。）

(define (matrix-*-vector m v) (map <??> m)) (define (transpose mat) (accumulate-n <??> <??> mat)) (define (matrix-*-matrix m n) (let ((cols (transpose n))) (map <??> m)))

练习 2.38. accumulate 过程也被称为 fold-right（右折叠），因为它将序列的第一个元素与右边所有元素组合的结果进行组合。还有一个 fold-left（左折叠），它与 fold-right 类似，不同之处在于它从相反方向组合元素：

(define (fold-left op initial sequence) (define (iter result rest) (if (null? rest) result (iter (op result (car rest)) (cdr rest)))) (iter initial sequence))

(fold-right / 1 (list 1 2 3)) (fold-left / 1 (list 1 2 3)) (fold-right list nil (list 1 2 3)) (fold-left list nil (list 1 2 3))

给出 op 应该满足的一个性质，以保证 fold-right 和 fold-left 对任何序列都会产生相同的值。

练习 2.39. 用练习 2.38 中的 fold-right 和 fold-left 完成下面（练习 2.18 中的）reverse 的定义：

(define (reverse sequence) (fold-right (lambda (x y) <??>) nil sequence)) (define (reverse sequence) (fold-left (lambda (x y) <??>) nil sequence))

嵌套映射

我们可以扩展序列范式，将许多通常用嵌套循环表示的计算包含进来。¹⁸ 考虑这个问题：给定一个正整数 n，找出所有满足 1< j< i< n 的不同正整数 i 和 j 的有序对，使得 i + j 是素数。例如，如果 n 为 6，那么这些对如下：

组织这个计算的一种自然方式是：生成所有小于或等于 n 的正整数有序对的序列，过滤选出那些和为素数的对，然后对每个通过过滤器的对 (i, j)，生成三元组 (i,j,i + j)。

以下是生成序对序列的一种方法：对于每个整数 i< n，枚举整数 j<i，并对每个这样的 i 和 j 生成序对 (i,j)。用序列操作的术语来说，我们沿序列 (enumerate-interval 1 n) 进行映射。对于该序列中的每个 i，我们沿序列 (enumerate-interval 1 (- i 1)) 进行映射。对于后一个序列中的每个 j，我们生成序对 (list i j)。这为每个 i 产生一个序对序列。将所有 i 的序列组合起来（通过用 append 累积）就产生了所需的序对序列：¹⁹

(accumulate append nil (map (lambda (i) (map (lambda (j) (list i j)) (enumerate-interval 1 (- i 1)))) (enumerate-interval 1 n)))

映射和用 append 累积的组合在这类程序中非常常见，我们将把它独立为一个单独的过程：

现在过滤这个序对序列，找出和为素数的那些。过滤谓词对序列的每个元素调用；它的参数是一个序对，它必须从序对中提取整数。因此，应用于序列中每个元素的谓词是

最后，通过使用以下过程映射过滤后的序对来生成结果序列，该过程构造一个由序对的两个元素及其和组成的三元组：

(define (make-pair-sum pair) (list (car pair) (cadr pair) (+ (car pair) (cadr pair))))

(define (prime-sum-pairs n) (map make-pair-sum (filter prime-sum? (flatmap (lambda (i) (map (lambda (j) (list i j)) (enumerate-interval 1 (- i 1)))) (enumerate-interval 1 n)))))

嵌套映射不仅对枚举区间的序列有用。假设我们想生成集合 S 的所有排列；即对集合中元素进行排序的所有方式。例如，{1,2,3} 的排列是 {1,2,3}、{1,3,2}、{2,1,3}、{2,3,1}、{3,1,2} 和 {3,2,1}。以下是生成 S 的排列的方案：对于 S 中的每个元素 x，递归地生成 S - x 的排列序列，²⁰ 并将 x 附加到每个排列的前面。这为 S 中的每个 x 产生了以 x 开头的 S 的排列序列。将所有 x 的这些序列组合起来就得到了 S 的所有排列：²¹

(define (permutations s) (if (null? s) ; empty set? (list nil) ; sequence containing empty set (flatmap (lambda (x) (map (lambda (p) (cons x p)) (permutations (remove x s)))) s)))

注意这个策略是如何将生成 S 的排列的问题归约为生成比 S 元素更少的集合的排列的问题。在终止情况下，我们一直向下到达空表，它表示没有元素的集合。对此，我们生成 (list nil)，它是一个包含一个元素的序列，即没有元素的集合。permutations 中使用的 remove 过程返回给定序列中除给定元素之外的所有元素。这可以表示为一个简单的过滤器：

(define (remove item sequence) (filter (lambda (x) (not (= x item))) sequence))

练习 2.40. 定义一个过程 unique-pairs，它接受一个整数 n，生成满足 1< j< i< n 的序对 (i,j) 的序列。使用 unique-pairs 来简化上面给出的 prime-sum-pairs 的定义。

练习 2.41. 编写一个过程，找出所有满足条件的不同正整数 i、j 和 k 的有序三元组，其中它们都小于或等于给定整数 n，且其和为给定整数 s。

"八皇后谜题"问的是如何在棋盘上放置八个皇后，使得没有任何一个皇后会受到其他皇后的攻击（即没有两个皇后在同一行、同一列或同一对角线上）。一个可能的解如图 2.8 所示。解决这个谜题的一种方法是在棋盘上逐列工作，在每一列放置一个皇后。一旦我们放置了 k - 1 个皇后，我们必须将第 k 个皇后放在一个不会攻击棋盘上已有任何皇后的位置。我们可以递归地表述这个方法：假设我们已经生成了在棋盘的前 k - 1 列放置 k - 1 个皇后的所有可能方式的序列。对于每种方式，通过在第 k 列的每一行放置一个皇后来生成一个扩展的位置集合。现在过滤这些位置，只保留第 k 列的皇后对其他皇后安全的位置。这就产生了在前 k 列放置 k 个皇后的所有方式的序列。通过继续这个过程，我们将不仅产生一个解，而是产生谜题的所有解。

我们将这个解实现为一个过程 queens，它返回在 n×n 棋盘上放置 n 个皇后问题的所有解的序列。Queens 有一个内部过程 queen-cols，它返回在棋盘的前 k 列放置皇后的所有方式的序列。

(define (queens board-size) (define (queen-cols k) (if (= k 0) (list empty-board) (filter (lambda (positions) (safe? k positions)) (flatmap (lambda (rest-of-queens) (map (lambda (new-row) (adjoin-position new-row k rest-of-queens)) (enumerate-interval 1 board-size))) (queen-cols (- k 1)))))) (queen-cols board-size))

在此过程中，rest-of-queens 是在前 k - 1 列放置 k - 1 个皇后的一种方式，new-row 是提议在第 k 列放置皇后的行。请通过实现棋盘位置集合的表示来完成该程序，包括过程 adjoin-position（它将一个新的行列位置添加到一个位置集合中）和 empty-board（它表示一个空的位置集合）。你还必须编写过程 safe?，它确定对于一个位置集合，第 k 列的皇后对其他皇后是否安全。（请注意，我们只需要检查新皇后是否安全——其他皇后之间已经保证是安全的。）

练习 2.43. Louis Reasoner 在做练习 2.42 时遇到了很大的麻烦。他的 queens 过程似乎能工作，但运行极慢。（Louis 甚至没能等到它解出 6×6 的情况。）当 Louis 向 Eva Lu Ator 求助时，她指出他在 flatmap 中交换了嵌套映射的顺序，写成了

(flatmap (lambda (new-row) (map (lambda (rest-of-queens) (adjoin-position new-row k rest-of-queens)) (queen-cols (- k 1)))) (enumerate-interval 1 board-size))

请解释为什么这个交换会使程序运行缓慢。假设练习 2.42 中的程序在时间 T 内解出八皇后谜题，请估计 Louis 的程序解出八皇后谜题需要多长时间。

2.2.4 实例：一个图形语言

本节介绍一种用于绘制图形的简单语言，它展示了数据抽象和闭包的威力，并且以本质性的方式利用了高阶过程。该语言的设计使我们可以方便地尝试如图 2.9 所示的模式，这些模式由重复的、经过平移和缩放的元素组成。²² 在这个语言中，被组合的数据对象被表示为过程，而不是表结构。正如满足闭包性质的 cons 使我们能够轻松构造任意复杂的表结构一样，该语言中也满足闭包性质的操作使我们能够轻松构造任意复杂的模式。

图形语言

当我们在第 1.1 节开始研究编程时，我们强调了通过关注语言的基元、组合方式和抽象手段来描述一个语言的重要性。我们将在这里沿用这个框架。

这个图形语言的优雅之处之一是它只有一种元素，称为画家。一个画家绘制一幅图像，该图像经过平移和缩放以适应一个指定的平行四边形框架。例如，有一个我们称之为 wave 的原始画家，它可以绘制一个粗略的线条画，如图 2.10 所示。绘图的实际形状取决于框架——图 2.10 中的所有四幅图像都是由同一个 wave 画家产生的，但针对四个不同的框架。画家可以比这更复杂：名为 rogers 的原始画家绘制的是 MIT 创始人 William Barton Rogers 的画像，如图 2.11 所示。²³ 图 2.11 中的四幅图像是相对于与图 2.10 中 wave 图像相同的四个框架绘制的。

为了组合图像，我们使用各种从给定画家构造新画家的操作。例如，beside 操作接受两个画家，生成一个新的复合画家，它在框架的左半部分绘制第一个画家的图像，在框架的右半部分绘制第二个画家的图像。类似地，below 接受两个画家，生成一个复合画家，它在第二个画家图像的下方绘制第一个画家的图像。有些操作通过变换单个画家来生成新的画家。例如，flip-vert 接受一个画家，生成一个上下颠倒绘制其图像的画家；flip-horiz 生成一个左右反转绘制原画家图像的画家。

图 2.12 展示了一个称为 wave4 的画家的绘制过程，它从 wave 开始分两个阶段构造：

(define wave2 (beside wave (flip-vert wave))) (define wave4 (below wave2 wave2))

**Figure 2.12:** Creating a complex figure, starting from the `wave` painter of figure 2.10.
`(define wave2 (define wave4 (beside wave (flip-vert wave))) (below wave2 wave2))`

通过这种方式构建复杂图像，我们利用了画家在该语言的组合方式下具有闭包性这一事实。两个画家的 beside 或 below 本身也是一个画家；因此，我们可以将它用作构造更复杂画家的元素。与使用 cons 构建表结构一样，数据在组合方式下的闭包性对于仅用少数操作就能创建复杂结构的能力至关重要。

一旦我们可以组合画家，我们就希望也能抽象出组合画家的典型模式。我们将把画家操作实现为 Scheme 过程。这意味着我们在图形语言中不需要特殊的抽象机制：由于组合方式就是普通的 Scheme 过程，我们自动具备了像处理过程一样处理画家操作的能力。例如，我们可以将 wave4 中的模式抽象为

(define (flipped-pairs painter) (let ((painter2 (beside painter (flip-vert painter)))) (below painter2 painter2)))

我们也可以定义递归操作。以下是一个使画家向右分裂和分支的操作，如图 2.13 和 2.14 所示：

(define (right-split painter n) (if (= n 0) painter (let ((smaller (right-split painter (- n 1)))) (beside painter (below smaller smaller)))))

**Figure 2.13:** Recursive plans for `right-split` and `corner-split`.
`right-split n corner-split n`

通过同时向上和向右分支，我们可以产生平衡的模式（见练习 2.44 以及图 2.13 和 2.14）：

(define (corner-split painter n) (if (= n 0) painter (let ((up (up-split painter (- n 1))) (right (right-split painter (- n 1)))) (let ((top-left (beside up up)) (bottom-right (below right right)) (corner (corner-split painter (- n 1)))) (beside (below painter top-left) (below bottom-right corner))))))

**Figure 2.14:** The recursive operations `right-split` and `corner-split` applied to the painters `wave` and `rogers`. Combining four `corner-split` figures produces symmetric `square-limit` designs as shown in figure 2.9.
`(right-split wave 4) (right-split rogers 4)` `(corner-split wave 4) (corner-split rogers 4)`

通过适当地放置四份 corner-split，我们得到一个称为 square-limit 的模式，它对 wave 和 rogers 的应用如图 2.9 所示：

(define (square-limit painter n) (let ((quarter (corner-split painter n))) (let ((half (beside (flip-horiz quarter) quarter))) (below (flip-vert half) half))))

练习 2.44. 定义 corner-split 使用的过程 up-split。它与 right-split 类似，只是交换了 below 和 beside 的角色。

高阶操作

除了抽象组合画家的模式之外，我们还可以在更高层次上工作，抽象组合画家操作的模式。也就是说，我们可以将画家操作视为可操作的元素，并可以为这些元素编写组合方式——即以画家操作为参数并创建新的画家操作的过程。

例如，flipped-pairs 和 square-limit 都将画家的四份副本排列成一个正方形模式；它们的不同之处仅在于如何定向这些副本。抽象这种画家组合模式的一种方式是使用以下过程，它接受四个单参数画家操作，并产生一个画家操作，该操作用这四个操作变换给定的画家，并将结果排列成一个正方形。Tl、tr、bl 和 br 分别是应用于左上副本、右上副本、左下副本和右下副本的变换。

(define (square-of-four tl tr bl br) (lambda (painter) (let ((top (beside (tl painter) (tr painter))) (bottom (beside (bl painter) (br painter)))) (below bottom top))))

(define (flipped-pairs painter) (let ((combine4 (square-of-four identity flip-vert identity flip-vert))) (combine4 painter)))

(define (square-limit painter n) (let ((combine4 (square-of-four flip-horiz identity rotate180 flip-vert))) (combine4 (corner-split painter n))))

练习 2.45. Right-split 和 up-split 可以表示为一个通用分裂操作的实例。定义一个过程 split，使得求值

(define right-split (split beside below)) (define up-split (split below beside))

产生与已定义的 right-split 和 up-split 具有相同行为的过程。

框架

在我们展示如何实现画家及其组合方式之前，我们必须首先考虑框架。一个框架可以用三个向量来描述——一个原点向量和两个边向量。原点向量指定了框架原点相对于平面上某个绝对原点的偏移，而边向量指定了框架角点相对于其原点的偏移。如果两条边垂直，则框架为矩形。否则框架将是一个更一般的平行四边形。

图 2.15 展示了一个框架及其关联的向量。根据数据抽象，我们暂时不需要具体说明框架如何表示，只需说明存在一个构造函数 make-frame，它接受三个向量并生成一个框架，以及三个相应的选择函数 origin-frame、edge1-frame 和 edge2-frame（见练习 2.47）。

我们将使用单位正方形 (0< x,y< 1) 中的坐标来指定图像。每个框架都关联一个框架坐标映射，它将用于平移和缩放图像以适应框架。该映射通过将向量 v = (x,y) 映射为向量和来将单位正方形变换为框架

例如，(0,0) 被映射到框架的原点，(1,1) 被映射到与原点对角相对的顶点，(0.5,0.5) 被映射到框架的中心。我们可以用以下过程创建框架的坐标映射：²⁶

(define (frame-coord-map frame) (lambda (v) (add-vect (origin-frame frame) (add-vect (scale-vect (xcor-vect v) (edge1-frame frame)) (scale-vect (ycor-vect v) (edge2-frame frame))))))

请注意，将 frame-coord-map 应用于一个框架返回一个过程，该过程给定一个向量，返回一个向量。如果参数向量在单位正方形内，则结果向量将在框架内。例如，

练习 2.46. 从原点到一个点的二维向量 v 可以表示为一个由 x-坐标和 y-坐标组成的序对。请通过给出构造函数 make-vect 和相应的选择函数 xcor-vect 和 ycor-vect 来实现向量的数据抽象。用你的选择函数和构造函数，实现执行向量加法、向量减法和向量标量乘法操作的过程 add-vect、sub-vect 和 scale-vect：

(define (make-frame origin edge1 edge2) (list origin edge1 edge2)) (define (make-frame origin edge1 edge2) (cons origin (cons edge1 edge2)))

画家

一个画家被表示为一个过程，该过程给定一个框架作为参数，绘制一幅经过平移和缩放以适应框架的特定图像。也就是说，如果 p 是一个画家，f 是一个框架，那么我们通过以 f 为参数调用 p 来在 f 中产生 p 的图像。

原始画家的实现细节取决于图形系统的具体特性和要绘制图像的类型。例如，假设我们有一个过程 draw-line，它在屏幕上两个指定点之间画一条线。那么我们可以从线段列表中创建线条画的画家，如图 2.10 中的 wave 画家，如下所示：²⁷

(define (segments->painter segment-list) (lambda (frame) (for-each (lambda (segment) (draw-line ((frame-coord-map frame) (start-segment segment)) ((frame-coord-map frame) (end-segment segment)))) segment-list)))

线段使用相对于单位正方形的坐标给出。对于表中的每个线段，画家用框架坐标映射变换线段的端点，并在变换后的点之间画一条线。

将画家表示为过程在图形语言中建立了一道强大的抽象屏障。我们可以基于各种图形能力创建和混合各种类型的原始画家。它们的实现细节并不重要。任何过程都可以作为画家使用，只要它接受一个框架作为参数，并绘制出经过缩放以适应框架的内容。²⁸

练习 2.48. 平面上的有向线段可以表示为一对向量——从原点到线段起点的向量，以及从原点到线段终点的向量。使用练习 2.46 中的向量表示来定义线段的表示，包括构造函数 make-segment 和选择函数 start-segment 和 end-segment。

变换和组合画家

对画家的操作（如 flip-vert 或 beside）通过创建一个画家来工作，该画家在从参数框架派生出的框架上调用原始画家。因此，例如，flip-vert 不需要知道画家是如何工作的就能翻转它——它只需要知道如何将框架上下颠倒：翻转后的画家只是使用原始画家，但在反转的框架中。

画家操作基于过程 transform-painter，它接受一个画家和关于如何变换框架的信息作为参数，并产生一个新的画家。变换后的画家在被框架调用时，会变换该框架，并在变换后的框架上调用原始画家。transform-painter 的参数是指定新框架角点的点（用向量表示）：当映射到框架中时，第一个点指定新框架的原点，另外两个点指定其边向量的终点。因此，单位正方形内的参数指定了包含在原始框架内的一个框架。

(define (transform-painter painter origin corner1 corner2) (lambda (frame) (let ((m (frame-coord-map frame))) (let ((new-origin (m origin))) (painter (make-frame new-origin (sub-vect (m corner1) new-origin) (sub-vect (m corner2) new-origin)))))))

(define (flip-vert painter) (transform-painter painter (make-vect 0.0 1.0) ; new origin (make-vect 1.0 1.0) ; new end of edge1 (make-vect 0.0 0.0))) ; new end of edge2

使用 transform-painter，我们可以轻松定义新的变换。例如，我们可以定义一个将其图像缩小到给定框架右上四分之一区域的画家：

(define (shrink-to-upper-right painter) (transform-painter painter (make-vect 0.5 0.5) (make-vect 1.0 0.5) (make-vect 0.5 1.0)))

(define (rotate90 painter) (transform-painter painter (make-vect 1.0 0.0) (make-vect 1.0 1.0) (make-vect 0.0 0.0)))

(define (squash-inwards painter) (transform-painter painter (make-vect 0.0 0.0) (make-vect 0.65 0.35) (make-vect 0.35 0.65)))

框架变换也是定义组合两个或更多画家的方式的关键。例如，beside 过程接受两个画家，将它们分别变换为在参数框架的左半部分和右半部分作画，并产生一个新的复合画家。当复合画家被给定一个框架时，它调用第一个变换后的画家在框架的左半部分作画，调用第二个变换后的画家在框架的右半部分作画：

(define (beside painter1 painter2) (let ((split-point (make-vect 0.5 0.0))) (let ((paint-left (transform-painter painter1 (make-vect 0.0 0.0) split-point (make-vect 0.0 1.0))) (paint-right (transform-painter painter2 split-point (make-vect 1.0 0.0) (make-vect 0.5 1.0)))) (lambda (frame) (paint-left frame) (paint-right frame)))))

请注意，画家的数据抽象，特别是将画家表示为过程的方式，使得 beside 的实现变得简单。beside 过程不需要知道组件画家的任何细节，只需要知道每个画家会在其指定的框架中绘制某些内容。

练习 2.50. 定义水平翻转画家的变换 flip-horiz，以及将画家逆时针旋转 180 度和 270 度的变换。

练习 2.51. 定义画家的 below 操作。Below 接受两个画家作为参数。生成的画家在给定框架时，用第一个画家在框架底部作画，用第二个画家在框架顶部作画。用两种不同的方式定义 below——首先编写一个类似于上面给出的 beside 过程的过程，然后再用 beside 和适当的旋转操作（来自练习 2.50）来定义。

为健壮设计而设置的语言层次

这个图形语言运用了我们所介绍的一些关于过程和数据的抽象的关键思想。基本的数据抽象——画家——是用过程表示来实现的，这使得该语言能够以统一的方式处理不同的基本绘图能力。组合方式满足闭包性质，使我们能够轻松构建复杂的设计。最后，所有抽象过程的工具都可以用来抽象画家的组合方式。

我们也瞥见了关于语言和程序设计的另一个关键思想。这就是 分层设计的方法，即一个复杂系统应该被构造为一系列层次的序列，每个层次用一系列语言来描述。每个层次通过组合在该层次被视为基元的部分来构造，而每个层次构造出的部分又被用作下一层次的基元。分层设计中每个层次使用的语言都有适应该细节层次的基元、组合方式和抽象手段。

分层设计遍布于复杂系统的工程设计中。例如，在计算机工程中，电阻和晶体管被组合（并用模拟电路语言描述）以产生与门和或门等部件，这些部件构成了数字电路设计语言的基元。³¹ 这些部件被组合以构建处理器、总线结构和存储系统，它们又用适合计算机体系结构的语言组合成计算机。计算机用适合描述网络互连的语言组合成分布式系统，以此类推。

作为分层设计的一个小小例子，我们的图形语言使用了通过一种指定点和线的语言创建的原始元素（原始画家），为 segments->painter 提供线段列表，或为像 rogers 这样的画家提供着色细节。我们对图形语言的大部分描述集中在使用几何组合子（如 beside 和 below）来组合这些基元。我们还在更高层次上工作，将 beside 和 below 视为基元，在一种语言中对其进行操作，该语言的操作（如 square-of-four）捕获了组合几何组合子的通用模式。

分层设计有助于使程序变得健壮，也就是说，它使得规范中的小改变很可能只要求程序中相应的小改变。例如，假设我们想要修改图 2.9 中基于 wave 的图像。我们可以在最底层改变 wave 元素的细节外观；可以在中间层改变 corner-split 复制 wave 的方式；也可以在最高层改变 square-limit 排列四份角块副本的方式。一般来说，分层设计的每一个层次都提供了不同的词汇来表达系统的特性，以及不同种类的改变系统的能力。

练习 2.52. 通过在上述描述的每个层次上进行修改，对图 2.9 中 wave 的方形极限进行改动。具体来说：

a. 为练习 2.49 中的原始 wave 画家添加一些线段（例如，添加一个微笑）。

b. 改变 corner-split 构造的模式（例如，只使用一份 up-split 和 right-split 图像，而不是两份）。

c. 修改使用 square-of-four 的 square-limit 版本，以不同的模式组合角块。（例如，你可以让大 Mr. Rogers 从方形的每个角向外看。）

⁶ 这里使用"闭包"（closure）一词来源于抽象代数，其中如果对集合中元素应用某个操作产生的结果仍然是该集合的元素，则称该集合在该操作下是封闭的。Lisp 社区也（不幸地）用"闭包"一词来描述一个完全不相关的概念：闭包是一种表示带有自由变量的过程的实现技术。我们在本书中不使用"闭包"的第二种含义。

⁷ 组合方式应该满足闭包性质这一概念是一个很直接的想法。不幸的是，许多流行编程语言中提供的数据组合子不满足闭包性质，或者使闭包的使用变得繁琐。在 Fortran 或 Basic 中，人们通常通过将数据元素装配到数组中来组合它们——但不能构造其元素本身也是数组的数组。Pascal 和 C 允许其元素是结构的结构。然而，这要求程序员显式地操作指针，并遵守结构每个字段只能包含预定义形式的元素的限制。与 Lisp 的序对不同，这些语言没有内建的通用粘合剂，使得以统一方式操作复合数据变得容易。这一局限性正是 Alan Perlis 在本书序言中评论的原因："在 Pascal 中，过多可声明的数据结构导致函数内部的专门化，这抑制和妨碍了随意的协作。让 100 个函数操作一个数据结构，比让 10 个函数操作 10 个数据结构要好。"

⁸ 在本书中，我们用表（list）表示以表尾标记结尾的序对链。与此相对，术语 表结构（list structure）指的是任何由序对构成的数据结构，而不仅仅是表。

⁹ 由于 car 和 cdr 的嵌套应用写起来很繁琐，Lisp 方言提供了它们的缩写——例如，

所有这些过程的名字都以 c 开头，以 r 结尾。它们之间的每个 a 代表一个 car 操作，每个 d 代表一个 cdr 操作，按它们在名字中出现的顺序应用。car 和 cdr 这些名字之所以保留下来，是因为像 cadr 这样的简单组合是可发音的。

¹⁰ 值得注意的是，Lisp 方言标准化过程中有多少精力浪费在了字面上关于"无"的争论上：nil 应该是一个普通名字吗？nil 的值应该是一个符号吗？它应该是一个表吗？它应该是一个序对吗？在 Scheme 中，nil 是一个普通名字，我们在本节中将其用作一个变量，其值是表尾标记（就像 true 是一个具有真值的普通变量一样）。Lisp 的其他方言，包括 Common Lisp，将 nil 视为一个特殊符号。本书的作者经历了太多的语言标准化争吵，因此希望完全避开这个问题。一旦我们在第 2.3 节中引入了引号，我们将用 '() 表示空表，并完全不再使用变量 nil。

¹¹ 要使用 lambda 定义 f 和 g，我们可以这样写

(define f (lambda (x y . z) <body>)) (define g (lambda w <body>))

¹² Scheme 标准提供了一个比这里描述的更通用的 map 过程。这个更通用的 map 接受一个 n 参数的过程以及 n 个表，并将该过程应用于所有表的第一个元素、所有表的第二个元素，以此类推，返回结果构成的表。例如：

(map + (list 1 2 3) (list 40 50 60) (list 700 800 900)) (741 852 963) (map (lambda (x y) (+ x (* 2 y))) (list 1 2 3) (list 4 5 6)) (9 12 15)

¹³ cond 中前两个子句的顺序很重要，因为空表满足 null? 且也不是序对。

¹⁴ 实际上，这正好是练习 2.28 中的 fringe 过程。这里我们重命名了它，以强调它是一系列通用序列操作过程中的一部分。

¹⁵ Richard Waters（1979）开发了一个程序，能够自动分析传统的 Fortran 程序，用映射、过滤和累积的视角来看待它们。他发现 Fortran 科学子程序包中整整 90% 的代码恰好符合这种范式。Lisp 作为编程语言成功的原因之一在于，表提供了一种标准的媒介来表达有序集合，从而可以用高阶操作来操作它们。编程语言 APL 的强大能力和吸引力很大程度上也归功于类似的选择。在 APL 中，所有数据都表示为数组，并且有一套通用且方便的通用操作符用于各种数组操作。

¹⁶ 根据 Knuth（1981），这个规则由 W. G. Horner 在十九世纪初提出，但这种方法实际上在更早一百多年前就被牛顿使用过。霍纳规则使用比先计算 a_n xⁿ，然后加上 a_n-1x^n-1 等等的直接方法更少的加法和乘法来求多项式的值。事实上，可以证明任何求任意多项式值的算法都必须至少使用与霍纳规则一样多的加法和乘法，因此霍纳规则是多项式求值的最优算法。这（对于加法次数）由 A. M. Ostrowski 在 1954 年的一篇论文中证明，该论文基本上开创了最优算法的现代研究。关于乘法的类似陈述由 V. Y. Pan 于 1966 年证明。Borodin 和 Munro（1975）的著作概述了这些及其他关于最优算法的结果。

¹⁷ 这个定义使用了脚注 12 中描述的扩展版 map。

¹⁸ 这种嵌套映射的方法由 David Turner 向我们展示，他的语言 KRC 和 Miranda 提供了处理这些构造的优雅形式化。本节中的例子（另见练习 2.42）改编自 Turner 1981。在第 3.5.3 节中，我们将看到这种方法如何推广到无穷序列。

¹⁹ 我们在这里将序对表示为两个元素的表，而不是 Lisp 序对。因此，"序对"(i,j) 被表示为 (list i j)，而不是 (cons i j)。

²⁰ 集合 S - x 是 S 中所有元素除去 x 后的集合。

²¹ Scheme 代码中的分号用于引入注释。从分号到行尾的所有内容都会被解释器忽略。在本书中，我们不使用太多注释；我们试图通过使用描述性的名字使程序自文档化。

²² 这个图形语言基于 Peter Henderson 为构造像 M.C. Escher 的"方形极限"木刻（见 Henderson 1982）这样的图像而创建的语言。该木刻包含重复的缩放模式，类似于本节中使用 square-limit 过程绘制的排列。

²³ William Barton Rogers（1804-1882）是 MIT 的创始人和第一任校长。他是一位地质学家和天才教师，曾在威廉玛丽学院和弗吉尼亚大学任教。1859 年，他搬到波士顿，在那里他有更多时间进行研究，制定建立"理工学院"的计划，并担任马萨诸塞州第一任煤气表州检查员。

当 MIT 于 1861 年成立时，Rogers 被选为第一任校长。Rogers 倡导一种"有用之学"的理想，这与当时过分强调古典学的大学教育不同，正如他所写的，古典学"阻碍了自然科学和社会科学更广泛、更高和更实用的教育和训练"。这种教育同样应与狭隘的技工学校教育不同。用 Rogers 的话说：

这个世界强加于实践工作者和科学工作者之间的区分是完全无益的，现代的全部经验已经证明了它的彻底无价值。

Rogers 担任 MIT 校长直到 1870 年，因健康原因辞职。1878 年，MIT 的第二任校长 John Runkle 在 1873 年恐慌带来的金融危机和抵御哈佛吞并 MIT 企图的压力下辞职。Rogers 重新出任校长直至 1881 年。

Rogers 在 1882 年毕业典礼上对 MIT 毕业班发表演讲时倒下并去世。Runkle 在同年的纪念演讲中引用了 Rogers 的临终遗言：

"当我今天站在这里，看到学院今天的样子，... 我想起了科学的开端。我记得一百五十年前 Stephen Hales 发表了一本关于照明气体的小册子，其中他说他的研究证明了 128 格令的烟煤——"
"烟煤，"这是他在世上的最后话语。说到这里他向前弯腰，好像在查看面前桌上的笔记，然后慢慢恢复直立的姿势，举起双手，从他在世间的劳作和成就的场景转移到了"死亡的明天"，在那里生命的奥秘得以解开，脱离了肉体的灵魂在思考无限的未来那崭新且仍然深不可测的奥秘中找到了无尽的满足。

用 Francis A. Walker（MIT 的第三任校长）的话说：

他一生都表现得最忠诚和最英勇，他正如一位好骑士所必定希望的，全副武装、坚守岗位、在履行公共职责的过程中去世。

²⁴ 等价地，我们可以这样写

(define flipped-pairs (square-of-four identity flip-vert identity flip-vert))

²⁵ Rotate180 将画家旋转 180 度（见练习 2.50）。我们可以用 (compose flip-vert flip-horiz) 代替 rotate180，其中使用了练习 1.42 中的 compose 过程。

²⁶ Frame-coord-map 使用了下面练习 2.46 中描述的向量操作，我们假设这些操作已经用某种向量表示实现了。由于数据抽象，向量表示是什么并不重要，只要向量操作行为正确即可。

²⁷ Segments->painter 使用了下面练习 2.48 中描述的线段表示。它还使用了练习 2.23 中描述的 for-each 过程。

²⁸ 例如，图 2.11 中的 rogers 画家是从灰度图像构造的。对于给定框架中的每个点，rogers 画家确定在框架坐标映射下映射到该点的图像中的点，并相应地着色。通过允许不同类型的画家，我们利用了第 2.1.3 节中讨论的抽象数据思想，我们在那里论证了有理数表示可以是任何满足适当条件的东西。这里我们利用了这样一个事实：画家可以以任何方式实现，只要它在指定的框架中绘制某些内容即可。第 2.1.3 节还展示了序对如何可以作为过程来实现。画家是我们用过程表示数据的第二个例子。

²⁹ Rotate90 仅对正方形框架是纯旋转，因为它还会拉伸和收缩图像以适应旋转后的框架。

³⁰ 图 2.10 和 2.11 中的菱形图像是通过将 squash-inwards 应用于 wave 和 rogers 创建的。

³¹ 第 3.3.4 节描述了这样一种语言。