2.6

练习 2.6 如果觉得将序对表示为过程还不足以令人如雷灌顶，那么请考虑，在一个可以对过程做各种操作的语言里，我们完全可以没有数（至少在只考虑非负整数的情况下），可以将0和加一操作实现为：

(define zero (lambda (f) (lambda (x) x)))

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

这一表示形式称为 Church 计数，名字来源于其发明人数理逻辑学家Alonzo Church（丘奇），$\lambda$ 演算也是他发明的。

请直接定义one和two（不用zero和add-1）（提示：利用代换去求值（add-1 zero））。请给出加法过程+的一个直接定义（不要通过反复应用add-1）。

先体验一下

先定义一个 to-int 方法，用来将 Church 计数转换为整数，以增进对 Church 计数的直观理解。

(define (to-int proc) ((proc (lambda (n) (+ n 1))) 0))

以上 to-int 方法，接收一个过程作为参数，该过程是用来表示数字的过程。然后，to-int 就调用该过程，并将一个把收到的参数增加 1 的函数作为参数传入，这样就得到了一个新的过程。最后，调用这个新的过程，并且用 0 做最后这个新的过程的参数，就完成了 to-int。

(to-int zero)

(to-int (add-1 zero))

to-int 可以写得罗嗦一点，就是这样的形式：

(define (inc n) (+ n 1))
(define (term proc) (proc inc))
(define (to-integer proc) ((term proc) 0))

(to-integer zero)

(to-integer (add-1 zero))

可以看出，to-integer 就是把表示数的操作应用于 inc 上，并且用 0 作为参数传入新得到的过程的求值结果。

这个 Church 计数很烧脑，我一开始一头雾水，只是直觉上觉得它很巧妙，让我想起了多年前一位谷哥程序员面试我时，给我写的一段 javascript 代码，不同于一般的要求用闭包实现 count()，每次执行就在上次的结果上加 1，他的实现，不依赖任何数字，但是依赖传入的参数的形式。现在想想，应该就是用了 Church 计数。

在网上搜索了一些信息，才知道这里的 zero 和 add-1，都是用一种可以表示数的过程（本身不是数），并且看了 https://tomstu.art/programming-with-nothing#numbers 这里的 ruby 版 to_integer 实现，仿写了 Scheme 的实现。

实现 one

由于已经在网上看了一些解释，再加上回过头来看 zero 的实现，就很清楚要实现数字几，就把 f 应用于传入的参数 x 上几次（zero 的 f 被应用了 0 次）。所以 one 的实现如下：

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

使用 to-int 验证一下：

(to-int one)

题目的提示中，说可以用代换法，我们来看一看，one = (add-1 zero)，即

one = (add-1 zero)
    = (lambda (f) (lambda (x) (f ((zero f) x))))

注意到 (lambda (f) (lambda (x) x)) = zero，因此

(zero f) = (lambda (x) x)
((zero f) x) = x

原来，lambda 就是替换呀！（在等式一边去掉 lambda，并把该lambda 的参数移到另一边，等式仍然成立）

于是，one 的实现就是：

one = ...
    = (lambda (f) (lambda (x) (f x)))

通过一步步演算，就得到了从网上启发出来的最后结果。

实现 two

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

(to-int two)

将 zero、one 和 two 的实现放在一起，很容易发现规律，不会那么烧脑，甚至是相当直观的。数字几就是把传入的函数 f 应用了几次，并且是应用在最初传入的参数 x 上，并且将应用 f 后结果做为下次的 x 传入 f。

但是在实现 one 和 two 之前，直接看了 add-1，彻底被整蒙了。在更好地理解了 zero、one 和 two 的实现之后，再看看 add-1 的实现，就明白了那个参数 n，不是数字，是表示数字的过程。而这个表示数字的过程，其参数是 f，并且在接收 f 后返回另一个函数，再接受一个参数 x，这就是为什么 add-1 会写成这样（(n f) x）。

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

实现 + 加法

直接将这种表示数的过程相加，还是难以理解。为了过渡，先实现 add-2：

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

; 期待得到 3
(to-int (add-2 one))

再实现 add-3：

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

; 期待得到 5
(to-int (add-3 two))

还是难以理解，不过可以发挥一些想像力（纯粹直观猜测），((n f) x) 是不是意味着把 f 往 x 上应用 n 次？只不过，实现上 n 不是一个原始数，而是一个过程，但既然这个过程用来表示数，在上面这个抽象的语境下，它就是 n 的意思？不然，题目为什么把这个取名为 n 呢？

如果是这样，上面的 add-2 和 add-3 应该可以简化（利用已经定义了的 two 以及再定义一个 three）：

(define (add-two n)
    ;;;;;;;;;;;;;;;;;;;; 这里的 f，直接改成 two 试试看，即把 (f (f ...)) 改成 ((two f) ...)
    (lambda (f) (lambda (x) ((two f) ((n f) x)))))

; 期待得到 3
(to-int (add-two one))

居然可以！这样太棒了，把 f 需要重复应用几次的操作也参数化了！这是我平时的编程工作中，一直想要做到的事情，但是却不会，还曾经一直猜想这是否能够做到。原来，Church 计数就是把这个过程抽象出来！高级、真高级！！

顿时有种“众里寻她千百度，蓦然回首”的这种 Aha 感觉。

现在， add-three 我也会了：

(define three (lambda (f) (lambda (x) (f (f (f x))))))

(to-int three)

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

; 期待得到 5
(to-int (add-three two))

现在，任意两数相加我也会了！

(define (add n m)
    (lambda (f) (lambda (x) ((n f) ((m f) x)))))

; 期待得到 5
(to-int (add two three))

写出来后，发现其实很直观！将 f 在 x 上应用 m 次，然后再将 f 在前面的结果上应用 n 次，就是这个过程！