点击查看第一章

第2章 构造数据抽象

现在到了数学抽象中最关键的一步：让我们忘记这些符号所表示的对象。……（数学家）不应在这里停步，有许多操作可以应用于这些符号，而根本不必考虑它们到底代表着什么东西。
--Hermann Weyl，The Mathematical Way of Thinking
（思维的数学方式）

我们在第1章里关注的是计算过程，以及过程在程序中所扮演的角色。在那里我们还看到了怎样使用基本数据（数）和基本操作（算术运算）；怎样通过复合、条件，以及参数的使用将一些过程组合起来，形成复合的过程；怎样通过define做过程抽象。我们也看到，可以将一个过程看作一类计算演化的一个模式。那里还对过程中蕴涵着的某些常见计算模式做了一些分类和推理，并做了一些简单的算法分析。我们也看到了高阶过程，这种机制能够提升语言的威力，因为它将使我们能去操纵通用的计算方法，并能对它们做推理。这些都是程序设计中最基本的东西。
在这一章里，我们将进一步去考察更复杂的数据。第1章里的所有过程，操作的都是简单的数值数据，而对我们希望用计算去处理的许多问题而言，只有这种简单数据还不够。许多程序在设计时就是为了模拟复杂的现象，因此它们就常常需要构造起一些计算对象，这些对象都是由一些部分组成的，以便去模拟真实世界里的那些具有若干侧面的现象。这样，与我们在第1章里所做的事情（通过将一些过程组合起来形成复合的过程，以这种方式构造起各种抽象）相对应，本章将重点转到各种程序设计语言都包含的另一个关键方面：讨论它们所提供的，将数据对象组合起来，形成复合数据的方式。
为什么在程序设计语言里需要复合数据呢？与我们需要复合过程的原因一样：同样是为了提升我们在设计程序时所位于的概念层次，提高设计的模块性，增强语言的表达能力。正如定义过程的能力使我们有可能在更高的概念层次上处理计算工作一样，能够构造复合数据的能力，也将使我们得以在比语言提供的基本数据对象更高的概念层次上，处理与数据有关的各种问题。
现在考虑设计一个系统，它完成有理数的算术。我们可以设想一个运算add-rat，它以两个有理数为参数，产生出它们的和。从基本数据出发，一个有理数可以看作两个整数，一个分子和一个分母。这样，我们就可以设计出一个程序，其中的每个有理数用两个整数表示（一个分子和一个分母），而其中的add-rat用两个过程实现（一个产生和数的分子，另一个产生和数的分母）。然而，这样做下去会非常难受，因为我们必须明确地始终记住哪个分子与哪个分母相互对应。在一个需要执行大量有理数操作的系统里，这种记录工作将会严重地搅乱我们的程序，而这些麻烦又与我们心中真正想做的事情毫无关系。如果能将一个分子和一个分母“粘在一起”，形成一个对偶—一个复合数据对象—事情就会好得多了，因为这样，程序中对有理数的操作就可以按照将它们作为一个概念单位的方式进行了。
复合数据的使用也使我们能进一步提高程序的模块性。如果我们可以直接在将有理数本身当作对象的方式下操作它们，那么也就可能把处理有理数的那些程序部分，与有理数如何表示的细节（可能是表示为一对整数）隔离开。这种将程序中处理数据对象的表示的部分，与处理数据对象的使用的部分相互隔离的技术非常具有一般性，形成了一种称为数据抽象的强有力的设计方法学。我们将会看到，数据抽象技术能使程序更容易设计、维护和修改。
复合对象的使用将真正提高程序设计语言的表达能力。考虑形成“线性组合”ax＋by，我们可能想到写一个过程，让它接受a、b、x和y作为参数并返回ax＋by的值。如果以数值作为参数，这样做没有任何困难，因为我们立刻就能定义出下面的过程：

(define (linear-combination a b x y) 
  (+ (* a x) (* b y)))

但是，如果我们关心的不仅仅是数，假定在写这个过程时，我们希望表述的是基于加和乘形成线性组合的思想，所针对的可以是有理数、复数、多项式或者其他东西，我们可能将其表述为下面形式的过程：

(define (linear-combination a b x y)     
  (add (mul a x) (mul b y)))

其中的add和mul不是基本过程＋和 *，而是某些更复杂的东西，它们能对通过参数a、b、x和y送来的任何种类的数据执行适当的操作。在这里最关键的是，linear-combination对于a、b、x和y需要知道的所有东西，也就是过程add和mul能够执行适当的操作。从过程linear-combination的角度看，a、b、x和y究竟是什么，其实根本就没有关系，至于它们是怎样基于更基本的数据表示就更没有关系了。这个例子也说明了，为什么一种程序设计语言能够提供直接操作复合对象的能力是如此的重要，因为如果没有这种能力，我们就没有办法让一个像linear-combination这样的过程将其参数传递给add和mul，而不必知道这些参数的具体细节结构。
作为本章的开始，我们要实现上面所说的那样一个有理数算术系统，它将成为后面讨论复合数据和数据抽象的一个基础。与复合过程一样，在这里需要考虑的主要问题，也是将抽象作为克服复杂性的一种技术。下面将会看到，数据抽象将如何使我们能在程序的不同部分之间建立起适当的抽象屏障。
我们将会看到，形成复合数据的关键就在于，程序设计语言里应该提供了某种“黏合剂”，它们可以用于把一些数据对象组合起来，形成更复杂的数据对象。黏合剂可能有很多不同的种类。确实的，我们还会发现怎样去构造出根本没有任何特定“数据”操作，只是由过程形成的复合数据。这将进一步模糊“过程”和“数据”之间的划分。实际上，在第1章的最后，这一界限已经开始变得不那么清楚了。我们还要探索表示序列和树的一些常规技术。在处理复合数据中的一个关键性思想是闭包的概念—也就是说，用于组合数据对象的黏合剂不但能用于组合基本的数据对象，同样也可以用于复合的数据对象。另一关键思想是，复合数据对象能够成为以混合与匹配的方式组合程序模块的方便界面。我们将通过给出一个利用闭包概念的简单图形语言的方式，阐释有关的思想。
而后我们要引进符号表达式，进一步扩大语言的表述能力。符号表达式的基本部分可以是任意的符号，不一定就是数。我们将探索表示对象集合的各种不同方式，由此可以发现，就像一个给定的数学函数可以通过许多不同的计算过程计算一样，对于一种给定的数据结构，也可以有许多方式将其表示为简单对象的组合，而这种表示的选择，有可能对操作这些数据的计算过程的时间与空间需求造成重大的影响。我们将在符号微分、集合的表示和信息编码的上下文中研究这些思想。
随后我们将转去处理在一个程序的不同部分可能采用不同表示的数据的问题，这就引出了实现通用型操作的需要，这种操作必须能处理许多不同的数据类型。为了维持模块性，通用型操作的出现，将要求比只有简单数据抽象更强大的抽象屏障。特别地，我们将介绍数据导向的程序设计。这是一种技术，它能允许我们孤立地设计每一种数据表示，而后用添加的方式将它们组合进去（也就是说，不需要任何修改）。为了展示这一系统设计方法的威力，在本章的最后，我们将用已经学到的东西实现一个多项式符号算术的程序包，其中多项式的系数可以是整数、有理数、复数，甚至还可以是其他多项式。

2.1 数据抽象导引

从1.1.8节可以看到，在构造更复杂的过程时可以将一个过程用作其中的元素，这样的过程不但可以看作是一组特定操作，还可以看作一个过程抽象。也就是说，有关过程的实现细节可以被隐蔽起来，这个特定过程完全可以由另一个具有同样整体行为的过程取代。换句话说，我们可以这样造成一个抽象，它将这一过程的使用方式，与该过程究竟如何通过更基本的过程实现的具体细节相互分离。针对复合数据的类似概念被称为数据抽象。数据抽象是一种方法学，它使我们能将一个复合数据对象的使用，与该数据对象怎样由更基本的数据对象构造起来的细节隔离开。
数据抽象的基本思想，就是设法构造出一些使用复合数据对象的程序，使它们就像是在“抽象数据”上操作一样。也就是说，我们的程序中使用数据的方式应该是这样的，除了完成当前工作所必要的东西之外，它们不对所用数据做任何多余的假设。与此同时，一种“具体”数据表示的定义，也应该与程序中使用数据的方式无关。在我们的系统里，这样两个部分之间的界面将是一组过程，称为选择函数和构造函数，它们在具体表示之上实现抽象的数据。为了展示这一技术，下面我们将考虑怎样设计出一组为操作有理数而用的过程。

2.1.1 实例：有理数的算术运算

假定我们希望做有理数上的算术，希望能做有理数的加减乘除运算，比较两个有理数是否相等，等等。
作为开始，我们假定已经有了一种从分子和分母构造有理数的方法。并进一步假定，如果有了一个有理数，我们有一种方法取得（选出）它的分子和分母。现在再假定有关的构造函数和选择函数都可以作为过程使用：

