1 归纳式数据集
解释器与检查器一类的程序是编程语言处理器的核心，本章介绍写这些用到的基本编程工具。
因为编程语言的语法通常为嵌套或者树状结构，递归将是我们的主要技巧。 递推定义的数据和推导递归程序介绍归纳定义数据结构的方法，并展示如何用这类定义指导 递归程序的编写。辅助过程和上下文参数展示如何将这些技巧推广到更为复杂的程序。本章以大量 练习作结。这些练习是本章的核心。欲掌握本书余下部分依赖的递归编程技巧，得自它们的 经验不可或缺。
1.1 递推定义的数据
编写过程代码时，必须明确知道什么样的值能作为过程的参数，什么样的值是过程的合法返 回值。这些值的集合通常很复杂。本节介绍定义值集合的形式化技术。
1.1.1 归纳定义法
归纳定义法是定义值集合的有效方法。为解释这一方法，我们用它来描述自然数 N = {0,1,2,...} 的某一子集 S。
n = 0，或
n - 3 \in S
来看看如何用这一定义判断哪些自然数属于 S。已知 0 \in S，因此 3 \in S， 因为 (3 - 3) = 0，且 0 \in S。同样地，6 \in S，因为 (6 - 3) = 3， 且 3 \in S。依此类推，可得结论：所有 3 的整数倍都属于 S。
其他自然数呢？1 \in S 吗？已知 1 \ne 0，所以条件一不满足。此外，(1 - 3) = -2，不是自然数，故不是 S 的元素，因此条件二不满足。因为 1 不满足任 一条件，所以 1 \notin S。同样地，2 \notin S。4呢？仅当 1 \in S 时 4 \in S。但 1 \notin S，所以 4 \notin S。同理可得，如果 n 是 自然数且不是 3 的整数倍，则 n \notin S。
据此推论，可得 S 是 3 的整数倍自然数集合。
可以用该定义编写一个函数，判断一个自然数 n 是否属于 S。
in-S? : \mathit{N} \to \mathit{Bool} 用法 : (in-S? n) = #t 若 n 属于 S，否则 #f (define in-S? (lambda (n) (if (zero? n) #t (if (>= (- n 3) 0) (in-S? (- n 3)) #f))))
这里根据定义，我们用Scheme编写了一个递归过程。符号 in-S? : \mathit{N} \to \mathit{Bool} 是一条注释，称为该函数 的合约 (contract)。它表示 in-S? 应为一过程，取一自然数，产生一 布尔值。这样的注释对阅读和编写代码很有帮助。
要判断是否 n \in S，先判断是否 n = 0。如果是，那么答案为真。否则，判断是 否 n - 3 \in S。欲知此，首先判断是否 (n - 3) \geqslant 0。如果是，那么可 以用我们的过程判断它是否属于 S。如果不是，那么 n 不可能属于 S。
S 又能够定义为：
集合 S 为 N 所包含的集合中，满足如下两条性质的最小集合：
0 \in S，且
若 n \in S，则 n + 3 \in S。
“最小集合”是指该集合满足性质 1 和 2，并且是其他任何 满足性质 1 和 2 的集合的子集。易知只能有一个这样的集合：如果 S_1 和 S_2 都满足性质 1 和 2，并且都为最小，那么 S_1 \subseteq S_2（因为 S_1 最小） 且 S_2 \subseteq S_1（因为 S_2 最小），因此 S_1 = S_2。之所以需要这 一额外条件，是因为否则的话将有许多集合满足其他两个条件（见）。
该定义还能表示为：
\infer{0 \in S}{}
\infer{(n + 3) \in S}{n \in S}
这只是前一定义的简便表示。每个条目称为一条推理规则 (rule of inference)， 或称规则 (rule)；水平线读作“若-则”。线上部分 称作假设 (hypothesis)或者前件 (antecedent)； 线下部分称作结论 (conclusion) 或者后件 (consequent)。罗列两个或 更多假设时，它们以隐含的“与”连接（见）。 不含假设的规则称作公理 (axiom)。写公理时通常不加水平 线，如：
0 \in S
该规则意为，自然数 n 属于 S，当且仅当能用有限次推理规则，从公理推得陈述 “n \in S”。这一解释自然使 S 成为闭合于该规则 的最小集合。
这些定义意思相同。我们把版本一称作自顶向下 (top-down) 的定义，版本二 称作自底向上 (bottom-up) 的定义，版本三称作推理规则定义。
再来看几个运用这些的例子。
我们用 \mathit{Int} 表示所有整数的集合，用 \mathit{List\mbox{-}of\mbox{-}Int} 表示所有整数列表的集合。
整数列表，自底向上集合\mathit{List\mbox{-}of\mbox{-}Int}是满足如下两条性质的最小Scheme列表集合：
\textnormal{()} \in \mathit{List\mbox{-}of\mbox{-}Int}，或
若 n \in \mathit{Int} 且 l \in \mathit{List\mbox{-}of\mbox{-}Int}，则 \textnormal{\texttt{(}}n\phantom{x}.\phantom{x}l\textnormal{\texttt{)}} \in \mathit{List\mbox{-}of\mbox{-}Int}。
这里，我们用中缀“.”代表 Scheme 中 cons 操 作的结果。式子 (n . l) 代表 Scheme 序对的首项为 n，余项为 l。
这三个定义等价。来看看如何用它们生成一些 \mathit{List\mbox{-}of\mbox{-}Int} 的元素。
-
由 的性质 1 或 的规则 1， () 是整数列表。
-
由 的性质 2，(14 . ()) 是整数列表。因为 14 是整数，() 是整数列表。写成 \mathit{List\mbox{-}of\mbox{-}Int} 规则二的形式， 就是
\infer{(14 . ()) \in \mathit{List\mbox{-}of\mbox{-}Int}} {14 \in \mathit{Int} & () \in \mathit{List\mbox{-}of\mbox{-}Int}}
-
由 的性质 2，(3 . (14 . ())) 是整数列表。因为 3 是整数，(14 . ()) 是整数列表。仍写成\mathit{List\mbox{-}of\mbox{-}Int} 规则二的 形式，是
\infer{(3 . (14 . ())) \in \mathit{List\mbox{-}of\mbox{-}Int}} {3 \in \mathit{Int} & (14 . ()) \in \mathit{List\mbox{-}of\mbox{-}Int}}
-
由 的性质 2，(-7 . (3 . (14 . ()))) 是整数列 表。因为 -7 是整数，(3 . (14 . ())) 是整数列表。再次写成 \mathit{List\mbox{-}of\mbox{-}Int} 规则二的形式，是
\infer{\hphantom{\texttt{x}}(-7 . (3 . (14 . ()))) \in \mathit{List\mbox{-}of\mbox{-}Int}\hphantom{\texttt{x}}} {-7 \in \mathit{Int} & (3 . (14 . ()))\in \mathit{List\mbox{-}of\mbox{-}Int}}
-
不按照这种方式得到的都不是整数列表。
改句点表示法为列表表示法，可知 ()、 (14)、 (3 14) 以及 (-7 3 14) 都是 \mathit{List\mbox{-}of\mbox{-}Int} 的元素。
还可以结合各条规则来证明 (-7 . (3 . (14 . ()))) \in \mathit{List\mbox{-}of\mbox{-}Int}， 以见出整个推理过程。下面的树状图叫做推导 (derivation) 或推理树 (deduction tree)。
\infer{\hphantom{\texttt{xx}}(-7 . (3 . (14 . ()))) \in \mathit{List\mbox{-}of\mbox{-}Int}\hphantom{\texttt{xx}}} {-7 \in \mathit{Int} \hphantom{\texttt{x}} & \infer{\hphantom{\texttt{x}}(3 . (14 . ())) \in \mathit{List\mbox{-}of\mbox{-}Int}\hphantom{\texttt{x}}} {3 \in \mathit{Int} & \infer{(14 . ()) \in \mathit{List\mbox{-}of\mbox{-}Int}} {14 \in \mathit{Int} & () \in \mathit{List\mbox{-}of\mbox{-}Int}}} }
\textnormal{[}{\star}\textnormal{]} 写出下列集合的归纳定义。以三种方式（自顶向下，自底向上，推理规则）写出每个定 义，并用你的规则推导出各集合的一些元素。
$\{ 3n + 2 \mid n \in N \}$
$\{ 2n + 3m + 1 \mid n, m \in N \}$
$\{ (n, 2n + 1) \mid n \in N \}$
$\{ (n, n^2) \mid n \in N \}$。不要在你的规则中使用平方。提示：想一想 方程 $ (n + 1) ^ 2 = n ^ 2 + 2n + 1$。
\textnormal{[}{\star}{\star}\textnormal{]} 下面的几对规则分别定义了什么集合？给出解释。
$(0, 1) \in S \qquad \infer{(n + 1, k + 7) \in S}{(n, k) \in S}$
$(0, 1) \in S \qquad \infer{(n + 1, 2k) \in S}{(n, k) \in S}$
$(0, 0, 1) \in S \qquad \infer{(n + 1, j, i + j) \in S}{(n, i, j) \in S}$
$\text{[}\mathord{\star}\mathord{\star}\mathord{\star}\text{]}$ $\quad$ $(0, 1, 0) \in S \qquad \infer{(n + 1, i + 2, i + j) \in S}{(n, i, j) \in S}$
\textnormal{[}{\star}\textnormal{]} 找出自然数的子集 $T$，满足 $0 \in T$，且对任何 $n \in T$，都有 $n + 3 \in T$，但 $T \neq S$，$S$ 是由 给出的集合。
1.1.2 语法定义法
前述例子较为直观，但是不难想象，描述更复杂的数据类型会有多麻烦。为了方便，我们展 示如何用语法 (grammar) 定义集合。语法通常用来指定字符串的集合，但也能用 来定义值的集合。
例如，集合 \mathit{List\mbox{-}of\mbox{-}Int} 可用语法定义为：
\begin{align*}\mathit{List\mbox{-}of\mbox{-}Int} &::= () \\[-3pt] \mathit{List\mbox{-}of\mbox{-}Int} &::= (\mathit{Int} . \mathit{List\mbox{-}of\mbox{-}Int})\end{align*}
这两条规则对应上述 中的两条性质。规则一是说空表属于 \mathit{List\mbox{-}of\mbox{-}Int}；规则二是说，若 n 属于 \mathit{Int} 且 l 属于 \mathit{List\mbox{-}of\mbox{-}Int}，则 (n . l) 属于 \mathit{List\mbox{-}of\mbox{-}Int}。这些规则 叫做语法。
来看看该定义的各个部分，其中有：
-
非终结符。这些是所定义的集合名。本例中只定义了一个集合，但是通常， 可能会定义数个集合。这些集合有时称为句法类别 (syntactic category)。
依照惯例，我们将非终结符和集合名的首字母大写，在文中提及它们的元素时，则 用小写。这要比听起来容易。例如， \mathit{Expression} 是非终结符，但 我们写作 e \in \mathit{Expression} 或 “e 是一个 expression”。
另一常见写法，名叫巴科斯-诺尔范 式 (Backus-Naur Form) 或BNF，是在词周围加 尖括号，如\langleexpression\rangle。
-
终结符。这些是集合外在表示中的字符，在本例中，是 “.”、 “(”和 “)”。这些常用打字机字体写出，如 lambda。
-
生成式。规则叫做生成式 (production)。 每个生成式的左边是一个非终结符，右边 包含终结符和非终结符。左右两边通常用符号 ::=分隔，读作是 或可以是。式子右边用其他句法类别和终结符（如左括号、 右括号和句点）指定一种方法，用以构建当前句法类别的元素。
如果某些句法类别的含义在上下文中足够清晰，在生成式中提到它们时通常不作定义，如 \mathit{Int}。
语法常常简写。当一个生成式的左边与前一生成式相同时，一般会略去。根据这一惯例，我 们的语法可以写作
\begin{align*}\mathit{List\mbox{-}of\mbox{-}Int} &::= () \\[-3pt] &::= (\mathit{Int} . \mathit{List\mbox{-}of\mbox{-}Int})\end{align*}
给同一句法类别编写一组规则时，也可以只写一次 ::= 和左边内容，随后的各个右边 内容用特殊符号“\mid”（竖线，读作或） 分隔。用“\mid”，\mathit{List\mbox{-}of\mbox{-}Int} 的语法可写成：
\mathit{List\mbox{-}of\mbox{-}Int} ::= () \mid (\mathit{Int} . \mathit{List\mbox{-}of\mbox{-}Int})
另一种简写是克莱尼星号 (Kleene Star)，写作 \{...\}^*。当它出现在右边时，表示一个序列，由任意多个花括号之间的内容组成。 用克莱尼星号，\mathit{List\mbox{-}of\mbox{-}Int} 的定义可以简写为
\mathit{List\mbox{-}of\mbox{-}Int} ::= (\{\mathit{Int}\}^*)
这也包含没有任何内容的情况。如果内容出现 0 次，得到的是空字符串。
星号的变体是克莱尼加号 (Kleene Plus) \{...\}^+，表示一个或多个内容的 序列。把上例中的 ^* 换成 ^+，定义的句法类别是非空整数列表。
星号的另一变体是分隔表 (separated list) 表示法。例如， \mathit{Int}^{*(c)} 表示一个序列，包含任意数量的非终结符 \mathit{Int} 元素，以非 空字符序列 c 分隔。这也包含没有元素的情况。如果有 0 个元素，得到的是空字符串。 例如，\mathit{Int}^{*(,)} 包含字符串
8
14, 12
7, 3, 14, 16
\mathit{Int}^{*(;)} 包含字符串
8
14; 12
7; 3; 14; 16
这些简写不是必需的，总能够不用它们重写语法。
对由语法定义的集合，可以用句法推导 (syntactic derivation) 证明给定值是其 元素。这样的推导从集合对应的非终结符开始，在由箭头\Rightarrow 指示的每一步中， 如果非终结符对应的句法类别未做定义，则将其代换为该类别的已知元素，否则代换为对应 规则右边的内容。例如，前述证明“(14 . ()) 是整数列表 ”，可以用句法推导化为
\begin{align*}\mathit{List\mbox{-}of\mbox{-}Int} &\Rightarrow (\mathit{Int} . \mathit{List\mbox{-}of\mbox{-}Int}) \\[-3pt] &\Rightarrow (14 . \mathit{List\mbox{-}of\mbox{-}Int}) \\[-3pt] &\Rightarrow (14 . ())\end{align*}
非终结符的替换顺序无关紧要，所以 (14 . ()) 的推导也可以写成：
\begin{align*}\mathit{List\mbox{-}of\mbox{-}Int} &\Rightarrow (\mathit{Int} . \mathit{List\mbox{-}of\mbox{-}Int}) \\[-3pt] &\Rightarrow (\mathit{Int} . ()) \\[-3pt] &\Rightarrow (14 . ())\end{align*}
\textnormal{[}{\star}\textnormal{]} 写出从 $\mathit{List\mbox{-}of\mbox{-}Int}$ 到 (-7 . (3 . (14 ()))) 的推导。
再来看一些有用集合的定义。
-
许多符号操作过程用于处理只包含符号和具有类似限制的列表。我们把这些叫做 s-list，定义如下：
\begin{align*}\mathit{S\mbox{-}list} &::= (\{\mathit{S\mbox{-}exp}\}^*) \\[-3pt] \mathit{S\mbox{-}exp} &::= \mathit{Symbol} \mid \mathit{S\mbox{-}list}\end{align*}
s-list 是 s-exp 的列表，s-exp 或者是 s-list，或者是一个符号。 这里是一些 s-list。
(a b c)
(an (((s-list)) (with () lots) ((of) nesting)))
-
使用三元素列表表示内部节点，则以数值为叶子，以符号标示内部节点的二叉树可 用语法表示为：
\mathit{Bintree} ::= \mathit{Int} \mid (\mathit{Symbol} \mathit{Bintree} \mathit{Bintree})
这是此类树的几个例子：
1
2
(foo 1 2)
(bar 1 (foo 1 2))
(baz
(bar 1 (foo 1 2))
(biz 4 5))
-
lambda 演算 (lambda calculus) 是一种简单语言，常用于研究编程语言 理论。这一语言只包含变量引用，单参数过程，以及过程调用，可用语法定义为：
\begin{align*}\mathit{LcExp} &::= \mathit{Identifier} \\[-3pt] &::= (lambda (\mathit{Identifier}) \mathit{LcExp}) \\[-3pt] &::= (\mathit{LcExp} \mathit{LcExp})\end{align*}
其中，identifier 是除 lambda 之外的任何符号。
第二个生成式中的 identifier 是 lambda 表达式主体内的变量名。这一变量叫做表 达式的绑定变量 (bound variable)，因为它绑定（或称捕获）主体内出现的任何 同名变量。出现在主体内的同名变量都指代这一个。
要明白这怎么用，考虑用算术操作符扩展的 lambda 演算。在这种语言里，
(lambda (x) (+ x 5)) 是一表达式，x 是其绑定变量。这式子表示一个过程，把它的参数加5。因此，在
((lambda (x) (+ x 5)) (- x 7)) 中，最后一个出现的 x 不是指 lambda 表达式中绑定的 x。 occurs-free?中介绍了 occurs-free?，到时我们再讨论这个问题。
该语法定义 \mathit{LcExp} 的元素为 Scheme 值，因此很容易写出程序来处理它们。
这些语法叫做上下文无关 (context-free) 语法，因为一条规则定义的句法类别可 以在任何引用它的上下文中使用。有时这不够严格。考虑二叉搜索树。 其节点或者为空，或者包含一个整数和两棵子树 \mathit{Binary\mbox{-}search\mbox{-}tree} ::= () \mid (\mathit{Int} \mathit{Binary\mbox{-}search\mbox{-}tree} \mathit{Binary\mbox{-}search\mbox{-}tree})
这如实反映了每个节点的结构，但是忽略了二叉搜索树的一个要点：所有左子树的键值都小 于（或等于）当前节点，所有右子树的键值都大于当前节点。
因为这条额外限制，从 \mathit{Binary\mbox{-}search\mbox{-}tree} 得出的句法推 导并不都是正确的二叉搜索树。要判定某个生成式能否用于特定的句法推导，必须检查生成 式用在哪种上下文。这种限制叫做上下文敏感 限制 (context-sensitive constraints)，或称不变式 (invariants)。
定义编程语言的语法也会产生上下文敏感限制。例如，在许多编程语言中变量必须在使用之 前声明。对变量使用的这一限制就对其上下文敏感。虽然可以用形式化方法定义上下文敏感 限制，但这些方法远比本章考虑的复杂。实际中，常用的方法是先定义上下文无关语法，随 后再用其他方法添加上下文敏感限制。类型展示了这种技巧的一个例子。
1.1.3 归纳证明法
用归纳法描述的集合，其定义有两种用法：证明关于集合元素的定理，写出操作集合元素的 程序。这里给出一个此类证明的例子，写程序留作下节的主题。
用归纳法证明 t 的大小。令 t 的大小等于 t 中节点的个数。归纳假设为 \mathit{IH}(k)：树的大小\leq k时有奇数个节点。依照归纳法的惯例：先证明 \mathit{IH}(0)为真，然后证明若对任一整数 k，\mathit{IH} 为真，则对 k + 1，\mathit{IH} 也为真。
没有哪棵树只有 0 个节点，所以 \mathit{IH}(0) 显然成立。
设 k 为整数时，\mathit{IH}(k) 成立，即，任何树的节点数 \leq k 时，其实际数目为奇数。需证明 \mathit{IH}(k + 1) 也成立：任何树的节点数 \leq k + 1 时，节点数为奇数。若 t 有 \leq k + 1 个节点，根据二叉树 的定义，只有两种可能：
t 形如 n，n 为整数。此时 t 只有一个节点，1为奇数。
t 形如 (sym t_1 t_2)，其中，sym 是一符号， t_1 和 t_2 是树。此时 t_1 和 t_2 节点数少于 t。因为 t 有 \leq k + 1个节点，t_1 和 t_2 一定有 \leq k 个节点。因此它 们符合 \mathit{IH}(k)，一定各有奇数个节点，不妨分别设为2n_1 + 1 和 2n_2 + 1。则算上两棵子树和根，原树中的节点总数为
(2n_1 + 1) + (2n_2 + 1) + 1 = 2(n_1 + n_2 + 1) + 1
也是一个奇数。
证明的关键是树 t 的子结构总是比 t 自身小。这种证明模式 叫做结构化归纳法 (structural induction)。
结构化归纳证明
欲证明假设 \mathit{IH}(s) 对所有结构 s 为真， 需证明：
\textnormal{[}{\star}{\star}\textnormal{]} 证明：若 $e \in \mathit{LcExp}$，则 $e$ 中的左右括号数量相等。
1.2 推导递归程序
我们已经用归纳定义法描述了复杂集合。我们能够分析归纳式集合的元素，观察如何从较小 元素构建集合。我们用这一想法写出了过程 in-S?，用以判断自然数是否属于集合 S。现在，我们用同样的想法定义更通用的过程，以便对归纳式集合做运算。
较小子问题原则
若能化问题为较小子问题，则能调用解决原问题的过程解决 子问题。
已求得的子问题解随后可用来求解原问题。这可行，因为每次过程调用都是针对较小的子问 题，直至最终调用，针对一个可以直接求解的问题，不需再次调用自身。
我们用一些例子解释这一想法。
1.2.1 list-length
标准的 Scheme 程序 length 求出列表中的元素个数。
> (length '(a b c)) 3
> (length '((x) ())) 2
我们来写出自己的过程 list-length，做同样的事。
先来写出过程的合约。合约指定了过程可取参数和可能返回值的集合。合约也 可以包含过程的期望用法或行为。这有助于我们在编写时及以后追踪我们的意图。在代码中， 这是一条注释，我们用打字机字体示之，以便阅读。
list-length : \mathit{List} \to \mathit{Int} 用法 : (list-length l) = l的长度 (define list-length (lambda (lst) ...))
列表的集合定义为
\mathit{List} ::= () \mid (Scheme \; value . \mathit{List})
因此，考虑列表的每种情况。若列表为空，则长度为0。
list-length : \mathit{List} \to \mathit{Int} 用法 : (list-length l) = l 的长度 (define list-length (lambda (lst) \begin{mdframed}[style=codediff] (if (null? lst) 0 \end{mdframed} ...)))
若列表非空，则其长度比其余项长度多1。这就给出了完整定义。
list-length : \mathit{List} \to \mathit{Int} 用法 : (list-length l) = l 的长度 (define list-length (lambda (lst) (if (null? lst) 0 \begin{mdframed}[style=codediff] (+ 1 (list-length (cdr lst)))))) \end{mdframed}
通过 list-length 的定义，我们可以看到它的运算过程。
(list-length '(a (b c) d))
= (+ 1 (list-length '((b c) d)))
= (+ 1 (+ 1 (list-length '(d))))
= (+ 1 (+ 1 (+ 1 (list-length '()))))
= (+ 1 (+ 1 (+ 1 0)))
= 3
1.2.2 nth-element
标准的 Scheme 过程 list-ref 取一列表 lst 和从 0 开始计数的索引 n， 返回 lst 的第 n 个元素。
> (list-ref '(a b c) 1) 'b
我们来写出自己的过程 nth-element，做同样的事。
仍沿用上述 List 的定义。
当 lst 为空时，(nth-element lst n) 应当返回什么？这种情况下， (nth-element lst n) 想要取空列表的元素，所以报错。
当 lst 非空时，(nth-element lst n) 应当返回什么？答案取决于 n。若 n = 0，答案是 lst 的首项。
当 lst 非空，且 n \neq 0 时，(nth-element lst n) 应当返回什 么？这种情况下，答案是 lst 余项的第 (n - 1) 个元素。由 n \in N 且 n \neq 0，可知 n - 1 一定属于 N，因此可以递归调用 nth-element找 出第 (n - 1) 个元素。
这就得出定义
nth-element : \mathit{List} \times \mathit{Int} \to \mathit{SchemeVal} 用法 : (nth-element lst n) = lst 的第 n 个元素 (define nth-element (lambda (lst n) (if (null? lst) (report-list-too-short n) (if (zero? n) (car lst) (nth-element (cdr lst) (- n 1)))))) (define report-list-too-short (lambda (n) (eopl:error 'nth-element "List too short by ~s elements.~%" (+ n 1))))
这里的注释 nth-element : \mathit{List} \times \mathit{Int} \to \mathit{SchemeVal} 表示 nth-element 是一个过程，取两个参数，一 个为列表，一个为整数，返回一个Scheme 值。这与数学中的表示 f : A \times B \to C 相同。
过程 report-list-too-short 调用 eopl:error 来报告错误，后者会终止计算。 它的首个参数是一符号，用于在错误信息中指示调用 eopl:error 的过程。第二个参 数是一个字符串，会打印为错误信息。对应于字符串中的每个字符序列 ~s，都必须有 一个额外参数。打印字符串时，这些参数的值会替换对应的 ~s 。~%代表换行。 错误信息打印后，计算终结。过程 eopl:error 并非标准 Scheme 的一部分，但大多 数 Scheme 实现提供这样的组件。在本书中，我们以类似方式，用名字含 report- 的 过程报告错误。
来看看 nth-element 如何算出答案：
(nth-element '(a b c d e) 3)
= (nth-element '(b c d e) 2)
= (nth-element '(c d e) 1)
= (nth-element '(d e) 0)
= d
这里，nth-element 递归处理越来越短的列表和越来越小的数字。
如果排除错误检查，我们得靠 car 和 cdr 报错来获知传递了空列表，但它们的 错误信息无甚帮助。例如，当我们收到 car 的错误信息，可能得找遍整个程序中使用 car 的地方。
\textnormal{[}{\star}\textnormal{]} 如果调换 nth-element 中两个条件的顺序，会有什么问题？
\textnormal{[}{\star}{\star}\textnormal{]} nth-element 的错误信息不够详尽。重写 nth-element，给出更详细的错误信 息，像是 “(a b c) 不足 8 个元素”。
1.2.3 remove-first
过程 remove-first 取两个参数：符号 s 和符号列表 los。它返回一个列表， 除了不含第一个出现在 los 中的符号 s 外，所含元素及其排列顺序与 los 相同。如果 s 没有出现在 los 中，则返回 los。
> (remove-first 'a '(a b c)) '(b c)
> (remove-first 'b '(e f g)) '(e f g)
> (remove-first 'a4 '(c1 a4 c1 a4)) '(c1 c1 a4)
> (remove-first 'x '()) '()
写出此过程之前，我们先要定义符号列表集合 \mathit{List\mbox{-}of\mbox{-}Symbol} ，以便给出问题的完整描述。不像上一节介 绍的 s-lists，符号列表不包含子列表。
\mathit{List\mbox{-}of\mbox{-}Symbol} ::= () \mid (\mathit{Symbol} . \mathit{List\mbox{-}of\mbox{-}Symbol})
符号列表或者是空列表，或者是首项为符号，余项为符号列表。
如果列表为空，不需要移除 s，则答案为空列表。
写合约时，我们用 \mathit{Listof}(\mathit{Sym}) 而不是 \mathit{List\mbox{-}of\mbox{-}Symbol}。用这种写法可以免除许多上面那样的定义。
如果 los 非空，有没有哪种情况可以立刻得出答案？如果 los 的第一个元素是 s，比如 los = (s s_1 ... s_{n-1})，s 首次出现时 是 los 的第一个元素，那么把它删除之后的结果是 (s_1 ... s_{n-1})。
remove-first : \mathit{Sym} \times \mathit{Listof}(\mathit{Sym}) \to \mathit{Listof}(\mathit{Sym}) (define remove-first (lambda (s los) (if (null? los) '() \begin{mdframed}[style=codediff] (if (eqv? (car los) s) (cdr los) ...)))) \end{mdframed}
如果 los 的第一个元素不是 s，比如 los = (s_0 s_1 ... s_{n-1})，可知 s_0 不是第一个出现的 s，因此答案中的第一个元素一定 是s_0，即表达式 (car los) 的值。而且，los 中的首个 s 一定在 (s_1 ... s_{n-1}) 中。所以答案的余下部分一定是移除 los 余项 中首个 s 的结果。因为 los 的余项比 los 短，我们可以递归调用 remove-first，从 los 的余项中移除 s，即答案的余项可用 (remove-first s (cdr los)) 求得。已知如何找出答案的首项和余项，可以用 cons 结合二者，通过表达式 (cons (car los) (remove-first s (cdr los))) 求得整个答案。由此，remove-first 的完整定义为
remove-first : \mathit{Sym} \times \mathit{Listof}(\mathit{Sym}) \to \mathit{Listof}(\mathit{Sym}) (define remove-first (lambda (s los) (if (null? los) '() (if (eqv? (car los) s) (cdr los) \begin{mdframed}[style=codediff] (cons (car los) (remove-first s (cdr los))))))) \end{mdframed}
\textnormal{[}{\star}\textnormal{]} 如果把 remove-first 定义中的最后一行改为 (remove-first s (cdr los))， 得到的过程做什么运算？对修改后的版本，给出合约，包括用法。
\textnormal{[}{\star}{\star}\textnormal{]} 定义 remove。它类似于 remove-first，但会从符号列表中移除所有给定符号， 而不只是第一个。
1.2.4 occurs-free?
过程 occurs-free? 取一个变量 var，由 Scheme 符号表示；一个 lambda 演算 表达式 exp，形如；判断 var 是否自由出现于 exp。 如果一个变量出现于表达式 exp 中，但不在某一 lambda 绑定之内，我们说该变 量自由出现 (occur free) 于表达式 exp 中。例如，
> (occurs-free? 'x 'x) #t
> (occurs-free? 'x 'y) #f
> (occurs-free? 'x '(lambda (x) (x y))) #f
> (occurs-free? 'x '(lambda (y) (x y))) #t
> (occurs-free? 'x '((lambda (x) x) (x y))) #t
> (occurs-free? 'x '(lambda (y) (lambda (z) (x (y z))))) #t
我们可以遵照 lambda 演算表达式的语法解决此问题：
\begin{align*}\mathit{LcExp} &::= \mathit{Identifier} \\ &::= (lambda (\mathit{Identifier}) \mathit{LcExp}) \\ &::= (\mathit{LcExp} \mathit{LcExp})\end{align*}
我们可以总结出规则的各种情况：
-
若表达式 e 是一变量，则当且仅当 x 与 e 相同时，变量 x 自 由出现于 e。
-
若表达式 e 形如 (lambda (y) e{}’)，则当且仅当 y 不 同于 x 且 x 自由出现于 e{}’ 时，变量 x 自由出现于 e。
-
若表达式 e 形如 (e_1 e_2)，则当且仅当 x 自由出现于 e_1 或 e_2 时，x 自由出现于 e。这里的“或 ”表示涵盖或 (inclusive or)，意为它包含 x 同时自由出现 于 e_1 和 e_2 的情况。我们通常用“或”表示这 种意思。
你可以说服自己，这些规则涵盖了“x 不在某一 lambda 绑定之中 ”表示的所有意思。
\textnormal{[}{\star}\textnormal{]} 我们常用“或”表示“涵盖或 ”。“或”还有什么含义？
然后，定义 occurs-free? 就很容易了。因为有三种情况要检查，我们不用 Scheme 的 if，而是用 cond。在 Scheme 中，若 exp_1 或 exp_2 返回真值， 则 (or exp_1 exp_2) 返回真值。
这一过程略显晦涩。比如，很难弄明白 (car (cadr exp)) 指代 lambda 表达式 中的变量声明，或者 (caddr exp) 指代 lambda 表达式的主体。在 抽象语法及其表示，我们展示如何显著改善这种情况。
1.2.5 subst
过程 subst 取三个参数：两个符号 new 和 old，一个 s-list， slist。它检查 slist 的所有元素，返回类似 slist 的新列表，但把其中 所有的 old 替换为 new。
> (subst 'a 'b '((b c) (b () d))) '((a c) (a () d))
因为 subst 定义于 s-list 上，它的结构应当反映 s-list 的定义（）：
\begin{align*}\mathit{S\mbox{-}list} &::= (\{\mathit{S\mbox{-}exp}\}^*) \\ \mathit{S\mbox{-}exp} &::= \mathit{Symbol} \mid \mathit{S\mbox{-}list}\end{align*}
克莱尼星号简洁地描述了集合 s-list，但对写程序没什么用。因此我们的第一步是抛开克 莱尼星号重写语法。得出的语法表明，我们的过程应当该递归处理 s-list 的首项和余项。
\begin{align*}\mathit{S\mbox{-}list} &::= () \\ &::= (\mathit{S\mbox{-}exp} . \mathit{S\mbox{-}list}) \\ \mathit{S\mbox{-}exp} &::= \mathit{Symbol} \mid \mathit{S\mbox{-}list}\end{align*}
这一例子比之前的复杂，因为它的语法输入包含两个非终结符，S\mbox{-}list 和 S\mbox{-}exp。因此，我们需要两个过程，一个处理 S\mbox{-}list，另一个处理 S\mbox{-}exp。
subst : $\mathit{Sym} \times \mathit{Sym} \times \mathit{S\mbox{-}list} \to \mathit{S\mbox{-}list}$ (define subst (lambda (new old slist) ...)) subst-in-s-exp : $\mathit{Sym} \times \mathit{Sym} \times \mathit{S\mbox{-}exp} \to \mathit{S\mbox{-}exp}$ (define subst-in-s-exp (lambda (new old sexp) ...))
我们首先处理 subst。如果列表为空，不需要替换 old。
subst : $\mathit{Sym} \times \mathit{Sym} \times \mathit{S\mbox{-}list} \to \mathit{S\mbox{-}list}$ (define subst (lambda (new old slist) (if (null? slist) '() ...)))
如果 slist 非空，它的首项是一个 S\mbox{-}exp，余项是另一 s-list。这时， 答案应当是一个列表，它的首项是把 slist 首项中的 old 替换为 new 的 结果，它的余项是把 slist 余项中的 old 替换为 new 的结果。因为 slist 的首项是 S\mbox{-}exp 的元素，我们用 subst-in-s-exp解决这一 子问题。因为 slist 的余项是 S\mbox{-}list 的元素，我们递归调用 subst 处理它。
现在来处理 subst-in-s-exp。由语法，可知符号表达式 sexp 或者是符号，或 者是 s-list。如果它是符号，那么得检查它与符号 old 是否相同。如果是，答案为 new；否则，答案还是 sexp。如果 sexp 是一个 s-list，那么我们递归调 用 subst 找出答案。
subst-in-s-exp : $\mathit{Sym} \times \mathit{Sym} \times \mathit{S\mbox{-}exp} \to \mathit{S\mbox{-}exp}$ (define subst-in-s-exp (lambda (new old sexp) \begin{mdframed}[style=codediff] (if (symbol? sexp) (if (eqv? sexp old) new sexp) (subst new old sexp)))) \end{mdframed}
因为我们严格依照 \mathit{S\mbox{-}list} 和 \mathit{S\mbox{-}exp} 的定义， 这个递归一定会终止。因为 subst 和 subst-in-s-exp 递归调用彼此，我们称 之为互递归 (mutually recursive)。
把 subst 拆解为两个过程——每个处理一种句法类别——是个重要技巧。对更为复杂的程 序，我们得以每次考虑一个句法类别，从而化繁为简。
\textnormal{[}{\star}\textnormal{]} subst-in-s-exp 的最后一行中，递归是针对 sexp 而非更小的子结构，为什 么一定能终止？
\textnormal{[}{\star}\textnormal{]} 用 subst-in-s-exp 的定义替换 subst 中的调用，从而排除这次调用，然后简 化得到的过程。结果中的 subst 应当不需要 subst-in-s-exp。这种技巧 叫做内联 (inlining)，用于优化编译器。
\textnormal{[}{\star}{\star}\textnormal{]} 在我们的例子中，我们从排除 $S\mbox{-}list$ 语法内的克莱尼星号开始。依照原本的 语法，用 map 重写 subst。
现在，我们有了编写过程处理归纳数据集的窍门，来把它总结成一句口诀。
定义过程处理归纳式数据时，程序的结构应当反映数据的结 构。
更准确地说：
1.3 辅助过程和上下文参数
窍门遵循语法很有效，有时却还是不够。考虑过程 number-elements。这 一过程取任何列表 (v_0 v_1 v_2 ...) ，返回一列表 ((0 v_0) (1 v_1) (2 v_2) ...)。
我们用过的那种直拆法不凑效，因为没有明显的方法能从 (number-elements (cdr lst)) 得出 (number-elements lst) （但是，看看）。
要解决这个问题，我们放宽 (generalize) 问题。我们写一个过程 number-elements-from ，它取一个额外参数 n，指定起始编号。用递归处理列表， 这个过程很容易写。
number-elements-from : $\mathit{Listof}(\mathit{SchemeVal}) \times \mathit{Int} \to \mathit{Listof}(\mathit{List}(\mathit{Int}, \mathit{SchemeVal}))$ \begin{alignedat}{-1}用法 : &(number-elements-from ’(v_0 v_1 v_2 ...) n) \\ &\hphantom{x}= ((n v_0) (n + 1 v_1) (n + 2 v_2) ...)\end{alignedat} (define number-elements-from (lambda (lst n) (if (null? lst) '() (cons (list n (car lst)) (number-elements-from (cdr lst) (+ n 1))))))
合约的标题告诉我们这个过程取两个参数，一个列表（包含任意 Scheme 值）和一个整数， 返回一个列表，列表中的每个元素是包含两个元素的列表：一个整数，一个 Scheme 值。
一旦我们定义了 number-elements-from，很容易写出所需的过程。
这里有两个要点。首先，过程 number-elements-from 的定义独立于 number-elements。程序员经常要写一个过程，只调用某个辅助过程，并传递额外的常 量参数。除非我们理解辅助过程对参数的每个值做什么，我们很难理解调用它的过 程做什么。这给了我们一条口诀：
定义辅助过程时，总是指明它对所有参数值做什么，而不只 是初始值。
其次，number-elements-from 的两个参数各有作用。第一个参数是我们要处理的列表， 随每一次递归调用而减小。而第二个参数，则是对我们当前任务上下文 (context) 的抽象。在本例中，当调用 number-elements 时，我们最终调用 number-elements-from 处理原列表的每个子列表。第二个参数告知我们子列表在原列 表中的位置。随递归调用，它不减反增，因为我们每次经过原列表的一个元素。有时我们称 之为上下文参数 (context argument)，或者继承 属性 (inherited attribute)。
另一个例子是向量求和。
要求列表中各项的和，我们可以遵循语法，递归处理列表的余项。那么我们的过程看起来像 是：
但是无法按照这种方式处理向量，因为它们不能够很方便地拆解。
\sum_{i=0}^{i=length(v)-1} v_i 其中，v 是整数向量。通过把上界改为一个参数 n，我们放宽了原问题，所以新的 任务是计算 \sum_{i=0}^{i=n} v_i 其中，0 \leq n < length(v)。
partial-vector-sum : \mathit{Vectorof}(\mathit{Int}) \times \mathit{Int} \to \mathit{Int} 用法 : 若 0 \leq n < length(v)，则 \[(partial-vector-sum v n) = \sum_{i=0}^{i=n} v_i\] (define partial-vector-sum (lambda (v n) (if (zero? n) (vector-ref v 0) (+ (vector-ref v n) (partial-vector-sum v (- n 1))))))
由于 n 一定会递减至零，证明此程序的正确性需要用归纳法处理 n。由 0 \leq n 且 n \neq 0，可得 0 \leq (n - 1)，所以递归调用过程 partial-vector-sum 仍然满足其合约。
现在，要解决原问题就简单多了。因为向量长度为0时无法使用过程 partial-vector-sum，所以得另行处理这种情况。
vector-sum : $\mathit{Vectorof}(\mathit{Int}) \to \mathit{Int}$ 用法 : (vector-sum $v$) = $\sum\limits_{i=0}^{i=length(v)-1} v_i$ (define vector-sum (lambda (v) (let ((n (vector-length v))) (if (zero? n) 0 (partial-vector-sum v (- n 1))))))
还有许多情况下，引入辅助变量或过程来解决问题会有帮助，甚至必不可少。只要能对新过 程做什么给出独立的定义，尽可以如此。
\textnormal{[}{\star}{\star}\textnormal{]} 若 $0 \leq n < length(v)$，证明 partial-vector-sum 的正确性。
1.4 练习
每道习题都假定 s 是一个符号，n 是一个非负整数，lst 是一个列表， loi 是一个整数列表，los 是一个符号列表，slist 是一个 s-list， x 是任意 Scheme 值；类似地，s1 是一个符号，los2 是一个符号列表， x1 是一个 Scheme 值，等等。还假定 pred 是一个谓词 (predicate)， 即一个过程，取任意 Scheme 值，返回 #t 或者 #f。除非某个具体问题另有限 制，不要对数据作其他假设。在这些习题中，不需要检查输入是否符合描述；对每个过程， 都假定输入值是指定集合的成员。
定义，测试和调试每个过程。你的定义应当有本章这种合约和用法注释。可以随便定义辅助 过程，但是你定义的每个辅助过程都应该有其说明，如同辅助过程和上下文参数那样。
测试这些程序时，先试试所有给出的例子，然后用其他例子测试，因为给定的例子不足以涵 盖所有可能的错误。
\textnormal{[}{\star}\textnormal{]} (duple n x) 返回包含 n 个 x 的列表。
> (duple 2 3) '(3 3)
> (duple 4 '(ha ha)) '((ha ha) (ha ha) (ha ha) (ha ha))
> (duple 0 '(blah)) '()
\textnormal{[}{\star}\textnormal{]} lst 是由二元列表（长度为2的列表）组成的列表，(invert lst) 返回一列表， 把每个二元列表反转。
> (invert '((a 1) (a 2) (1 b) (2 b))) '((1 a) (2 a) (b 1) (b 2))
\textnormal{[}{\star}\textnormal{]} (down lst) 给 lst 的每个顶层元素加上一对括号。
> (down '(1 2 3)) '((1) (2) (3))
> (down '((a) (fine) (idea))) '(((a)) ((fine)) ((idea)))
> (down '(a (more (complicated)) object)) '((a) ((more (complicated))) (object))
\textnormal{[}{\star}\textnormal{]} (swapper s1 s2 slist) 返回一列表，将 slist 中出现的所有 s1 替换为 s2，所有 s2 替换为 s1。
> (swapper 'a 'd '(a b c d)) '(d b c a)
> (swapper 'a 'd '(a d () c d)) '(d a () c a)
> (swapper 'x 'y '((x) y (z (x)))) '((y) x (z (y)))
\textnormal{[}{\star}{\star}\textnormal{]} (list-set lst n x) 返回一列表，除第 n 个元素 （从零开始计数）为 x 外，与 lst 相同。
> (list-set '(a b c d) 2 '(1 2)) '(a b (1 2) d)
> (list-ref (list-set '(a b c d) 3 '(1 5 10)) 3) '(1 5 10)
\textnormal{[}{\star}\textnormal{]} (count-occurrences s slist) 返回 slist 中出现的 s 个数。
> (count-occurrences 'x '((f x) y (((x z) x)))) 3
> (count-occurrences 'x '((f x) y (((x z) () x)))) 3
> (count-occurrences 'w '((f x) y (((x z) x)))) 0
\textnormal{[}{\star}{\star}\textnormal{]} sos1 和 sos2 是两个没有重复元素的符号列表，(product sos1 sos2)返 回二元列表的列表，代表 sos1 和 sos2 的笛卡尔积。二元列表排列顺序不限。
> (product '(a b c) '(x y)) '((a x) (a y) (b x) (b y) (c x) (c y))
\textnormal{[}{\star}{\star}\textnormal{]} (filter-in pred lst) 返回的列表，由 lst 中满足谓词 pred 的元素组 成。
> (filter-in number? '(a 2 (1 3) b 7)) '(2 7)
> (filter-in symbol? '(a (b c) 17 foo)) '(a foo)
\textnormal{[}{\star}{\star}\textnormal{]} (list-index pred lst) 返回 lst 中第一个满足谓词 pred 的元素位置， 从零开始计数。如果 lst 中没有元素满足谓词，list-index 返回 #f。
> (list-index number? '(a 2 (1 3) b 7)) 1
> (list-index symbol? '(a (b c) 17 foo)) 0
> (list-index symbol? '(1 2 (a b) 3)) #f
\textnormal{[}{\star}{\star}\textnormal{]} 若 lst 中的任何元素不满足 pred，(every? pred lst) 返回 #f， 否则返回 #t。
> (every? number? '(a b c 3 e)) #f
> (every? number? '(1 2 3 4 5)) #t
\textnormal{[}{\star}{\star}\textnormal{]} 若 lst 中的任何元素满足 pred，(exists? pred lst) 返回 #t，否则返回 #f。
> (exists? number? '(a b c 3 e)) #t
> (exists? number? '(a b c d e)) #f
\textnormal{[}{\star}{\star}\textnormal{]} (up lst) 移除 lst 中每个顶层元素周围的一对括号。如果顶层元素不是列表， 则照原样放入结果中。(up (down lst)) 的结果与 lst 相同，但 (down (up lst)) 不一定是 lst（参见）。
> (up '((1 2) (3 4))) '(1 2 3 4)
> (up '((x (y)) z)) '(x (y) z)
\textnormal{[}{\star}{\star}\textnormal{]} (flatten slist) 返回一列表，由 slist 中的符号按出现顺序组成。直观上， flatten 移除参数内的所有内层括号。
> (flatten '(a b c)) '(a b c)
> (flatten '((a) () (b ()) () (c))) '(a b c)
> (flatten '((a b) c (((d)) e))) '(a b c d e)
> (flatten '(a b (() (c)))) '(a b c)
\textnormal{[}{\star}{\star}\textnormal{]} loi1 和 loi2 是元素按照升序排列的整数列表，(merge loi1 loi2) 返 回 loi1 和 loi2 中所有整数组成的的有序列表。
> (merge '(1 4) '(1 2 8)) '(1 1 2 4 8)
> (merge '(35 62 81 90 91) '(3 83 85 90)) '(3 35 62 81 83 85 90 90 91)
\textnormal{[}{\star}{\star}\textnormal{]} (sort loi) 返回一列表，将 loi 中的元素按照升序排列。
> (sort '(8 2 5 2 3)) '(2 2 3 5 8)
\textnormal{[}{\star}{\star}\textnormal{]} (sort/predicate pred loi) 返回一列表，将 loi 的元素按照谓词指定的顺序 排列。
> (sort/predicate < '(8 2 5 2 3)) '(2 2 3 5 8)
> (sort/predicate > '(8 2 5 2 3)) '(8 5 3 2 2)
\textnormal{[}{\star}\textnormal{]} 写出如下过程，对二叉树（）做运算：leaf 和 interior-node 生成二叉树，leaf? 检查二叉树是否是一片叶子，lson、rson和 contents-of 取出一个节点的各部分。contents-of 应对叶子和内部节点都适 用。
\textnormal{[}{\star}\textnormal{]} 写出过程 double-tree，它取一棵二叉树，形如，生成另一棵二叉树，把 原二叉树中的所有整数翻倍。
\textnormal{[}{\star}{\star}\textnormal{]} 写出过程 mark-leaves-with-red-depth，它取一棵二叉树（），生成与 原树形状相同的另一棵二叉树，但在新的二叉树中，每个叶子中的整数表示它和树根之间 含有 red 符号的节点数。例如，表达式
(mark-leaves-with-red-depth (interior-node 'red (interior-node 'bar (leaf 26) (leaf 12)) (interior-node 'red (leaf 11) (interior-node 'quux (leaf 117) (leaf 14))))) 使用 中定义的过程，应返回二叉树
(red (bar 1 1) (red 2 (quux 2 2)))
\textnormal{[}{\star}{\star}{\star}\textnormal{]} 写出过程 path，它取一个整数 n 和一棵含有整数 n 的二叉搜索树 （bst）bst，返回由 left 和 right 组成的列表，表示如何 找到包含 n 的节点。如果在树根处发现 n，它返回空列表。
> (path 17 '(14 (7 () (12 () ())) (26 (20 (17 () ()) ()) (31 () ())))) '(right left left)
\textnormal{[}{\star}{\star}{\star}\textnormal{]} 写出过程 number-leaves，它取一棵二叉树，生成与原树形状相同的二叉树，但叶子 的内容从 0 开始计的整数。例如，
(number-leaves (interior-node 'foo (interior-node 'bar (leaf 26) (leaf 12)) (interior-node 'baz (leaf 11) (interior-node 'quux (leaf 117) (leaf 14))))) 应返回
(foo (bar 0 1) (baz 2 (quux 3 4)))
\textnormal{[}{\star}{\star}{\star}\textnormal{]} 写出过程 g，则n-e的 number-elements 可以定义为：
(define number-elements (lambda (lst) (if (null? lst) '() (g (list 0 (car lst)) (number-elements (cdr lst))))))