2.1 Introduction to Data Abstraction - CloneableX/SICP-learning GitHub Wiki

在 1.1.8 节时，当一个程式用作另一个复杂程式的元素时，它并只是作为一组特殊运算符看待，而是被视为一个程式抽象。因为程式的实现细节被忽略，所以它能够被实现相同功能的其他程式替换，也就是将程式的实现细节与使用分离开。复合数据与此类情况类似，所以也称 数据抽象（data abstraction）。数据抽象是一种方法，它能够将组合数据对象的细节与用于组合的基础数据对象隔离。

数据抽象的基础概念一般用于构建通过复合数据对象构建的程序，便于程序操作抽象数据。也就是说，复合数据的定义与程序使用此数据是相互独立的。一组程式将作为介于我们系统这两者间的接口，它们被称为 查询器（selector） 和 构造器（constructor），它们将实现计算时抽象数据的具体表现。为了解释这项技术，我们先思考一下如何设计一组用于维护小数的程式。

示例：有理数的算数运算符

假如我们要计算有理数的算术运算，希望能够对有理数进行加法、减法、乘法、除法及相等运算。

我们首先假设已经有办法通过分子和分母构建有理数，并且只要提供有理数我们也有办法提取其中的分子和分母，于是可以假设有理数的构造器和查询器能够作为程式使用：

(make-rat <n> <d>) 返回有理数，其中分子是 <n>，分母是 <d>
(numer <x>) 返回有理数 <x> 的分子
(denom <x>) 返回有理数 <x> 的分母

上述描述中我们使用了一种强大的综合策略：假设性思考（wishful thinking），但我们还没有描述有理数将如何表示，或者说 numer、denom 和 make-rat 程式要如何实现。当我们拥有这三个程式后，便能完成如下有理数的算术运算：

$https://latex.codecogs.com/svg.image?\inline \frac{n_{1}}{d_{1}}+\frac{n_{2}}{d_{2}}=\frac{n_{1}d_{2}+n_{2}d_{1}}{d_{1}d_{2}}$
$https://latex.codecogs.com/svg.image?\inline \frac{n_{1}}{d_{1}}-\frac{n_{2}}{d_{2}}=\frac{n_{1}d_{2}-n_{2}d_{1}}{d_{1}d_{2}}$
$https://latex.codecogs.com/svg.image?\inline \frac{n_{1}}{d_{1}}\ast \frac{n_{2}}{d_{2}}=\frac{n_{1}n_{2}}{d_{1}d_{2}}$
$https://latex.codecogs.com/svg.image?\inline \frac{n_{1}/d_{1}}{n_{2}/d_{2}}=\frac{n_{1}d_{2}}{n_{2}d_{1}}$
$https://latex.codecogs.com/svg.image?\inline \frac{n_{1}}{d_{1}}=\frac{n_{2}}{d_{2}}$ 有且只有 $https://latex.codecogs.com/svg.image?\inline n_{1}d_{2}=n_{2}d_{1}$

将上述的规则改写为程式如下：

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

现在我们已经拥有关于有理数的算术运算程式，但我们还没有定义需要的选择器和构造器。

序对

Scheme 通过 序对（pair） 结构为我们提供实现数据抽象的能力，我们可以通过基础程式 cons 构建复合数据。cons 程式接收两个参数，并返回一个复合数据对象，此对象包含了传入的两个参数。只要提供序对，通过基础程式 car 和 cdr 便可以提取其中的组成成分。所以我们能够如下使用 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

在下一节内容中，我们将通过序对的这种能力处理复杂数据的排序。通过序对构建的数据对象也称为 列表结构数据（list-structured data）。

表示有理数

序对提供了构建有理数系统的能力，我们可以将有理数简单地表现为一对整数，一个为分子一个为分母。然后 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 的代码。如果我们已经拥有 gcd（也就是 1.2.5 节介绍的最大公约数）程式，在构建有理数时便可以将其化作最简形式，如下：

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

再次运算有理数：

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

结果满足我们的预期。

抽象屏障

在展示更多的数据抽象示例之前，我们先思考一些有理数示例中抛出的问题。在上述示例中，我们分别定义了有理数的构造器 make-rat 和选择器 numer、denom。总的来说，数据抽象的根本概念是是为了识别一组运算过程中需要操作的所有数据类型，然后通过抽象使运算只对抽象数据进行操作。

