构造数据抽象

发表于 更新于 分类于

SICP 第二章

概要

  • 数据抽象
  • 数据与程序

构造数据抽象

设计一个完成有理数运算的系统。完成有理数的加减乘除运算
、判断两个有理数是否相等，等等。

我们假定已经有了一种从分子和分母构造有理数的方法，并进一步假定如果有了一个有理数，我们有一种方法取得它的分子和分母。现在再假定有关的构造函数和选择函数都可以作为过程使用：

  • (make-rat <n> <d>): 返回一个有理数，其分子是整数<n>，分母是整数<d>。
  • (numer <x>): 返回有理数<x>的分子。
  • (denom <x>): 返回有理数<x>的分母。
    我们要在这里使用一种称为按愿望思维的策略。现在我们还没有说有理数将如何表示，也没有说过程numer, denom和make-rat应如何实现。然而，如果我们真的有了这三个过程，那么就可以根据下面关系去做有理数的加减乘除和相等判断：

$$\begin{split}\frac{n_1}{d_1} + \frac{n_2}{d_2} =& \frac{n_1d_1+n_2d_2}{d_1d_2} \\
\frac{n_1}{d_1} - \frac{n_2}{d_2} = & \frac{n_1d_1-n_2d_2}{d_1d_2} \\
\frac{n_1}{d_1} \times \frac{n_2}{d_2} = & \frac{n_1n_2}{d_1d_2} \\
\frac {\frac{n_1}{d_1} } {\frac{n_2}{d_2}} = & \frac{n_1d_2}{n_2d_1} \\
\frac{n_1}{d_1} = \frac{n_2}{d_2} & \text{当且仅当} n_1d_2=n_2d_1\end{split}$$

编程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
(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和cdr按如下方式提取出其中各个部分：

名字cons表示“构造”(construct)。名字car和cdr则来自Lisp最初在 IBM 704 机器上的实现。在这种机器有一种取址模式，使人可以访问一个存储地址中的“地址”(address）部分和“减量”(decrement）部分。car表示“Contents of Address part of Register”(寄存器的地址部分的内容)，cdr （读作“could-er”)表示“Contents of Decrement part of Register”(寄存器的减量部分的内容)。

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

1

1
(cdr x)

2

还可以用cons构造序对的序对：

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

1

1
(car (cdr z))

3

通过过程cons、car和cdr实现的这样一种最基本的复合数据称作序对，从序对构造起来的数据对象称为表结构数据。

使用序对很容易做出下面make-rat、numer和denom的实现：

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

或者直接：

1
2
3
(define make-rat cons)
(define numer car)
(define denom cdr)

为便于说明问题，此处使用第一种。

另定义print-rat用于输出分数：

1
2
3
4
5
(define (print-rat x)
  (newline)
  (display (numer x))
  (display "/")
  (display (denom x)))

做个测试：

1
2
(define one-half (make-rat 1 2))
(print-rat one-half)

1/2

1
2
(define one-third (make-rat 1 3))
(print-rat (add-rat one-half one-third))

5/6

1
2
(print-rat (mul-rat one-half one-third))
(print-rat (add-rat one-third one-third))

1/6
6/9

发现该程序不能实现自动约分，故使用求最大公约数的gcd改写make-rat实现约分：

1
2
3
4
5
6
7
8
9
(define (gcd x y)
  (let ((tmp (remainder x y)))
  (if (= 0 tmp)
    y
    (gcd y tmp))))

(define (make-rat n d)        ; n为分子，d为分母
  (let ((g (gcd n d)))        ; g为n和d的最大公约数
  (cons (/ n g) (/ d g))))    ; 构造分数时先约分

现在测试先前的语句，输出2/3。
另考虑兼容分数的正负号，make-rat改写为：

1
2
3
4
5
(define (make-rat x y)
  (let ((g (gcd x y)))
  (if (< (/ x y) 0)
    (cons (/ (- x) g) (/ y g))
    (cons (/ x g) (/ y g)))))

抽象屏障

使用有理数的程序
————————————————————
问题域中的有理数
————————————————————
add-rat sub-rat...
————————————————————
作为分子和分母的有理数
————————————————————
make-rat numer denom
————————————————————
作为序对的有理数
————————————————————
cons car cdr
————————————————————
序对也需要实现

上图形象化地表示了有理数系统的结构。其中的水平线表示抽象屏障，它们隔离了系统中不同的层次。在每一层上，这种屏障都把使用数据抽象的程序（上面）与实现数据抽象的程序（下面）分开来。使用有理数的程序将仅仅通过有理数包提供给“公众使用”的那些过程(add-rat、sub-rat、mul-rat、div-rat和equal-rat?）去完成对有理数的各种操作，这些过程转而又是完全基于构造函数和选择函数make-rat、numer和denom实现的，而这些函数又是基于序对实现的。只要序对可以通过cons、car和cdr操作，有关序对如何实现的细节与有理数包的其余部分都完全没有关系。从作用上看，每一层次中的过程构成了所定义的抽象屏障的界面,联系起系统中的不同层次。

把对于具体表示方式的依赖性限制到少数几个界面过程，不但对修改程序有帮助，同时也有助于程序的设计，因为这种做法将使我们能保留考虑不同实现方式的灵活性。数据抽象方法使我们能推迟决策的时间，而又不会阻碍系统其他部分的工作进展。

数据与程序