• (make-rat ）返回一个有理数，其分子是整数，分母是整数。
• (numer ）返回有理数的分子。
• (denom ）返回有理数的分母。

我们要在这里使用一种称为按愿望思维的强有力的综合策略。现在我们还没有说有理数将如何表示，也没有说过程numer、denom和make-rat应如何实现。然而，如果我们真的有了这三个过程，那么就可以根据下面关系去做有理数的加减乘除和相等判断了：

我们可以将这些规则表述为如下几个过程：

(define (add-rat x y)
  (make-rat (+ (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))
(define (sub-rat x y)
  (make-rat (- (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))
(define (mul-rat x y)
  (make-rat (* (numer x) (numer y))
            (* (denom x) (denom y))))
(define (div-rat x y)
  (make-rat (* (numer x) (denom y))
            (* (denom x) (numer y))))
(define (equal-rat? x y)
  (= (* (numer x) (denom y))
     (* (numer y) (denom x))))

这样，我们已经有了定义在选择和构造过程numer、denom和make-rat基础之上的各种有理数运算，而这些基础还没有定义。现在需要有某种方式，将一个分子和一个分母粘接起来，构成一个有理数。
序对
为了在具体的层面上实现这一数据抽象，我们所用的语言提供了一种称为序对的复合结构，这种结构可以通过基本过程cons构造出来。过程cons取两个参数，返回一个包含这两个参数作为其成分的复合数据对象。如果给了一个序对，我们可以用基本过程car和cdr68，按如下方式提取出其中各个部分：

(define x (cons 1 2))
(car x)
1
(cdr x)
2

请注意，一个序对也是一个数据对象，可以像基本数据对象一样给它一个名字且操作它。进一步说，还可以用cons去构造那种其元素本身就是序对的序对，并继续这样做下去。

(define x (cons 1 2))
(define y (cons 3 4))
(define z (cons x y))
(car (car z))
1
(car (cdr z))
3

在2.2节里我们将看到，这种组合起序对的能力表明，序对可以用作构造任意种类的复杂数据结构的通用的基本构件。通过过程cons、car和cdr实现的这样一种最基本的复合数据，序对，也就是我们需要的所有东西。从序对构造起来的数据对象称为表结构数据。
有理数的表示
序对为完成这里的有理数系统提供了一种自然方式，我们可以将有理数简单表示为两个整数（分子和分母）的序对。这样就很容易做出下面make-rat、numer和denom的实现：

(define (make-rat n d) (cons n d))
(define (numer x) (car x))
(define (denom x) (cdr x))

还有，为了显示这里的计算结果，我们可以将有理数打印为一个分子，在斜线符之后打印相应的分母：

(define (print-rat x)
  (newline)
  (display (numer x))
  (display "/")
  (display (denom x)))

现在就可以试验我们的有理数过程了：

(define one-half (make-rat 1 2))
(print-rat one-half)
1/2
(define one-third (make-rat 1 3))
(print-rat (add-rat one-half one-third))
5/6
(print-rat (mul-rat one-half one-third))
1/6
(print-rat (add-rat one-third one-third))
6/9

正如上面最后一个例子所显示的，我们的有理数实现并没有将有理数约化到最简形式。通过修改make-rat很容易做到这件事。如果我们有了一个如1.2.5节中那样的gcd过程，用它可以求出两个整数的最大公约数，那么现在就可以利用它，在构造序对之前将分子和分母约化为最简单的项：

(define (make-rat n d)
  (let ((g (gcd n d)))
    (cons (/ n g) (/ d g))))

现在我们就有：

(print-rat (add-rat one-third one-third))
2/3

正如所期望的。为了完成这一改动，我们只需修改构造符make-rat，完全不必修改任何实现实际运算的过程（例如add-rat和mul-rat）。
练习2.1 请定义出make-rat的一个更好的版本，使之可以正确处理正数和负数。当有理数为正时，make-rat应当将其规范化，使它的分子和分母都是正的。如果有理数为负，那么就应只让分子为负。

2.1.2 抽象屏障

在继续讨论更多复合数据和数据抽象的实例之前，让我们首先考虑一下由有理数的例子提出的几个问题。前面给出的所有有理数操作，都是基于构造函数make-rat和选择函数numer、denom定义出来的。一般而言，数据抽象的基本思想就是为每一类数据对象标识出一组操作，使得对这类数据对象的所有操作都可以基于它们表述，而且在操作这些数据对象时也只使用它们。
图2-1形象化地表示了有理数系统的结构。其中的水平线表示抽象屏障，它们隔离了系统中不同的层次。在每一层上，这种屏障都把使用数据抽象的程序（上面）与实现数据抽象的程序（下面）分开来。使用有理数的程序将仅仅通过有理数包提供给“公众使用”的那些过程（add-rat、sub-rat、mul-rat、div-rat和equal-rat?）去完成对有理数的各种操作；这些过程转而又是完全基于构造函数和选择函数make-rat、numer和denom实现的；而这些函数又是基于序对实现的。只要序对可以通过cons、car和cdr操作，有关序对如何实现的细节与有理数包的其余部分都完全没有关系。从作用上看，每一层次中的过程构成了所定义的抽象屏障的界面，联系起系统中的不同层次。

这一简单思想有许多优点。第一个优点是这种方法使程序很容易维护和修改。任意一种比较复杂的数据结构，都可以以多种不同方式用程序设计语言所提供的基本数据结构表示。当然，表示方式的选择会对操作它的程序产生影响，这样，如果后来表示方式改变了，所有受影响的程序也都需要随之改变。对于大型程序而言，这种工作将非常耗时，而且代价极其昂贵，除非在设计时就已经将依赖于表示的成分限制到很少的一些程序模块上。
例如，将有理数约化到最简形式的工作，也完全可以不在构造的时候做，而是在每次访问有理数中有关部分时去做。这样就会导致另一套不同的构造函数和选择函数：

(define (make-rat n d)
  (cons n d))
(define (numer x)
  (let ((g (gcd (car x) (cdr x))))
    (/ (car x) g)))
(define (denom x)
  (let ((g (gcd (car x) (cdr x))))
    (/ (cdr x) g)))

这一实现与前面实现的不同之处在于何时计算gcd。如果在有理数的典型使用中，我们需要多次访问同一个有理数的分子和分母，那么最好是在构造有理数的时候计算gcd。如果情况并不是这样，那么把对gcd的计算推迟到访问时也许更好一些。在这里，在任何情况下，当我们从一种表示方式转到另一种表示时，过程add-rat、sub-rat等等都完全不必修改。
把对于具体表示方式的依赖性限制到少数几个界面过程，不但对修改程序有帮助，同时也有助于程序的设计，因为这种做法将使我们能保留考虑不同实现方式的灵活性。继续前面的简单例子，假定现在我们正在设计有理数程序包，而且还无法决定究竟是在创建时执行gcd，还是应该将它推迟到选择的时候。数据抽象方法使我们能推迟决策的时间，而又不会阻碍系统其他部分的工作进展。
练习2.2 请考虑平面上线段的表示问题。一个线段用一对点表示，它们分别是线段的始点与终点。请定义构造函数make-segment和选择函数start-segment、end-segment，它们基于点定义线段的表示。进而，一个点可以用数的序对表示，序对的两个成分分别表示点的x坐标和y坐标。请据此进一步给出构造函数make-point和选择函数x-point、y-point，用它们定义出点的这种表示。最后，请基于所定义的构造函数和选择函数，定义出过程midpoint-segment，它以一个线段为参数，返回线段的中点（也就是那个坐标值是两个端点的平均值的点）。为了试验这些过程，还需要定义一种打印点的方法：

(define (print-point p)
  (newline)
  (display "(")
  (display (x-point p))
  (display ",")
  (display (y-point p))
  (display ")"))

练习2.3 请实现一种平面矩形的表示（提示：你有可能借用练习2.2的结果）。基于你的构造函数和选择函数定义几个过程，计算给定矩形的周长和面积等。现在请再为矩形实现另一种表示方式。你应该怎样设计系统，使之能提供适当的抽象屏障，使同一个周长或者面积过程对两种不同表示都能工作？

2.1.3 数据意味着什么

在2.1.1节里实现有理数时，我们基于三个尚未定义的过程make-rat、numer和denom，由这些出发去做有理数操作add-rat、sub-rat等等的实现。按照那时的想法，这些操作是基于数据对象（分子、分母、有理数）定义的，这些对象的行为完全由前面三个过程刻画。
那么，数据究竟意味着什么呢？说它就是“由给定的构造函数和选择函数所实现的东西”还是不够的。显然，并不是任意的三个过程都适合作为有理数实现的基础。在这里，我们需要保证，如果从一对整数n和d构造出一个有理数x，那么，抽取出x的numer和denom并将它们相除，得到的结果应该与n除以d相同。换句话说，make-rat、numer和denom必须满足下面条件，对任意整数n和任意非零整数d，如果x是（make-rat n d），那么：

事实上，这就是为了能成为适宜表示有理数的基础，make-rat、numer和denom必须满足的全部条件。一般而言，我们总可以将数据定义为一组适当的选择函数和构造函数，以及为使这些过程成为一套合法表示，它们就必须满足的一组特定条件。
这一观点不仅可以服务于“高层”数据对象的定义，例如有理数，同样也可用于低层的对象。请考虑序对的概念，我们在前面用它定义有理数。我们从来都没有说过序对究竟是什么，只说所用的语言为序对的操作提供了三个过程cons、car和cdr。有关这三个操作，我们需要知道的全部东西就是，如果用cons将两个对象粘接到一起，那么就可以借助于car和cdr提取出这两个对象。也就是说，这些操作满足的条件是：对任何对象x和y，如果z是（cons x y），那么（car z）就是x，而（cdr z）就是y。我们确实说过这三个过程是所用的语言里的基本过程。然而，任何能满足上述条件的三个过程都可以成为实现序对的基础。下面这个令人吃惊的事实能够最好地说明这一点：我们完全可以不用任何数据结构，只使用过程就可以实现序对。下面是有关的定义：

(define (cons x y)
  (define (dispatch m)
    (cond ((= m 0) x)
          ((= m 1) y)
          (else (error "Argument not 0 or 1 -- CONS" m))))
  dispatch)
(define (car z) (z 0))
(define (cdr z) (z 1))

过程的这一使用方式与我们有关数据应该是什么的直观认识大相径庭。但不管怎么说，如果要求我们说明这确实是一种表示序对的合法方式，那么只需要验证，上述几个过程满足了前面提出的所有条件。
应该特别注意这里的一个微妙之处：由（cons x y）返回的值是一个过程—也就是那个内部定义的过程dispatch，它有一个参数，并能根据参数是0还是1，分别返回x或者y。与此相对应，（car z）被定义为将z应用于0，这样，如果z是由（cons x y）形成的过程，将z应用于0将会产生x，这样就证明了（car（cons x y））产生出x，正如我们所需要的。与此类似，（cdr（cons x y））将（cons x y）产生的过程应用于1而得到y。因此，序对的这一过程实现确实是一个合法的实现，如果只通过cons、car和cdr访问序对，我们将无法把这一实现与“真正的”数据结构区分开。
上面展示了序对的一种过程性表示，这并不意味着我们所用的语言就是这样做的（Scheme和一般的Lisp系统都直接实现序对，主要是为了效率），而是说它确实可以这样做。这一过程性表示虽然有些隐晦，但它确实是一种完全合适的表示序对的方式，因为它满足了序对需要满足的所有条件。这一实例也说明可以将过程作为对象去操作，因此就自动地为我们提供了一种表示复合数据的能力。这些东西现在看起来好像只是很好玩，但实际上，数据的过程性表示将在我们的程序设计宝库里扮演一种核心角色。有关的程序设计风格通常称为消息传递。在第3章里讨论模型和模拟时，我们将用它作为一种基本工具。
练习2.4 下面是序对的另一种过程性表示方式。请针对这一表示验证，对于任意的x和y，（car（cons x y））都将产生出x。

(define (cons x y)
  (lambda (m) (m x y)))
(define (car z)
  (z (lambda (p q) p)))

对应的cdr应该如何定义？（提示：为了验证这一表示确实能行，请利用1.1.5节的代换模型。）
练习2.5 请证明，如果将a和b的序对表示为乘积2a 3b对应的整数，我们就可以只用非负整数和算术运算表示序对。请给出对应的过程cons、car和cdr的定义。
练习2.6 如果觉得将序对表示为过程还不足以令人如雷灌顶，那么请考虑，在一个可以对过程做各种操作的语言里，我们完全可以没有数（至少在只考虑非负整数的情况下），可以将0和加一操作实现为：

(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

这一表示形式称为Church计数，名字来源于其发明人数理逻辑学家Alonzo Church（丘奇），l演算也是他发明的。
请直接定义one和two（不用zero和add-1）（提示：利用代换去求值（add-1 zero））。请给出加法过程＋的一个直接定义（不要通过反复应用add-1）。

2.1.4 扩展练习：区间算术

Alyssa P. Hacker正在设计一个帮助人们求解工程问题的系统。她希望这个系统提供的一个特征是能够去操作不准确的量（例如物理设备的测量参数），这种量具有已知的精度，所以，在对这种近似量进行计算时，得到的结果也应该是已知精度的数值。
电子工程师将会用Alyssa的系统去计算一些电子量。有时他们必须使用下面公式，从两个电阻R1和R2计算出并联等价电阻Rp的值：

此时所知的电阻值通常是由电阻生产厂商给出的带误差保证的值，例如你可能买到一支标明“6.8欧姆误差10%”的电阻，这时我们就只能确定，这支电阻的阻值在6.8－0.68＝6.12和6.8＋0.68＝7.48欧姆之间。这样，如果将一支6.8欧姆误差10%的电阻与另一支4.7欧姆误差5%的电阻并联，这一组合的电阻值可以在大约2.58欧姆（如果两支电阻都有最小值）和2.97欧姆（如果两支电阻都是最大值）之间。
Alyssa的想法是实现一套“区间算术”，即作为可以用于组合“区间”（表示某种不准确量的可能值的对象）的一组算术运算。两个区间的加、减、乘、除的结果仍是一个区间，表示的是计算结果的范围。
Alyssa假设有一种称为“区间”的抽象对象，这种对象有两个端点，一个下界和一个上界。她还假定，给了一个区间的两个端点，就可以用数据构造函数make-interval构造出相应的区间来。Alyssa首先写出了一个做区间加法的过程，她推理说，和的最小值应该是两个区间的下界之和，其最大值应该是两个区间的上界之和：

(define (add-interval x y)
  (make-interval (+ (lower-bound x) (lower-bound y))
                 (+ (upper-bound x) (upper-bound y))))

Alyssa还找出了这种界的乘积的最小和最大值，用它们做出了两个区间的乘积（min和max是求出任意多个参数中的最小值和最大值的基本过程）。

(define (mul-interval x y)
  (let ((p1 (* (lower-bound x) (lower-bound y)))
        (p2 (* (lower-bound x) (upper-bound y)))
        (p3 (* (upper-bound x) (lower-bound y)))
        (p4 (* (upper-bound x) (upper-bound y))))
    (make-interval (min p1 p2 p3 p4)
                   (max p1 p2 p3 p4))))

为了做出两个区间的除法，Alyssa用第一个区间乘上第二个区间的倒数。请注意，倒数的两个界限分别是原来区间的上界的倒数和下界的倒数：

(define (div-interval x y)
  (mul-interval x 
                (make-interval (/ 1.0 (upper-bound y))
                               (/ 1.0 (lower-bound y)))))

练习2.7 Alyssa的程序是不完整的，因为她还没有确定区间抽象的实现。这里是区间构造符的定义：

(define (make-interval a b) (cons a b))

请定义选择符upper-bound和lower-bound，完成这一实现。
练习2.8 通过类似于Alyssa的推理，说明两个区间的差应该怎样计算。请定义出相应的减法过程sub-interval。
练习2.9 区间的宽度就是其上界和下界之差的一半。区间宽度是有关区间所描述的相应数值的非确定性的一种度量。对于某些算术运算，两个区间的组合结果的宽度就是参数区间的宽度的函数，而对其他运算，组合区间的宽度则不是参数区间宽度的函数。证明两个区间的和（与差）的宽度就是被加（或减）的区间的宽度的函数。举例说明，对于乘和除而言，情况并非如此。
练习2.10 Ben Bitdiddle是个专业程序员，他看了Alyssa工作后评论说，除以一个跨过横跨0的区间的意义不清楚。请修改Alyssa的代码，检查这种情况并在出现这一情况时报错。
练习2.11 在看了这些东西之后，Ben又说出了下面这段有些神秘的话：“通过监测区间的端点，有可能将mul-interval分解为9种情况，每种情况中所需的乘法都不超过两次。”请根据Ben的建议重写这个过程。
在排除了自己程序里的错误之后，Alyssa给一个可能用户演示自己的程序。那个用户却说她的程序解决的问题根本不对。他希望能够有一个程序，可以用于处理那种用一个中间值和一个附加误差的形式表示的数，也就是说，希望程序能处理3.5±0.15而不是[3.35，3.65]。Alyssa回到自己的办公桌来纠正这一问题，另外提供了一个构造符和一个选择符：

(define (make-center-width c w)
  (make-interval (- c w) (+ c w)))
(define (center i)
  (/ (+ (lower-bound i) (upper-bound i)) 2))
(define (width i)
  (/ (- (upper-bound i) (lower-bound i)) 2))

不幸的是，Alyssa的大部分用户是工程师，现实中的工程师经常遇到只有很小非准确性的测量值，而且常常是以区间宽度对区间中点的比值作为度量值。他们通常用的是基于有关部件的参数的百分数描述的误差，就像前面描述电阻值的那种方式一样。
练习2.12 请定义一个构造函数make-center-percent，它以一个中心点和一个百分比为参数，产生出所需要的区间。你还需要定义选择函数percent，通过它可以得到给定区间的百分数误差，选择函数center与前面定义的一样。
练习2.13 请证明，在误差为很小的百分数的条件下，存在着一个简单公式，利用它可以从两个被乘区间的误差算出乘积的百分数误差值。你可以假定所有的数为正，以简化这一问题。
经过相当多的工作之后，Alyssa P. Hacker发布了她的最后系统。几年之后，在她已经忘记了这个系统之后，接到了一个愤怒的用户Lem E. Tweakit的发疯式的电话。看起来Lem注意到并联电阻的公式可以写成两个代数上等价的公式：

和

这样他就写了两个程序，它们以不同的方式计算并联电阻值：

(define (par1 r1 r2)
  (div-interval (mul-interval r1 r2)
                (add-interval r1 r2)))
(define (par2 r1 r2)
  (let ((one (make-interval 1 1))) 
    (div-interval one
                  (add-interval (div-interval one r1)
                                (div-interval one r2)))))

Lem抱怨说，Alyssa程序对两种不同计算方法给出不同的值。这确实是很严重的抱怨。
练习2.14 请确认Lem是对的。请你用各种不同的算术表达式来检查这一系统的行为。请做出两个区间A和B，并用它们计算表达式A/A和A/B。如果所用区间的宽度相对于中心值取很小百分数，你将会得到更多的认识。请检查对于中心－百分比形式（见练习2.12）进行计算的结果。
练习2.15 另一用户Eva Lu Ator也注意到了由不同的等价代数表达式计算出的区间的差异。她说，如果一个公式可以写成一种形式，其中具有非准确性的变量不重复出现，那么Alyssa的系统产生出的区间的限界更紧一些。她说，因此，在计算并联电阻时，par2是比par1“更好的”程序。她说得对吗？
练习2.16 请给出一个一般性的解释：为什么等价的代数表达式可能导致不同计算结果？你能设计出一个区间算术包，使之没有这种缺陷吗？或者这件事情根本不可能做到？（警告：这个问题非常难。）

2.2 层次性数据和闭包性质

正如在前面已经看到的，序对为我们提供了一种用于构造复合数据的基本“黏结剂”。图2-2展示的是一种以形象的形式看序对的标准方式，其中的序对是通过（cons 1 2）形成的。在这种称为盒子和指针表示方式中，每个对象表示为一个指向盒子的指针。与基本对象相对应的盒子里包含着该对象的表示，例如，表示数的盒子里就放着那个具体的数。用于表示序对的盒子实际上是一对方盒，其中左边的方盒里放着序对的car（指向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 1
      (cons 2
            (cons 3
                  (cons 4 nil))))

通过嵌套的cons形成的这样一个序对的序列称为一个表，Scheme为方便表的构造，提供了一个基本操作list74，上面序列也可以通过（list 1 2 3 4）产生。一般说：

(list <a1> <a2> ... <an>)

等价于：

(cons <a1> (cons <a2> (cons ... (cons <an> nil) ...)))

Lisp系统通常用元素序列的形式打印出表，外面用括号括起。按照这种方式，图2-4里的数据对象就将打印为（1 2 3 4）：

(define one-through-four (list 1 2 3 4))
one-through-four
(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)

nil的值用于表示序对的链结束，它也可以当作一个不包含任何元素的序列，空表。单词“nil”是拉丁词汇“nihil”的缩写，这个拉丁词汇表示“什么也没有”。

表操作
利用序对将元素的序列表示为表之后，我们就可以使用常规的程序设计技术，通过顺序“向下cdr”表的方式完成对表的各种操作了。例如，下面的过程list-ref的实际参数是一个表和一个数n，它返回这个表中的第n个项。这里人们习惯令表元素的编号从0开始。计算list-ref的方法如下：

• 对n＝0，list-ref应返回表的car。
• 否则，list-ref返回表的cdr的第（n－1）个项。

(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

过程length实现一种简单的递归方案，其中的递归步骤是：

• 任意一个表的length就是这个表的cdr的length加一。

顺序地这样应用，直至达到了基础情况：

• 空表的length是0。

我们也可以用一种迭代方式来计算length：

(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，按如下方式做：

• 如果list1是空表，结果就是list2。
• 否则应先做出list1的cdr和list2的append，而后再将list1的car通过cons加到结果的前面：

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

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

(last-pair (list 23 72 149 34))
(34)

练习2.18 请定义出过程reverse，它以一个表为参数，返回的表中所包含的元素与参数表相同，但排列顺序与参数表相反：

(reverse (list 1 4 9 16 25))
(25 16 9 4 1)

练习2.19 请考虑1.2.2节的兑换零钱方式计数程序。如果能够轻而易举地改变程序里所用的兑换币种就更好了。譬如说，那样我们就能计算出1英镑的不同兑换方式的数目。在写前面那个程序时，有关币种的知识中有一部分出现在过程first-denomination里，另一部分出现在过程里count-change（它知道有5种U.S.硬币）。如果能够用一个表来提供可用于兑换的硬币就更好了。
我们希望重写出过程cc，使其第二个参数是一个可用硬币的币值表，而不是一个指定可用硬币种类的整数。而后我们就可以针对各种货币定义出一些表：

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

然后我们就可以通过如下方式调用cc：

(cc 100 us-coins)
292

为了做到这件事，我们需要对程序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。在一个过程定义中，如果在形式参数表的最后一个参数之前有一个点号，那就表明，当这一过程被实际调用时，前面各个形式参数（如果有的话）将以前面的各个实际参数为值，与平常一样。但最后一个形式参数将以所有剩下的实际参数的表为值。例如，假若我们定义了：

(define (f x y . z) <body>)

过程f就可以用两个以上的参数调用。如果求值：

(f 1 2 3 4 5 6)

那么在f的体里，x将是1，y将是2，而z将是表（3 4 5 6）。给了定义：

(define (g . w) <body>)

过程g可以用0个或多个参数调用。如果求值：

(g 1 2 3 4 5 6)

那么在g的体里，w将是表（1 2 3 4 5 6）。
请采用这种记法形式写出过程same-parity，它以一个或者多个整数为参数，返回所有与其第一个参数有着同样奇偶性的参数形成的表。例如：

(same-parity 1 2 3 4 5 6 7)
(1 3 5 7)
(same-parity 2 3 4 5 6 7)
(2 4 6)

对表的映射
一个特别有用的操作是将某种变换应用于一个表的所有元素，得到所有结果构成的表。举例来说，下面过程将一个表里的所有元素按给定因子做一次缩放：

(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，它有一个过程参数和一个表参数，返回将这一过程应用于表中各个元素得到的结果形成的表。

(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的一个新定义：

(define (scale-list items factor)
  (map (lambda (x) (* x factor))
       items))

map是一种很重要的结构，不仅因为它代表了一种公共模式，而且因为它建立起了一种处理表的高层抽象。在scale-list原来的定义里，程序的递归结构将人的注意力吸引到对于表中逐个元素的处理上。通过map定义scale-list抑制了这种细节层面上的情况，强调的是从元素表到结果表的一个缩放变换。这两种定义形式之间的差异，并不在于计算机会执行不同的计算过程（其实不会），而在于我们对这同一个过程的不同思考方式。从作用上看，map帮我们建起了一层抽象屏障，将实现表变换的过程的实现，与如何提取表中元素以及组合结果的细节隔离开。与图2-1里所示的屏障类似，这种抽象也提供了新的灵活性，使我们有可能在保持从序列到序列的变换操作框架的同时，改变序列实现的低层细节。2.2.3节将把序列的这种使用方式扩展为一种组织程序的框架。
练习2.21 过程square-list以一个数值表为参数，返回每个数的平方构成的表：

(square-list (list 1 2 3 4))
(1 4 9 16)

下面是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产生出的结果表中，元素的顺序正好与我们所需要的相反。为什么？
Louis又试着修正其程序，交换了cons的参数：

(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 (lambda (x) (newline) (display x))
          (list 57 321 88))
57
321
88

由for-each的调用返回的值（上面没有显示）可以是某种任意的东西，例如逻辑值真。请给出一个for-each的实现。

2.2.2 层次性结构

将表作为序列的表示方式，可以很自然地推广到表示那些元素本身也是序列的序列。举例来说，我们可以认为对象（（1 2）3 4）是通过下面方式构造出来的：

(cons (list 1 2) (list 3 4))

这是一个包含三个项的表，其中的第一项本身又是表（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

为了实现count-leaves，可以先回忆一下length的递归方案：

• 表x的length是x的cdr的length加一。
• 空表的length是0。

count-leaves的递归方案与此类似，对于空表的值也相同：

• 空表的count-leaves是0，

但是在递归步骤中，当我们去掉一个表的car时，就必须注意这一car本身也可能是树，其树叶也需要考虑。这样，正确的归约步骤应该是：

• 对于树x的count-leaves应该是x的car的count-leaves与x的cdr的count-leaves之和。

最后，在通过car达到一个实际的树叶时，我们还需要另一种基本情况：

• 一个树叶的count-leaves是1。

为了有助于写出树上的各种递归，Scheme提供了基本过程pair?，它检查其参数是否为序对。下面就是我们完成的过程79：

(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组合：

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

练习2.26 假定已将x和y定义为如下的两个表：

(define x (list 1 2 3))
(define y (list 4 5 6))

解释器对于下面各个表达式将打印出什么结果：

(append x y)
(cons x y)
(list x y)

练习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）：

(define (make-mobile left right)
  (list left right))

分支可以从一个length（它应该是一个数）再加上一个structure构造出来，这个structure或者是一个数（表示一个简单重量），或者是另一个活动体：

(define (make-branch length structure)
  (list length structure))

a) 请写出相应的选择函数left-branch和right-branch，它们分别返回活动体的两个分支。还有branch-length和branch-structure，它们返回一个分支上的成分。
b) 用你的选择函数定义过程total-weight，它返回一个活动体的总重量。
c) 一个活动体称为是平衡的，如果其左分支的力矩等于其右分支的力矩（也就是说，如果其左杆的长度乘以吊在杆上的重量，等于这个活动体右边的同样乘积），而且在其每个分支上吊着的子活动体也都平衡。请设计一个过程，它能检查一个二叉活动体是否平衡。
d) 假定我们改变活动体的表示，采用下面构造方式：

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

你需要对自己的程序做多少修改，才能将它改为使用这种新表示？

对树的映射
map是处理序列的一种强有力抽象，与此类似，map与递归的结合也是处理树的一种强有力抽象。举例来说，可以有与2.2.1节的scale-list类似的scale-tree过程，以一个数值因子和一棵叶子为数值的树作为参数，返回一棵具有同样形状的树，树中的每个数值都乘以了这个因子。对于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 请定义一个与练习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做出的解答进一步抽象，做出一个过程，使它的性质保证能以下面形式定义square-tree：

(define (square-tree tree) (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))

虽然这两个过程在结构上差异非常大，但是对于两个计算的抽象描述却会揭示出它们之间极大的相似性。第一个程序：

• 枚举出一棵树的树叶；
• 过滤它们，选出其中的奇数；
• 对选出的每一个数求平方；
• 用＋累积起得到的结果，从0开始。

而第二个程序：

• 枚举从0到n的整数；
• 对每个整数计算相应的斐波那契数；
• 过滤它们，选出其中的偶数；
• 用cons累积得到的结果，从空表开始。

信号处理工程师们可能会发现，这种过程可以很自然地用流过一些级联的处理步骤的信号的方式描述，其中的每个处理步骤实现程序方案中的一个部分，如图2-7所示。对于第一种情况sum-odd-squares，我们从一个枚举器开始，它产生出由给定的树的所有树叶组成“信号”。这一信号流过一个过滤器，所有不是奇数的数都被删除了。这样得到的信号又通过一个映射，这是一个“转换装置”，它将square过程应用于每个元素。这一映射的输出被馈入一个累积器，该装置用＋将得到的所有元素组合起来，以初始的0开始。even-fibs的工作过程与此类似。

遗憾的是，上面的两个过程定义并没有展现出这种信号流结构。譬如说，如果仔细考察sum-odd-squares过程，就会发现其中的枚举工作部分地由检查null?和pair?实现，部分地由过程的树形递归结构实现。与此类似，在那些检查中也可以看到一部分累积工作，另一部分是用在递归中的加法。一般而言，在这两个过程里，没有一个部分正好对应于信号流描述中的某一要素。我们的两个过程采用不同的方式分解了这个计算，将枚举工作散布在程序中各处，并将它与映射、过滤器和累积器混在一起。如果我们能够重新组织这一程序，使得信号流结构明显表现在写出的过程中，将会大大提高结果代码的清晰性。

序列操作
要组织好这些程序，使之能够更清晰地反映上面信号流的结构，最关键的一点就是将注意力集中在处理过程中从一个步骤流向下一个步骤的“信号”。如果我们用一些表来表示这些信号，那么就可以利用表操作实现每一步骤的处理。举例来说，我们可以用2.2.1节的map过程实现信号流图中的映射步骤：

(map square (list 1 2 3 4 5))
(1 4 9 16 25)

过滤一个序列，也就是选出其中满足某个给定谓词的元素，可以按下面方式做：

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

例如，

(filter odd? (list 1 2 3 4 5))
(1 3 5)

累积工作可以实现如下：

(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)

要枚举出一棵树的所有树叶，则可以用80：

(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的值，也可以形式化为一种累积。假定需要求下面多项式的值：

anxn＋an－1xn－1＋…＋a1x＋a0

采用著名的Horner规则，可以构造出下面的计算：

(… (anx＋an－1) x＋…＋a1) x＋a0

换句话说，我们可以从an开始，乘以x，再加上an－1，乘以x，如此下去，直到处理完a0^82。请填充下面的模板，做出一个利用Horner规则求多项式值的过程。假定多项式的系数安排在一个序列里，从a0直至an。

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

例如，为了计算1＋3x＋5x^3＋x^5在x＝2的值，你需要求值：

(horner-eval 2 (list 1 3 0 5 0 1))

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

(define (count-leaves t)
  (accumulate <??> <??> (map <??> <??>)))

练习2.36 过程accumulate-n与accumulate类似，除了它的第三个参数是一个序列的序列，假定其中每个序列的元素个数相同。它用指定的累积过程去组合起所有序列的第一个元素，而后是所有序列的第二个元素，并如此做下去，返回得到的所有结果的序列。例如，如果s是包含着4个序列的序列（（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＝(vi) 表示为数的序列，将矩阵m＝(mij) 表示为向量（矩阵行）的序列。例如，矩阵：

用序列（（1 2 3 4）（4 5 6 6）（6 7 8 9））表示。对于这种表示，我们可以用序列操作简洁地表达基本的矩阵与向量运算。这些运算（任何有关矩阵代数的书里都有描述）如下：

(dot-product v w)      返回和穒viwi;
(matrix-*-vector m v)  返回向量 t，其中ti＝穓mijvj;
(matrix-*-matrix m n)  返回矩阵 p，其中pij＝穔miknkj;
(transpose m)          返回矩阵 n，其中nij＝mji.

我们可以将点积（dot product）定义为：

(define (dot-product v w)
  (accumulate + 0 (map * v w)))

请填充下面过程里缺失的表达式，它们计算出其他的矩阵运算结果（过程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对任何序列都产生同样的结果，请给出op应该满足的性质。
练习2.39 基于练习2.38的fold-right和fold-left完成reverse（练习2.18）下面的定义：

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

嵌套映射
我们可以扩充序列范型，将许多通常用嵌套循环表述的计算也包含进来84。现在考虑下面的问题：给定了自然数n，找出所有不同的有序对i和j，其中1≤j＜i≤n，使得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 (flatmap proc seq)
  (accumulate append nil (map proc seq)))

现在可以过滤这一序对的序列，找出那些和为素数的序对。对序列里的每个元素调用过滤谓词。由于这个谓词的参数是一个序对，所以它必须将两个整数从序对里提取出来。这样，作用到序列中每个元素上的谓词就是：

(define (prime-sum? pair)
  (prime? (+ (car pair) (cadr pair))))

最后还要生成出结果的序列，为此只需将下面过程映射到通过过滤后的序对上，对每个有序对里的两个元素，这一过程生成出一个包含了它们的和的三元组：

(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的所有排列的序列86，而后将x加到每个序列的前面。这样就能对S里的每个x，产生出了S的所有以x开头的排列。将对所有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，它产生出序对 (i, j)，其中1≤j＜i≤n。请用unique-pairs去简化上面prime-sum-pairs的定义。
练习2.41 请写出一个过程，它能产生出所有小于等于给定整数n的正的相异整数i、j和k的有序三元组，使每个三元组的三个元之和等于给定的整数s。
练习2.42 “八皇后谜题”问的是怎样将八个皇后摆在国际象棋盘上，使得任意一个皇后都不能攻击另一个皇后（也就是说，任意两个皇后都不在同一行、同一列或者同一对角线上）。一个可能的解如图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))

请解释一下，为什么这样交换顺序会使程序运行得非常慢。估计一下，用Louis的程序去解决八皇后问题大约需要多少时间，假定练习2.42中的程序需用时间T求解这一难题。

2.2.4 实例：一个图形语言

本节将介绍一种用于画图形的简单语言，以展示数据抽象和闭包的威力，其中也以一种非常本质的方式使用了高阶过程。这一语言的设计就是为了很容易地做出一些模式，例如图2-9中所示的那类图形，它们是由某些元素的重复出现而构成的，这些元素可以变形或者改变大小。在这个语言里，数据元素的组合都用过程表示，而不是用表结构表示。就像cons满足一种闭包性质，使我们能构造出任意复杂的表结构一样，这一语言中的操作也满足闭包性质，使我们很容易构造出任意复杂的模式。

图形语言
在1.1节里开始研究程序设计时我们就强调说，在描述一种语言时，应该将注意力集中到语言的基本原语、它的组合手段以及它的抽象手段，这是最重要的。这里的工作也将按照同样的框架进行。
这一图形语言的优美之处，部分就在于语言中只有一种元素，称为画家（painter）。一个画家将画出一个图像，这种图像可以变形或者改变大小，以便能正好放到某个指定的平行四边形框架里。举例来说，这里有一个称为wave的基本画家，它能做出如图2-10所示的折线画，而所做出图画的实际形状依赖于具体的框架—图2-10里的四个图像都是由同一个画家wave产生的，但却是相对于四个不同的框架。有些画家比它更精妙：称为rogers的基本画家能画出MIT的创始人William Barton Rogers的画像，如图2-11所示89。图2-11里的四个图像是相对于与图2-10中wave形象同样的四个框架画出来的。

为了组合起有关的图像，我们要用一些可以从给定画家构造出新画家的操作。例如，操作beside从两个画家出发，产生一个复合型画家，它将第一个画家的图像画在框架中左边的一半里，将第二个画家的图像画在框架里右边一半里。与此类似，below从两个画家出发产生一个组合型画家，将第一个画家的图像画在第二个画家的图像之下。有些操作将一个画家转换为另一个新画家。例如，flip-vert从一个画家出发，产生一个将该画家所画图像上下颠倒画出的画家，而flip-horiz产生的画家将原画家的图像左右反转后画出。
图2-12说明了从wave出发，经过两步做出一个名为wave4的画家的方式：

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

在按这种方法构造复杂的图像时，我们利用了一个事实：画家在有关语言的组合方式下是封闭的：两个画家的beside或者below还是画家，因此还可以用它们作为元素去构造更复杂的画家。就像用cons构造起各种表结构一样，我们所用的数据在组合方式下的闭包性质非常重要，因为这使我们能用不多几个操作构造出各种复杂的结构。
一旦能做画家的组合之后，我们就希望能抽象出典型的画家组合模式，以便将这种组合操作实现为一些Scheme过程。这也意味着我们并不需要这种图形语言里包含任何特殊的抽象机制，因为组合的方式就是采用普通的Scheme过程。这样，对于画家，我们就自动有了能够做原来可以对过程做的所有事情。例如，我们可以将wave4中的模式抽象出来：

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

并将wave4重新定义为这种模式的实例：

(define wave4 (flipped-pairs wave))

我们也可以定义递归操作。下面就是一个这样的操作，它在图形的右边做分割和分支，就像在图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)))))

通过同时在图形中向上和向右分支，我们可以产生出一种平衡的模式（见练习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))))))

