[SICP] Church 计数

[yangruihan]

最近计划抽空余时间重读一下经典书籍《SICP》，看到习题 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（丘奇），λ演算也是他发明的。

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

---

以下是思考和解答：

首先使用代换方法求值(add-1 zero)

代换为（以下用λ来表示lambda）：

(λ (f) (λ (x) (f ((zero f) x))))
->
(λ (f) (λ (x) (f ((λ (x) x) x))))
->
(λ (f) (λ (x) (f x)))

于是one可以定义为：

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

同理可以得到two的定义为：

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

可以发现，Church计数通过将f函数作为参数，又用另一个λ函数将其包起来，f不会立即求值，通过f函数的调用次数来表示数值，非常巧妙。

于是我们可以通过下面的代码来显示具体的数字，进行调试：

(define (show-num n)
    ((n (lambda (x) (+ x 1))) 0)
)

其中(n (λ (x) (+ x 1)))，n为上述定义的代表数值的函数（即上述one、two等），其返回一个调用λ函数n次的函数，这里的λ函数，即上文提到的f，我们只要调用这里返回的函数，并传入初值0就可以通过调用次数，累加到对应的数值。

比如：

(newline)
(display (show-num one)) ; 1
(newline)
(display (show-num two)) ; 2

那么，相加操作就是对f函数调用次数的相加：

(define (add a b)
    (lambda (f)
        (lambda (x) 
            ((a f) ((b f) x))
        )
    )
)

也可以推导出相乘函数：

(define (multi a b)
    (lambda (f)
        (lambda (x)
            ((a (b f)) x)
        )
    )
)

完整测试代码如下：

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

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

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

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

(define (add a b)
    (lambda (f)
        (lambda (x) 
            ((a f) ((b f) x))
        )
    )
)

(define (multi a b)
    (lambda (f)
        (lambda (x)
            ((a (b f)) x)
        )
    )
)

(define (show-num n)
    ((n (lambda (x) (+ 1 x))) 0)
)

(define three (add-1 two))

(newline)
(display (show-num one))
(newline)
(display (show-num two))
(newline)
(display (show-num three))
(newline)
(display (show-num (add two three)))
(newline)
(display (show-num (add (add two three) (add one two))))
(newline)
(display (show-num (multi three three)))
(newline)
(display (show-num (multi (multi three three) (multi two three))))
(newline)

参考：Church计数