数据抽象

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

2016-04-09

blog