数据抽象，邱奇数

之前的部分我们对 procedure 做了很多的抽象，而实际上数据也可以构造多层的抽象，来方便我们设计复杂的功能。

比如我们可以设计一种抽象数据，用来表示有理数（分数形式）：

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

同时还有一些它的常用操作，比如加减乘除和是否相等：

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

通过定义的这些函数，我们就建立起了 abstraction barrier，上层应用在使用 rat 的时候完全不需要关心下层的东西。实际上这里分了多层：

程序 抽象层次
最上层的应用
add-rat, sub-rat … 将有理数这个抽象数据视为一个整体
make-rat, number, denom … 将有理数视为分子和分母
cons, car, cdr … 将有理数视为 pairs

在这里我们看的这种结构是到构造抽象数据的一般方式，即创造一层类似 mat-rat, number 这样的构造函数和选择函数，然后让上层——暴露给外层应用的函数去调用。

我们这里的这个抽象数据是基于一个数学上真正存在的「有理数」概念去定义的，但是实际上我们完全可以定义一个没有这种真是概念依靠的抽象数据。也就是说，对于抽象数据来说，他的这种依靠——也就是我们所说的「数据」，实际上是一种满足了特定概念的构造函数和选择函数。于是，抽象数据实际上只要满足我们对它的这种特定的构造函数和选择函数就可以，与它本身是什么完全无关。

比如，我们对 scheme 中的 pair 这种数据的假设就是我们可以用 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))

于是我们可以看到，数据和过程是没有明确的分界的，数据完全可以是过程。对于这种概念，还有一个更突出的例子就是 Alonzo Church 发明的 Church numerals (邱奇数)。因为在 Lambda Calculus 中，一切都是函数，所以 Church 使用了这种方式来将自然数编码成函数，从而将数据引入 Lambda Calculus。

我们可以先定义 0，这是一个接受了 f 和 x 两个参数的函数，并直接返回 x ：

(define zero (lambda (f) (lambda (x) x)))

而 1 则是同样接受这两个参数，但是返回 f(x) ， 2 则是 f(f(x)) …

(define one (lambda (f) (lambda (x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x)))))
(define three (lambda (f) (lambda (x) (f (f (f x))))))

我们可以看到，在邱奇数的体系中，这个数是几实际上就是被 f 调用了几次。于是可以很自然得写出将一个邱奇数加上 1 的函数，也就是在这个数的基础上多被 f 调用一次：

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

而两数的加法就是将一个数作用于另一个数：

(define add (lambda (a b)
	      (lambda (f)
		(lambda (x) ((a f) ((b f) x))))))

闭包，通用界面

在之前第一章的时候，我们使用高阶函数来表示一种概念，然后我们得以在高阶函数的参数中传递不同的函数来构造出相同概念但是不同计算的函数。之所以能这么做，是因为高阶函数的特性：函数本身可以作为参数来传入函数。

而数据同样可以有类似的性质，比如我们使用 cons 组成的 pair。比如我们可以将这个 pair 中空间指向另外的 pair，比如 (cons 1 (cons 2 3)) 。这种可以一个数据的元素也可以是这种数据的性质就被称为 Closure property (闭包性质)。

于是当我们需要一个粘合更多的元素的时候，可以借助这种性质，用 pair 来构造出一个 list。相比于上面例子的这种表示方式，更统一的方式是 car 永远存放元素，而 cdr 永远是下一个 pair，如果到底了就为 nil 。

(cons 1 (cons 2 (cons 3 (cons 4 nil))))

我们把这种结构称为 list ，在 scheme 中也提供了一种简化的等价表示：

(list 1 2 3 4)

同时，在 list 的框架下，我们也可以表示具有层次的、超过一维的数据结构，比如下面这个 list 实际上是一棵树：

(cons (list 1 2) (list 3 4))
=> '((1 2) 3 4)

((1 2) 3 4)
├── (1 2)
│   ├── 1
│   └── 2
├── 3
└── 4

我们现在可以把 list 作为一个 Conventional interface。它不仅能力表现一些结构化的数据，同时具有 closure property，使得对它操作的结果仍然是 list，从而可以无碍传入下一个模块。这种情况就使得我们的程序构建可以非常灵活得组合各种模块。

书中在此的例子是两个程序，第一个是计算树的叶子结点为奇数的平方和，第二个是获得偶数的 Fib 表：

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

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

