数学 Lisp 实现加一操作
如何理解 lisp 里加一操作的这个实现？实在理解不了。
Exercise 2.6. In case representing pairs as procedures wasn't mind-boggling enough, consider that, in a language that can manipulate procedures, we can get by without numbers (at least insofar as nonnegative integers are concerned) by implementing 0 and the operation of adding 1 as
(define zero (lambda (f) (lambda (x) x)))
(define (add_1 n)
(lambda (f) (lambda (x) (f ((n f) x)))))
这是 Church number 的自然数定义。出发点就是你除了 lamda 以外什么都没有，推出整个数学体系的各种定理 (例如 1+1 = 2, x + y = y + x 等等). 最基本的第一步就是建立整数体系。
首先是 0 怎么定义？我们猜把 identity 函数定义为 0 可能比较好
0 = λx.x
1 是 0 的后继数，2 是 1 的后继数，我们想到 f(x) 这种形式可能适合作为"后继" 的表述
1 = λx. f(x)
上面这样写不行，f 哪里来不知道，所以我们套一层，重新定义 0, 1, 2, ...
0 = λf. λx. x
1 = λf. λx. f(x)
2 = λf. λx. f(f(x))
假设我们有数字 n, 我们先要从数字的定义中取出 x, f(x), f(f(x))... 来
n(f)(x)
然后给多套一层 f()
f(n(f)(x))
所以
add_1 = λn. λf. λx. f(n(f)(x))
这个就是老子的，一生二，二生三，三生万物。。。好吧我承认我在扯淡。
推荐这个 http://hi.baidu.com/xiangxuehai000/item/30b7583024bd02c91a9696c6 觉得可以考虑下重命名试试。 比如把 zero 改成 zero-time-operation?
倒是觉得这句话很牛逼“算法可计算函数都是递归函数“ http://zhidao.baidu.com/link?url=hQqthbqY96AAqUkUJWevU8k7Qr6At1cnDHavhiioUdyvCQyYurfRK3DW1D6yhdofx9VtzniqFDPh_R-8KogAJK
觉得递归，就是定义了 0，然后定义了 1，再然后再在上面构建加法，乘法什么的。这个是不是就是丘奇数的意义？我不知道。。。
church 比图灵早提出的一种计算模型，实际上却没法流行开来，为什么呢，因为没现实对照物，图灵以 side effect 弄了个比老师更好用的模型，直接影响了后来计算机的发展。
！