将某个corner-split的4个拷贝适当地组合起来，我们就可以得到一种称为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))))

操作flipped-pairs可以基于square-of-four定义如下90：

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

而square-limit可以描述为：

(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) 映射到下面的向量和：

Origin (Frame)＋x·Edge1 (Frame)＋y·Edge2 (Frame)

例如，点 (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应用于一个框架的结果是返回了一个过程，它对于每个给定的向量返回另一个向量。如果参数向量位于单位正方形里，得到的对应结果向量也将位于相应的框架里。例如：

((frame-coord-map a-frame) (make-vect 0 0))

返回的向量如下：

(origin-frame a-frame)

练习2.46 从原点出发的一个二维向量v可以用一个由x坐标和y坐标构成的序对表示。请为这样的向量实现一个数据抽象：给出一个构造函数make-vect，以及对应的选择函数xcor-vect和ycor-vect。借助于你给出的构造函数和选择函数，实现过程add-vect、sub-vect和scale-vect，它们能完成向量加法、向量减法和向量的伸缩。

(x1，y1)＋(x2，y2)＝(x1＋x2，y1＋y2)
(x1，y1)－(x2，y2)＝(x1－x2，y1－y2)
                                                             s·(x，y)＝(sx，sy)

练习2.47 下面是实现框架的两个可能的过程函数：

(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。
练习2.49 利用segments->painter定义下面的基本画家：
a) 画出给定框架边界的画家。
b) 通过连接框架两对角画出一个大叉子的画家。
c) 通过连接框架各边的中点画出一个菱形的画家。
d) 画家wave。

画家的变换和组合
各种对画家的操作（例如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)))

另一个变换将图形按照逆时针方向旋转90度：

(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）完成有关工作。

强健设计的语言层次
在上述的图形语言中，我们演习了前面介绍的有关过程和数据抽象的关键思想。其中的基本数据抽象和画家都用过程表示实现，这就使该语言能以一种统一方式去处理各种本质上完全不同的画图能力。实现组合的方法也满足闭包性质，使我们很容易构造起各种复杂的设计。最后，用于做过程抽象的所有工具，现在也都可用作组合画家的抽象手段。
我们也对程序设计的另一个关键概念有了一点认识，这就是分层设计的问题。这一概念说的是，一个复杂的系统应该通过一系列的层次构造出来，为了描述这些层次，需要使用一系列的语言。构造各个层次的方式，就是设法组合起作为这一层次中部件的各种基本元素，而这样构造出的部件又可以作为另一个层次里的基本元素。在分层设计中，每个层次上所用的语言都提供了一些基本元素、组合手段，还有对该层次中的适当细节做抽象的手段。
在复杂系统的工程中广泛使用这种分层设计方法。例如，在计算机工程里，电阻和晶体管被组合起来（用模拟电路的语言），产生出一些部件，例如与门、或门等等；这些门电路又被作为数字电路设计的语言中的基本元素97。将这类部件组合起来，构成了处理器、总线和存储系统，随即，又通过它们的组合构造出各种计算机，此时采用的是适合于描述计算机体系结构的语言。计算机的组合可以进一步构成分布式系统，采用的是适合描述网络互联的语言。我们还可以这样做下去。
作为分层设计的一个小例子，我们的图形语言用了一些基本元素（基本画家），它们是基于描述点和直线的语言建立起来，为segments->painter提供线段表，或者为rogers之类提供着色能力。前面关于这一图形语言的描述，主要是集中在这些基本元素的组合方面，采用的是beside和below一类的几何组合手段。我们也在更高的层次上工作，将beside和below作为基本元素，在一个具有square-of-four一类操作的语言中处理它们，这些操作抓住了一些将几何组合手段组合起来的常见模式。
分层设计有助于使程序更加强健，也就是说，使我们更有可能在给定规范发生一些小改变时，只需对程序做少量的修改。例如，假定我们希望改变图2-9所示的基于wave的图像，我们就可以在最低的层次上工作，直接去修改wave元素的表现细节；也可以在中间层次上工作，改变corner-split里重复使用wave的方式；也可以在最高的层次上工作，改变对图形中各个角上4个副本的安排。一般来说，分层结构中的每个层次都为表述系统的特征提供了一套独特词汇，以及一套修改这一系统的方式。
练习2.52 在上面描述的各个层次上工作，修改图2-9中所示的方块的限制。特别是：
a) 给练习2.49的基本wave画家加入某些线段（例如，加上一个笑脸）。
b) 修改corner-split的构造模式（例如，只用up-split和right-split的图像的各一个副本，而不是两个）。
c) 修改square-limit，换一种使用square-of-four的方式，以另一种不同模式组合起各个角区（例如，你可以让大的Rogers先生从正方形的每个角向外看）。

2.3 符号数据

到目前为止，我们已经使用过的所有复合数据，最终都是从数值出发构造起来的。在这一节里，我们要扩充所用语言的表述能力，引进将任意符号作为数据的功能。

2.3.1 引号

如果我们能构造出采用符号的复合数据，我们就可以有下面这类的表：

(a b c d)
(23 45 17)
((Norah 12) (Molly 9) (Anna 7) (Lauren 6) (Charlotte 4))

这些包含着符号的表看起来就像是我们语言里的表达式：

(* (+ 23 45) (+ x 9))
(define (fact n) (if (= n 1) 1 (* n (fact (- n 1)))))

为了能够操作这些符号，我们的语言里就需要有一种新元素：为数据对象加引号的能力。假定我们希望构造出表（a b），当然不能用（list a b）完成这件事，因为这一表达式将要构造出的是a和b的值的表，而不是这两个符号本身的表。在自然语言的环境中，这种情况也是众所周知的，在那里的单词和句子可能看作语义实体，也可以看作是字符的序列（语法实体）。在自然语言里，常见的方式就是用引号表明一个词或者一个句子应作为文字看待，将它们直接作为字符的序列。例如说，“John”的第一个字母显然是“J”。如果我们对某人说“大声说你的名字”，此时希望听到的是那个人的名字。如果说“大声说‘你的名字’”，此时希望听到的就是词组“你的名字”。请注意，我们在这里不得不用嵌套的引号去描述别人应该说的东西。
我们可以按照同样的方式，将表和符号标记为应该作为数据对象看待，而不是作为应该求值的表达式。然而，这里所用的引号形式与自然语言中的不同，我们只在被引对象的前面放一个引号（按照习惯，在这里用单引号）。在Scheme里可以不写结束引号，因为这里已经靠空白和括号将对象分隔开，一个单引号的意义就是引用下一个对象。
现在我们就可以区分符号和它们的值了：

(define a 1)
(define b 2)
(list a b)
(1 2)
(list 'a 'b)
(a b)
(list 'a b)
(a 2)

引号也可以用于复合对象，其中采用的是表的方便的输出表示方式：

(car 'a b c))
a
(cdr 'a b c))
(b c)

记住这些之后，我们就可以通过求值 '() 得到空表，这样就可以丢掉变量nil了。
为了能对符号做各种操作，我们还需要用另一个基本过程eq?，这个过程以两个符号作为参数，检查它们是否为同样的符号。利用eq?可以实现一个称为memq的有用过程，它以一个符号和一个表为参数。如果这个符号不包含在这个表里（也就是说，它与表里的任何项目都不eq?），memq就返回假；否则就返回该表的由这个符号的第一次出现开始的那个子表：

(define (memq item x)
  (cond ((null? x) false)
        ((eq? item (car x)) x)
        (else (memq item (cdr x)))))

举例来说，表达式：

(memq 'apple '(pear banana prune))

的值是假，而表达式：

(memq 'apple '(x (apple sauce) y apple pear))

的值是（apple pear）。
练习2.53 解释器在求值下面各个表达式时将打印出什么？

(list 'a 'b 'c)
(list (list 'george))
(cdr '(x1 x2) (y1 y2)))
(cadr '(x1 x2) (y1 y2)))
(pair? (car ?a short list)))
(memq 'red '(red shoes) (blue socks)))
(memq 'red 'red shoes blue socks))

练习2.54** 如果两个表包含着同样元素，这些元素也按同样顺序排列，那么就称这两个表equal?。例如：
(equal? '(this is a list) '(this is a list))
是真；而
(equal? '(this is a list) '(this (is a) list))
是假。说得更准确些，我们可以从符号相等的基本eq?出发，以递归方式定义出equal?。a和b是equal?的，如果它们都是符号，而且这两个符号满足eq?；或者它们都是表，而且（car a）和（car b）相互equal?，它们的（cdr a）和（cdr b）也是equal?。请利用这一思路定义出equal?过程。
练习2.55 Eva Lu Ator输入了表达式：

(car ''abracadabra)

令她吃惊的是解释器打印出的是quote。请解释这一情况。

2.3.2 实例：符号求导

为了阐释符号操作的情况，并进一步阐释数据抽象的思想，现在考虑设计一个执行代数表达式的符号求导的过程。我们希望该过程以一个代数表达式和一个变量作为参数，返回这个表达式相对于该变量的导数。例如，如果送给这个过程的参数是ax2＋bx＋c和x，它应该返回2ax＋b。符号求导数对于Lisp有着特殊的历史意义，它正是推动人们去为符号操作开发计算机语言的重要实例之一。进一步说，它也是人们为符号数学工作开发强有力系统的研究领域的开端，今天已经有越来越多的应用数学家和物理学家们正在使用这类系统。
为了开发出一个符号计算程序，我们将按照2.1.1节开发有理数系统那样，采用同样的数据抽象策略。也就是说，首先定义一个求导算法，令它在一些抽象对象上操作，例如“和”、“乘积”和“变量”，并不考虑这些对象实际上如何表示，以后才去关心具体表示的问题。
对抽象数据的求导程序
为了使有关的讨论简单化，我们在这里考虑一个非常简单的符号求导程序，它处理的表达式都是由对于两个参数的加和乘运算构造起来的。对于这种表达式求导的工作可以通过下面几条归约规则完成：

可以看到，这里的最后两条规则具有递归的性质，也就是说，要想得到一个和式的导数，我们首先要找出其中各个项的导数，而后将它们相加。这里的每个项又可能是需要进一步分解的表达式。通过这种分解，我们能得到越来越小的片段，最终将产生出常量或者变量，它们的导数就是0或者1。
为了能在一个过程中体现这些规则，我们用一下按愿望思维，就像在前面设计有理数的实现时所做的那样。如果现在有了一种表示代数表达式的方式，我们一定能判断出某个表达式是否为一个和式、乘式、常量或者变量，也能提取出表达式里的各个部分。对于一个和式（举例来说），我们可能希望取得其被加项（第一个项）和加项（第二个项）。我们还需要能从几个部分出发构造出整个表达式。让我们假定现在已经有了一些过程，它们实现了下述的构造函数、选择函数和谓词：

(variable? e)     e是变量吗？
(same-variable? v1 v2)     v1和v2是同一个变量吗？
(sum? e)     e是和式吗？
(addend e)     e的被加数
(augend e)     e的加数
(make-sum a1 a2)     构造起a1与a2的和式
(product? e)     e是乘式吗？
(multiplier e)     e的被乘数
(multiplicand e)     e的乘数
(make-product m1 m2)     构造起m1与m2的乘式

利用这些过程，以及判断表达式是否数值的基本过程number?，我们就可以将各种求导规则用下面的过程表达出来了：

(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
           (make-product (multiplier exp)
                         (deriv (multiplicand exp) var))
           (make-product (deriv (multiplier exp) var)
                         (multiplicand exp))))
        (else
         (error "unknown expression type -- DERIV" exp))))

过程deriv里包含了一个完整的求导算法。因为它是基于抽象数据表述的，因此，无论我们如何选择代数表达式的具体表示，只要设计了一组正确的选择函数和构造函数，这个过程都可以工作。表示的问题是下面必须考虑的问题。

代数表达式的表示
我们可以设想出许多用表结构表示代数表达式的方法。例如，可以利用符号的表去直接反应代数的记法形式，将表达式ax＋b表示为表（a x ＋ b）。然而，一种特别直截了当的选择，是采用Lisp里面表示组合式的那种带括号的前缀形式，也就是说，将ax＋b表示为（＋ ( a x) b）。这样，我们有关求导问题的数据表示就是：

• 变量就是符号，它们可以用基本谓词symbol?判断：

(define (variable? x) (symbol? x))

• 两个变量相同就是表示它们的符号相互eq?：

(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))

• 和式与乘式都构造为表：

(define (make-sum a1 a2) (list ? a1 a2))
(define (make-product m1 m2) (list ? m1 m2))

• 和式就是第一个元素为符号＋的表：

(define (sum? x)
  (and (pair? x) (eq? (car x) '()))

• 被加数是表示和式的表里的第二个元素：

(define (addend s) (cadr s))

• 加数是表示和式的表里的第三个元素：

(define (augend s) (caddr s))

• 乘式就是第一个元素为符号 * 的表：

(define (product? x)
  (and (pair? x) (eq? (car x) '()))

• 被乘数是表示乘式的表里的第二个元素：

(define (multiplier p) (cadr p))

• 乘数是表示乘式的表里的第三个元素：

(define (multiplicand p) (caddr p))

这样，为了得到一个能够工作的符号求导程序，我们只需将这些过程与deriv装在一起。现在让我们看几个表现这一程序的行为的实例：

(deriv '(+ x 3) 'x)
(+ 1 0)
(deriv '(* x y) 'x)
(+ (* x 0) (* 1 y))
(deriv '(* (* x y) (+ x 3)) 'x)
(+ (* (* x y) (+ 1 0))
   (* (+ (* x 0) (* 1 y))
      (+  x 3)))

程序产生出的这些结果是对的，但是它们没有经过化简。我们确实有：

当然，我们也可能希望这一程序能够知道x·0＝0，1·y＝y以及0＋y＝y。因此，第二个例子的结果就应该是简单的y。正如上面的第三个例子所显示的，当表达式变得更加复杂时，这一情况也可能变成严重的问题。
现在所面临的困难很像我们在做有理数首先时所遇到的问题：希望将结果化简到最简单的形式。为了完成有理数的化简，我们只需要修改构造函数和选择函数的实现。这里也可以采取同样的策略。我们在这里也完全不必修改deriv，只需要修改make-sum，使得当两个求和对象都是数时，make-sum求出它们的和返回。还有，如果其中的一个求和对象是0，那么make-sum就直接返回另一个对象。

(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (list ? a1 a2))))

在这个实现里用到了过程＝number?，它检查某个表达式是否等于一个给定的数。

(define (=number? exp num)
  (and (number? exp) (= exp num)))

与此类似，我们也需要修改make-product，设法引进下面的规则：0与任何东西的乘积都是0，1与任何东西的乘积总是那个东西：

(define (make-product m1 m2)
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        (else (list ? m1 m2))))

下面是这一新过程版本对前面三个例子的结果：

(deriv '(+ x 3) 'x)
1
(deriv '(* x y) 'x)
y
(deriv '(* (* x y) (+ x 3)) 'x)
(+ (* x y) (* y (+ x 3)))

显然情况已经大大改观。但是，第三个例子还是说明，要想做出一个程序，使它能将表达式做成我们都能同意的“最简单”形式，前面还有很长的路要走。代数化简是一个非常复杂的问题，除了其他各种因素之外，还有另一个根本性的问题：对于某种用途的最简形式，对于另一用途可能就不是最简形式。
练习2.56 请说明如何扩充基本求导规则，以便能够处理更多种类的表达式。例如，通过给程序deriv增加一个新子句，并以适当方式定义过程exponentiation?、base、exponent和make-exponentiation的方式，实现下述求导规则（你可以考虑用符号**表示乘幂）：

请将如下规则也构造到程序里：任何东西的0次幂都是1，而它们的1次幂都是其自身。
练习2.57 请扩充求导程序，使之能处理任意项（两项或者更多项）的和与乘积。这样，上面的最后一个例子就可以表示为：

(deriv '(* x y (+ x 3)) 'x)

设法通过只修改和与乘积的表示，而完全不修改过程deriv的方式完成这一扩充。例如，让一个和式的addend是它的第一项，而其augend是和式中的其余项。
练习2.58 假定我们希望修改求导程序，使它能用于常规数学公式，其中＋和 * 采用的是中缀运算符而不是前缀。由于求导程序是基于抽象数据定义的，要修改它，使之能用于另一种不同的表达式表示，我们只需要换一套工作在新的、求导程序需要使用的代数表达式的表示形式上的谓词、选择函数和构造函数。
a) 请说明怎样做出这些过程，以便完成在中缀表示形式（例如（x＋（3（x＋（y＋2）））））上的代数表达式求导。为了简化有关的工作，现在可以假定＋和 总是取两个参数，而且表达式中已经加上了所有的括号。
b) 如果允许标准的代数写法，例如（x ＋ 3 *（x ＋ y ＋ 2）），问题就会变得更困难许多。在这种表达式里可能不写不必要的括号，并要假定乘法应该在加法之前完成。你还能为这种表示方式设计好适当的谓词、选择函数和构造函数，使我们的求导程序仍然能工作吗？

2.3.3 实例：集合的表示

在前面的实例中，我们已经构造起两类复合数据对象的表示：有理数和代数表达式。在这两个实例中，我们都采用了某一种选择，在构造时或者选择成员时去简化（约简）有关的表示。除此之外，选择用表的形式来表示这些结构都是直截了当的。现在我们要转到集合的表示问题，此时，表示方式的选择就不那么显然了。实际上，在这里存在几种选择，而且它们相互之间在几个方面存在明显的不同。
非形式地说，一个集合就是一些不同对象的汇集。要给出一个更精确的定义，我们可以利用数据抽象的方法，也就是说，用一组可以作用于“集合”的操作来定义它们。这些操作是union-set，intersection-set，element-of-set? 和adjoin-set。其中element-of-set?是一个谓词，用于确定某个给定元素是不是某个给定集合的成员。adjoin-set以一个对象和一个集合为参数，返回一个集合，其中包含了原集合的所有元素，再加上刚刚加入进来的这个新元素。union-set计算出两个集合的并集，这也是一个集合，其中包含了所有属于两个参数集合之一的元素。intersection-set计算出两个集合的交集，它包含着同时出现在两个参数集合中的那些元素。从数据抽象的观点看，我们在设计有关的表示方面具有充分的自由，只要在这种表示上实现的上述操作能以某种方式符合上面给出的解释。
集合作为未排序的表
集合的一种表示方式是用其元素的表，其中任何元素的出现都不超过一次。这样，空集就用空表来表示。对于这种表示形式，element-of-set?类似于2.3.1节的过程memq，但它应该用equal? 而不是eq?，以保证集合元素可以不是符号：

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((equal? x (car set)) true)
        (else (element-of-set? x (cdr set)))))