乍看之下这二者似乎没有很明显的共同结构，但是实际上他们对于信息的处理可以遵循类似的模式：

  • enumerate 所有的叶子结点 –> filter 出奇数 –> map 作平方 –> accumulate 求和
  • enumerate 所有的整数 –> map 算 fib –> filter 出偶数 –> accumulate 求和

于是我们可以抽象这些过程，以 list 为 interface 构造出更通用的程序。

enumerate 部分：

(define (enumerate-tree tree)
  (cond ((null? tree) nil)
	((not (pair? tree)) (list tree))
	(else (append (enumerate-tree (car tree))
		      (enumerate-tree (cdr tree))))))

(define (enumerate-interval low high)
  (if (> low high)
      nil
      (cons low
	    (enumerate-interval (+ low 1) high))))

filter 部分：

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

map 是一个 scheme 本身就有的函数，就不需要我们自己构建了。

accumulate 部分：

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
	  (accumulate op initial (cdr sequence)))))

这种方式构建的两个程序：

(define (sum-odd-squares tree)
  (accumulate
   +
   0
   (map square
	(filter odd?
		(enumerate-tree tree)))))

(define (even-fibs n)
  (accumulate
   cons
   nil
   (filter even?
	   (map fib
		(enumerate-interval 0 n)))))

抽象数据的多重表示

我们上面通过设计构造函数和选择函数建立起了 abstraction barrier，让上层程序的操作不用关心下层数据实际上是如何表示的。而实际上在一个系统中，一种抽象数据的表示方法是可以超过一种的，我们有时候会需要构建一个能够处理多种表示方法的系统。

典型的例子如对于复数的表示可以有两种：直角坐标表示法和极坐标表示法，前者会存储复数的 real-part (实部)和 imag-part (虚部)，后者则是 mag (模) 和 ang (幅角)。如果使用直角坐标表示，那么其构造函数和选择函数应该是这样的：

(define (make-from-real-imag x y) (cons x y))

(define (make-from-mag-ang r a)
  (cons (* r (cos a)) (* r (sin a))))

(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-mag-ang r a) (cons r a))
(define (make-from-real-imag x y)
  (cons (sqrt (+ (square x) (square y)))
	(atan y x)))

(define (magnitude z) (car z))
(define (angle z) (cdr z))

(define (real-part z)
  (* (magnitude z) (cos (angle z))))
(define (imag-part z)
  (* (magnitude z) (sin (angle z))))

那么如何才能让一个系统里面同时存在两种表示方式呢？很容易想到的就是打上一个 tag，然后根据这个 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)))

然后我们就可以构建通用的选择函数：

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

但是我们可以看到，这样的系统会存在一个明显的问题，就是可加性 (additively ) 非常差。当我们需要新增一种数据表示方式的时候，我们就需要修改之前所有相关的构造函数和选择函数。

有一种新的思路可以解决这个问题，我们称之为数据导向 ( data-directed ) 的。其实就是为不同的数据类型单独定义它自身的选择函数，然后使用一个通用的 apply 过程去为不同的数据表示使用不同的选择函数。很自然的，我们所需要构建的选择函数和数据表示的关系应该是这样一张表：

Operations Polar Rectangle
real-part real-part-polar real-part-rectangle
imag-part imag-part-polar imag-part-rectangle
magnitude magnitude-polar magnitude-rectangle
angle angle-polar angle-rectangle

所以每次创建新的数据表示方式，就只需要将新的选择函数插入这个表中。而通用的 apply 会自动选择适合的函数：

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

另外，相比于我们最初增加 tag 之后形成的风格，还有一种消息传递 (message passing) 的风格。前者在处理的时候其实是将表格看成一行一行的，而后者则是看成一列一列的。比如这个风格下的构造函数，就是去判断所需要的选择函数（而不是数据表示方法）：

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

总的来说，我们一开始直接在抽象数据上增加 tag，会带来可加性比较差的问题，每增加一种数据表示就需要修改之前的函数。而 message passing 实际上没有解决这个问题，只是将看表格的方式 transform 了一下，从而使得可加性比较差的问题只在要增加选择函数的类型的时候才会出现，所以很少会碰到。而 data-directed 是一个更加全面的解决方案，通过在 apply-general 里面判断了 tag 而消除了可加性的问题。