数据抽象

SICP在第二章(构造数据抽象)中提出了一个问题:
数据究竟意味着什么?
书中的答案是:数据是一组适当的选择函数和构造函数。
(这里的适当的是指那些能够刻画数据本质特征的)
也即是:数据是函数
书中接着举了例子,将序对用函数实现:

(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 的函数定义:

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

然后要求依据这两个定义,利用代换求值得到1和2的定义:

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

这就是丘奇计数(Church numerals)
初看add-1的定义比较难以理解,我们可以看看 three,four ,n 是如何定义的:

(define three
  (lambda (f)
    (lambda (x) (f (f (f x))))))
(define four
  (lambda (f)
    (lambda (x) (f (f (f (f x)))))))
(define n
  (lambda (f)
    (f (f (f ...(f x)...)))))    

哦,数字被定义成了f对x的作用次数。
但这个结论还有点问题,two其实是f对one作用了一次,n是f对n-1作用了一次,要想让上面结论正确就得要求(f x)的结果跟x属于同一个集合。这样f就能继续对结果进行作用,数学中对这样的特性有定义:若对某个集合的成员进行一种运算,生成的结果依然是这集合的成员,该集合被称为在这运算下闭合。而自然数集N在加法运算下确实是闭合的。
ps:其实这里的闭合数学上有时候称为闭包。但是跟我们说的函数闭包不是同一个概念。不要混淆。
现在数字被定义成了f对x的作用次数说的通了,那么我能积攒n次f然后再应用到x上吗?
就是(n f) 有意义吗?代入刚才的n的定义就知道了:

(define (n f)
  (lambda (x)
    (f (f (f ...( f x)...)))))

好了,再也不用写n次f了。回头再看add-1,是不是很自然了。

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