利用它就能写出adjoin-set。如果要加入的对象已经在相应集合里，那么就返回那个集合；否则就用cons将这一对象加入表示集合的表里：

(define (adjoin-set x set)
  (if (element-of-set? x set)
      set
      (cons x set)))

实现intersection-set时可以采用递归策略：如果我们已知如何做出set2与set1的cdr的交集，那么就只需要确定是否应将set1的car包含到结果之中了，而这依赖于（car set1）是否也在set2里。下面是这样写出的过程：

(define (intersection-set set1 set2)
  (cond ((or (null? set1) (null? set2)) '())
        ((element-of-set? (car set1) set2)        
         (cons (car set1)
               (intersection-set (cdr set1) set2)))
        (else (intersection-set (cdr set1) set2))))

在设计一种表示形式时，有一件必须关注的事情是效率问题。为考虑这一问题，就需要考虑上面定义的各集合操作所需要的工作步数。因为它们都使用了element-of-set?，这一操作的速度对整个集合的实现效率将有重大影响。在上面这个实现里，为了检查某个对象是否为一个集合的成员，element-of-set?可能不得不扫描整个集合（最坏情况是这一元素恰好不在集合里）。因此，如果集合有n个元素，element-of-set?就可能需要n步才能完成。这样，这一操作所需的步数将以 的速度增长。adjoin-set使用了这个操作，因此它所需的步数也以 的速度增长。而对于intersection-set，它需要对set1的每个元素做一次element-of-set?检查，因此所需步数将按所涉及的两个集合的大小之乘积增长，或者说，在两个集合大小都为n时就是 。union-set的情况也是如此。
练习2.59 请为采用未排序表的集合实现定义union-set操作。
练习2.60 我们前面说明了如何将集合表示为没有重复元素的表。现在假定允许重复，例如，集合 {1，2，3} 可能被表示为表（2 3 2 1 3 2 2）。请为在这种表示上的操作设计过程element-of-set?、adjoin-set、union-set和intersection-set。与前面不重复表示里的相应操作相比，现在各个操作的效率怎么样？在什么样的应用中你更倾向于使用这种表示，而不是前面那种无重复的表示？

集合作为排序的表
加速集合操作的一种方式是改变表示方式，使集合元素在表中按照上升序排列。为此，我们就需要有某种方式来比较两个元素，以便确定哪个元素更大一些。例如，我们可以按字典序做符号的比较；或者同意采用某种方式为每个对象关联一个唯一的数，在比较元素的时候就比较与之对应的数。为了简化这里的讨论，我们将仅仅考虑集合元素是数值的情况，这样就可以用 > 和 < 做元素的比较了。下面将数的集合表示为元素按照上升顺序排列的表。在前面第一种表示方式下，集合 {1，3，6，10} 的元素在相应的表里可以任意排列，而在现在的新表示方式中，我们就只允许用表（1 3 6 10）。
从操作element-of-set?可以看到采用有序表示的一个优势：为了检查一个项的存在性，现在就不必扫描整个表了。如果检查中遇到的某个元素大于当时要找的东西，那么就可以断定这个东西根本不在表里：

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((= x (car set)) true)
        ((< x (car set)) false)
        (else (element-of-set? x (cdr set)))))

这样能节约多少步数呢？在最坏情况下，我们要找的项目可能是集合中的最大元素，此时所需步数与采用未排序的表示时一样。但另一方面，如果需要查找许多不同大小的项，我们总可以期望，有些时候这一检索可以在接近表开始处的某一点停止，也有些时候需要检查表的一大部分。平均而言，我们可以期望需要检查表中的一半元素，这样，平均所需的步数就是大约n/2。这仍然是 的增长速度，但与前一实现相比，平均来说，现在我们节约了大约一半的步数（这一解释并不合理，因为前面说未排序表需要检查整个表，考虑的只是一种特殊情况：查找没有出现在表里的元素。如果查找的是表里存在的元素，即使采用未排序的表，平均查找长度也是表元素的一半。—译者注）。
操作intersection-set的加速情况更使人印象深刻。在未排序的表示方式里，这一操作需要 的步数，因为对set1的每个元素，我们都需要对set2做一次完全的扫描。对于排序表示则可以有一种更聪明的方法。我们在开始时比较两个集合的起始元素，例如x1和x2。如果x1等于x2，那么这样就得到了交集的一个元素，而交集的其他元素就是这两个集合的cdr的交集。如果此时的情况是x1小于x2，由于x2是集合set2的最小元素，我们立即可以断定x1不会出现在集合set2里的任何地方，因此它不应该在交集里。这样，两集合的交集就等于集合set2与set1的cdr的交集。与此类似，如果x2小于x1，那么两集合的交集就等于集合set1与set2的cdr的交集。下面是按这种方式写出的过程：

(define (intersection-set set1 set2)
  (if (or (null? set1) (null? set2))
      '()    
      (let ((x1 (car set1)) (x2 (car set2)))
        (cond ((= x1 x2)
               (cons x1
                     (intersection-set (cdr set1)
                                       (cdr set2))))
              ((< x1 x2)
               (intersection-set (cdr set1) set2))
              ((< x2 x1)
               (intersection-set set1 (cdr set2)))))))

为了估计出这一过程所需的步数，请注意，在每个步骤中，我们都将求交集问题归结到更小集合的交集计算问题—去掉了set1和set2之一或者是两者的第一个元素。这样，所需步数至多等于set1与set2的大小之和，而不像在未排序表示中它们的乘积。这也就是 的增长速度，而不是 —这一加速非常明显，即使对中等大小的集合也是如此。
练习2.61 请给出采用排序表示时adjoin-set的实现。通过类似element-of-set?的方式说明，可以如何利用排序的优势得到一个过程，其平均所需的步数是采用未排序表示时的一半。
练习2.62 请给出在集合的排序表示上union-set的一个 实现。

集合作为二叉树
如果将集合元素安排成一棵树的形式，我们还可以得到比排序表表示更好的结果。树中每个结点保存集合中的一个元素，称为该结点的“数据项”，它还链接到另外的两个结点（可能为空）。其中“左边”的链接所指向的所有元素均小于本结点的元素，而“右边”链接到的元素都大于本结点里的元素。图2-16显示的是一棵表示集合的树。同一个集合表示为树可以有多种不同的方式，我们对一个合法表示的要求就是，位于左子树里的所有元素都小于本结点里的数据项，而位于右子树里的所有元素都大于它。

树表示方法的优点在于：假定我们希望检查某个数x是否在一个集合里，那么就可以用x与树顶结点的数据项相比较。如果x小于它，我们就知道现在只需要搜索左子树；如果x比较大，那么就只需搜索右子树。在这样做时，如果该树是“平衡的”，也就是说，每棵子树大约是整个树的一半大，那么，这样经过一步，我们就将需要搜索规模为n的树的问题，归约为搜索规模为n/2的树的问题。由于经过每个步骤能够使树的大小减小一半，我们可以期望搜索规模为n的树的计算步数以Q(log n) 速度增长10。在集合很大时，相对于原来的表示，现在的操作速度将明显快得多。
我们可以用表来表示树，将结点表示为三个元素的表：本结点中的数据项，其左子树和右子树。以空表作为左子树或者右子树，就表示没有子树连接在那里。我们可以用下面过程描述这种表示：

(define (entry tree) (car tree))
(define (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr tree))
(define (make-tree entry left right)
  (list entry left right))

现在，我们就可以采用上面描述的方式实现过程element-of-set?了：

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((= x (entry set)) true)
        ((< x (entry set))
         (element-of-set? x (left-branch set)))
        ((> x (entry set))
         (element-of-set? x (right-branch set)))))

向集合里加入一个项的实现方式与此类似，也需要Q(log n) 步数。为了加入元素x，我们需要将x与结点数据项比较，以便确定x应该加入右子树还是左子树中。在将x加入适当的分支之后，我们将新构造出的这个分支、原来的数据项与另一分支放到一起。如果x等于这个数据项，那么就直接返回这个结点。如果需要将x加入一个空子树，那么我们就生成一棵树，以x作为数据项，并让它具有空的左右分支。下面是这个过程：

(define (adjoin-set x set)
  (cond ((null? set) (make-tree x '() '()))
        ((= x (entry set)) set)
        ((< x (entry set))
         (make-tree (entry set) 
                    (adjoin-set x (left-branch set))
                    (right-branch set)))
        ((> x (entry set))
         (make-tree (entry set)
                    (left-branch set)
                    (adjoin-set x (right-branch set))))))

我们在上面断言，搜索树的操作可以在对数步数中完成，这实际上依赖于树“平衡”的假设，也就是说，每个树的左右子树中的结点大致上一样多，因此每棵子树中包含的结点大约就是其父的一半。但是我们怎么才能确保构造出的树是平衡的呢？即使是从一棵平衡的树开始工作，采用adjoin-set加入元素也可能产生出不平衡的结果。因为新加入元素的位置依赖于它与当时已经在树中的那些项比较的情况。我们可以期望，如果“随机地”将元素加入树中，平均而言将会使树趋于平衡。但在这里并没有任何保证。例如，如果我们从空集出发，顺序将数值1至7加入其中，我们就会得到如图2-17所示的高度不平衡的树。在这个树里，所有的左子树都为空，所以它与简单排序表相比一点优势也没有。解决这个问题的一种方式是定义一个操作，它可以将任意的树变换为一棵具有同样元素的平衡树。在每执行过几次adjoin-set操作之后，我们就可以通过执行它来保持树的平衡。当然，解决这一问题的方法还有许多，大部分这类方法都涉及设计一种新的数据结构，设法使这种数据结构上的搜索和插入操作都能够在Q(log n) 步数内完成。

练习2.63 下面两个过程都能将树变换为表：

(define (tree->list-1 tree)
  (if (null? tree)
      '()
      (append (tree->list-1 (left-branch tree))
              (cons (entry tree)
                    (tree->list-1 (right-branch tree))))))
(define (tree->list-2 tree)
  (define (copy-to-list tree result-list)
    (if (null? tree)
        result-list
        (copy-to-list (left-branch tree)
                      (cons (entry tree)
                            (copy-to-list (right-branch tree)
                                          result-list)))))
  (copy-to-list tree '()))

a) 这两个过程对所有的树都产生同样结果吗？如果不是，它们产生出的结果有什么不同？它们对图2-16中的那些树产生什么样的表？
b) 将n个结点的平衡树变换为表时，这两个过程所需的步数具有同样量级的增长速度吗？如果不一样，哪个过程增长得慢一些？
练习2.64 下面过程list->tree将一个有序表变换为一棵平衡二叉树。其中的辅助函数partial-tree以整数n和一个至少包含n个元素的表为参数，构造出一棵包含这个表的前n个元素的平衡树。由partial-tree返回的结果是一个序对（用cons构造），其car是构造出的树，其cdr是没有包含在树中那些元素的表。

(define (list->tree elements)
  (car (partial-tree elements (length elements))))
(define (partial-tree elts n)
  (if (= n 0)
      (cons '() elts)
      (let ((left-size (quotient (- n 1) 2)))
        (let ((left-result (partial-tree elts left-size)))
          (let ((left-tree (car left-result))
                (non-left-elts (cdr left-result))
                (right-size (- n (+ left-size 1))))
            (let ((this-entry (car non-left-elts))
                  (right-result (partial-tree (cdr non-left-elts)
                                              right-size)))
              (let ((right-tree (car right-result))
                    (remaining-elts (cdr right-result)))
                (cons (make-tree this-entry left-tree right-tree)
                      remaining-elts))))))))

a) 请简要地并尽可能清楚地解释为什么partial-tree能完成工作。请画出将list->tree用于表（1 3 5 7 9 11）产生出的树。
b) 过程list->tree转换n个元素的表所需的步数以什么量级增长？
练习2.65 利用练习2.63和练习2.64的结果，给出对采用（平衡）二叉树方式实现的集合的union-set和intersection-set操作的 实现。

集合与信息检索
我们考察了用表表示集合的各种选择，并看到了数据对象表示的选择可能如何深刻地影响到使用数据的程序的性能。关注集合的另一个原因是，这里所讨论的技术在涉及信息检索的各种应用中将会一次又一次地出现。
现在考虑一个包含大量独立记录的数据库，例如一个企业中的人事文件，或者一个会计系统里的交易记录。典型的数据管理系统都需将大量时间用在访问和修改所存的数据上，因此就需要访问记录的高效方法。完成此事的一种方式是将每个记录中的一部分当作标识key（键值）。所用键值可以是任何能唯一标识记录的东西。对于人事文件而言，它可能是雇员的ID编码。对于会计系统而言，它可能是交易的编号。在确定了采用什么键值之后，就可以将记录定义为一种数据结构，并包含key选择过程，它可以从给定记录中提取出有关的键值。
现在就可以将这个数据库表示为一个记录的集合。为了根据给定键值确定相关记录的位置，我们用一个过程lookup，它以一个键值和一个数据库为参数，返回具有这个键值的记录，或者在找不到相应记录时报告失败。lookup的实现方式几乎与element-of-set?一模一样，如果记录的集合被表示为未排序的表，我们就可以用：

(define (lookup given-key set-of-records)
  (cond ((null? set-of-records) false)
        ((equal? given-key (key (car set-of-records)))
         (car set-of-records))
        (else (lookup given-key (cdr set-of-records)))))

不言而喻，还有比未排序表更好的表示大集合的方法。常常需要“随机访问”其中记录的信息检索系统通常用某种基于树的方法实现，例如用前面讨论过的二叉树。在设计这种系统时，数据抽象的方法学将很有帮助。设计师可以创建某种简单而直接的初始实现，例如采用未排序的表。对于最终系统而言，这种做法显然并不合适，但采用这种方式提供一个“一挥而就”的数据库，对用于测试系统的其他部分则可能很有帮助。然后可以将数据表示修改得更加精细。如果对数据库的访问都是基于抽象的选择函数和构造函数，这种表示的改变就不会要求对系统其余部分做任何修改。
练习2.66 假设记录的集合采用二叉树实现，按照其中作为键值的数值排序。请实现相应的lookup过程。

2.3.4 实例：Huffman编码树

本节将给出一个实际使用表结构和数据抽象去操作集合与树的例子。这一应用是想确定一些用0和1（二进制位）的序列表示数据的方法。举例说，用于在计算机里表示文本的ASCII标准编码将每个字符表示为一个包含7个二进制位的序列，采用7个二进制位能够区分27种不同情况，即128个可能不同的字符。一般而言，如果我们需要区分n个不同字符，那么就需要为每个字符使用log2 n个二进制位。假设我们的所有信息都是用A、B、C、D、E、F、G和H这样8个字符构成的，那么就可以选择每个字符用3个二进制位，例如：

A 000     C 010     E 100     G 110
B 001     D 011     F 101     H 111

采用这种编码方式，消息：

BACADAEAFABBAAAGAH

将编码为54个二进制位

001000010000011000100000101000001001000000000110000111

像ASCII码和上面A到H编码这样的编码方式称为定长编码，因为它们采用同样数目的二进制位表示消息中的每一个字符。变长编码方式就是用不同数目的二进制位表示不同的字符，这种方式有时也可能有些优势。举例说，莫尔斯电报码对于字母表中各个字母就没有采用同样数目的点和划，特别是最常见的字母E只用一个点表示。一般而言，如果在我们的消息里，某些符号出现得很频繁，而另一些却很少见，那么如果为这些频繁出现的字符指定较短的码字，我们就可能更有效地完成数据的编码（对于同样消息使用更少的二进制位）。请考虑下面对于字母A到H的另一种编码：

A 0     C 1010     E 1100     G 1110
B 100     D 1011     F 1101     H 1111

采用这种编码方式，上面的同样信息将编码为如下的串：

100010100101101100011010100100000111001111

这个串中只包含42个二进制位，也就是说，与上面定长编码相比，现在的这种方式节约了超过20%的空间。
采用变长编码有一个困难，那就是在读0/1序列的过程中确定何时到达了一个字符的结束。莫尔斯码解决这一问题的方式是在每个字母的点划序列之后用一个特殊的分隔符（它用的是一个间歇）。另一种解决方式是以某种方式设计编码，使得其中每个字符的完整编码都不是另一字符编码的开始一段（或称前缀）。这样的编码称为前缀码。在上面例子里，A编码为0而B编码为100，没有其他字符的编码由0或者100开始。
一般而言，如果能够通过变长前缀码去利用被编码消息中符号出现的相对频度，那么就能明显地节约空间。完成这件事情的一种特定方式称为Huffman编码，这个名称取自其发明人David Huffman。一个Huffman编码可以表示为一棵二叉树，其中的树叶是被编码的符号。树中每个非叶结点代表一个集合，其中包含了这一结点之下的所有树叶上的符号。除此之外，位于树叶的每个符号还被赋予一个权重（也就是它的相对频度），非叶结点所包含的权重是位于它之下的所有叶结点的权重之和。这种权重在编码和解码中并不使用。下面将会看到，在构造树的过程中需要它们的帮助。
图2-18显示的是上面给出的A到H编码所对应的Huffman编码树，树叶上的权重表明，这棵树的设计所针对的消息是，字母A具有相对权重8，B具有相对权重3，其余字母的相对权重都是1。
给定了一棵Huffman树，要找出任一符号的编码，我们只需从树根开始向下运动，直到到达了保存着这一符号的树叶为止，在每次向左行时就给代码加上一个0，右行时加上一个1。在确定向哪一分支运动时，需要检查该分支是否包含着与这一符号对应的叶结点，或者其集合中包含着这个符号。举例说，从图2-18中树的根开始，到达D的叶结点的方式是走一个右分支，而后一个左分支，而后是右分支，而后又是右分支，因此其代码为1011。

在用Huffman树做一个序列的解码时，我们也从树根开始，通过位序列中的0或1确定是移向左分支还是右分支。每当我们到达一个叶结点时，就生成出了消息中的一个符号。此时就重新从树根开始去确定下一个符号。例如，如果给我们的是上面的树和序列10001010。从树根开始，我们移向右分支（因为串中第一个位是1），而后向左分支（因为第二个位是0），而后再向左分支（因为第三个位也是0）。这时已经到达B的叶，所以被解码消息中的第一个符号是B。现在再次从根开始，因为序列中下一个位是0，这就导致一次向左分支的移动，使我们到达A的叶。然后我们再次从根开始处理剩下的串1010，经过右左右左移动后到达了C。这样，整个消息也就是BAC。
生成Huffman树
给定了符号的“字母表”和它们的相对频度，我们怎么才能构造出“最好的”编码呢？换句话说，哪样的树能使消息编码的位数达到最少？Huffman给出了完成这件事的一个算法，并且证明了，对于符号所出现的相对频度与构造树的消息相符的消息而言，这样产生出的编码确实是最好的变长编码。我们并不打算在这里证明Huffman编码的最优性质，但将展示如何去构造Huffman树。
生成Huffman树的算法实际上十分简单，其想法就是设法安排这棵树，使得那些带有最低频度的符号出现在离树根最远的地方。这一构造过程从叶结点的集合开始，这种结点中包含各个符号和它们的频度，这就是开始构造编码的初始数据。现在要找出两个具有最低权重的叶，并归并它们，产生出一个以这两个结点为左右分支的结点。新结点的权重就是那两个结点的权重之和。现在我们从原来集合里删除前面的两个叶结点，并用这一新结点代替它们。随后继续这一过程，在其中的每一步都归并两个具有最小权重的结点，将它们从集合中删除，并用一个以这两个结点作为左右分支的新结点取而代之。当集合中只剩下一个结点时，这一过程终止，而这个结点就是树根。下面显示的是图2-18中的Huffman树的生成过程：

