2 数据抽象

2.1 用接口定义数据

每当我们想以某种方式表示一些量时，我们就新定义了一种数据类型：它的取值是其表示， 它的操作是处理其实体的过程。

这些实体的表示通常很复杂，所以如能避免，我们不愿关心其细节。我们可能想改变数据的 表示。最高效的表示往往难以实现，所以我们可能希望先简单实现，只在确知系统的整体性 能与之攸关时，才改用更高效的表示。不管出于什么原因，如果我们决定改变某些数据的表 示方式，我们得能定位程序中所有依赖表示方式的部分。这就需要 借助数据抽象 (data abstraction) 技术。

数据抽象将数据类型分为两部分：接口 (interface) 和实现 (implementation)。 接口告诉我们某类型表示什么数据，能对数据做什么操作，以及可由这些操作得出 的性质。实现给出数据的具体表示，以及处理数据表示的代码。

这样抽象出的数据类型称为抽象数据类型 (abstract data type)。程序的其余部 分——数据类型的客户 (client) ——只能通过接口中指定的操作处理新数据。这样一 来，如果我们希望改变数据的表示，只需改变数据处理接口的实现。

这一想法并不陌生：我们写程序处理文件时，多数时候只关心能否调用过程来打开，关闭， 读取文件或对文件做其他操作。同样地，大多数时候，我们不关心整数在机器中究竟怎样表 示，只关心能否可靠地执行算术操作。

当客户只能通过接口提供的过程处理某类型的数据时，我们说客户代码 与表示无关 (representation-independent)，因为这些代码不依赖数据类型值的 表示。

那么所有关于数据表示的信息必然在实现代码之中。实现最重要的部分就是表示数据的规范。 我们用符号 \lceil v \rceil 指代“数据 v 的表示”。

要说得更明白些，来看一个简单例子：自然数类型。待表示的数据是自然数。接口由四个过 程组成：zero、is-zero?、successor 和 predecessor。当然，不是 随便几个过程都可以作为这一接口的实现。当且仅当一组过程满足如下四个方程时，可以作 为 zero、is-zero?、successor 和 predecessor 的实现：

(zero) = \lceil 0 \rceil

(is-zero? \lceil n \rceil) = $\begin{cases}#t & n = 0 \\ #f & n \neq 0\end{cases}$

(successor \lceil n \rceil) = \lceil n + 1 \rceil \quad (n \geq 0)

(predecessor \lceil n + 1 \rceil) = \lceil n \rceil \quad (n \geq 0)

这一定义没有指明自然数应当如何表示，它只要求这些过程都产生指定的行为。即，过程 zero 必须返回 0 的表示；给定数字 n 的表示，过程 successor 必须 返回数字 n + 1 的表示，等等。这个定义没对 (predecessor (zero)) 做出说明， 所以按这个定义，任何行为都是可以接受的。

现在可以写出处理自然数的客户程序，而且不论用哪种表示方式，都保证能得出正确的结果。 例如，不论怎样实现自然数，

(define plus

(lambda (x y)

(if (is-zero? x)

y

(successor (plus (predecessor x) y)))))

都满足 (plus \lceil x \rceil \lceil y \rceil) = \lceil x + y\rceil。

大多数接口都包含：若干构造器 (constructor)，用来产生数据类型的元素； 若干观测器 (observer)，用来从数据类型的值中提取信息。这里有三个构造器， zero、successor 和 predecessor；一个观测器，is-zero?。

可以用多种方式表示这套接口，我们考虑其中三种。

