Church Encoding 是一种以函数的调用次数为计数方式的编码方式^{[1]编码是这样的一套规则，它定义了从符号集到某事物的映射关系，比方以数字 2 代表第二个东西。}，比如将调用 0 次定义为 0，把增加一次调用定义为自加：

将 0 定义为：f -> x -> x
将 1 定义为：f -> x -> f(x)
将 2 定义为：f -> x -> f(f(x))
依此类推

# Church Encoding ↵

按照 Church Encoding 的定义，我们可以很容易的写出 Church Encoding 中的 0 1 2：

00;; 定义 0 
01(define zero
02    (lambda (f) (lambda (x) x)) )
03
04;; 直接写出 1 的定义
05(define one
06    (lambda (f) (lambda (x) (f x))))
07
08;; 直接写出 2 的定义
09(define two
10    (lambda (f) (lambda (x) (f (f x) ))))

Church 其实是一种计数方式，因此需要定义它如何计数，而它是利用函数的调用次数来计数的，因此，它的自增可以这样实现：

00;; 定义自加
01(define (add-1 n)
02    (lambda (f)
03        (lambda (x)
04            (f ((n f) x)))))

那，两个 Church Number 之间的加法怎么弄呢？比如 a + b，那么需要把 f 调用 (a + b) 次就行，实现如下：

00;; 写出 Church Encoding 的加法
01(define (add a b)
02    (lambda (f)
03        (lambda (x)
04            ((a f) ((b f) x)) )))

# 退化为正整数 ↵

注意到这种编码方式是以函数的调用次数为计数方式，因此我们可以将这种编码方式用来编码我们的正整数，也就是将 Church Encoding 退化为我们熟知的整数：

00;; 利用 inc 将 Church 退化为数学上的正整数
01
02;; 这个是数学上的自加
03(define (inc x) (+ x 1))
04
05;; one 是上面的定义，这里的结果是整数 1
06((one inc) 0)
07;; 结果是整数 2
08((two inc) 0)
09
10;; 验证 add 是否正确 （如果正确，则结果应该是 3）
11(define three (add one two))
12((three inc) 0)

有趣。

# JavaScript 等价写法 ↵

00// 定义 0 
01const zero = f => x => x;
02
03// 直接写出 1, 2 的定义
04const one = f => x => f(x);
05const two = f => x => f(f(x));
06
07// 定义自加
08const add_1 = n => f => x => f(n(f)(x));
09
10// 写出 Church Encoding 的加法
11const add = (a, b) => f => x => a(f)(b(f)(x));
12
13// 整数自加
14const inc = x => x + 1;
15
16// 测试
17console.log('Church To Number 1:', one(inc)(0));
18console.log('Church To Number 2:', two(inc)(0));
19
20const three = add(one, two);
21console.log('Church To Number 3:', three(inc)(0));

虽然 js 写起来简洁很多，但是括号和表达式的中缀写法使得函数体读起来不太舒服（很多括号）

编码是这样的一套规则，它定义了从符号集到某事物的映射关系，比方以数字 2 代表第二个东西。 ↩︎