在第 1.1.8 节中，我们指出，一个被用作构件来创建更复杂过程的过程，不仅可以被看作一组特定操作的集合，也可以被看作一个过程抽象。也就是说，过程如何实现的细节可以被隐藏起来，这个特定的过程本身可以被任何其他具有相同整体行为的过程所替代。换句话说，我们可以构造一种抽象，将过程的使用方式与过程如何以更基本的过程来实现的细节分离开来。复合数据中的对应概念被称为数据抽象。数据抽象是一种方法论，它使我们能够将复合数据对象的使用方式与其如何从更基本的数据对象构造而来的细节隔离开来。
数据抽象的基本思想是，将使用复合数据对象的程序设计为对"抽象数据"进行操作。也就是说，我们的程序应该以这样的方式使用数据：不对那些并非执行当前任务所必需的数据做任何假设。与此同时，"具体"数据表示的定义与使用这些数据的程序是独立的。我们系统中这两部分之间的接口将是一组过程，称为选择函数和构造函数，它们以具体表示的方式实现抽象数据。为了说明这项技术，我们将考虑如何设计一组用于操作有理数的过程。
假设我们想要进行有理数的算术运算。我们希望可以对它们进行加、减、乘、除，并测试两个有理数是否相等。
让我们先假设我们已经有一种方法，可以从一个分子和一个分母构造一个有理数。我们还假设，给定一个有理数，我们有一种方法可以提取（或选择）它的分子和分母。让我们进一步假设构造函数和选择函数可以作为以下过程使用：
这里我们使用了一种强大的合成策略：一厢情愿。我们还没有说明有理数如何表示，也没有说明过程 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 来构造。这个过程接受两个参数，返回一个包含这两个参数作为部分的复合数据对象。给定一个序对，我们可以用基本过程 car 和 cdr 提取其部分。2 因此，我们可以如下使用 cons、car 和 cdr：
(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 就可以很容易地实现如下：3
(define (make-rat n d) (cons n d))
(define (numer x) (car x))
(define (denom x) (cdr x))
此外，为了显示我们计算的结果，我们可以通过打印分子、斜杠和分母来 打印有理数：4
(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 过程那样的、能计算两个整数最大公约数的过程，我们就可以在构造序对之前使用 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 应该规范化符号，使得如果有理数为正，则分子和分母都为正；如果有理数为负，则只有分子为负。
在继续更多复合数据和数据抽象的例子的之前，让我们考虑有理数例子提出的一些问题。我们通过构造函数 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.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 为了形成有理数表示的合适基础而必须满足的唯一条件。一般来说，我们可以认为数据是由某些选择函数和构造函数的集合以及这些过程为了成为有效表示而必须满足的指定条件来定义的。5
这种观点不仅可以用来定义"高层次"的数据对象（如有理数），也可以用于定义低层次的对象。考虑一下我们用来定义有理数的序对概念。我们从未真正说明序对是什么，只是说语言提供了 cons、car 和 cdr 这些用于操作序对的过程。但关于这三个操作，我们唯一需要知道的是，如果我们使用 cons 将两个对象粘合在一起，就可以使用 car 和 cdr 检索这些对象。也就是说，这些操作满足以下条件：对于任何对象 x 和 y，如果 z 是 (cons x y)，那么 (car z) 是 x 且 (cdr z) 是 y。确实，我们提到过这三个过程是作为基本过程包含在我们的语言中的。然而，任何满足上述条件的三元组过程都可以作为实现序对的基础。这一点通过一个引人注目的事实得以说明：我们可以在完全不使用任何数据结构的情况下实现 cons、car 和 cdr，而只使用过程。以下是定义：
(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 和加 1 操作实现如下，从而在没有数的情况下（至少就非负整数而言）也能应付：
(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n)
(lambda (f) (lambda (x) (f ((n f) x)))))
这种表示称为 丘奇数，以其发明者 Alonzo Church 命名，他是发明了 
算学的逻辑学家。
请直接定义 one 和 two（不是通过 zero 和 add-1）。（提示：使用代换计算 (add-1 zero)。）给出加法过程 + 的直接定义（不是通过重复应用 add-1）。
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 的肩膀上看过去，评论说用一个跨越零的区间做除法意味着什么并不清楚。请修改 Alyssa 的代码以检查这种情况，并在发生这种情况时发出错误信号。
练习 2.11. 顺便说一句，Ben 还神秘地评论道："通过测试区间端点的符号，可以将 mul-interval 分解为九种情况，其中只有一种情况需要超过两次乘法。" 请使用 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 名称 cons 代表 "construct"（构造）。名称 car 和 cdr 来源于 Lisp 在 IBM 704 上的原始实现。那台机器有一种寻址方案，允许引用内存位置的"地址"和"减量"部分。Car 代表"寄存器地址部分的内容"，而 cdr（读作 "could-er"）代表"寄存器减量部分的内容"。
3 定义选择函数和构造函数的另一种方式是
(define make-rat cons)
(define numer car)
(define denom cdr)
第一个定义将名称 make-rat 与表达式 cons 的值关联起来，cons 是构造序对的基本过程。因此 make-rat 和 cons 是同一个基本构造函数的不同名称。
以这种方式定义选择函数和构造函数是高效的：不是 make-rat 调用 cons，而是 make-rat 就是 cons，因此在调用 make-rat 时只调用了一个过程，而不是两个。另一方面，这样做会破坏跟踪过程调用或在过程调用上设置断点的调试辅助功能：你可能希望看到 make-rat 被调用，但你肯定不希望看到每次对 cons 的调用。
我们选择不在本书中使用这种定义风格。
4 Display 是 Scheme 中用于打印数据的基本过程。Scheme 的基本过程 newline 开始一个新行用于打印。这两个过程都不返回有用的值，因此在下面使用 print-rat 时，我们只显示 print-rat 打印的内容，而不显示解释器打印的 print-rat 返回的值。
5 令人惊讶的是，这个想法很难严格地表述出来。有两种途径可以给出这样的表述。一种由 C. A. R. Hoare（1972）开创，被称为 抽象模型 方法。它将"过程加条件"的规范形式化，如上面的有理数例子中所概述的。注意，有理数表示的条件是用关于整数的事实（相等和除法）来陈述的。一般来说，抽象模型根据先前定义的数据对象类型来定义新种类的数据对象。因此，关于数据对象的断言可以通过将其归约为关于先前定义的数据对象的断言来检查。另一种方法由 MIT 的 Zilles、IBM 的 Goguen、Thatcher、Wagner 和 Wright（参见 Thatcher、Wagner 和 Wright 1978）以及多伦多的 Guttag（参见 Guttag 1977）引入，被称为 代数规格说明。它将"过程"视为抽象代数系统的元素，其行为由对应于我们的"条件"的公理来指定，并使用抽象代数的技术来检查关于数据对象的断言。这两种方法都在 Liskov 和 Zilles（1975）的论文中进行了综述。