我们从一道习题开始，解决 Church 数的各种定义和操作。
SICP 习题 2.5:
Church 数(church number)用 Scheme 语言是这样定义的：
(define zero (lambda (f) (lambda (x) x))) (define (1+ n) (lambda (f) (lambda (x) (f ((n f) x)))))
这样，我们有了 “零”(zero) 和一个可以把一个 church 数加 1 的操作符 1+. 那么问题是：
上面的东西很抽象。只有做实验才能体会到它的中心思想。
我们先定义一个函数 f，用来作为 church 数的参数：
(define (f x) (cons 'x x))
然后用 1+ 和 zero 定义出 one 和 two。这违反了题目规则，但是 这可以让我们对问题的实质有更清晰的认识。
(define one (1+ zero)) (define two (1+ one))
那么
从上面的实验可以看出：
其实数“零”(zero) 是这样一个函数，它接受一个函数 f 作为参数， 然后返回一个函数，这个函数原封不动的把它的参数 x 返回。
1+ 的意思就是：不管参数 n 是怎样一个 church 数，返回这样一个 church 数：这个 church 数接受一个函数 f 作为参数，然后返回一 个函数，这个函数比 (n f) 对它的参数 x 多进行一次 f 操作。
一个 church 数就是这样一个函数，它接受一个函数 f 作为参数， 然后返回一个函数，这个函数对它的参数 x 进行某种数量的 f 操作， 然后返回结果。这个 f 操作的嵌套层数就是这个 church 数区别于 其它 church 数的特征。
(define one (lambda (f) (lambda (x) (f x)))) (define two (lambda (f) (lambda (x) (f (f x)))))
加法就很简单了当 (b f) 对 x 嵌套执行 church 数 b 表示的次数 后，再用 (a f) 对这个结果嵌套 a 次 f.
(define (add a b) (lambda (f) (lambda (x) ((a f) ((b f) x)))))
为了让我的解释器的加法 "+" 能继续工作，我用了 add 这个名字。
来试一下：
(define three (add one two)) ((three f) '())
结果是 '(x x x)。正确。
其实加法有一个更加简单的定义，但是这需要使用以前定义过的 1+ 操作：
(define (add2 a b) ((a 1+) b))
很简单吧。就是对 b 进行 a 次嵌套的 1+.
SICP 的习题只要求我们定义出加法，但是做完了之后似乎意犹未尽。 所以我们接着来把剩下的东西都定义出来吧。
更进一步，乘法如何定义呢？
(define (mul a b) (lambda (f) (lambda (x) ((a (b f)) x))))
它的意思是，通过两个 church 数，返回一个 church 数。这个 church 数接受一个函数 f 作为参数，返回一个函数。这个函数把 (a (b f)) 作用于它的参数 x。
这个 (a (b f)) 怎样理解呢？(b f) 实际上就是这样一个函数，它 对它的参数嵌套执行函数 f，嵌套的层数是 church 数 b 表示的数。 那么 (a (b f)) 就是这样一个函数，它对它的参数嵌套执行函数 (b f), 嵌套的层数是 church 数 a 表示的数。这样 (a (b f)) 实际上 就是这样一个函数，这个函数对它的参数嵌套执行 church 数 a 和 b 的积那么多次 f。
我们可以用这个乘法对 two 和 three 进行操作得到一个 six:
(define six (mul two three)) ((six f) '())
((six f) '()) 的结果是 '(x x x x x x)。
乘方就更简单了：
(define (pow a b) (b a))
试一下：
(define eight (pow two three)) ((eight f) '())
((eight f) '()) 结果是 '(x x x x x x x x).
布尔变量可以这样定义：
(define true (lambda (x y) x)) (define false (lambda (x y) y))
那么我们可以定义一个判断语句 if*:
(define if* (lambda (test a b) (test a b)))
那么 (if* true one two) 会得到 one. (if* false one two) 会得 到 two. 注意这个简单的 if* 必须明确写出两个判断的后果。
接着我们可以定义一些布尔操作符：与，或，非，蕴涵。
(define and* (lambda (a b) (if* a b false))) (define or* (lambda (a b) (if* a true b))) (define not* (lambda (x) (if* x false true))) (define implies* (lambda (a b) (or* (not* a) b)))
我们可以接着定义一个永远为假的函数 always-false:
(define always-false (lambda (x) false))
接着我们就能定义一个能够判断一个 Church 数是不是“零”的函数：
(define is-zero?
(lambda (n)
((n always-false) true)))
因为 always-false 只有对 true 嵌套执行 0 次的时候才能返回 true，否则返回 false.
我们能定义出 cons, car 和 cdr 等 pair 操作，以及 null 和用来 判断null 的 null?*。这样我们就可以使用 pair 和 list 了。list 只不过就是最后一个 cdr* 是 null 的 pair.
为了不跟原来的操作符名字冲突， 我为它们每个都加一个 *.
(define cons*
(lambda (a b)
(lambda (c)
(c a b))))
(define car*
(lambda (pair)
(pair true)))
(define cdr*
(lambda (pair)
(pair false)))
(define null
(lambda (x) true))
(define null?*
(lambda (d)
(d (lambda (x y) false))))
下面是测试例子：
(define c1 (cons* one two)) (car* c1) (cdr* c1) (null?* null) (null?* c1)
我们定义一个函数 f*，它能够由 list (x) 得到 (x+1 x)。
(define f*
(lambda (x)
(cons* (1+ (car* x)) x)))
那么我们就可以定义前驱函数 pred 为:
(define pred
(lambda (n)
(if* (is-zero? n)
zero
(car* (cdr* ((n f*) (cons* zero null)))))))
(((pred three) f) '())
它从一个 (n n-1 n-2 ... zero) 的 list 里取出第二个元素。 如果我们把一个 church 数作用于这个 pred 函数，就可以得到某一 个数前面的离它有一段距离的那个数了。
测试例子：
(((pred three) f) '()) ((((three pred) eight) f) '())
比较两个 church 数的大小可以有很多种办法，其中一种就是让一个 数在一个初值为 (false false) 的 list 前面嵌套 cons* 上 true。 然后然另一个数把这个生成的 list 不断的削减。如果削减到最底下， 它就能看到 false；说明第二个数比第一个大，反之，第二个数比第 一个小。
(define greater?*
(lambda (a b)
(car* ((b (lambda (z) (if* (car* z) (cdr* z) z)))
((a (lambda (z) (cons* true z))) (cons* false false))))))
(greater?* three two)
(greater?* two three)
这个似乎很难。lambda calculas 的发明者 Church 当年虽然设计出 了 Church number，却没能定义出减法和除法。
如果要用减法，我们首先要定义出带符号整数和负数……