lambda 演算的基本语法只有变量、函数和调用。前一篇已经写出规约器，说明函数应用可以通过替换一步步化简。
接下来的问题是数据从哪里来。日常编程语言有数字、布尔值、条件表达式和集合；纯 lambda 演算没有这些原语。Church 编码给出一种极端答案：数据可以表示成行为。布尔值是“选择左边还是右边”的函数，数字是“把某个函数重复执行多少次”的函数。
本文用 Python 高阶函数实现 Church boolean 和 Church numeral，再把它们映射回工程直觉。
数据也可以是行为
普通编程里，数字 2 看起来是一块数据。Church 编码换一个定义：
1
| 2 = 接收函数 f 和初始值 x，然后执行 f(f(x))
|
也就是说，数字不再保存为整数对象，而是保存为“重复应用函数的次数”。
布尔值也类似：
1
2
| true = 选择第一个分支
false = 选择第二个分支
|
这个视角把“值是什么”改成“值能做什么”。在 lambda 演算里，只要函数和调用足够表达这些行为，就可以构造出数字、布尔值和条件选择。
Church 布尔值
Church boolean 的定义很短。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| from collections.abc import Callable
from typing import TypeVar
T = TypeVar("T")
ChurchBoolean = Callable[[T], Callable[[T], T]]
def TRUE(x: T) -> Callable[[T], T]:
return lambda y: x
def FALSE(x: T) -> Callable[[T], T]:
return lambda y: y
|
TRUE 接收两个值，返回第一个。FALSE 接收两个值，返回第二个。条件表达式可以直接写成：
1
2
| def IF(condition: ChurchBoolean[T]) -> Callable[[T], Callable[[T], T]]:
return lambda consequence: lambda alternative: condition(consequence)(alternative)
|
IF(TRUE)("left")("right") 得到 "left"，IF(FALSE)("left")("right") 得到 "right"。条件判断不需要特殊语法，只是把布尔函数应用到两个候选分支上。
模式提炼：布尔值是选择器
1
| boolean = choose(first, second)
|
这个模式在工程中并不陌生。策略对象、回调、分支选择器都可以把“状态值”改写成“选择行为”。布尔值不必总是先变成 if，也可以作为一个可调用对象决定后续路径。
Church 数字
Church numeral 把自然数定义成函数重复次数。
1
2
3
4
5
| ChurchNumeral = Callable[[Callable[[T], T]], Callable[[T], T]]
def ZERO(f: Callable[[T], T]) -> Callable[[T], T]:
return lambda x: x
|
ZERO 表示执行 f 零次，所以直接返回初始值 x。
自增函数把一个数字 n 变成 n + 1：
1
2
| def INCREMENT(n: ChurchNumeral[T]) -> ChurchNumeral[T]:
return lambda f: lambda x: f(n(f)(x))
|
n(f)(x) 表示执行 f 共 n 次。外层再包一层 f(...)，就变成执行 n + 1 次。
于是可以构造：
1
2
3
| ONE = INCREMENT(ZERO)
TWO = INCREMENT(ONE)
THREE = INCREMENT(TWO)
|
用 Church 数字构造数字
Church 数字也可以“驱动”另一个函数。TWO(INCREMENT)(ZERO) 的含义是：从 ZERO 开始，把 INCREMENT 执行两次。
1
2
3
| TWO(INCREMENT)(ZERO)
= INCREMENT(INCREMENT(ZERO))
= TWO
|
这就是“数据作为行为”的味道。TWO 本身不保存整数 2，它保存的是“执行两次”的能力。把这个能力作用在 INCREMENT 和 ZERO 上，就得到 Church 数字二。
加法也可以用同样方式实现。
1
2
| def ADD(m: ChurchNumeral[T]) -> Callable[[ChurchNumeral[T]], ChurchNumeral[T]]:
return lambda n: lambda f: lambda x: m(f)(n(f)(x))
|
n(f)(x) 先执行 f 共 n 次，m(f)(...) 再执行 m 次，总共就是 m + n 次。
转回 Python 值观察结果
为了让输出可读，可以写两个转换函数。
1
2
3
4
5
6
| def to_bool(boolean: ChurchBoolean[bool]) -> bool:
return boolean(True)(False)
def to_int(numeral: ChurchNumeral[int]) -> int:
return numeral(lambda x: x + 1)(0)
|
to_bool 把 Church boolean 应用到 Python 的 True 和 False。to_int 把 Church numeral 应用到 “加一” 函数和初始值 0，观察它执行了几次。
完整示例
完整代码如下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| from collections.abc import Callable
from typing import TypeVar
T = TypeVar("T")
ChurchBoolean = Callable[[T], Callable[[T], T]]
ChurchNumeral = Callable[[Callable[[T], T]], Callable[[T], T]]
def TRUE(x: T) -> Callable[[T], T]:
return lambda y: x
def FALSE(x: T) -> Callable[[T], T]:
return lambda y: y
def IF(condition: ChurchBoolean[T]) -> Callable[[T], Callable[[T], T]]:
return lambda consequence: lambda alternative: condition(consequence)(alternative)
def ZERO(f: Callable[[T], T]) -> Callable[[T], T]:
return lambda x: x
def INCREMENT(n: ChurchNumeral[T]) -> ChurchNumeral[T]:
return lambda f: lambda x: f(n(f)(x))
def ADD(m: ChurchNumeral[T]) -> Callable[[ChurchNumeral[T]], ChurchNumeral[T]]:
return lambda n: lambda f: lambda x: m(f)(n(f)(x))
def to_bool(boolean: ChurchBoolean[bool]) -> bool:
return boolean(True)(False)
def to_int(numeral: ChurchNumeral[int]) -> int:
return numeral(lambda x: x + 1)(0)
ONE = INCREMENT(ZERO)
TWO = INCREMENT(ONE)
THREE = INCREMENT(TWO)
TWO_BY_ITERATION = TWO(INCREMENT)(ZERO)
FIVE = ADD(TWO)(THREE)
print("true:", to_bool(TRUE))
print("false:", to_bool(FALSE))
print("if true:", IF(TRUE)("left")("right"))
print("if false:", IF(FALSE)("left")("right"))
print("zero:", to_int(ZERO))
print("one:", to_int(ONE))
print("two:", to_int(TWO))
print("three:", to_int(THREE))
print("two by iteration:", to_int(TWO_BY_ITERATION))
print("two + three:", to_int(FIVE))
|
运行结果：
1
2
3
4
5
6
7
8
9
10
| true: True
false: False
if true: left
if false: right
zero: 0
one: 1
two: 2
three: 3
two by iteration: 2
two + three: 5
|
读取执行结果
前四行说明 Church boolean 只做选择：
1
2
3
4
| true: True
false: False
if true: left
if false: right
|
TRUE 和 FALSE 的差别只在于返回第一个参数还是第二个参数。IF 没有实现新的控制结构，只是把条件函数应用到两个分支上。
后六行说明 Church numeral 是重复次数：
1
2
3
4
5
6
| zero: 0
one: 1
two: 2
three: 3
two by iteration: 2
two + three: 5
|
to_int 用 Python 的加一函数观察重复次数。TWO_BY_ITERATION 展示了 Church 数字可以驱动 INCREMENT，FIVE 展示了加法可以由函数组合得到。
Java 程序员的迁移表
| Church 编码 |
Java 对照 |
工程含义 |
TRUE / FALSE |
Function<T, Function<T, T>> |
分支选择器 |
IF(condition) |
策略选择 / lazy branch |
控制结构函数化 |
ZERO / ONE / TWO |
高阶函数 |
数据表示为调用次数 |
INCREMENT |
函数组合 |
在行为外再包一层行为 |
ADD |
组合器 |
把两个行为串接 |
to_int |
adapter |
把抽象表示投影成宿主语言值 |
Java 里直接写 Church 编码会很别扭，因为泛型和函数式接口语法较重。但它提供了一个清晰的抽象：数据结构不一定靠字段保存，也可以靠统一接口暴露行为。策略模式、访问者模式、解释器模式都能看到这个思路。
模式提炼：数据表示的抽象层
1
| external_value <-> encoded_behavior
|
to_int 和 to_bool 很像适配器。内部使用 Church 编码，外部观察时再转回 Python 值。工程系统里也常见这种分层。
| 场景 |
内部表示 |
外部观察 |
| Church numeral |
函数重复次数 |
Python int |
| ORM |
对象图 / change set |
SQL |
| 编译器 IR |
中间表示 |
机器码 / 字节码 |
| 查询引擎 |
逻辑计划 |
结果集 |
| 规则引擎 |
规则网络 |
决策结果 |
这一层抽象让内部表示可以按计算需求设计，而不被外部展示形式绑死。
与 lambda 规约器的关系
本文使用 Python 函数直接运行 Church 编码。放回前一篇的 lambda 规约器里，TRUE、FALSE、ZERO、INCREMENT 也可以写成 lambda 表达式，然后通过规约得到同样结果。
差别只在表现形式：Python 函数把规约交给宿主语言执行，lambda 规约器显式打印每一步替换。两者表达的是同一件事：函数应用足以表示数据和计算过程。
练习
第一，实现 MULTIPLY(m)(n)，让它表示 m * n。
第二，实现 IS_ZERO(n)，让 IS_ZERO(ZERO) 得到 TRUE，IS_ZERO(ONE) 得到 FALSE。
第三，把 to_int 的初始值从 0 改成 10，观察 Church numeral 表示的“次数”如何作用在不同初始值上。
第四，用 Java 的 Function 尝试写出 TRUE 和 FALSE，比较类型声明的复杂度。
参考资料
