2. 构造数据抽象

上一章操作的数字都是简单的数值数据，但计算机不可能只会处理这种简单数据，计算机要描述复杂现象，首先要构造计算对象。 本章就讨论将数据对象组合，形成复合数据的方式。

考虑线性组合 \(ax+by\) ,我们可以编写一个函数，接受四个参数 \(a,b,x,y\) 并立即返回 \(ax+by\)

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

如果a,b,x,y是可以被*和+符号执行的数值数据，这当然是可以的。但在 我们编写线性组合时， 我们希望的是将四个对象进行这样的线性组合，对象不一定是数值数据，可能是有理数、复数、多项式 或者其它东西。这时我们表述成如下过程

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

其中add和mul不是简单的+和*，而是更复杂的东西，根据a,b,x,y具体是什么来执行相应add或mul运算。

刚才既然已经提到有理数，不妨就先编写一个有理数的算术系统。

2.1. 数据抽象

已知数值数据是可以直接使用+-*/等符号直接运算的。假定我们已经有一种用分子分母表示有理数的方法。 并且可以获取这个有理数的分子或分母。

(define (make-rat a b) (cons a b))
(define (numer r) (car r))
(define (denom r) (car (cdr r)))

对于两个有理数，首先有加、减、乘、除、判等，这样五种基本操作。

\[\frac{n_1}{d_1} + \frac{n_2}{d_2} = \frac{n_1d_2+n_2d_1}{d_1d_2}\]

\[\frac{n_1}{d_1} - \frac{n_2}{d_2} = \frac{n_1d_2-n_2d_1}{d_1d_2}\]

\[\frac{n_1}{d_1} * \frac{n_2}{d_2} = \frac{n_1n_2}{d_1d_2}\]

\[\frac{n_1}{d_1} / \frac{n_2}{d_2} = \frac{n_1d_2}{d_1n_2}\]

\[\frac{n_1}{d_1} = \frac{n_2}{d_2} \text{ when } \frac{n_1}{n_2} = \frac{d_1}{d_2}\]

可以将这些规则表述成:

(define (add-rat r1 r2)
    (make-rat (+ (* (numer r1) (denom r2)) (* (numer r2) (denom r1))) (* (denom r1) (denom r2)) )
)

(define (sub-rat r1 r2)
    (make-rat (- (* (numer r1) (denom r2)) (* (numer r2) (denom r1))) (* (denom r1) (denom r2)) )
)

(define (mul-rat r1 r2)
    (make-rat (* (numer r1) (numer r2)) (* (denom r1) (denom r2)))
)

(define (div-rat r1 r2)
    (make-rat (* (numer r1) (denom r2)) (* (denom r1) (numer r2)))
)

同时再编写一个对我们的有理数类型进行输出的函数，就可以测试一下我们程序的功能了：

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

(print-rat (add-rat (make-rat 1 2) (make-rat 1 3)))
(print-rat (sub-rat (make-rat 1 2) (make-rat 1 3)))
(print-rat (mul-rat (make-rat 1 2) (make-rat 2 3)))
(print-rat (div-rat (make-rat 1 2) (make-rat 2 3)))

得到结果

5/6

1/6

2/6

3/4

可以看到，有理数并没有化为最简分数的形式。当然，通过修改make-rat函数很容易改正过来： 计算分子分母的最小公倍数gcd，并将之相除。

(define (make-rat a b)
    (define g (gcd a b))
    (cons (/ a g) (/ b g))
)

这样，我们的 \(\frac{1}{2} \times \frac{2}{3}\) 就正确地等于了 \(\frac{1}{3}\)。完全不需要修改 实际运算的函数。

目前只考虑了分子分母都是正数的情况，要更完善的设计的话，可以将其规范化一下：如果出现负数，则保持 分子为负，分母永远为正数。若出现数值0，则保持分子为0且分母为1。

2.2. 抽象屏障

上边我们使用一个序对，表示了一个有理数，所有的有理数操作都是基于make-rat,numer和denom完成的。 一般而言，数据抽象的基本思想就是为每一类数据标识出一组操作，使这类数据对象都可以基于它们来表述，且 在操作这些数据对象时也只使用它们。

对于外部使用有理数运算的程序而言，只需要了解问题域中的有理数是使用add-rat,sub-rat,mul-rat,div-rat等 操作执行，而不关心其中的实现。而对于add-rat,sub-rat等操作，只关心如何获取一个有理数以及如何构造它。 获取和构造有理数时则关心有理数的数据表示方法，为cons序对，且第一个元素表示分子，第二个数字表示分母。

每一个层次都相当于一个抽象屏障，在这个层次上的方法不会穿越屏障，但是可以通过下一层的抽象将所有层联系起来。

前述的将有理数化为最简，我们是在make-rat时进行的。由于上层各方法不需要知道底层如何表示， 所以还可以在numer和denom时将有理数化为最简，而make-rat时则直接连接。 如果我们的操作会多次访问分子分母，那么确实在构造时计算gcd比较有效率。 反之，则gcd的计算推迟在需要读取时再计算也许更好。但不论如何， 上级抽象层的add-rat,sub-rat等方法都完全不需要修改。

2.3. 数据意味着什么

前述是用cons两个数值数据表示的一个有理数，但只要我们的make-rat,numer和denom能够用统一的方法 构造或读取相应的值，使用其它的约定的数据也可以用来表示。我们也总是可以用两个数字的cons序列 来表示一个平面直角坐标系上的点，或者表示一个复数a+bi。它实际表示什么，只和构造与获取它的方式有关。