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)))))
This representation is known as Church numerals, after its inventor, Alonzo Church, the logician who invented the
Define one and two directly (not in terms of zero and add-1). (Hint: Use substitution to evaluate (add-1 zero)). Give a direct definition of the addition procedure + (not in terms of repeated application of add-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)))))
根据上面的规律，数字 n，即表示为有 n 个 f 的 (lambda (f) (lambda (x) (f ... (f x))..))。
要定义 +，那么我们需要了解清楚，church 表示的数字有什么特点。
先看看对一个数字 n 的操作。(add-1 n) 的实际工作原理是使用这个表达式剥掉最外层的的两个 lambda：
<inner> = ((n f) x)
得到 (f ... (f x)...)。然后再加上一个 f 在 <inner> 里面。
<new-inner> = (f ((n f) x))然后再在最外面加上两个 lambda，得到 add-1 的结果。
我们可以看到，如果要将一个 n 加到 m 上面，我们可以仿照把 n 加到 1 上面一样。所以有 + 的表示思路：
首先剥掉最外层的两个 lambda：
<inner-n> = ((n f) x)
得到 n 的内层 (f (f (..n..((f x)...)。然后我们要在这个内层外面加上 m 个 f。因为数字 m 内层就有 m 个 f，所以只需要我们想办法将上面得到的 n 的内层，当做 m 的 lambda (x) 的参数传递进去，自然就有了 n+m 个 f 了。
<new-inner> = ((lambda (x) (f (f (..m..(f x)))))
(f (f (..n..(f x)))))
; => (f (f (f (..n+m..(f x)))))
所以我们的内层如下：
<new-inner> = ((m f) ((n f) x))
可以得到 + 表示如下：
(define (+ n m)
(lambda (f) (lambda (x) ((m f) ((n f) x)))))
可以看到，与 add-1 不一样的地方只是 (m f) 而已。