初始树叶    {(A 8) (B 3) (C 1) (D 1) (E 1) (F 1) (G 1) (H 1)}
归并    {(A 8) (B 3) ({C D} 2) (E 1) (F 1) (G 1) (H 1)}
归并    {(A 8) (B 3) ({C D} 2) ({E F} 2) (G 1) (H 1)}
归并    {(A 8) (B 3) ({C D} 2) ({E F} 2) ({G H} 2)}
归并    {(A 8) (B 3) ({C D} 2) ({E F G H} 4)}
归并    {(A 8) ({B C D} 5) ({E F G H} 4)}
归并    {(A 8) ({B C D E F G H} 9)}
最后归并    {({A B C D E F G H} 17)}

这一算法并不总能描述一棵唯一的树，这是因为，每步选择出的最小权重结点有可能不唯一。还有，在做归并时，两个结点的顺序也是任意的，也就是说，随便哪个都可以作为左分支或者右分支。
Huffman树的表示
在下面的练习中，我们将要做出一个使用Huffman树完成消息编码和解码，并能根据上面给出的梗概生成Huffman树的系统。开始还是讨论这种树的表示。
将一棵树的树叶表示为包含符号leaf、叶中符号和权重的表：

(define (make-leaf symbol weight)
  (list 'leaf symbol weight))
(define (leaf? object)
  (eq? (car object) 'leaf))
(define (symbol-leaf x) (cadr x))
(define (weight-leaf x) (caddr x))

一棵一般的树也是一个表，其中包含一个左分支、一个右分支、一个符号集合和一个权重。符号集合就是符号的表，这里没有用更复杂的集合表示。在归并两个结点做出一棵树时，树的权重也就是这两个结点的权重之和，其符号集就是两个结点的符号集的并集。因为这里的符号集用表来表示，通过2.2.1节的append过程就可以得到它们的并集：

(define (make-code-tree left right)
  (list left
        right
        (append (symbols left) (symbols right))
        (+ (weight left) (weight right))))

如果以这种方式构造，我们就需要采用下面的选择函数：

(define (left-branch tree) (car tree))
(define (right-branch tree) (cadr tree))
(define (symbols tree)
  (if (leaf? tree)
      (list (symbol-leaf tree))
      (caddr tree)))
(define (weight tree)
  (if (leaf? tree)
      (weight-leaf tree)
      (cadddr tree)))

在对树叶或者一般树调用过程symbols和weight时，它们需要做的事情有一点不同。这些不过是通用型过程（可以处理多于一种数据的过程）的简单实例，有关这方面的情况，在2.4节和2.5节将有很多讨论。
解码过程
下面的过程实现解码算法，它以一个0/1的表和一棵Huffman树为参数：

(define (decode bits tree)
  (define (decode-1 bits current-branch)
    (if (null? bits)
        '()
        (let ((next-branch
               (choose-branch (car bits) current-branch)))
          (if (leaf? next-branch)
              (cons (symbol-leaf next-branch)
                    (decode-1 (cdr bits) tree))
              (decode-1 (cdr bits) next-branch)))))
  (decode-1 bits tree))
(define (choose-branch bit branch)
  (cond ((= bit 0) (left-branch branch))
        ((= bit 1) (right-branch branch))
        (else (error "bad bit -- CHOOSE-BRANCH" bit))))

过程decode-1有两个参数，其中之一是包含二进制位的表，另一个是树中的当前位置。它不断在树里“向下”移动，根据表中下一个位是0或者1选择树的左分支或者右分支（这一工作由过程choose-branch完成）。一旦到达了叶结点，它就把位于这里的符号作为消息中的下一个符号，将其cons到对于消息里随后部分的解码结果之前。而后这一解码又从树根重新开始。请注意choose-branch里最后一个子句的错误检查，如果过程遇到了不是0/1的东西时就会报告错误。
带权重元素的集合
在树表示里，每个非叶结点包含着一个符号集合，在这里表示为一个简单的表。然而，上面讨论的树生成算法要求我们也能对树叶和树的集合工作，以便不断地归并一对一对的最小项。因为在这里需要反复去确定集合里的最小项，采用某种有序的集合表示会比较方便。
我们准备将树叶和树的集合表示为一批元素的表，按照权重的上升顺序排列表中的元素。下面用于构造集合的过程adjoin-set与练习2.61中描述的过程类似，但这里比较的是元素的权重，而且加入集合的新元素原来绝不会出现在这个集合里。

(define (adjoin-set x set)
  (cond ((null? set) (list x))
        ((< (weight x) (weight (car set))) (cons x set))
        (else (cons (car set)
                    (adjoin-set x (cdr set))))))

下面过程以一个符号-权重对偶的表为参数，例如（（A 4）（B 2）（C 1）（D 1）），它构造出树叶的初始排序集合，以便Huffman算法能够去做归并：

(define (make-leaf-set pairs)
  (if (null? pairs)
      '()
      (let ((pair (car pairs)))
        (adjoin-set (make-leaf (car pair)    ; symbol
                               (cadr pair))  ; frequency
                    (make-leaf-set (cdr pairs))))))

练习2.67 请定义一棵编码树和一个样例消息：

(define sample-tree
  (make-code-tree (make-leaf 誂 4)
                  (make-code-tree
                   (make-leaf 誃 2)
                   (make-code-tree (make-leaf 誅 1)
                                   (make-leaf 誄 1)))))
(define sample-message ?0 1 1 0 0 1 0 1 0 1 1 1 0))

然后用过程decode完成该消息的编码，给出编码的结果。
练习2.68 过程encode以一个消息和一棵树为参数，产生出被编码消息所对应的二进制位的表：

(define (encode message tree)
  (if (null? message)
      '()
      (append (encode-symbol (car message) tree)
              (encode (cdr message) tree))))

其中的encode-symbol是需要你写出的过程，它能根据给定的树产生出给定符号的二进制位表。你所设计的encode-symbol在遇到未出现在树中的符号时应报告错误。请用在练习2.67中得到的结果检查所实现的过程，工作中用同样一棵树，看看得到的结果是不是原来那个消息。
练习2.69 下面过程以一个符号-频度对偶表为参数（其中没有任何符号出现在多于一个对偶中），并根据Huffman算法生成出Huffman编码树。

(define (generate-huffman-tree pairs)
  (successive-merge (make-leaf-set pairs)))

其中的make-leaf-set是前面给出的过程，它将对偶表变换为叶的有序集，successive-merge是需要你写的过程，它使用make-code-tree反复归并集合中具有最小权重的元素，直至集合里只剩下一个元素为止。这个元素就是我们所需要的Huffman树。（这一过程稍微有点技巧性，但并不很复杂。如果你正在设计的过程变得很复杂，那么几乎可以肯定是在什么地方搞错了。你应该尽可能地利用有序集合表示这一事实。）
练习2.70 下面带有相对频度的8个符号的字母表，是为了有效编码20世纪50年代的摇滚歌曲中的词语而设计的。（请注意，“字母表”中的“符号”不必是单个字母。）

A     2     NA     16
BOOM     1     SHA     3
GET     2     YIP     9
JOB     2     WAH     1

请用（练习2.69的）generate-huffman-tree过程生成对应的Huffman树，用（练习2.68的）encode过程编码下面的消息：

Get a job
Sha na na na na na na na na 
Get a job 
Sha na na na na na na na na 
Wah yip yip yip yip yip yip yip yip yip 
Sha boom

这一编码需要多少个二进制位？如果对这8个符号的字母表采用定长编码，完成这个歌曲的编码最少需要多少个二进制位？
练习2.71 假定我们有一棵n个符号的字母表的Huffman树，其中各符号的相对频度分别是1，2，4，…，2n－1。请对n＝5和n＝10勾勒出有关的树的样子。对于这样的树（对于一般的n），编码出现最频繁的符号用多少个二进制位？最不频繁的符号呢？
练习2.72 考虑你在练习2.68中设计的编码过程。对于一个符号的编码，计算步数的增长速率是什么？请注意，这时需要把在每个结点中检查符号表所需的步数包括在内。一般性地回答这一问题是非常困难的。现在考虑一类特殊情况，其中的n个符号的相对频度如练习2.71所描述的。请给出编码最频繁的符号所需的步数和最不频繁的符号所需的步数的增长速度（作为n的函数）。

2.4 抽象数据的多重表示

我们已经介绍过数据抽象，这是一种构造系统的方法学，采用这种方法，将使一个程序中的大部分描述能与这一程序所操作的数据对象的具体表示的选择无关。举例来说，在2.1.1节里，我们看到如何将一个使用有理数的程序的设计与有理数的实现工作相互分离，具体实现中采用的是计算机语言所提供的构造复合数据的基本机制。这里的关键性思想就是构筑起一道抽象屏障—对于上面情况，也就是有理数的选择函数和构造函数（make-rat，numer，denom）—它能将有理数的使用方式与其借助于表结构的具体表示形式隔离开。与此类似的抽象屏障，也把执行有理数算术的过程（add-rat，sub-rat，mul-rat和div-rat）与使用有理数的“高层”过程隔离开。这样做出的程序所具有的结构如图2-1所示。
数据抽象屏障是控制复杂性的强有力工具。通过对数据对象基础表示的屏蔽，我们就可以将设计一个大程序的任务，分割为一组可以分别处理的较小任务。但是，这种类型的数据抽象还不够强大有力，因为在这里说数据对象的“基础表示”并不一定总有意义。
从一个角度看，对于一个数据对象也可能存在多种有用的表示方式，而且我们也可能希望所设计的系统能处理多种表示形式。举一个简单的例子，复数就可以表示为两种几乎等价的形式：直角坐标形式（实部和虚部）和极坐标形式（模和幅角）。有时采用直角坐标形式更合适，有时极坐标形式更方便。的确，我们完全可能设想一个系统，其中的复数同时采用了两种表示形式，而其中的过程可以对具有任意表示形式的复数工作。
更重要的是，一个系统的程序设计常常是由许多人通过一个相当长时期的工作完成的，系统的需求也在随着时间而不断变化。在这样一种环境里，要求每个人都在数据表示的选择上达成一致是根本就不可能的事情。因此，除了需要将表示与使用相隔离的数据抽象屏障之外，我们还需要有抽象屏障去隔离互不相同的设计选择，以便允许不同的设计选择在同一个程序里共存。进一步说，由于大型程序常常是通过组合起一些现存模块构造起来的，而这些模板又是独立设计的，我们也需要一些方法，使程序员可能逐步地将许多模块结合成一个大型系统，而不必去重新设计或者重新实现这些模块。
在这一节里，我们将学习如何去处理数据，使它们可能在一个程序的不同部分中采用不同的表示方式。这就需要我们去构造通用型过程—也就是那种可以在不止一种数据表示上操作的过程。这里构造通用型过程所采用的主要技术，是让它们在带有类型标志的数据对象上工作。也就是说，让这些数据对象包含着它们应该如何处理的明确信息。我们还要讨论数据导向的程序设计，这是一种用于构造采用了通用型操作的系统有力而且方便的技术。
我们将从简单的复数实例开始，看看如何采用类型标志和数据导向的风格，为复数分别设计出直角坐标表示和极坐标表示，而又维持一种抽象的“复数”数据对象的概念。做到这一点的方式就是定义基于通用型选择函数定义复数的算术运算（add-complex、sub-complex、mul-complex和div-complex），使这些选择函数能访问一个复数的各个部分，无论复数采用的是什么表示方式。作为结果的复数系统如图2-19所示，其中包含两种不同类型的抽象屏障，“水平”抽象屏障扮演的角色与图2-1中的相同，它们将“高层”操作与“低层”表示隔离开。此外，还存在着一道“垂直”屏障，它使我们能够隔离不同的设计，并且还能够安装其他的表示方式。

在2.5节里，我们将说明如何利用类型标志和数据导向的风格去开发一个通用型算术包，其中提供的过程（add、mul等）可以用于操作任何种类的“数”，在需要另一类新的数时也很容易进行扩充。在2.5.3节里，我们还要展示如何在执行符号代数的系统里使用通用型算术功能。

2.4.1 复数的表示

这里要开发一个完成复数算术运算的系统，作为使用通用型操作的程序的一个简单的，但不那么实际的例子。开始时，我们要讨论将复数表示为有序对的两种可能表示方式：直角坐标形式（实部和虚部）以及极坐标形式（模和幅角）。2.4.2节将展示如何通过类型标志和通用型操作，使这两种表示共存于同一个系统中。
与有理数一样，复数也可以很自然地用有序对表示。我们可以将复数集合设想为一个带有两个坐标轴（“实”轴和“虚”轴）的二维空间（见图2-20）。按照这一观点，复数z＝x＋iy（其中i2＝－1）可看作这个平面上的一个点，其中的实坐标是x而虚坐标为y。在这种表示下，复数的加法就可以归结为两个坐标分别相加：

实部 (z1＋z2)＝实部 (z1)＋实部 (z2)
虚部 (z1＋z2)＝虚部 (z1)＋虚部 (z2)

在需要乘两个复数时，更自然的考虑是采用复数的极坐标形式，此时复数用一个模和一个幅角表示（图2-20中的r和A）。两个复数的乘积也是一个向量，得到它的方式是模相乘，幅角相加。

模 (z1·z2)＝模 (z1)·模 (z2)
幅角 (z1·z2)＝幅角 (z1)＋幅角 (z2)

可见，复数有两种不同表示方式，它们分别适合不同的运算。当然，从编写使用复数的程序的开发人员角度看，数据抽象原理的建议是所有复数操作都应该可以使用，无论计算机所用的具体表示形式是什么。例如，我们也常常需要取得一个复数的模，即使它原本采用的是复数的直角坐标表示。同样，我们也常常需要得到复数的实部，即使它实际采用的是极坐标形式。
在设计一个这样的系统时，我们将沿用在2.1.1节设计有理数包时所采用的同样的数据抽象策略，假定所有复数运算的实现都基于如下四个选择函数：real-part、imag-part、magnitude和angle；还要假定有两个构造复数的过程：make-from-real-imag返回一个采用实部和虚部描述的复数，make-from-mag-ang返回一个采用模和幅角描述的复数。这些过程的性质是，对于任何复数z，下面两者：

(make-from-real-imag (real-part z) (imag-part z))

和

(make-from-mag-ang (magnitude z) (angle z))

产生出的复数都等于z。
利用这些构造函数和选择函数，我们就可以实现复数算术了，其中使用由这些构造函数和选择函数所刻画的“抽象数据”，就像前面在2.1.1节中针对有理数所做的那样。正如上面公式中所描述的，复数的加法和减法采用实部和虚部的方式描述，而乘法和除法采用模和幅角的方式描述：

(define (add-complex z1 z2)
  (make-from-real-imag (+ (real-part z1) (real-part z2))
                       (+ (imag-part z1) (imag-part z2))))
(define (sub-complex z1 z2)
  (make-from-real-imag (- (real-part z1) (real-part z2))
                       (- (imag-part z1) (imag-part z2))))
(define (mul-complex z1 z2)
  (make-from-mag-ang (* (magnitude z1) (magnitude z2))
                     (+ (angle z1) (angle z2))))
(define (div-complex z1 z2)
  (make-from-mag-ang (/ (magnitude z1) (magnitude z2))
                     (- (angle z1) (angle z2))))

为了完成这一复数包，我们必须选择一种表示方式，而且必须基于基本的数值和基本表结构，基于它们实现各个构造函数和选择函数。现在有两种显见的方式完成这一工作：可以将复数按“直角坐标形式”表示为一个有序对（实部，虚部），或者按照“极坐标形式”表示为有序对（模，幅角）。究竟应该选择哪一种方式呢？
为了将不同选择的情况看得更清楚些，现在让我们假定有两个程序员，Ben Bitdiddle和Alyssa P. Hacker，他们正在分别独立地设计这一复数系统的具体表示形式。Ben选择了复数的直角坐标表示形式，采用这一选择，选取复数的实部与虚部是直截了当的，因为这种复数就是由实部和虚部构成的。而为了得到模和幅角，或者需要在给定模和幅角的情况下构造复数时，他利用了下面的三角关系：

这些公式建立起实部和虚部对偶 (x，y) 与模和幅角对偶 (r，A) 之间的联系。Ben在这种表示之下给出了下面这几个选择函数和构造函数：

(define (real-part z) (car z))
(define (imag-part z) (cdr z))
(define (magnitude z)
  (sqrt (+ (square (real-part z)) (square (imag-part z)))))
(define (angle z)
  (atan (imag-part z) (real-part z)))
(define (make-from-real-imag x y) (cons x y))
(define (make-from-mag-ang r a) 
  (cons (* r (cos a)) (* r (sin a))))

而在另一边，Alyssa却选择了复数的极坐标形式。对于她而言，选取模和幅角的操作直截了当，但必须通过三角关系去得到实部和虚部。Alyssa的表示是：

(define (real-part z)
  (* (magnitude z) (cos (angle z))))
(define (imag-part z)
  (* (magnitude z) (sin (angle z))))
(define (magnitude z) (car z))
(define (angle z) (cdr z))
(define (make-from-real-imag x y) 
  (cons (sqrt (+ (square x) (square y)))
        (atan y x)))
(define (make-from-mag-ang r a) (cons r a))

数据抽象的规则保证了add-complex、sub-complex、mul-complex和div-complex的同一套实现对于Ben的表示或者Alyssa的表示都能正常工作。

2.4.2 带标志数据

认识数据抽象的一种方式是将其看作“最小允诺原则”的一个应用。在2.4.1节中实现复数系统时，我们可以采用Ben的直角坐标表示形式或者Alyssa的极坐标表示形式，由选择函数和构造函数形成的抽象屏障，使我们可以把为自己所用数据对象选择具体表示形式的事情尽量向后推，而且还能保持系统设计的最大灵活性。
最小允诺原则还可以推进到更极端的情况。如果我们需要的话，那么还可以在设计完成选择函数和构造函数，并决定了同时使用Ben的表示和Alyssa的表示之后，仍然维持所用表示方式的不确定性。如果要在同一个系统里包含这两种不同表示形式，那么就需要有一种方式，将极坐标形式的数据与直角坐标形式的数据区分开。否则的话，如果现在要找出对偶（3, 4）的magnitude，我们将无法知道答案是5（将数据解释为直角坐标表示形式）还是3（将数据解释为极坐标表示）。完成这种区分的一种方式，就是在每个复数里包含一个类型标志部分—用符号rectangular或者polar。此后如果我们需要操作一个复数，借助于这个标志就可以确定应该使用的选择函数了。
为了能对带标志数据进行各种操作，我们将假定有过程type-tag和contents，它们分别从数据对象中提取出类型标志和实际内容（对于复数的情况，其中的极坐标或者直角坐标）。还要假定有一个过程attach-tag，它以一个标志和实际内容为参数，生成出一个带标志的数据对象。实现这些的直接方式就是采用普通的表结构：

(define (attach-tag type-tag contents)
  (cons type-tag contents))
(define (type-tag datum)
  (if (pair? datum)
      (car datum)
      (error "Bad tagged datum -- TYPE-TAG" datum)))
(define (contents datum)
  (if (pair? datum)
      (cdr datum)
      (error "Bad tagged datum -- CONTENTS" datum)))

利用这些过程，我们就可以定义出谓词rectangular?和polar?，它们分别辨识直角坐标的和极坐标的复数：

(define (rectangular? z)
  (eq? (type-tag z) 'rectangular))
(define (polar? z)
  (eq? (type-tag z) 'polar))

有了类型标志之后，Ben和Alyssa现在就可以修改自己的代码，使他们的两种不同表示能够共存于同一个系统中了。当Ben构造一个复数时，总为它加上标志，说明采用的是直角坐标；而当Alyssa构造复数时，总将其标志设置为极坐标。此外，Ben和Alyssa还必须保证他们所用的过程名并不冲突。保证这一点的一种方式是，Ben总为在他的表示上操作的过程名字加上后缀rectangular，而Alyssa为她的过程名加上后缀polar。这里是Ben根据2.4.1节修改后的直角坐标表示：

(define (real-part-rectangular z) (car z))
(define (imag-part-rectangular z) (cdr z))
(define (magnitude-rectangular z)
  (sqrt (+ (square (real-part-rectangular z))
           (square (imag-part-rectangular z)))))
(define (angle-rectangular z)
  (atan (imag-part-rectangular z)
        (real-part-rectangular z)))
(define (make-from-real-imag-rectangular x y)
  (attach-tag 'rectangular (cons x y)))
(define (make-from-mag-ang-rectangular r a) 
  (attach-tag 'rectangular
              (cons (* r (cos a)) (* r (sin a)))))

下面是修改后的极坐标表示：

(define (real-part-polar z)
  (* (magnitude-polar z) (cos (angle-polar z))))
(define (imag-part-polar z)
  (* (magnitude-polar z) (sin (angle-polar z))))
(define (magnitude-polar z) (car z))
(define (angle-polar z) (cdr z))
(define (make-from-real-imag-polar x y) 
  (attach-tag 'polar
               (cons (sqrt (+ (square x) (square y)))
                     (atan y x))))
(define (make-from-mag-ang-polar r a)
  (attach-tag 'polar (cons r a)))

每个通用型选择函数都需要实现为这样的过程，它首先检查参数的标志，而后去调用处理该类数据的适当过程。例如，为了得到一个复数的实部，real-part需要通过检查，设法确定是去使用Ben的real-part-rectangular，还是所用Alyssa的real-part-polar。在这两种情况下，我们都用contents提取出原始的无标志数据，并将它送给所需的直角坐标过程或者极坐标过程：

(define (real-part z)
  (cond ((rectangular? z) 
         (real-part-rectangular (contents z)))
        ((polar? z)
         (real-part-polar (contents z)))
        (else (error "Unknown type -- REAL-PART" z))))
(define (imag-part z)
  (cond ((rectangular? z)
         (imag-part-rectangular (contents z)))
        ((polar? z)
         (imag-part-polar (contents z)))
        (else (error "Unknown type -- IMAG-PART" z))))
(define (magnitude z)
  (cond ((rectangular? z)
         (magnitude-rectangular (contents z)))
        ((polar? z)
         (magnitude-polar (contents z)))
        (else (error "Unknown type -- MAGNITUDE" z))))
(define (angle z)
  (cond ((rectangular? z)
         (angle-rectangular (contents z)))
        ((polar? z)
         (angle-polar (contents z)))
        (else (error "Unknown type -- ANGLE" z))))

在实现复数算术运算时，我们仍然可以采用取自2.4.1节的同样过程add-complex、sub-complex、mul-complex和div-complex，因为它们所调用的选择函数现在都是通用型的，对任何表示都能工作。例如，过程add-complex仍然是：

(define (add-complex z1 z2)
  (make-from-real-imag (+ (real-part z1) (real-part z2))
                       (+ (imag-part z1) (imag-part z2))))

最后，我们还必须选择是采用Ben的表示还是Alyssa的表示构造复数。一种合理选择是，在手头有实部和虚部时采用直角坐标表示，有模和幅角时就采用极坐标表示：

(define (make-from-real-imag x y)
  (make-from-real-imag-rectangular x y))
(define (make-from-mag-ang r a)
  (make-from-mag-ang-polar r a))

这样得到的复数系统所具有的结构如图2-21所示。这一系统已经分解为三个相对独立的部分：复数算术运算、Alyssa的极坐标实现和Ben的直角坐标实现。极坐标或直角坐标的实现可以是Ben和Alyssa独立工作写出的东西，这两部分又被第三个程序员作为基础表示，用于在抽象构造函数和选择函数界面之上实现各种复数算术过程。

因为每个数据对象都以其类型作为标志，选择函数就能够在不同的数据上以一种通用的方式操作。也就是说，每个选择函数的定义行为依赖于它操作其上的特定的数据类型。请注意这里建立不同表示之间的界面的一般性机制：在一种给定的表示实现中（例如Alyssa的极坐标包），复数是一种无类型的对偶（模, 幅角）。当通用型选择函数对一个polar类型的复数进行操作时，它会剥去标志并将相应内容传递给Alyssa的代码。与此相对应，当Alyssa去构造一个供一般性使用的复数时，她也为其加上类型标志，使这个数据对象可以为高层过程所识别。在将数据对象从一个层次传到另一层次的过程中，这种剥去和加上标志的规范方式可以成为一种重要的组织策略，正如我们将在2.5节中看到的那样。

2.4.3 数据导向的程序设计和可加性

检查一个数据项的类型，并据此去调用某个适当过程称为基于类型的分派。在系统设计中，这是一种获得模块性的强有力策略。而另一方面，像2.4.2节那样实现的分派有两个显著的弱点。第一个弱点是，其中的这些通用型界面过程（real-part、imag-part、magnitude和angle）必须知道所有的不同表示。举例来说，假定现在希望能为前面的复数系统增加另一种表示，我们就必须将这一新表示方式标识为一种新类型，而且要在每个通用界面过程里增加一个子句，检查这一新类型，并对这种表示形式使用适当的选择函数。
这一技术还有另一个弱点。即使这些独立的表示形式可以分别设计，我们也必须保证在整个系统里不存在两个名字相同的过程。正因为这一原因，Ben和Alyssa必须去修改原来在2.4.1节中给出的那些过程的名字。
位于这两个弱点之下的基础问题是，上面这种实现通用型界面的技术不具有可加性。在每次增加一种新表示形式时，实现通用选择函数的人都必须修改他们的过程，而那些做独立表示的界面的人也必须修改其代码，以避免名字冲突问题。在做这些事情时，所有修改都必须直接对代码去做，而且必须准确无误。这当然会带来极大的不便，而且还很容易引进错误。对于上面这样的复数系统，这种修改还不是什么大问题。但如果假定现在需要处理的不是复数的两种表示形式，而是几百种不同表示形式，假定在抽象数据界面上有许许多多需要维护的通用型选择函数，再假定（事实上）没有一个程序员了解所有的界面过程和表示形式，情况又会怎样呢？在例如大规模的数据库管理系统中，这一问题是现实存在，且必须去面对的。
现在我们需要的是一种能够将系统设计进一步模块化的方法。一种称为数据导向的程序设计的编程技术提供了这种能力。为了理解数据导向的程序设计如何工作，我们首先应该看到，在需要处理的是针对不同类型的一集公共通用型操作时，事实上，我们正是在处理一个二维表格，其中的一个维上包含着所有的可能操作，另一个维就是所有的可能类型。表格中的项目是一些过程，它们针对作为参数的每个类型实现每一个操作。在前一节中开发的复数系统里，操作名字、数据类型和实际过程之间的对应关系散布在各个通用界面过程的各个条件子句里，我们也可以将同样的信息组织为一个表格，如图2-22所示。

数据导向的程序设计就是一种使程序能直接利用这种表格工作的程序设计技术。在我们前面的实现里，是采用一集过程作为复数算术与两个表示包之间的界面，并让这些过程中的每一个去做基于类型的显式分派。下面我们要把这一界面实现为一个过程，由它用操作名和参数类型的组合到表格中查找，以便找出应该调用的适当过程，并将这一过程应用于参数的内容。如果能做到这些，再把一种新的表示包加入系统里，我们就不需要修改任何现存的过程，而只要在这个表格里添加一些新的项目即可。
为了实现这一计划，现在假定有两个过程put和get，用于处理这种操作-类型表格：

• (put <op> <type> <item>)

将项<item>加入表格中，以<op>和<type>作为这个表项的索引。

• (get <op> <type>)

在表中查找与<op>和<type>对应的项，如果找到就返回找到的项，否则就返回假。
从现在起，我们将假定put和get已经包含在所用的语言里。在第3章里（3.3.3节，练习3.24）可以看到如何实现这些函数，以及其他操作表格的过程。
下面我们要说明，这种数据导向的程序设计如何用于复数系统。在开发了直角坐标表示时，Ben完全按他原来所做的那样实现了自己的代码，他定义了一组过程或者说一个程序包，并通过向表格中加入一些项的方式，告诉系统如何去操作直角坐标形式表示的数，这样就建立起了与系统其他部分的界面。完成此事的方式就是调用下面的过程：

(define (install-rectangular-package)
  ;; internal procedures
  (define (real-part z) (car z))
  (define (imag-part z) (cdr z))
  (define (make-from-real-imag x y) (cons x y))
  (define (magnitude z)
    (sqrt (+ (square (real-part z))
             (square (imag-part z)))))
  (define (angle z)
    (atan (imag-part z) (real-part z)))
  (define (make-from-mag-ang r a) 
    (cons (* r (cos a)) (* r (sin a))))
  ;; interface to the rest of the system
  (define (tag x) (attach-tag 'rectangular x))
  (put 'real-part ?rectangular) real-part)
  (put 'imag-part ?rectangular) imag-part)
  (put 'magnitude ?rectangular) magnitude)
  (put 'angle ?rectangular) angle)
  (put 'make-from-real-imag 'rectangular 
       (lambda (x y) (tag (make-from-real-imag x y))))
  (put 'make-from-mag-ang 'rectangular 
       (lambda (r a) (tag (make-from-mag-ang r a))))
  'done)

请注意，这里的所有内部过程，与2.4.1节里Ben在自己独立工作中写出的过程完全一样，在将它们与系统的其他部分建立联系时，也不需要做任何修改。进一步说，由于这些过程定义都是上述安装过程内部的东西，Ben完全不必担心它们的名字会与直角坐标程序包外面的其他过程的名字相互冲突。为了能与系统里的其他部分建立起联系，Ben将他的real-part过程安装在操作名字real-part和类型（rectangular）之下，其他选择函数的情况也都与此类似。这一界面还定义了提供给外部系统的构造函数，它们也与Ben自己定义的构造函数一样，只是其中还需要完成添加标志的工作。
Alyssa的极坐标包与此类似：

(define (install-polar-package)
  ;; internal procedures
  (define (magnitude z) (car z))
  (define (angle z) (cdr z))
  (define (make-from-mag-ang r a) (cons r a))
  (define (real-part z)
    (* (magnitude z) (cos (angle z))))
  (define (imag-part z)
    (* (magnitude z) (sin (angle z))))
  (define (make-from-real-imag x y) 
    (cons (sqrt (+ (square x) (square y)))
          (atan y x)))
  ;; interface to the rest of the system
  (define (tag x) (attach-tag 'polar x))
  (put 'real-part ?polar) real-part)
  (put 'imag-part ?polar) imag-part)
  (put 'magnitude ?polar) magnitude)
  (put 'angle ?polar) angle)
  (put 'make-from-real-imag 'polar
       (lambda (x y) (tag (make-from-real-imag x y))))
  (put 'make-from-mag-ang 'polar 
       (lambda (r a) (tag (make-from-mag-ang r a))))
  'done)

虽然Ben和Alyssa两个人仍然使用着他们原来的过程定义，这些过程也有着同样的名字（例如real-part），但对于其他过程而言，这些定义都是内部的（参见1.1.8节），所以在这里不会出现名字冲突问题。
复数算术的选择函数通过一个通用的名为apply-generic的“操作”过程访问有关表格，这个过程将通用型操作应用于一些参数。apply-generic在表格中用操作名和参数类型查找，如果找到，就去应用查找中得到的过程：

(define (apply-generic op . args)
  (let ((type-tags (map type-tag args)))
    (let ((proc (get op type-tags)))
      (if proc
          (apply proc (map contents args))
          (error
            "No method for these types -- APPLY-GENERIC"
            (list op type-tags))))))

利用apply-generic，各种通用型选择函数可以定义如下：

(define (real-part z) (apply-generic 'real-part z))
(define (imag-part z) (apply-generic 'imag-part z))
(define (magnitude z) (apply-generic 'magnitude z))
(define (angle z) (apply-generic 'angle z))

请注意，如果要将一个新表示形式加入这个系统，上述这些都完全不必修改。
我们同样可以从表中提取出构造函数，用到包之外的程序中，从实部和虚部或者模和幅角构造出复数来。就像在2.4.2节中那样，当我们有的是实部和虚部时就构造直角坐标表示的复数，有模和幅角时就构造极坐标的数：

(define (make-from-real-imag x y)
  ((get 'make-from-real-imag 'rectangular) x y))
(define (make-from-mag-ang r a)
  ((get 'make-from-mag-ang 'polar) r a))

练习2.73 2.3.2节描述了一个执行符号求导的程序：

(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp) (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
           (make-product (multiplier exp)
                         (deriv (multiplicand exp) var))
           (make-product (deriv (multiplier exp) var)
                         (multiplicand exp))))
        <更多规则可以加在这里>
        (else (error "unknown expression type -- DERIV" exp))))

可以认为，这个程序是在执行一种基于被求导表达式类型的分派工作。在这里，数据的“类型标志”就是代数运算符（例如＋），需要执行的操作是deriv。我们也可以将这一程序变换到数据导向的风格，将基本求导过程重新写成：

(define (deriv exp var)
   (cond ((number? exp) 0)
         ((variable? exp) (if (same-variable? exp var) 1 0))
         (else ((get 'deriv (operator exp)) (operands exp)
                                            var))))
(define (operator exp) (car exp))
(define (operands exp) (cdr exp))

a) 请解释上面究竟做了些什么。为什么我们无法将相近的谓词number?和same-variable?也加入数据导向分派中？
b) 请写出针对和式与积式的求导过程，并把它们安装到表格里，以便上面程序使用所需要的辅助性代码。
c) 请选择一些你希望包括的求导规则，例如对乘幂（练习2.56）求导等等，并将它们安装到这一数据导向的系统里。
d) 在这一简单的代数运算器中，表达式的类型就是构造起它们来的代数运算符。假定我们想以另一种相反的方式做索引，使得deriv里完成分派的代码行像下面这样：

((get (operator exp) 'deriv) (operands exp) var)

求导系统里还需要做哪些相应的改动？
练习2.74 Insatiable Enterprise公司是一个高度分散经营的联合公司，由大量分布在世界各地的分支机构组成。公司的计算机设施已经通过一种非常巧妙的网络连接模式连接成一体，它使得从任何一个用户的角度看，整个网络就像是一台计算机。在第一次试图利用网络能力从各分支机构的文件中提取管理信息时，Insatiable的总经理非常沮丧地发现，虽然所有分支机构的文件都被实现为Scheme的数据结构，但是各分支机构所用的数据结构却各不相同。她马上召集了各分支机构的经理会议，希望寻找一种策略集成起这些文件，以便在维持各个分支机构中现存独立工作方式的同时，又能满足公司总部管理的需要。
请说明这种策略可以如何通过数据导向的程序设计技术实现。作为例子，假定每个分支机构的人事记录都存放在一个独立文件里，其中包含了一集以雇员名字作为键值的记录。而有关集合的结构却由于分支机构的不同而不同。进一步说，某个雇员的记录本身又是一个集合（各分支机构所用的结构也不同），其中所包含的信息也在一些作为键值的标识符之下，例如address和salary。特别是考虑如下问题：
a) 请为公司总部实现一个get-record过程，使它能从一个特定的人事文件里提取出一个特定的雇员记录。这一过程应该能应用于任何分支机构的文件。请说明各个独立分支机构的文件应具有怎样的结构。特别是考虑，它们必须提供哪些类型信息？
b) 请为公司总部实现一个get-salary过程，它能从任何分支机构的人事文件中取得某个给定雇员的薪金信息。为了使这一操作能够工作，这些记录应具有怎样的结构？
c) 请为公司总部实现一个过程find-employee-record，该过程需要针对一个特定雇员名，在所有分支机构的文件去查找对应的记录，并返回找到的记录。假定这一过程的参数是一个雇员名和所有分支文件的表。
d) 当Insatiable购并新公司后，要将新的人事文件结合到系统中，必须做哪些修改？
消息传递
在数据导向的程序设计里，最关键的想法就是通过显式处理操作－类型表格（例如图2-22里的表格）的方式，管理程序中的各种通用型操作。我们在2.4.2节中所用的程序设计风格，是一种基于类型进行分派的组织方式，其中让每个操作管理自己的分派。从效果上看，这种方式就是将操作－类型表格分解为一行一行，每个通用型过程表示表格中的一行。
另一种实现策略是将这一表格按列进行分解，不是采用一批“智能操作”去基于数据类型进行分派，而是采用“智能数据对象”，让它们基于操作名完成所需的分派工作。如果我们想这样做，所需要做的就是做出一种安排，将每一个数据对象（例如一个采用直角坐标表示的复数）表示为一个过程。它以操作的名字作为输入，能够去执行指定的操作。按照这种方式，make-from-real-imag应该写成下面样子：

(define (make-from-real-imag x y)
  (define (dispatch op)
    (cond ((eq? op 'real-part) x)
          ((eq? op 'imag-part) y)
          ((eq? op 'magnitude)
           (sqrt (+ (square x) (square y))))
          ((eq? op 'angle) (atan y x))
          (else
           (error "Unknown op -- MAKE-FROM-REAL-IMAG" op))))
  dispatch)

与之对应的apply-generic过程应该对其参数应用一个通用型操作，此时它只需要简单地将操作名馈入该数据对象，并让那个对象去完成工作：
(define (apply-generic op arg) (arg op))
请注意，make-from-real-imag返回的值是一个过程—它内部的dispatch过程。这也就是当apply-generic要求执行一个操作时所调用的过程。
这种风格的程序设计称为消息传递，这一名字源自将数据对象设想为一个实体，它以“消息”的方式接收到所需操作的名字。在2.1.3节中我们已经看到过一个消息传递的例子，在那里看到的是如何用没有数据对象而只有过程的方式定义cons、car和cdr。现在我们看到的是，消息传递并不是一种数学机巧，而是一种有价值的技术，可以用于组织带有通用型操作的系统。在本章剩下的部分里，我们将要继续使用数据导向的程序设计（而不是用消息传递），进一步讨论通用型算术运算的问题。在第3章里我们将会回到消息传递，并在那里看到它可能怎样成为构造模拟程序的强有力工具。
练习2.75 请用消息传递的风格实现构造函数make-from-mag-ang。这一过程应该与上面给出的make-from-real-imag过程类似。
练习2.76 一个带有通用型操作的大型系统可能不断演化，在演化中常需要加入新的数据对象类型或者新的操作。对于上面提出的三种策略—带有显式分派的通用型操作，数据导向的风格，以及消息传递的风格—请描述在加入一个新类型或者新操作时，系统所必须做的修改。哪种组织方式最适合那些经常需要加入新类型的系统？哪种组织方式最适合那些经常需要加入新操作的系统？

2.5 带有通用型操作的系统

在前一节里，我们看到了如何去设计一个系统，使其中的数据对象可以以多于一种方式表示。这里的关键思想就是通过通用型界面过程，将描述数据操作的代码连接到几种不同表示上。现在我们将看到如何使用同样的思想，不但定义出能够在不同表示上的通用操作，还能定义针对不同参数种类的通用型操作。我们已经看到过几个不同的算术运算包：语言内部的基本算术（＋，－，*，/），2.1.1节的有理数算术（add-rat，sub-rat，mul-rat，div-rat），以及2.4.3节里实现的复数算术。现在我们要使用数据导向技术构造起一个算术运算包，将前面已经构造出的所有算术包都结合进去。
图2-23展示了我们将要构造的系统的结构。请注意其中的各抽象屏障。从某些使用“数值”的人的观点看，在这里只存在一个过程add，无论提供给它的数是什么。add是通用型界面的一部分，这一界面将使那些使用数的程序能以一种统一的方式，访问相互分离的常规算术、有理数算术和复数算术程序包。任何独立的算术程序包（例如复数包）本身也可能通过通用型过程（例如add-complex）访问，它也可能由针对不同表示形式设计的包（直角坐标表示和极坐标表示）组合而成。进一步说，这一系统具有可加性，这样，人们还可以设计出其他独立的算术包，并将其组合到这一通用型的算术系统中。

2.5.1 通用型算术运算

设计通用型算术运算的工作类似于设计通用型复数运算。我们希望（例如）有一个通用型的加法过程add，对于常规的数，它的行为就像常规的基本加法＋；对于有理数，它就像add-rat，对于复数就像add-complex。我们可以沿用在2.4.3节为实现复数上的通用选择函数所用的同样策略，去实现add和其他通用算术运算。下面将为每种数附着一个类型标志，以便通用型过程能够根据其参数的类型完成到某个适用的程序包的分派。
通用型算术过程的定义如下：

(define (add x y) (apply-generic 'add x y))
(define (sub x y) (apply-generic 'aub x y))
(define (mul x y) (apply-generic 'mul x y))
(define (div x y) (apply-generic 'div x y))

下面我们将从安装处理常规数（即，语言中基本的数）的包开始，对这种数采用的标志是符号scheme-number。这个包里的算术运算都是基本算术过程（因此不需要再定义过程去处理无标志的数）。因为每个操作都有两个参数，所以用表（scheme-number scheme-number）作为表格中的键值去安装它们：

(define (install-scheme-number-package)
  (define (tag x)
    (attach-tag 'acheme-number x))    
  (put 'add ?scheme-number scheme-number)
       (lambda (x y) (tag (+ x y))))
  (put 'aub ?scheme-number scheme-number)
       (lambda (x y) (tag (- x y))))
  (put 'mul ?scheme-number scheme-number)
       (lambda (x y) (tag (* x y))))
  (put 'div ?scheme-number scheme-number)
       (lambda (x y) (tag (/ x y))))
  (put 'make 'acheme-number
       (lambda (x) (tag x)))
  'done)

Scheme数值包的用户可以通过下面过程，创建带标志的常规数：

(define (make-scheme-number n)
  ((get 'make 'acheme-number) n))

现在我们已经做好了通用型算术系统的框架，可以将新的数类型加入其中了。下面是一个执行有理数算术的程序包。请注意，由于具有可加性，我们可以直接把取自2.1.1节的有理数代码作为这个程序包的内部过程，完全不必做任何修改：

(define (install-rational-package)
  ;; internal procedures
  (define (numer x) (car x))
  (define (denom x) (cdr x))
  (define (make-rat n d)
    (let ((g (gcd n d)))
      (cons (/ n g) (/ d g))))
  (define (add-rat x y)
    (make-rat (+ (* (numer x) (denom y))
                 (* (numer y) (denom x)))
              (* (denom x) (denom y))))
  (define (sub-rat x y)
    (make-rat (- (* (numer x) (denom y))
                 (* (numer y) (denom x)))
              (* (denom x) (denom y))))
  (define (mul-rat x y)
    (make-rat (* (numer x) (numer y))
              (* (denom x) (denom y))))
  (define (div-rat x y)
    (make-rat (* (numer x) (denom y))
              (* (denom x) (numer y))))
  ;; interface to rest of the system
  (define (tag x) (attach-tag 'rational x))
  (put 'add ?rational rational)
       (lambda (x y) (tag (add-rat x y))))
  (put 'aub ?rational rational)
       (lambda (x y) (tag (sub-rat x y))))
  (put 'mul ?rational rational)
       (lambda (x y) (tag (mul-rat x y))))
  (put 'div ?rational rational)
       (lambda (x y) (tag (div-rat x y))))
  (put 'make 'rational
       (lambda (n d) (tag (make-rat n d))))
  'done)
(define (make-rational n d)
  ((get 'make 'rational) n d))

我们可以安装上另一个处理复数的类似程序包，采用的标志是complex。在创建这个程序包时，我们要从表格里抽取出操作make-from-real-imag和make-from-mag-ang，它们原来分别定义在直角坐标和极坐标包里。可加性使我们能把取自2.4.1节同样的add-complex、sub-complex、mul-complex和div-complex过程用作内部操作。

(define (install-complex-package)
  ;; imported procedures from rectangular and polar packages
  (define (make-from-real-imag x y)
    ((get 'make-from-real-imag 'rectangular) x y))
  (define (make-from-mag-ang r a)
    ((get 'make-from-mag-ang 'polar) r a))
  ;; internal procedures
  (define (add-complex z1 z2)
    (make-from-real-imag (+ (real-part z1) (real-part z2))
                         (+ (imag-part z1) (imag-part z2))))
  (define (sub-complex z1 z2)
    (make-from-real-imag (- (real-part z1) (real-part z2))
                         (- (imag-part z1) (imag-part z2))))
  (define (mul-complex z1 z2)
    (make-from-mag-ang (* (magnitude z1) (magnitude z2))
                       (+ (angle z1) (angle z2))))
  (define (div-complex z1 z2)
    (make-from-mag-ang (/ (magnitude z1) (magnitude z2))
                       (- (angle z1) (angle z2))))
  ;; interface to rest of the system
  (define (tag z) (attach-tag 'complex z))
  (put 'add ?complex complex)
       (lambda (z1 z2) (tag (add-complex z1 z2))))
  (put 'aub ?complex complex)
       (lambda (z1 z2) (tag (sub-complex z1 z2))))
  (put 'mul ?complex complex)
       (lambda (z1 z2) (tag (mul-complex z1 z2))))
  (put 'div ?complex complex)
       (lambda (z1 z2) (tag (div-complex z1 z2))))
  (put 'make-from-real-imag 'complex
       (lambda (x y) (tag (make-from-real-imag x y))))
  (put 'make-from-mag-ang 'complex
       (lambda (r a) (tag (make-from-mag-ang r a))))
  'done)

在复数包之外的程序可以从实部和虚部出发构造复数，也可以从模和幅角出发。请注意这里如何将原先定义在直角坐标和极坐标包里的集成过程导出，放入复数包中，又如何从这里导出送给外面的世界。

(define (make-complex-from-real-imag x y)
  ((get 'make-from-real-imag 'complex) x y))
(define (make-complex-from-mag-ang r a)
  ((get 'make-from-mag-ang 'complex) r a))

这里描述的是一个具有两层标志的系统。一个典型的复数如直角坐标表示的3＋4i，现在的表示形式如图2-24所示。外层标志（complex）用于将这个数引导到复数包，一旦进入复数包，下一个标志（rectangular）就会引导这个数进入直角坐标表示包。在一个大型的复杂系统里可能有许多层次，每层与下一层次之间的连接都借助于一些通用型操作。当一个数据对象被“向下”传输时，用于引导它进入适当程序包的最外层标志被剥除（通过使用contents），下一层次的标志（如果有的话）变成可见的，并将被用于下一次分派。

在上面这些程序包里，我们使用了add-rat、add-complex以及其他算术过程，完全按照它们原来写出的形式。一旦把这些过程定义为不同安装过程内部的东西，它们的名字就没有必要再相互不同了，可以在两个包中都简单地将它们命名为add、sub、mul和div。
练习2.77 Louis Reasoner试着去求值（magnitude z），其中的z就是图2-24里的那个对象。令他吃惊的是，从apply-generic出来的不是5而是一个错误信息，说没办法对类型（complex）做操作magnitude。他将这次交互的情况给Alyssa P. Hacker看，Alyssa说“问题出在没有为complex数定义复数选择函数，而只是为polar和rectangular数定义了它们。你需要做的就是在complex包里加入下面这些东西”：

(put 'real-part '(complex) real-part)
(put 'imag-part '(complex) imag-part)
(put 'magnitude '(complex) magnitude)
(put 'angle '(complex) angle)

请详细说明为什么这样做是可行的。作为一个例子，请考虑表达式（magnitude z）的求值过程，其中z就是图2-24里展示的那个对象，请追踪一下这一求值过程中的所有函数调用。特别是看看apply-generic被调用了几次？每次调用中分派的是哪个过程？
练习2.78 包scheme-number里的内部过程几乎什么也没做，只不过是去调用基本过程＋、－等等。直接使用语言的基本过程当然是不可能的，因为我们的类型标志系统要求每个数据对象都附加一个类型。然而，事实上所有Lisp实现都有自己的类型系统，使用在系统实现的内部，基本谓词symbol?和number?等用于确定某个数据对象是否具有特定的类型。请修改2.4.2节中type-tag、contents和attach-tag的定义，使我们的通用算术系统可以利用Scheme的内部类型系统。这也就是说，修改后的系统应该像原来一样工作，除了其中常规的数直接采用Scheme的数形式，而不是表示为一个car部分是符号scheme-number的序对。
练习2.79 请定义一个通用型相等谓词equ?，它能检查两个数是否相等。请将它安装到通用算术包里。这一操作应该能处理常规的数、有理数和复数。
练习2.80 请定义一个通用谓词＝zero?，检查其参数是否为0，并将它安装到通用算术包里。这一操作应该能处理常规的数、有理数和复数。

2.5.2 不同类型数据的组合

前面已经看到了如何定义出一个统一的算术系统，其中包含常规的数、复数和有理数，以及我们希望发明的任何其他数值类型。但在那里也忽略了一个重要的问题。我们至今定义的所有运算，都把不同数据类型看作相互完全分离的东西，也就是说，这里有几个完全分离的程序包，它们分别完成两个常规的数，或者两个复数的加法。我们至今还没有考虑的问题是下面事实：定义出能够跨过类型界限的操作也很有意义，譬如完成一个复数和一个常规数的加法。在前面，我们一直煞费苦心地在程序的各个部分之间引进了屏障，以使它们能够分别开发和分别理解。现在却又要引进跨类型的操作。当然，我们必须以一种经过精心考虑的可控方式去做这件事情，以使我们在支持这种操作的同时又没有严重地损害模块间的分界。
处理跨类型操作的一种方式，就是为每一种类型组合的合法运算设计一个特定过程。例如，我们可以扩充复数包，使它能提供一个过程用于加起一个复数和一个常规的数，并用标志（complex scheme-number）将它安装到表格里：

;; to be included in the complex package
(define (add-complex-to-schemenum z x)
  (make-from-real-imag (+ (real-part z) x)
                       (imag-part z)))
(put 'add ?complex scheme-number)
     (lambda (z x) (tag (add-complex-to-schemenum z x))))

这一技术确实可以用，但也非常麻烦。对于这样的一个系统，引进一个新类型的代价就不仅仅需要构造出针对这一类型的所有过程的包，还需要构造并安装好所有实现跨类型操作的过程。后一件事所需要的代码很容易就会超过定义类型本身所需的那些操作。这种方法也损害了以添加方式组合独立开发的程序包的能力，至少给独立程序包的实现者增加了一些限制，要求他们在对独立程序包工作时，必须同时关注其他的程序包。比如，在上面例子里，如果要处理复数和常规数的混合运算，将其看作复数包的责任是合理的。然而，有关有理数和复数的组合工作却存在许多选择，完全可以由复数包、有理数包，或者由另外的，使用了从前面两个包中取出的操作的第三个包完成。在设计包含许多程序包和许多跨类型操作的系统时，要想规划好一套统一的策略，分清各种包之间的责任，很容易变成非常复杂的任务。
强制
最一般的情况是需要处理针对一批完全无关的类型的一批完全无关的操作，直接实现跨类型操作很可能就是解决问题的最好方式了，当然，这样做起来确实比较麻烦。幸运的是，我们常常可以利用潜藏在类型系统之中的一些额外结构，将事情做得更好些。不同的数据类型通常都不是完全相互无关的，常常存在一些方式，使我们可以把一种类型的对象看作另一种类型的对象。这种过程就称为强制。举例来说，如果现在需要做常规数值与复数的混合算术，我们就可以将常规数值看成是虚部为0的复数。这样就把问题转换为两个复数的运算问题，可以由复数包以正常的方式处理了。
一般而言，要实现这一想法，我们可以设计出一些强制过程，它们能把一个类型的对象转换到另一类型的等价对象。下面是一个典型的强制过程，它将给定的常规数值转换为一个复数，其中的实部为原来的数而虚部是0：

(define (scheme-number->complex n)
  (make-complex-from-real-imag (contents n) 0))

我们将这些强制过程安装到一个特殊的强制表格中，用两个类型的名字作为索引：

(put-coercion 'acheme-number 'complex scheme-number->complex)

（这里假定了存在着用于操纵这个表格的put-coercion和get-coercion过程。）一般而言，这一表格里的某些格子将是空的，因为将任何数据对象转换到另一个类型并不是都能做的。例如并不存在某种将任意复数转换为常规数值的方式，因此，这个表格中就不应包括一般性的complex->scheme-number过程。
一旦将上述转换表格装配好，我们就可以修改2.4.3节的apply-generic过程，得到一种处理强制的统一方法。在要求应用一个操作时，我们将首先检查是否存在针对实际参数类型的操作定义，就像前面一样。如果存在，那么就将任务分派到由操作－类型表格中找出的相应过程去，否则就去做强制。为了简化讨论，这里只考虑两个参数的情况。我们检查强制表格，查看其中第一个参数类型的对象能否转换到第二个参数的类型。如果可以，那就对第一个参数做强制后再试验操作。如果第一个参数类型的对象不能强制到第二个类型，那么就试验另一种方式，看看能否从第二个参数的类型转换到第一个参数的类型。最后，如果不存在从一个类型到另一类型的强制，那么就只能放弃了。下面是这个过程：

(define (apply-generic op . args)
  (let ((type-tags (map type-tag args)))
    (let ((proc (get op type-tags)))
      (if proc
          (apply proc (map contents args))
          (if (= (length args) 2)
              (let ((type1 (car type-tags))
                    (type2 (cadr type-tags))
                    (a1 (car args))
                    (a2 (cadr args)))
                (let ((t1->t2 (get-coercion type1 type2))
                      (t2->t1 (get-coercion type2 type1)))
                  (cond (t1->t2
                         (apply-generic op (t1->t2 a1) a2))
                        (t2->t1
                         (apply-generic op a1 (t2->t1 a2)))
                        (else
                         (error "No method for these types"
                                (list op type-tags))))))
              (error "No method for these types"
                     (list op type-tags)))))))

与显式定义的跨类型操作相比，这种强制模式有许多优越性。就像在上面已经说过的。虽然我们仍然需要写出一些与各种类型有关的强制过程（对于n个类型的系统可能需要n2个过程），但是却只需要为每一对类型写一个过程，而不是为每对类型和每个通用型操作写一个过程。能够这样做的基础就是，类型之间的适当转换只依赖于类型本身，而不依赖于所实际应用的操作。
另一方面，也可能存在一些应用，对于它们而言我们的强制模式还不足够一般。即使需要运算的两种类型的对象都不能转换到另一种类型，也完全可能在将这两种类型的对象都转换到第三种类型后执行这一运算。为了处理这种复杂性，同时又能维持我们系统的模块性，通常就需要在建立系统时利用类型之间的进一步结构，有关情况见下面的讨论。

类型的层次结构
上面给出的强制模式，依赖于一对对类型之间存在着某种自然的关系。在实际中，还常常存在着不同类型间相互关系的更“全局性”的结构。例如，假定我们想要构造出一个通用型的算术系统，处理整数、有理数、实数、复数。在这样的一个系统里，一种很自然的做法是把整数看作是一类特殊的有理数，而有理数又是一类特殊的实数，实数转而又是一类特殊的复数。这样，我们实际有的就是一个所谓的类型的层次结构，在其中，（例如）整数是有理数的子类型（也就是说，任何可以应用于有理数的操作都可以应用于整数）。与此相对应，人们也说有理数形成了整数的一个超类型。在这个例子里所看到的类型层次结构是最简单的一种，其中一个类型只有至多一个超类型和至多一个子类型。这样的结构称为一个类型塔，如图2-25所示。

如果我们面对的是一个塔结构，那么将一个新类型加入层次结构的问题就可能极大地简化了，因为需要做的所有事情，也就是刻画清楚这一新类型将如何嵌入正好位于它之上的超类型，以及它如何作为下面一个类型的超类型。举例说，如果我们希望做一个整数和一个复数的加法，那么并不需要明确定义一个特殊强制函数integer->complex。相反，我们可以定义如何将整数转换到有理数，如何将有理数转换到实数，以及如何将实数转换到复数。而后让系统通过这些步骤将该整数转换到复数，在此之后再做两个复数的加法。
我们可以按照下面的方式重新设计那个apply-generic过程。对于每个类型，都需要提供一个raise过程，它将这一类型的对象“提升”到塔中更高一层的类型。此后，当系统遇到需要对两个不同类型的运算时，它就可以逐步提升较低的类型，直至所有对象都达到了塔的同一个层次（练习2.83和练习2.84关注的就是实现这种策略的一些细节）。
类型塔的另一优点，在于使我们很容易实现一种概念：每个类型能够“继承”其超类型中定义的所有操作。举例说，如果我们没有为找出整数的实部提供一个特定过程，但也完全可能期望real-part过程对整数有定义，因为事实上整数是复数的一个子类型。对于类型塔的情况，我们可以通过修改apply-generic过程，以一种统一的方式安排好这些事情。如果所需操作在给定对象的类型中没有明确定义，那么就将这个对象提升到它的超类型并再次检查。在向塔顶攀登的过程中，我们也不断转换有关的参数，直至在某个层次上找到了所需的操作而后去执行它，或者已经到达了塔顶（此时就只能放弃了）。
与其他层次结构相比，塔形结构的另一优点是它使我们有一种简单的方式去“下降”一个数据对象，使之达到最简单的表示形式。例如，如果现在做了2＋3i和4－3i的加法，如果结果是整数6而不是复数6＋0i当然就更好了。练习2.85讨论了实现这种下降操作的一种方式。这里的技巧在于需要有一种一般性的方式，分辨出哪些是可以下降的对象（例如6＋0i），哪些是不能下降的对象（例如6＋2i）。

层次结构的不足
如果在一个系统里，有关的数据类型可以自然地安排为一个塔形，那么正如在前面已经看到的，处理不同类型上通用型操作的问题将能得到极大的简化。遗憾的是，事情通常都不是这样。图2-26展示的是类型之间关系的一种更复杂情况，其中显示出的是表示几何图形的各种类型之间的关系。从这个图里可以看到，一般而言，一个类型可能有多于一个子类型，例如三角形和四边形都是多边形的子类型。此外，一个类型也可能有多于一个超类型，例如，等腰直角三角形可以看作是等腰三角形，又可以看作是直角三角形。这种存在多重超类型的问题特别令人棘手，因为这就意味着，并不存在一种唯一方式在层次结构中去“提升”一个类型。当我们需要将一个操作应用于一个对象时，为此而找出“正确”超类型的工作（例如，这就是apply-generic这类过程中的一部分）可能涉及对整个类型网络的大范围搜索。由于一般说一个类型存在着多个子类型，需要在类型层次结构中“下降”一个值时也会遇到类似的问题。在设计大型系统时，处理好一大批相互有关的类型而同时又能保持模块性，这是一个非常困难的问题，也是当前正在继续研究的一个领域。

练习2.81 Louis Reasoner注意到，甚至在两个参数的类型实际相同的情况下，apply-generic也可能试图去做参数间的类型强制。由此他推论说，需要在强制表格中加入一些过程，以将每个类型的参数“强制”到它们自己的类型。例如，除了上面给出的scheme-number->complex强制之外，他觉得应该有：

(define (scheme-number->scheme-number n) n)
(define (complex->complex z) z)
(put-coercion 'acheme-number 'acheme-number
              scheme-number->scheme-number)
(put-coercion 'complex 'complex complex->complex)

a) 如果安装了Louis的强制过程，如果在调用apply-generic时各参数的类型都为scheme-number或者类型都为complex，而在表格中又找不到相应的操作，这时会出现什么情况？例如，假定我们定义了一个通用型的求幂运算：

(define (exp x y) (apply-generic 'exp x y))

并在Scheme数值包里放入了一个求幂过程，但其他程序包里都没有：

;; following added to Scheme-number package
(put 'exp ?scheme-number scheme-number)
     (lambda (x y) (tag (expt x y)))) ; using primitive expt

如果对两个复数调用exp会出现什么情况？
b) Louis真的纠正了有关同样类型参数的强制问题吗？apply-generic还能像原来那样正确工作吗？
c) 请修改apply-generic，使之不会试着去强制两个同样类型的参数。
练习2.82 请阐述一种方法，设法推广apply-generic，以便处理多个参数的一般性情况下的强制问题。一种可能策略是试着将所有参数都强制到第一个参数的类型，而后试着强制到第二个参数的类型，并如此试下去。请给出一个例子说明这种策略还不够一般（就像上面对两个参数的情况给出的例子那样）。（提示：请考虑一些情况，其中表格里某些合用的操作将不会被考虑。）
练习2.83 假定你正在设计一个通用型的算术包，处理图2-25所示的类型塔，包括整数、有理数、实数和复数。请为每个类型（除复数外）设计一个过程，它能将该类型的对象提升到塔中的上面一层。请说明如何安装一个通用的raise操作，使之能对各个类型工作（除复数之外）。
练习2.84 利用练习2.83的raise操作修改apply-generic过程，使它能通过逐层提升的方式将参数强制到同样的类型，正如本节中讨论的。你将需要安排一种方式，去检查两个类型中哪个更高。请以一种能与系统中其他部分“相容”，而且又不会影响向塔中加入新层次的方式完成这一工作。
练习2.85 本节中提到了“简化”数据对象表示的一种方法，就是使之在类型塔中尽可能地下降。请设计一个过程drop（下落），使它能在如练习2.83所描述的类型塔中完成这一工作。这里的关键是以某种一般性的方式，判断一个数据对象能否下降。举例来说，复数 1.5＋0i至多可以下降到real，复数1＋0i至多可以下降到integer，而复数2＋3i就根本无法下降。现在提出一种确定一个对象能否下降的计划：首先定义一个运算project（投影），它将一个对象“压”到塔的下面一层。例如，投影一个复数就是丢掉其虚部。这样，一个数能够向下落，如果我们首先project它而后将得到的结果raise到开始的类型，最终得到的东西与开始的东西相等。请阐述实现这一想法的具体细节，并写出一个drop过程，使它可以将一个对象尽可能地下落。你将需要设计各种各样的投影函数119，并需要把project安装为系统里的一个通用型操作。你还需要使用一个通用型的相等谓词，例如练习2.79所描述的。最后，请利用drop重写练习2.84的apply-generic，使之可以“简化”其结果。
练习2.86 假定我们希望处理一些复数，它们的实部、虚部、模和幅角都可以是常规数值、有理数，或者我们希望加入系统的任何其他数值类型。请描述和实现系统需要做的各种修改，以满足这一需要。你应设法将例如sine和cosine一类的运算也定义为在常规数和有理数上的通用运算。

2.5.3 实例：符号代数

符号表达式的操作是一种很复杂的计算过程，它能够展示出在设计大型系统时常常会出现的许多困难问题。一般来说，一个代数表达式可以看成一种具有层次结构的东西，它是将运算符作用于一些运算对象而形成的一棵树。我们可以从一集基本对象，例如常量和变量出发，通过各种代数运算符如加法和乘法的组合，构造起各种各样的代数表达式。就像在其他语言里一样，在这里也需要形成各种抽象，使我们能够有简单的方式去引用复合对象。在符号代数中，与典型抽象的有关想法包括线性组合、多项式、有理函数和三角函数等等。可以将这些看作是复合的“类型”，它们在制导对表达式的处理过程方面非常有用。例如，我们可以将表达式：

x2 sin (y2＋1)＋x cos 2y＋cos (y3－2y2)

看作一个x的多项式，其参数是y的多项式的三角函数，而y的多项式的系数是整数。
下面我们将试着开发一个完整的代数演算系统。这类系统都是异乎寻常地复杂的程序，包含着深入的代数知识和美妙的算法。我们将要做的，只是考察代数演算系统中一个简单但却很重要的部分，多项式算术。我们将展示在设计这样一个系统时所面临的各种抉择，以及如何应用抽象数据和通用型操作的思想，以利于组织好这一工作项目。
多项式算术
要设计一个执行多项式算术的系统，第一件事情就是确定多项式到底是什么。多项式通常总是针对某些特定的变量（多项式中的未定元）定义的。为了简单起见，我们把需要考虑的多项式限制到只有一个未定元的情况（单变元多项式）。下面将多项式定义为项的和式，而每个项或者就是一个系数，或者是未定元的乘方，或者是一个系数与一个未定元乘方的乘积。系数也定义为一个代数表达式，但它不依赖于这个多项式的未定元。例如：

5x2＋3x＋7

是x的一个简单多项式，而

(y2＋1) x3＋(2y) x＋1

是x的一个多项式，而其参数又是y的多项式。
这样，我们就已经绕过了某些棘手问题。例如，上面的第一个多项式是否与多项式5y2＋3y＋7相同？为什么？合理的回答可以是“是，如果我们将多项式看作一种纯粹的数学函数；但又不是，如果只是将多项式看作一种语法形式”。第二个多项式在代数上等价于一个y的多项式，其系数是x的多项式。我们的系统将应认定这一情况吗，或者不认定？进一步说，表示一个多项式的方式可以有很多种—例如，将其作为因子的乘积，或者（对于单变元多项式）作为一组根，或者作为多项式在些特定集合里各个点处的值的列表。我们可以使一点手段以避免这些问题。现在我们确定，在这一代数演算系统里，一个“多项式”就是一种特殊的语法形式，而不是在其之下的数学意义。
现在必须进一步去考虑怎样做多项式算术。在这个简单的系统里，我们将仅仅考虑加法和乘法。进一步说，我们还强制性地要求两个参与运算的多项式具有相同的未定元。
下面将根据我们已经熟悉的数据抽象的一套方式，开始设计这个系统。多项式将用一种称为poly的数据结构表示，它由一个变量和一组项组成。我们假定已有选择函数variable 和term-list，用于从一个多项式中提取相应的部分。还有一个构造函数make-poly，从给定变量和项表构造出一个多项式。一个变量也就是一个符号，因此我们可以用2.3.2节的same-variable?过程做变量的比较。下面过程定义多项式的加法和乘法：

define (add-poly p1 p2)
  (if (same-variable? (variable p1) (variable p2))
      (make-poly (variable p1)
                 (add-terms (term-list p1)
                            (term-list p2)))
      (error "Polys not in same var -- ADD-POLY"
             (list p1 p2))))
(define (mul-poly p1 p2)
  (if (same-variable? (variable p1) (variable p2))
      (make-poly (variable p1)
                 (mul-terms (term-list p1)
                            (term-list p2)))
      (error "Polys not in same var -- MUL-POLY"
             (list p1 p2))))

为了将多项式结合到前面建立起来的通用算术系统里，我们需要为其提供类型标志。这里采用标志polynomial，并将适合用于带标志多项式的操作安装到操作表格里。我们将所有代码都嵌入完成多项式包的安装过程中，与在2.5.1节里采用的方式类似：

(define (install-polynomial-package)
  ;; internal procedures
  ;; representation of poly
  (define (make-poly variable term-list)
    (cons variable term-list))
  (define (variable p) (car p))
  (define (term-list p) (cdr p))
  <过程 same-variable? 和 variable? 取自2.3.2节>
  ;; representation of terms and term lists
  <过程 adjoin-term ...coeff 在下面定义>
  (define (add-poly p1 p2) ...)
  <add-poly 使用的过程>
  (define (mul-poly p1 p2) ...)
  <mul-poly 使用的过程>
  ;; interface to rest of the system
  (define (tag p) (attach-tag 'polynomial p))
  (put 'add ?polynomial polynomial) 
       (lambda (p1 p2) (tag (add-poly p1 p2))))
  (put 'mul ?polynomial polynomial) 
       (lambda (p1 p2) (tag (mul-poly p1 p2))))
  (put 'make 'polynomial
       (lambda (var terms) (tag (make-poly var terms))))
  'done)

多项式加法通过一项项的相加完成，同次的项（即，具有同样未定元幂次的项）必须归并到一起。完成这件事的方式是建立一个同次的新项，其系数是两个项的系数之和。仅仅出现在一个求和多项式中的项就直接累积到正在构造的多项式里。
为了能完成对于项表的操作，我们假定有一个构造函数the-empty-termlist，它返回一个空的项表，还有一个构造函数adjoin-term将一个新项加入一个项表里。我们还假定有一个谓词empty-termlist?，可用于检查一个项表是否为空；选择函数first-term提取出一个项表中最高次数的项，选择函数rest-terms返回除最高次项之外的其他项的表。为了能对项进行各种操作，我们假定已经有一个构造函数make-term，它从给定的次数和系数构造出一个项；选择函数order和coeff分别返回一个项的次数和系数。这些操作使我们可以将项和项表都看成数据抽象，其具体实现就可以另行单独考虑了。
下面是一个过程，它从两个需要求和的多项式构造起一个项表：

(define (add-terms L1 L2)
  (cond ((empty-termlist? L1) L2)
        ((empty-termlist? L2) L1)
        (else
         (let ((t1 (first-term L1)) (t2 (first-term L2)))
           (cond ((> (order t1) (order t2))
                  (adjoin-term
                   t1 (add-terms (rest-terms L1) L2)))
                 ((< (order t1) (order t2))
                  (adjoin-term
                   t2 (add-terms L1 (rest-terms L2))))
                 (else
                  (adjoin-term
                   (make-term (order t1)
                              (add (coeff t1) (coeff t2)))
                   (add-terms (rest-terms L1)
                              (rest-terms L2)))))))))

在这里需要注意的最重要的地方是，我们采用了通用型的加法过程add去求需要归并的项的系数之和。这样做有一个特别有利的后果，下面就会看到。
为了乘起两个项表，我们用第一个表中的每个项去乘另一表中所有的项，通过反复应用mul-term-by-all-terms（这个过程用一个给定的项去乘一个项表里的各个项）完成项表的乘法。这样得到的结果项表（对于第一个表的每个项各有一个表）通过求和积累起来。乘起两个项形成一个新项的方式是求出两个因子的次数之和作为结果项的次数，求出两个因子的系数的乘积作为结果项的系数：

(define (mul-terms L1 L2)
  (if (empty-termlist? L1)
      (the-empty-termlist)
      (add-terms (mul-term-by-all-terms (first-term L1) L2)
                 (mul-terms (rest-terms L1) L2))))
(define (mul-term-by-all-terms t1 L)
  (if (empty-termlist? L)
      (the-empty-termlist)
      (let ((t2 (first-term L)))
        (adjoin-term
         (make-term (+ (order t1) (order t2))
                    (mul (coeff t1) (coeff t2)))
         (mul-term-by-all-terms t1 (rest-terms L))))))

这些也就是多项式加法和乘法的全部了。请注意，因为我们这里的操作都是基于通用型过程add和mul描述的，所以这个多项式包将自动地能够处理任何系数类型，只要它是这里的通用算术程序包能够处理的。如果我们还把2.5.2节所讨论的强制机制也包括进来，那么我们也就自动地有了能够处理不同系数类型的多项式操作的能力，例如

由于我们已经把多项式的求和、求乘积的过程add-poly和mul-poly作为针对类型polynomial的操作，安装进通用算术系统的add和mul操作里，这样得到的系统将能自动处理如下的多项式操作：

能够完成此事的原因是，当系统试图去归并系数时，它将通过add和mul进行分派。由于这时的系数本身也是多项式（y的多项式），它们将通过使用add-poly和mul-poly完成组合。这样就产生出一种“数据导向的递归”，举例来说，在这里，对mul-poly的调用中还会递归地调用mul-poly，以便去求系数的乘积。如果系数的系数仍然是多项式（在三个变元的多项式中可能出现这种情况），数据导向就会保证这一系统仍能进入另一层递归调用，并能这样根据被处理数据的结构进入任意深度的递归调用。
项表的表示
我们最后面临的工作，就是需要为项表实现一种很好的表示形式。从作用上看，一个项表就是一个以项的次数作为键值的系数集合，因此，任何能够用于有效表示集合的方法（见2.2.3节的讨论）都可以用于完成这一工作。但另一方面，我们所用的过程add-terms和mul-terms都以顺序方式进行访问，按照从最高次项到最低次项的顺序，因此应该考虑采用某种有序表表示。
我们应该如何构造表示项表的表结构呢？有一个需要考虑的因素是可能需要操作的多项式的“密度”。一个多项式称为稠密的，如果它大部分次数的项都具有非0系数。如果一个多项式有许多系数为0的项，那么就称它是稀疏的。例如：

A :   x5＋2x4＋3x2－2x－5

是稠密的，而

B :   x100＋2x2＋1

是稀疏的。
对于稠密多项式而言，项表的最有效表示方式就是直接采用其系数的表。例如，上面的多项式A可以很好地表示为（1 2 0 3 -2 -5）。在这种表示中，一个项的次数也就是从这个项开始的子表的长度减1124。对于像B那样的稀疏多项式，这种表示将变得十分可怕，因为它将是一个很大的几乎全都是0值的表，其中零零落落地点缀着几个非0项。对于稀疏多项式有一种更合理方式，那就是将它们表示为非0项的表，表中的每一项包含着多项式里的一个次数和对应于这个次数的系数。按照这种模式，多项式B可以有效地表示为（（100 1）（2 2）（0 1））。由于被操作的大部分多项式运算都是稀疏多项式，我们采用后一种方式。现在假定项表被表示为项的表，按照从最高次到最低次的顺序安排。一旦我们做出了这一决定，为项表实现选择函数和构造函数就已经直截了当了。

(define (adjoin-term term term-list)
  (if (=zero? (coeff term))
      term-list
      (cons term term-list)))
(define (the-empty-termlist) '())
(define (first-term term-list) (car term-list))
(define (rest-terms term-list) (cdr term-list))
(define (empty-termlist? term-list) (null? term-list))
(define (make-term order coeff) (list order coeff))
(define (order term) (car term))
(define (coeff term) (cadr term))

这里的＝zero?在练习2.80中定义（另见下面练习2.87）。
多项式程序包的用户可以通过下面过程创建多项式：

(define (make-polynomial var terms)
  ((get 'make 'polynomial) var terms))

练习2.87 请在通用算术包中为多项式安装＝zero?，这将使adjoin-term也能对系数本身也是多项式的多项式使用。
练习2.88 请扩充多项式系统，加上多项式的减法。（提示：你可能发现定义一个通用的求负操作非常有用。）
练习2.89 请定义一些过程，实现上面讨论的适宜稠密多项式的项表表示。
练习2.90 假定我们希望有一个多项式系统，它应该对稠密多项式和稀疏多项式都非常有效。一种途径就是在我们的系统里同时允许两种表示形式。这时的情况类似于2.4节复数的例子，那里同时允许采用直角坐标表示和极坐标表示。为了完成这一工作，我们必须区分不同的项表类型，并将针对项表的操作通用化。请重新设计这个多项式系统，实现这种推广。这将是一项需要付出很多努力的工作，而不是一个局部修改。
练习2.91 一个单变元多项式可以除以另一个多项式，产生出一个商式和一个余式。例如：

除法可以通过长除完成。也就是说，用被除式的最高次项除以除式的最高次项，得到商式的第一项；而后用这个结果乘以除式，并从被除式中减去这个乘积。剩下的工作就是用减后得到的差作为新的被除式，以便产生出随后的结果。当除式的次数超过被除式的次数时结束，将此时的被除式作为余式。还有，如果被除式就是0，那么就返回0作为商和余式。
我们可以基于add-poly和mul-poly的模型，设计出一个除法过程div-poly。这一过程首先检查两个多项式是否具有相同的变元，如果是的话就剥去这一变元，将问题送给过程div-terms，它执行项表上的除法运算。div-poly最后将变元重新附加到div-terms返回的结果上。将div-terms设计为同时计算出除法的商式和余式是比较方便的。div-terms可以以两个表为参数，返回一个商式的表和一个余式的表。
请完成下面div-terms的定义，填充其中空缺的表达式，并基于它实现div-poly。该过程应该以两个多项式为参数，返回一个包含商和余式多项式的表。

(define (div-terms L1 L2)
  (if (empty-termlist? L1)
      (list (the-empty-termlist) (the-empty-termlist))
      (let ((t1 (first-term L1))
            (t2 (first-term L2)))
        (if (> (order t2) (order t1))
            (list (the-empty-termlist) L1)
            (let ((new-c (div (coeff t1) (coeff t2)))
                  (new-o (- (order t1) (order t2))))
              (let ((rest-of-result
                     <递归地计算结果的其余部分>
                     ))
                <形成完整的结果>
                ))))))

符号代数中类型的层次结构
我们的多项式系统显示出，一种类型（多项式）的对象事实上可以是一个复杂的对象，又以许多不同类型的对象作为其组成部分。这种情况并不会给定义通用型操作增加任何实际困难。我们需要做的就是针对这种复合对象的各个部分的操作，并安装好适当的通用型过程。事实上，我们可以看到多项式形成了一类“递归数据抽象”，因为多项式的某些部分本身也可能是多项式。我们的通用型操作和数据导向的程序设计风格完全可以处理这种复杂性，这里并没有多少困难。
但另一方面，多项式代数也是这样的一个系统，其中的数据类型不能自然地安排到一个类型塔里。例如，在这里可能有x的多项式，其系数是y的多项式；也完全可能有y的多项式，其系数是x的多项式。这些类型中没有哪个类型自然地位于另一类型的“上面”，然而我们却常常需要去求不同集合的成员之和。有几种方式可以完成这件事情。一个可能性就是将一个多项式变换到另一个多项式的类型，这可以通过展开并重新安排多项式里的项，使两个多项式都具有同样的主变元。也可以通过对变元的排序，在其中强行加入一个类型塔结构，并且永远把所有的多项式都变换到一种“规范形式”，使具有最高优先级的变元成为主变元，将优先级较低的变元藏在系数里面。这种策略工作的相当好，但是，在做这种变换时，有可能毫无必要地扩大了多项式，使它更难读，也可能操作起来的效率更低。塔形策略在这个领域中确实不大自然，对于另一些领域也是一样，如果在那里用户可以动态地通过已有类型的各种组合形式引进新类型。这样的例子如三角函数、幂级数和积分。
如果说在设计大型代数演算系统时，对于强制的控制会变成一个很严重的问题，那完全不应该感到奇怪。这种系统里的大部分复杂性都牵涉多个类型之间的关系。确实，公平地说，我们到现在还没有完全理解强制。事实上，我们还没有完全理解类型的概念。但无论如何，已知的东西已经为我们提供了支持大型系统设计的强有力的结构化和模块化原理。
练习2.92 通过加入强制性的变量序扩充多项式程序包，使多项式的加法和乘法能对具有不同变量的多项式进行。（这绝不简单！）
扩充练习：有理函数
我们可以扩充前面已经做出的通用算术系统，将有理函数也包含进来。有理函数也就是“分式”，其分子和分母都是多项式，例如：

这个系统应该能做有理函数的加减乘除，并可以完成下面的计算：

（这里的和已经经过了简化，删除了公因子。常规的“交叉乘法”得到的将是一个4次多项式的分子和5次多项式的分母。）
修改前面的有理数程序包，使它能使用通用型操作，就能完成我们希望做的事情，除了无法将分式化简到最简形式之外。
练习2.93 请修改有理数算术包，采用通用型操作，但在其中改写make-rat，使它并不企图去将分式化简到最简形式。对下面两个多项式调用make-rational做出一个有理函数，以便检查你的系统：

(define p1 (make-polynomial 'x ?(2 1)(0 1))))
(define p2 (make-polynomial 'x ?(3 1)(0 1))))
(define rf (make-rational p2 p1))

现在用add将rf与它自己相加。你会看到这个加法过程不能将分式化简到最简形式。
我们可以用与前面针对整数工作时的同样想法，将分子和分母都是多项式的分式简化到最简形式：修改make-rat，将分子和分母都除以它们的最大公因子。“最大公因子”的概念对于多项式也是有意义的。事实上，我们也可以用与整数的欧几里得算法本质上相同的算法求出两个多项式的GCD（最大公因子）126。对于整数的算法是：

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

利用它，再做一点非常明显的修改，就可以定义出一个对项表工作的GCD操作：

(define (gcd-terms a b)
  (if (empty-termlist? b)
      a
      (gcd-terms b (remainder-terms a b))))

其中的remainder-terms提取出由项表除法操作div-terms返回的表里的余式成分，该操作在练习2.91中实现。
练习2.94 利用div-terms实现过程remainder-terms，并用它定义出上面的gcd-terms。现在写出一个过程gcd-poly，它能计算出两个多项式的多项式GCD（如果两个多项式的变元不同，这个过程应该报告错误）。在系统中安装通用型操作greatest-common-divisor，使得遇到多项式时，它能归约到gcd-poly，对于常规的数能归约到常规的gcd。作为试验，请做：

(define p1 (make-polynomial 'x ?(4 1) (3 -1) (2 -2) (1 2))))
(define p2 (make-polynomial 'x ?(3 1) (1 -1))))
(greatest-common-divisor p1 p2)

并用手工检查得到的结果。
练习2.95 请定义多项式P1、P2和P3：

P1 : x2－2x＋1 P2 : 11x2＋7 P3 : 13x＋5

现在定义Q1为P1和P2的乘积，定义Q2为P1和P3的乘积，而后用greatest-common-divisor（练习2.94）求出Q1和Q2的GCD。请注意得到的回答与P1并不一样。这个例子将非整数操作引进了计算过程，从而引起了GCD算法的困难。要理解这里发生了什么，请试着手工追踪gcd-terms在计算GCD或者做除法时的情况。
如果我们对于GCD算法采用下面的修改，就可以解决练习2.95揭示出的问题（这只能对整数系数的多项式使用）。在GCD计算中执行任何多项式除法之前，我们先将被除式乘以一个整数的常数因子，选择的方式是保证在除的过程中不出现分数。这样得到的回答将比实际的GCD多出一个整的常数因子，但它不会在将有理函数化简到最简形式的过程中造成任何问题。由于将用这个GCD去除分子和分母，所以这个常数因子会被消除掉。
说得更精确些，如果P和Q都是多项式，令O1是P的次数（P的最高次项的次数），令O2是Q的次数，令c是Q的首项系数。可以证明，如果我们给P乘上一个整数化因子c1＋O1－O2，得到的多项式用div-terms算法除以Q将不会引进任何分数。将被除式乘上这样的常数后除以除式，这种操作在某些地方称为P对于Q的伪除，这样除后得到的余式也被称为伪余。
练习2.96
a) 请实现过程pseudoremainder-terms，它就像是remainder-terms，但是像上面所描述的那样，在调用div-terms之前，先将被除式乘了整数化因子。请修改gcd-terms使之能使用pseudoremainder-terms，并检验现在greatest-common-divisor能否对练习2.95的例子产生出一个整系数的答案。
b) 现在的GCD保证能得到整系数，但它们将比P1的系数大，请修改gcd-terms使它能从答案的所有系数中删除公因子，方法是将这些系数都除以它们的（整数）最大公约数。
至此我们已经弄清了如何将一个有理函数化简到最简形式：

• 用取自练习2.96的gcd-terms版本计算出分子和分母的GCD；
• 在你得到了这个GCD后，在用GCD去除分子和分母之前，先将它们都乘以同一个整数化因子，以使除以这个GCD不会引进任何非整数系数。作为这个因子，你可以使用得到的GCD的首项系数的1＋O1－O2次幂。其中O2是这个GCD的次数，O1是分子与分母的次数中大的那一个。这将保证用这个GCD去除分子和分母不会引进任何分数。
• 这一操作得到的结果将是具有整系数的分子和分母。它们的系数通常会由于整数化因子而变得非常大。所以最后一步是去除这个多余的因子，为此需要首先计算出分子和分母中所有系数的（整数）最大公约数，而后除去这个公约数。

练习2.97
a) 请将这一算法实现为过程reduce-terms，它以两个项表n和d为参数，返回一个包含nn和dd的表，它们分别是由n和d通过上面描述的算法简化而得到的最简形式。另请写出一个与add-poly类似的过程reduce-poly，它检查两个多项式是否具有同样变元。如果是的话，reduce-poly就剥去其中变元，并将问题交给reduce-terms，最后为reduce-terms返回的表里的两个项表重新附加上变元。
b) 请定义一个类似于reduce-terms的过程，它完成的工作就像是make-rat对整数做的事情：

(define (reduce-integers n d)
  (let ((g (gcd n d)))
    (list (/ n g) (/ d g))))

再将reduce定义为一个通用型操作，它调用apply-generic完成到reduce-poly（对于polynomial参数）或者到reduce-integers（对scheme-number参数）的分派。你可以很容易让有理数算术包将分式简化到最简形式，采用的方式就是让make-rat在组合给定分子和分母，做出有理数之前也调用reduce。这一系统现在就能处理整数或者多项式的有理表达式了。为测试你的程序，请首先试验下面的扩充练习：

(define p1 (make-polynomial 'x ?(1 1)(0 1))))
(define p2 (make-polynomial 'x ?(3 1)(0 -1))))
(define p3 (make-polynomial 'x ?(1 1))))
(define p4 (make-polynomial 'x ?(2 1)(0 -1))))
(define rf1 (make-rational p1 p2))
(define rf2 (make-rational p3 p4))
(add rf1 rf2)

看看能否得到正确结果，结果是否正确地化简为最简形式。
GCD计算是所有需要完成有理函数操作的系统的核心。上面所使用的算法虽然在数学上直截了当，但却异常低效。低效的部分原因在于大量的除法操作，部分在于由伪除产生的巨大的中间系数。在开发代数演算系统的领域中，一个很活跃问题就是设计计算多项式GCD的更好算法。