SICP 习题 2.6 之丘奇数

16 年时阅读 SICP 时写下这篇文章，现在看来感觉还可以，再次发出来和大家一起讨论一下。

最近一直在阅读《SICP》，然后下午做其中的习题 2.6，对其题意很不理解，于是搜索了相关资料，不禁如题设所说感到如雷灌顶，特此记录下来，以供大家阅读和交流。

题目

请考虑，在一个可以对程序做各类操作的语言中，我们完全可以没有数（至少是没有整数，比如说 0，1，2）的情况下，可以将 zero 和加一操作实现为：

(define zero (lambda (f) (lambda (x) x)))  # 定义zero(define (add-1 n)    (lambda (f) (lambda (x) (f ((n f) x))))) # 定义加一操作

上述语言是 LISP，同学们不必了解其语法，也能大致了解语句的含义。下一小节中会做出具体的解释。

这一表现形式称为 Church 计数，也就是丘奇数，名字来源于其发明人数理学家 Church，请直接定义 one 和 two（不使用 zero 和 add-1 ）（提示：利用代换法去求值）。请给出加法过程 + 的一个直接定义（不要反复应用 add-1 ）

丘奇数

说实话，我一直没有看懂题目中关于 zero 和 add-1 的定义，于是我搜索了相关资料。下边就结合资料谈一下它的概念。

首先要明确的是丘奇数中的 zero，one 并不等同于数值上的 0, 1, 2。你可以理解为它是零概念的一种表现形式。换句话说，它就是零的函数式表现形式，而整数 0 则是零的数值表现形式。我们先来看一下丘奇数中 zero，one 和 two 的表现形式。

(define zero  (lambda (f) (lambda (x) x)))(define one  (lambda (f) (lambda (x) (f x))))(define two  (lambda (f) (lambda (x) (f (f x)))))

我们会发现 zero，one 和 two 都是一个函数，它接收 (f) 作为参数，其返回结果是一个接收 (x) 作为参数的函数。大家可能需要注意的是，(f) 在这里显然也是一个函数，在 LISP 中函数是可以作为输入参数的。然后我们会发现 zero，one 和 two 的区别好像就是 (f) 函数被使用的次数。 zero 中 (f) 没有被使用，one 中 (f) 使用了一次，two 中 (f) 使用了两次。丘奇数就是用这个次数来表示 0, 1, 2 的概念。

我们可以实验一下检验一下

(define (inc n) (+ n 1)) ;inc是加一操作，作为zero的参数，返回一个函数，作用于数字0> ((zero inc) 0)  0 > ((zero inc) 1)1> ((one inc) 1)2> (((add-1 one) inc) 1)3

我们定义一个过程 inc 就是数值意义上的加一，然后使用 zero, one 和 add-1 发现确实如同我们所想的，zero 表示 inc 过程不会被使用，返回原数值；one 表示 inc 被使用一次，返回加一的数值。

替换法求 one

我们来使用替换法通过 add-1 和 zero 来求解 one 吧，求解 two 的过程类似。

(add-1 zero) ;展开add-1定义(lambda (f) (lambda (x) (f ((zero f) x))))
; 替换zero(lambda (f) (lambda (x) (f ((lambda (x) x) x))))
; 简化,因为((lambda (x) x) x)就等于x(lambda (f) (lambda (x) (f x)))

加法定义

首先我们要明白丘奇数加法的含义，我们先记其加法为 add-church ,那么如下代码所示，最后一个过程得出的值应该是多少呢？

> ((one incr) 1)2> ((two incr) 1)3> (((add-church one two) incr) 1)?

根据猜测，应该是 4 吧。因为 one 表示 incr 对 1 这个数值使用一次，two 标示使用两次，那么将二者加起来，那么就应该是 three 的含义啦，就是表示 incr 对 1 这个数值使用 3 次，那么就是 4 啦。

add-church 的实现如下

(define (add-church m n)   (lambda (f) (lambda (x) ((m f) ((n f) x)))))(define (add-1 n)    (lambda (f) (lambda (x) (f ((n f) x))))) # 定义加一操作

如果你将其与 add-1 进行对比，你会发现 add-1 中的 f 变成了(m f) ，如果把 add-1 中的 f 记住(one f)，你可能就会更加理解。

比如 (f) 为 incr 函数，(n incr) 的结果就是一个进行 n 次 incr 的函数，(incr ((n incr) x)) 就是在 (n incr) 的基础上再进行一次 incr，所以就表示了 add-1 操作。所以((m incr) ((n incr) x))就代表在 (n incr) 的基础上再进行 m 次 incr，所以就是 add-church 操作。

那么大家思考一下， add-m 应该如何表示呢？