Data-abstraction barriers in the rational-number package

我们能够预见有理数系统的结构将如上图所示。横线表示的就是 抽象屏障（abstraction barriers），用于隔离系统每个层级间的差别。在系统的每个层级，抽象屏障的上层程序使用的都是下层程序实现的数据抽象。运用有理数进行计算的程序仅仅是对有理数包的程式进行应用。不过确切地说，make-rat、numer 和 denom 都是通过序对实现，有理数包中的其他程式对序对的实现并不关心。实际上，每个层级的程式都是定义抽象屏障和连接不同层级的接口。

这个简单的概念却有着大量的优势。一个优势是，它使程序更容易维护和修改。任何复杂的数据结构都可以通过编程语言构造。而构造方式影响着程序对数据的操作，所以如果对数据结构的修改应该保持它在程序中的一致性。如果不将数据构建的依赖限制在小范围的模块中，要实现这种一致性将花费大量时间，并且还要编写大量代码。

例如，要解决有理数未约分的问题也可以通过修改有理数的访问器实现，修改后的程式如下：

(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 运算的时机，也不影响其他相关程式的功能。

数据的含义

在有理数包实现初期，我们在 make-rat、numer 和 denom 程式的基础上实现了有理数运算 add-rat、sub-rat 等等。我们可以认为定义在运算过程的数据对象（分子、分母及有理数）的行为是由 make-rat、numer 和 denom 确定。

不过数据的准确含义是什么呢？“提供的选择器和构建器的实现就是数据的含义” 并不足以说明情况。更准确地说，并不是任意三个程式都适合作为有理数系统的基础。并且我们需要保证，如果通过一对整数 n 和 d 构建有理数 x，那么通过 numer 和 denom 取出的分子、分母应该与 n 除以 d 的结果相同。换句话说，make-rat、numer 和 denom 对于任意整数 n 和任意非零整数 d 构建产生有理数 x（通过 (make-rat n d) 构建）应该满足如下等式：

$https://latex.codecogs.com/svg.image?\inline \frac{(numer\ x)}{(denom\ x)}=\frac{n}{d}$

实际上，这是 make-rat、numer 和 denom 适合作为有理数表现形式必须满足的条件。通常来说，我们可以认为数据由一组选择器和构造器定义，同时这些程式还必须完全满足这种数据表现形式的指定条件。

上述观点不仅对高阶数据对象有效，对低阶数据对象同样有效。比如在实现有理数系统时使用了序对，我们从未确切谈起序对的实质，只是了解编程语言通过 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，它定义于 cons 程式中，并且通过参数为 0 或 1 返回 x 或 y 作为结果。(car z) 其实是 (z 0) 表达式的结果，如果 z 是程式 (cons x y)，则 (car z) 返回 x，(cdr (cons x y)) 同理。因此上述程式是一个对序对的有效实现，而且仅通过对上述程式的使用，我们无法分辨它们是否通过真正的数据结构实现的。

上述程式并不是想表达 Scheme 的序对就是如此实现，而只是说明这样实现也可以正常运转。虽然这种程式的表现形式比较晦涩，但也足以表示序对，毕竟它完全满足序对的条件。同时这个示例也说明了，将程式作为对象维护的能力自然会提供表达组合数据的能力。虽然看起来很奇怪，但数据通过程式方式表现将在我们的编程中扮演核心角色。这种风格的程序称为 消息传递（message passing），并且在第三章中它将成为定位建模和模拟问题的基础工具。

扩展练习：区间算术

Alyssa P.Hacker 正在设计一个系统帮助人们解决工程问题。此系统需要提供这样一种功能，它能够通过精度维护一个不精确的数量，当计算发生时将产生基于精度的数值。

电子工程师通过 Alyssa 的系统计算了电量，这对于计算并联电阻值不可或缺，计算公式如下：

$https://latex.codecogs.com/svg.image?\inline R_{p}=\frac{1}{1/R_{1}+1/R_{2}}$

电阻值只能通过生产厂家提供的正负值确定。例如，如果你购买了一个 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 构造区间。她的理由是两个区间的最小值相加将得到新区间的最小值，两个最大值相加将得到新区间的最大值，程式如下：

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

Alyssa 也对区间进行了乘法运算，程式如下：

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

区间的除法由第一个区间乘上第二个区间的倒数区间，程式如下：

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