1. 一元表示法 (Unary representation)：在一元表示法中，自然数n 由 n 个 #t 组成的列表表示。所以，0 表示为 ()，1 表示为 (#t)，2 表示为 (#t #t)，等等。可以用归纳法定义这种表示方式：

   \lceil 0 \rceil = ()

   \lceil n + 1 \rceil = (#t . \lceil n \rceil)

   要满足该表示的定义，数据处理过程可以写成：

   (define zero (lambda () '()))

   (define is-zero? (lambda (n) (null? n)))

   (define successor (lambda (n) (cons #t n)))

   (define predecessor (lambda (n) (cdr n)))

2. Scheme 数字表示法 (Scheme number representation)：在这种表示中， 只需用 Scheme 内置的数字表示法（本身可能十分复杂！）。令 \lceil n \rceil 为 Scheme 整数 n，则所需的四个过程可以定义为：

   (define zero (lambda () 0))

   (define is-zero? (lambda (n) (zero? n)))

   (define successor (lambda (n) (+ n 1)))

   (define predecessor (lambda (n) (- n 1)))

3. 大数表示法 (Bignum representation)： 在大数表示法中，数值以 N 进制表示，N 是某个大整数。该方法以 0 到 N-1 之间的数字（有时不称数位，而称大位 (bigits)）组成的列表表示数值， 这就很容易表示远超机器字长的整数。这里，为了便于使用，我们把最低位放在列表最前 端。这种表示法可用归纳法定义为：

   $\lceil n \rceil = \begin{cases}() & n = 0 \\ (r . \lceil q \rceil) & n = qN + r, 0 \leqslant r < N\end{cases}$

   所以，如果 N = 16，那么 \lceil 33 \rceil = (1 2)，\lceil 258 \rceil = (2 0 1)，因为：

   258 = 2 \times 16^0 + 0 \times 16^1 + 1 \times 16^2

这些实现都没有强制数据抽象：无法防止客户程序查验表示用 的是列表还是 Scheme 整数。与之相对，有些语言直接支持数据抽象：它们允许程序员创建 新的接口，确保只能通过接口提供的过程处理新数据。如果类型的表示隐藏起来，不会因任 何操作而暴露（包括打印），那就说该类型是模糊 (opaque) 的，否则称之 为透明 (transparent) 的。

Scheme 没有提供标准机制来创建新的模糊类型，所以我们退而求其次：定义接口，靠客户 程序的作者小心行事，只使用接口中定义的过程。

在模块中，我们讨论一些方法，以便强化语言的这种协议。

\textnormal{[}{\star}\textnormal{]}  实现大数表示法的四种操作。然后用你的实现计算10的阶乘。随着参数改变，执行时间如 何变化？随着进制改变，执行时间如何变化？解释原因。

\textnormal{[}{\star}{\star}\textnormal{]} 详加分析上述表示。从满足数据类型定义的角度来说，它们在何种程度上是成功或失败的？

\textnormal{[}{\star}{\star}\textnormal{]}  用差分树表示所有整数（负数和非负数）。差分树是一列表，可用语法定义如下：

\mathit{Diff\text{-}tree} ::= (one) \mid (diff \mathit{Diff\text{-}tree} \mathit{Diff\text{-}tree})

列表 (one) 表示 1。如果 t_1 表示 n_1，t_2 表示 n_2，那么 (diff n_1 n_2) 表示 n_1 - n_2。

所以，(one) 和 (diff (one) (diff (one) (one))) 都表示1；(diff (diff (one) (one)) (one)) 表示 -1。

1. 证明此系统中，每个数都有无限种表示方式。

2. 实现这种整数表示法：写出nat定义的 zero、is-zero?、 successor 和 predecessor，此外还要能表示负数。这种方式下，整数的任 何合法表示都应该能作为你过程的参数。例如，你的过程 successor 可以接受无 限多种 1 的合法表示，且都应给出一个 2的合法表示。对 1 的不同合法 表示，可以给出不同的 2 的合法表示。

3. 写出过程 diff-tree-plus，用这种表示做加法。你的过程应针对不同的差 分树进行优化，并在常数时间内得出结果（即与输入大小无关）。注意，不可使用递归。

2.2 数据类型的表示策略

使用数据抽象的程序具有表示无关性：与用来实现抽象数据类型的具体表示方式无关，甚至 可以通过重新定义接口中的一小部分过程来改变表示。在后面的章节中我们常会用到这条性 质。

本节介绍几种数据类型的表示策略。我们用数据类型环境 (environment) 解释这 些选择。对有限个变量组成的集合，环境将值与其中的每个元素关联起来。在编程语言的实 现之中，环境可用来维系变量与值的关系。编译器也能用环境将变量名与变量信息关联起来。

只要能够检查两个变量是否相等，变量能够用我们喜欢的任何方式表示。我们选用 Scheme 符号表示变量，但在没有符号数据类型的语言中，变量也可以用字符串，哈希表引用，甚至 数字表示（见 消除变量名）。

2.2.1 环境的接口

环境是一函数，定义域为有限个变量的集合，值域为所有 Scheme 值的集合。数学上常说的 有限函数是指有序数对组成的有限集合，我们采用这一含义，就得表示形如 $\{(var_1,\allowbreak val_1),\allowbreak ...,\allowbreak (var_n, val_n)\}$的所 有集合。其中，var_i 是某一变量，val_i 是任意 Scheme 值。有时称环境 env 中变量 var 的值 val 为其在 env 中的绑定 (binding)。

这一数据类型的接口有三个过程，定义如下：

\begin{align*}&(empty-env) &= &\ \lceil \emptyset \rceil \\ &(apply-env \lceil f \rceil var) &= &\ f(var) \\ &(extend-env var v \lceil f \rceil) &= &\ \lceil g \rceil \\ &\phantom{x} &其中，&\ g(var_1) = \begin{cases}v & 若\ var_1 = var \\ f(var_1) & 否则\end{cases}\end{align*}

过程 empty-env 不带参数，必须返回空环境的表示；apply-env 用环境对变量 求值；(extend-env var val env) 产生一个新环境，将变量 var 的值设为 val，此外与 env 相同。例如，表达式

> (define e

(extend-env 'd 6

(extend-env 'y 8

(extend-env 'x 7

(extend-env 'y 14

(empty-env))))))

定义了一个环境 e，使 e(d) = 6，e(x) = 7，e(y) = 8，且对任何其他变量，e未定义。本例中，y先绑定到 14，随后绑定到 8。这当然只是生成该环境的众多方法之一。

如同前一个例子，可以将接口中的过程分为构造器和观测器。本例中，empty-env和 extend-env是构造器，apply-env是唯一的观测器。

\textnormal{[}{\star}{\star}\textnormal{]}  考虑数据类型栈 (stack)，其接口包含过程 empty-stack、push、 pop、top 和 empty-stack?。按照示例中的方式写出这些操作的定义。哪 些操作是构造器？哪些是观测器？

2.2.2 数据结构表示法

观察可知，每个环境都能从空环境开始，n 次调用 extend-env 得到，其中 n \geqslant 0。例如，

(extend-env var_n val_n

...

(extend-env var_1 val_1

(empty-env)))

由此可得一种环境的表示方法。

每个环境都能用下列语法定义的表达式生成：

\begin{align*}\mathit{Env\text{-}exp} &::= (empty-env) \\ &::= (extend-env \mathrm{Identifier} \mathrm{Scheme\text{-}value} \mathrm{Env\text{-}exp})\end{align*}

可以用描述列表集合的语法表示环境，由此得出 中的实现。过程 apply-env 查 看表示环境的数据结构 env，判断它表示哪种环境，并做适当操作。如果它表示空环 境，那就报错；如果它表示 extend-env 生成的环境，那就判断要查找的变量是否与 环境中绑定的某一变量相同，如果是，则返回保存的值，否则在保存的环境中查找变量。

这是一种常见的代码模式。我们叫它解释器秘方 (interpreter recipe)：

解释器秘方

1. 查看一段数据。

2. 判断它表示什么样的数据。

3. 提取数据的各个部分，对它们做适当操作。

\textnormal{[}{\star}\textnormal{]}  只要能区分空环境和非空环境，并能从后者中提取出数据片段，就能用任何数据结构表示环 境。按这种方式实现环境：空环境由空列表表示，extend-env生成如下环境：

这叫 a-list 或关联列表 (association-list) 表示法。

\textnormal{[}{\star}\textnormal{]} 发明三种以上的环境接口表示，给出实现。

\textnormal{[}{\star}\textnormal{]} 重写 中的 apply-env，给出更详细的错误信息。

\textnormal{[}{\star}\textnormal{]}  给环境接口添加观测器 empty-env?，用 a-list 表示法实现它。

\textnormal{[}{\star}\textnormal{]} 给环境接口添加观测器 has-binding?，它取一环境 env，一个变量 s，判断 s 在 env 中是否有绑定值。用 a-list 表示法实现它。

\textnormal{[}{\star}\textnormal{]}  给环境接口添加构造器 extend-env*，用 a-list 表示法实现它。这个构造器取一变 量列表和一长度相等的值列表，以及一环境，其定义为：

\begin{align*}& (extend-env* (var_1 \dots var_k) (val_1 \dots var_k) \lceil f \rceil) = \lceil g \rceil, \\ & \quad 其中，g(var) = \begin{cases}val_i & 若 \ var = var_i \ 对某个 \ i \ 成立，1 \leqslant i \leqslant k \\ f(var) & 否则\end{cases}\end{align*}

\textnormal{[}{\star}{\star}\textnormal{]} 前一题中的 extend-env* 实现比较拙劣的话，运行时间与 k 成正比。有一种表 示可使 extend-env* 的运行时间为常数：用空列表表示空环境，用下面的数据结构表 示非空环境：

那么一个环境看起来像是这样：

这叫做肋排 (ribcage) 表示法。环境由名为肋骨 (rib) 的序对列表表示； 每根左肋是变量列表，右肋是对应的值列表。

用这种表示实现 extend-env* 和其他环境接口。

2.2.3 过程表示法

环境接口有一条重要性质：它只有 apply-env 一个观测器。这样就能用取一变量，返 回绑定值的 Scheme 过程表示环境。

要这样表示，定义 empty-env 和 extend-env 的返回值为过程，调用二者的返 回值就如同调用上一节的 apply-env 一样。由此得出下面的实现。

\mathit{Env} = \mathit{Var} \to \mathit{SchemeVal}

\mathit{Var} = \mathit{Sym}

empty-env : () \to \mathit{Env}

(define empty-env

(lambda ()

(lambda (search-var)

(report-no-binding-found search-var))))

extend-env : \mathit{Var} \times \mathit{SchemeVal} \times \mathit{Env} \to \mathit{Env}

(define extend-env

(lambda (saved-var saved-val saved-env)

(lambda (search-var)

(if (eqv? search-var saved-var)

saved-val

(apply-env saved-env search-var)))))

apply-env : \mathit{Env} \times \mathit{Var} \to \mathit{SchemeVal}

(define apply-env

(lambda (env search-var)

(env search-var)))

empty-env 创建的空环境收到任何变量都会报错，表明给定的变量不在其中。过程 extend-env 返回的过程代表扩展而得的环境。这个过程收到变量 search-var 后，判断该变量是否与环境中绑定的相同。如果相同，就返回保存的值；否则，就在保存的 环境中查找它。

这种表示法中，数据由 apply-env 执行的动作表示，我们称之 为过程表示法 (procedural representation)。

数据类型只有一个观测器的情形并非想象中那般少见。比如，当数据是一组函数，就能用调 用时执行的动作表示。这种情况下，可以按照下 列步骤提炼出接口和过程表示法：

1. 找出客户代码中求取指定类型值的 lambda 表达式。为每个这样的 lambda 表达式 写一个构造器过程。构造器过程的参数用作 lambda 表达式中的自由变量。在客户代码中， 用构造器调用替换对应的 lambda 表达式。

2. 像定义 apply-env 那样定义一个 apply- 过程。找出客户代码中所有使 用指定类型值的地方，包括构造器过程的主体。所有使用指定类型值的地方都改用 apply- 过程。

一旦完成这些步骤，接口就包含所有的构造器过程和 apply- 过程，客户代码则与表 示无关：它不再依赖表示，我们将能随意换用另一套接口实现，正如 数据结构表示法所述。

如果用于实现的语言不支持高阶过程，那就得再做一些步骤，用数据结构表示法和解释器秘 方实现所需接口，就像上一节那样。这一操作叫做消函 (defunctionalization)。 环境的数据结构表示中，各种变体都是消函的简单例子。过程表示法和消函表示法的关系将 是本书反复出现的主题。

\textnormal{[}{\star}\textnormal{]}  用过程表示法实现 中的栈数据类型。

\textnormal{[}{\star}{\star}\textnormal{]} 扩展过程表示法，用两个过程组成的列表表示环境，实现 empty-env?。一个过程像前 面那样，返回变量的绑定值；一个返回环境是否为空。

\textnormal{[}{\star}{\star}\textnormal{]} 扩展前一题中的表示法，加入第三个过程，用它来 has-binding? （见 ）。

2.3 递推数据类型的接口

归纳式数据集大部分都在处理递推数据类型。例如， 给出了 lambda 演算表达式的语法：

\begin{align*}\mathit{Lc\text{-}Exp} &::= \mathit{Identifier} \\ &::= \normalfont{(lambda (\mathit{Identifier}) \mathit{Lc\text{-}Exp})} \\ &::= \normalfont{(\mathit{Lc\text{-}Exp} \mathit{Lc\text{-}Exp})}\end{align*}

我们还写出了过程 occurs-free?。像当时提到的，occurs-free?中 occurs-free? 的定义不大容易读懂。比如，很难搞明白 (car (cadr exp)) 指 代 lambda 表达式中的变量声明，或者 (caddr exp) 指代表达式的主体。

要改善这种情况，可以给 lambda 演算表达式添加一套接口。我们的接口有几个构造器，以 及两种观测器：谓词和提取器。

构造器有：

var-exp: \mathit{Var} \to \mathit{Lc\text{-}Exp}

lambda-exp: \mathit{Var} \times \mathit{Lc\text{-}Exp} \to \mathit{Lc\text{-}Exp}

app-exp: \mathit{Lc\text{-}Exp} \times \mathit{Lc\text{-}Exp} \to \mathit{Lc\text{-}Exp}

谓词有：

var-exp?: \mathit{Lc\text{-}Exp} \to \mathit{Bool}

lambda-exp?: \mathit{Lc\text{-}Exp} \to \mathit{Bool}

app-exp?: \mathit{Lc\text{-}Exp} \to \mathit{Bool}

提取器有：

var-exp->var: \mathit{Lc\text{-}Exp} \to \mathit{Var}

lambda-exp->bound-var: \mathit{Lc\text{-}Exp} \to \mathit{Var}

lambda-exp->body: \mathit{Lc\text{-}Exp} \to \mathit{Lc\text{-}Exp}

app-exp->rator: \mathit{Lc\text{-}Exp} \to \mathit{Lc\text{-}Exp}

app-exp->rand: \mathit{Lc\text{-}Exp} \to \mathit{Lc\text{-}Exp}

每个提取器对应 lambda 演算表达式中的一部分。现在可以写出一版只依赖接口的 occurs-free?。

occurs-free? : \mathit{Sym} \times \mathit{LcExp} \to \mathit{Bool}

(define occurs-free?

(lambda (search-var exp)

(cond

((var-exp? exp) (eqv? search-var (var-exp->var exp)))

((lambda-exp? exp)

(and

(not (eqv? search-var (lambda-exp->bound-var exp)))

(occurs-free? search-var (lambda-exp->body exp))))

(else

(or

(occurs-free? search-var (app-exp->rator exp))

(occurs-free? search-var (app-exp->rand exp)))))))

只要使用上述构造器，怎样表示 lambda 演算表达式都可以。

我们可以写出设计递推数据类型接口的一般步骤：

设计递推数据类型的接口

1. 为数据类型的每种变体加入一个构造器。

2. 为数据类型的每种变体加入一个谓词。

3. 为传给数据类型构造器的每段数据加入一个提取器。

\textnormal{[}{\star}\textnormal{]}  上述语法指定了 lambda 演算表达式的表示方式，实现其接口。

\textnormal{[}{\star}\textnormal{]} 修改实现，换用另一种表示，去掉 lambda 表达式绑定变量周围的括号。

\textnormal{[}{\star}\textnormal{]} 再发明至少两种方式来表示数据类型 lambda 演算表达式，实现它们。

\textnormal{[}{\star}\textnormal{]}  我们常用列表表示值的序列。在这种表示法中，很容易从序列中的一个元素移动到下一个， 但是不借助上下文参数，很难从一个元素移动到上一个。实现非空双向整数序列，语法为：

\[\mathit{NodeInSequence} ::= (\mathit{Int} \mathit{Listof(\mathit{Int})} \mathit{Listof(\mathit{Int})})\]

第一个整数列表是当前元素之前的序列，反向排列。第二个列表是当前元素之后的序列。例 如，(6 (5 4 3 2 1) (7 8 9)) 表示列表 (1 2 3 4 5 6 7 8 9)，当前元素为6。

用这种表示实现过程 number->sequence，它取一数字，生成只包含该数字的序列。接 着实现 current-element、move-to-left、move-to-right、 insert-to-left、insert-to-right、at-left-end? 和 at-right-end?。

例如：

> (number->sequence 7)

'(7 () ())

> (current-element '(6 (5 4 3 2 1) (7 8 9)))

6

> (move-to-left '(6 (5 4 3 2 1) (7 8 9)))

'(5 (4 3 2 1) (6 7 8 9))

> (move-to-right '(6 (5 4 3 2 1) (7 8 9)))

'(7 (6 5 4 3 2 1) (8 9))

> (insert-to-left 13 '(6 (5 4 3 2 1) (7 8 9)))

'(6 (13 5 4 3 2 1) (7 8 9))

> (insert-to-right 13 '(6 (5 4 3 2 1) (7 8 9)))

'(6 (5 4 3 2 1) (13 7 8 9))

如果参数在序列最右端，过程move-to-right应失败。如果参数在序列最左端，过程 move-to-left应失败。

\textnormal{[}{\star}\textnormal{]}  空二叉树和用整数标记内部节点的二叉树可以用语法表示为：

\[\mathit{BinTree} ::= () \mid (\mathit{Int} \mathit{BinTree} \mathit{BinTree})\]

用这种表示实现过程 number->bintree，它取一个整数，产生一棵新的二叉树，树的 唯一节点包含该数字。接着实现 current-element、move-to-left-son、 move-to-right-son、at-leaf?、insert-to-left 和 insert-to-right。例如：

> (number->bintree 13)

'(13 () ())

> (define t1 (insert-to-right 14                (insert-to-left 12                  (number->bintree 13))))

> t1

'(13 (12 () ()) (14 () ()))

> (move-to-left-son t1)

'(12 () ())

> (current-element (move-to-left-son t1))

12

> (at-leaf? (move-to-right-son (move-to-left-son t1)))

#t

> (insert-to-left 15 t1)

'(13 (15 (12 () ()) ()) (14 () ()))

\textnormal{[}{\star}{\star}{\star}\textnormal{]} 按照 中的二叉树表示，很容易从父节点移到某个子节点，但是不借 助上下文参数，无法从子节点移动到父节点。扩展 中的列表表示法， 用以表示二叉树中的节点。提示：想想怎样用逆序列表表示二叉树在当前节点以上的部分， 就像 那样。

用这种表示实现 中的过程。接着实现 move-up 和 at-root?。

2.4 定义递推数据类型的工具

对复杂的数据类型，按照上述步骤设计接口很快就会使人厌倦。本节介绍用 Scheme 自动设 计和实现接口的工具。这个工具产生的接口与前一节的虽不完全相同，却很类似。

仍考虑前一节讨论的数据类型 lambda 演算表达式。lambda 演算表达式的接口可以这样写：

(define-datatype lc-exp lc-exp?

(var-exp

(var identifier?))

(lambda-exp

(bound-var identifier?)

(body lc-exp?))

(app-exp

(rator lc-exp?)

(rand lc-exp?)))

这里的名字 var-exp、var、bound-var、app-exp、rator 和 rand 分别是 变量表达式 (variable expression)、变 量 (variable)、绑定变量 (bound variable)、调用表达 式 (application expression)、操作符 (operator) 和操作数 (operand) 的缩写。

这些表达式声明了三种构造器：var-exp、lambda-exp 和 app-exp，以及 一个谓词 lc-exp?。三个构造器用谓词 identifier? 和 lc-exp? 检查它 们的参数，确保参数合法。所以，如果生成 lc-exp 时只用这些构造器，可以确保表达式及 其所有子表达式合法。如此一来，处理 lambda 表达式时就能跳过许多检查。

我们用形式 cases 代替谓词和提取器，判断数据类型的实例属于哪种变体，并提取出 它的组件。为解释这一形式，我们用数据类型 lc-exp 重写 occurs-free?（occurs-free?）：

occurs-free? : \mathit{Sym} \times \mathit{LcExp} \to \mathit{Bool}

(define occurs-free?

(lambda (search-var exp)

(cases lc-exp exp

(var-exp

(var) (eqv? var search-var))

(lambda-exp

(bound-var body)

(and

(not (eqv? search-var bound-var))

(occurs-free? search-var body)))

(app-exp

(rator rand)

(or

(occurs-free? search-var rator)

(occurs-free? search-var rand))))))

要理解它，假设 exp 是由 app-exp 生成的 lambda 演算表达式。根据 exp 的取值，分支 app-exp 将被选中，rator 和 rand 则绑定到两 个子表达式，接着，表达式

(or

(occurs-free? search-var rator)

(occurs-free? search-var rand))

将会求值，就像我们写：

(if (app-exp? exp)

(let ((rator (app-exp->rator exp))

(rand (app-exp->rand exp)))

(or

(occurs-free? search-var rator)

(occurs-free? search-var rand)))

...)

递归调用 occurs-free? 像这样完成运算。

一般的 define-datatype 声明形如：

(define-datatype type\text{-}name type\text{-}predicate\text{-}name

\{(variant\text{-}name \quad \{(filed\text{-}name \quad predicate)\}^{*} )\}^{+})

这新定义了一种数据类型，名为 type\text{-}name，它有一些变 体 (variants)。每个变体有一变体名，以及 0 或多个字段，每个字段各有其 字段名和相应的谓词。不论是否属于不同的类型，变体都不能重名。类型也不能重名，且类 型名不能用作变体名。每个字段的谓词必须是一个 Scheme 谓词。

每个变体都有一个构造器过程，用于创建该变体的值。这些过程的名字与对应的变体相同。 如果一个变体有 n 个字段，那么它的构造器取 n 个参数，用对应的谓词检查每个 参数值，并返回变体值，值的第 i 个字段为第 i 个参数值。

type\text{-}predicate\text{-}name 绑定到一个谓词。这个谓词判断其参数值是否是 相应的类型。

记录表 (record) 可以用只有一种变体的数据类型定义。 为了区分只有一种变体的数据类型，我们遵循一种命名惯例：当只有一个变体时，我们以 a-type\text{-}name 或 an-type\text{-}name 命名构造器；否则，以 variant\text{-}name\text{-}type\text{-}name 命名构造器。

由 define-datatype 生成的数据结构可以互递归。例如，递推定义的数据中的 s-list 语法为：

\begin{align*}\mathit{S\text{-}list} &::= {\normalfont{(\{\mathit{S\text{-}exp}\}^{*})}} \\ \mathit{S\text{-}exp} &::= \mathit{Symbol} \mid \mathit{S\text{-}list}\end{align*}

s-list中的数据可以用数据类型 s-list表示为：

(define-datatype s-list s-list?

(empty-s-list)

(non-empty-s-list

(first s-exp?)

(rest s-list?)))

(define-datatype s-exp s-exp?

(symbol-s-exp

(sym symbol?))

(s-list-s-exp

(slst s-list?)))

数据类型 s-list 用 (empty-s-list) 和 non-empty-s-list 代替 () 和 cons 来表示列表。如果我们还想用 Scheme 列表，可以写成：

(define-datatype s-list s-list?

(an-s-list

(sexps (list-of s-exp?))))

(define list-of

(lambda (pred)

(lambda (val)

(or (null? val)

(and (pair? val)

(pred (car val))

((list-of pred) (cdr val)))))))

这里 (list-of pred) 生成一个谓词，检查其参数值是否是一个列表，且列表的 每个元素都满足 pred。

cases 语法的一般姓形式为：

(cases type\text{-}name expression

\{(variant\text{-}name \phantom{x} (\{filed\text{-}name\}^{*}) \phantom{x} consequent)\}^{*}

(else default))

该形式指定类型，一个待求值和检查的表达式，以及一些从句。每个从句以指定类型的某一 变体名及相应字段名为标识。else 从句可有可无。首先求 expression 的值，得 到 type\text{-}name 的某个值 v。如果 v 是某个 variant\text{-}name 的变体，那就选中对应的从句。各 type\text{-}name 绑定 到 v 中对应的字段值。然后在这些绑定的作用域内求取并返回 consequent 的值。 如果 v 不属于任何变体，且有 else 从句，则求取并返回 default 的值。 如果没有 else 从句，必须为指定数据类型的每个变体指定从句。

形式 cases 根据位置绑定变量： 第 i 个变量绑定到第 i 个字段。所以， 我们可以用：

(app-exp (exp1 exp2)

(or

(occurs-free? search-var exp1)

(occurs-free? search-var exp2)))

代替

(app-exp (rator rand)

(or

(occurs-free? search-var rator)

(occurs-free? search-var rand)))

define-datatype 和 cases 形式提供了一种简洁的方式来定义递推数据类型， 但这种方式并不是唯一的。根据使用场景，可能得用专门的表示方式，它们利用数据的特殊 性质，更紧凑或者更高效。获得这些优势的代价是必须动手实现接口中的过程。

define-datatype 形式是特定领域语言 (domain-specific language) 的例 子。特定领域语言是一种小巧的语言，用来描述小而明确的任务中的单一任务。本例中的任 务是定义一种递推数据类型。这种语言可能像 define-datatype 一样，存在于通用语 言中；也可能是一门单独的语言，别有一套工具。一般来说，创造这类语言首先要找出任务 的不同变体，然后设计语言，描述这些变体。这种策略通常非常有效。

\textnormal{[}{\star}\textnormal{]}  用 define-datatype 实现数据结构表示法中的环境数据类型。然后 实现 中的 has-binding?。

\textnormal{[}{\star}\textnormal{]}  用 define-datatype 实现 中的栈数据类型。

\textnormal{[}{\star}\textnormal{]}  lc-exp 的定义忽略了 中的条件： “\mathit{Identifier} 是除 lambda 之外的任何符号。 ”修改 identifier? 的定义，补充这一条件。提示：任何谓词都能在 define-datatype 中使用，你定义的也能。

\textnormal{[}{\star}\textnormal{]}  这是用 define-datatype 表示的二叉树：

(define-datatype bintree bintree?

(leaf-node

(num integer?))

(interior-node

(key symbol?)

(left bintree?)

(right bintree?)))

实现操作二叉树的过程 bintree-to-list，则 (bintree-to-list (interior-node ’a (leaf-node 3) (leaf-node 4))) 应返回列表：

(interior-node

a

(leaf-node 3)

(leaf-node 4))

\textnormal{[}{\star}{\star}\textnormal{]}  用 cases 写出 max-interior，它取至少有一个内部节点的整数二叉树（像前一 道练习那样），返回叶子之和最大的内部节点对应的标签。

> (define tree-1     (interior-node 'foo (leaf-node 2) (leaf-node 3)))

> (define tree-2     (interior-node 'bar (leaf-node -1) tree-1))

> (define tree-3     (interior-node 'baz tree-2 (leaf-node 1)))

> (max-interior tree-2)

'foo

> (max-interior tree-3)

'baz

最后一次调用 max-interior 也可能返回 foo，因为节点 foo 和 baz 的叶子之和都为 5。

\textnormal{[}{\star}{\star}\textnormal{]}  还有一种写法。树的集合可以用下列语法定义：

\begin{align*}\mathit{Red\text{-}blue\text{-}tree} &::= \mathit{Red\text{-}blue\text{-}subtree} \\ \mathit{Red\text{-}blue\text{-}subtree} &::= (red-node \mathit{Red\text{-}blue\text{-}subtree} \mathit{Red\text{-}blue\text{-}subtree}) \\ &::= (blue-node \{\mathit{Red\text{-}blue\text{-}subtree}\}^{*}) \\ &::= (leaf-node \mathit{Int})\end{align*}

用 define-datatype 写出等价定义，用得到的接口写出一个过程，它取一棵树，生成 形状相同的另一棵树，但把每片叶子的值改为从当前叶子节点到树根之间红色节点的数目。

2.5 抽象语法及其表示

语法通常指定归纳式数据类型的某一具体表示，后者使用前者生成的字符串或值。这种表示 叫做具体语法 (concrete syntax)，或外在 (external) 表示。

例如， 指定集合 lambda 演算表达式，用的就是 lambda 演算表 达式的具体语法。我们可以用其他具体语法表示 lambda 演算表达式。例如，可以用

\begin{align*}\mathit{Lc\text{-}exp} &::= \mathit{Identifier} \\ &::= proc \mathit{Identifier} => \mathit{Lc\text{-}exp} \\ &::= \mathit{Lc\text{-}exp} (\mathit{Lc\text{-}exp})\end{align*}

把 lambda 演算表达式定义为另一个字符串集合。

为了处理这样的数据，需要将其转换为内在 (internal) 表示。 define-datatype 形式提供了一种简洁的方式来定义这样的内在表示。我们称之 为抽象语法 (abstract syntax)。在抽象语法中，不需要存储括号之类的终止符， 因为它们不传达信息。另一方面，我们要确保数据结构足以区分它所表示的 lambda 演算表 达式，并提取出各部分。lc-exp的数据类型 lc-exp 助我们轻松实现这些。

将内在表示形象化为抽象语法树 (abstract syntax tree) 也很不错。 展示了一棵抽象语法树，它代表数据类型 lc-exp 表示的 lambda 演算表达式 (lambda (x) (f (f x)))。树的每个内部节点以相应的生成式名 字为标识。树枝以所出现的非终结符名字为标识。叶子对应终止符字符串。

要为某种具体语法设计抽象语法，需要给其中的每个生成式，以及生成式中出现的每个非终 止符命名。很容易将抽象语法写成 define-datatype 声明。我们为每个非终结符添加 一个 define-datatype，为每个生成式添加一个变体。

中挑出的内容可以精确表示如下：

\begin{align*}\mathit{Lc\text{-}Exp} &::= \mathit{Identifier} \\[-3pt] &\mathrel{\phantom{::=}} \fbox{var-exp (var)} \\[5pt] &::= \normalfont{(lambda (\mathit{Identifier}) \mathit{Lc\text{-}Exp})} \\[-3pt] &\mathrel{\phantom{::=}} \fbox{lambda-exp (bound-var body)} \\[5pt] &::= \normalfont{(\mathit{Lc\text{-}Exp} \mathit{Lc\text{-}Exp})} \\[-3pt] &\mathrel{\phantom{::=}} \fbox{app-exp (rator rand)}\end{align*}

本书采用这种表示，同时指明具体语法和抽象语法。

具体语法主要供人使用，抽象语法主要供计算机使用，既已区分二者，现在来看看如何将一 种语法转换为另一种。

当具体语法是个字符串集合，推导出对应的抽象语法树可能相当棘手。这一任务 叫做解析 (parsing)，由解析器 (parser) 完成。因为写解析器通常比较 麻烦，所以最好借由工具解析器生成器 (parser generator) 完成。 解析器生成器以一套语法作为输入，产生一个解析器。由于语法是由工具处理的，它们必需 以某种机器能够理解的语言写成，即写语法用的特定领域语言。有很多现成的解析器生成器。

如果具体语法以列表集合的形式给出，解析过程就会大大简化。比如， 和define-datatype define-datatype 的语法类似， 本节开头的 lambda 演算表达式指定了一个列表集合。这样，Scheme 过程 read 会自动把字符串解析为列表和符号。然后，把这些列表结构解析为抽象语 法树就容易多了，就像 parse-expression 这样。

parse-expression : \mathit{SchemeVal} \to \mathit{LcExp}

(define parse-expression

(lambda (datum)

(cond

((symbol? datum) (var-exp datum))

((pair? datum)

(if (eqv? (car datum) 'lambda)

(lambda-exp

(car (cadr datum))

(parse-expression (caddr datum)))

(app-exp

(parse-expression (car datum))

(parse-expression (cadr datum)))))

(else (report-invalid-concrete-syntax datum)))))

通常，很容易把抽象语法树重新转换为列表-符号表示。我们这样做了，Scheme 的打印过程 就会将其显示为列表形式的具体语法。这由 unparse-lc-exp 完成：

unparse-lc-exp : \mathit{LcExp} \to \mathit{SchemeVal}

(define unparse-lc-exp

(lambda (exp)

(cases lc-exp exp

(var-exp (var) var)

(lambda-exp

(bound-var body)

(list 'lambda

(list bound-var)

(unparse-lc-exp body)))

(app-exp

(rator rand)

(list (unparse-lc-exp rator)

(unparse-lc-exp rand))))))

\textnormal{[}{\star}\textnormal{]}  画出下面 lambda 演算表达式的抽象语法树：

((lambda (a) (a b)) c)

(lambda (x)

(lambda (y)

((lambda (x)

(x y))

x)))

\textnormal{[}{\star}\textnormal{]}  写出反向解析器，将lc-exp的抽象语法转换为符合本节第二个语法 （lc-grammar2）的字符串。

\textnormal{[}{\star}\textnormal{]}  当具体语法使用克莱尼星号或加号（kleene-star）时，生成抽象语法树时最好 使用相应子树的列表。例如，如果 lambda 演算表达式的语法为：

\begin{align*}\mathit{Lc\text{-}Exp} &::= \mathit{Identifier} \\[-3pt] &\mathrel{\phantom{::=}} \fbox{var-exp (var)} \\[5pt] &::= \normalfont{(lambda (\{\mathit{Identifier}\}^{*}) \mathit{Lc\text{-}Exp})} \\[-3pt] &\mathrel{\phantom{::=}} \fbox{lambda-exp (bound-vars body)} \\[5pt] &::= \normalfont{(\mathit{Lc\text{-}Exp} \{\mathit{Lc\text{-}Exp}\}^{*})} \\[-3pt] &\mathrel{\phantom{::=}} \fbox{app-exp (rator rands)}\end{align*}

那么字段 bound-vars 的谓词可写作 (list-of identifier?)，rands 的 谓词可写作 (list-of lc-exp?)。以这种方式写出该语法的 define-datatype 和解析器。

\textnormal{[}{\star}{\star}\textnormal{]} 上面定义的过程 parse-expression 很不可靠：它检查不到某些可能的语法错误，例 如 (a b c)，并且因其他表达式终止时给不出恰当的错误信息，如 (lambda)。 修改一下，使之更健壮，可接受任何s-exp，并且对不表示 lambda 演算表达式的 s-exp 给 出恰当的错误信息。

\textnormal{[}{\star}{\star}\textnormal{]}  有时，把具体语法定义为括号包围的符号和整数序列很有用。例如，可以把 集合前缀列表 (prefix list) 定义为：

\begin{align*}\mathit{Prefix\text{-}list} &::= (\mathit{Prefix\text{-}exp}) \\ \mathit{Prefix\text{-}exp} &::= \mathit{Int} \\ &::= - \mathit{Prefix\text{-}exp} \mathit{Prefix\text{-}exp}\end{align*}

那么 (- - 3 2 - 4 - 12 7)是一个合法的前缀列表。有时为纪念其发明者Jan Łukasiewicz，称之为波兰前缀表示法 (Polish prefix notation)。写一个 解析器，将前缀列表表示法转换为抽象语法：

(define-datatype prefix-exp prefix-exp?

(const-exp

(num integer?))

(diff-exp

(operand1 prefix-exp?)

(operand2 prefix-exp?)))

使上例与这几个构造器生成相同抽象语法树：

(diff-exp

(diff-exp

(const-exp 3)

(const-exp 2))

(diff-exp

(const-exp 4)

(diff-exp

(const-exp 12)

(const-exp 7))))

提示：想想如何写一个过程，取一列表，产生一个 prefix-exp 和列表剩余元素组成 的列表。