不用数字也能计算：Church 编码

lambda 演算的基本语法只有变量、函数和调用。前一篇已经写出规约器，说明函数应用可以通过替换一步步化简。

接下来的问题是数据从哪里来。日常编程语言有数字、布尔值、条件表达式和集合；纯 lambda 演算没有这些原语。Church 编码给出一种极端答案：数据可以表示成行为。布尔值是“选择左边还是右边”的函数，数字是“把某个函数重复执行多少次”的函数。

本文用 Python 高阶函数实现 Church boolean 和 Church numeral，再把它们映射回工程直觉。

数据也可以是行为

普通编程里，数字 2 看起来是一块数据。Church 编码换一个定义：

2 = 接收函数 f 和初始值 x，然后执行 f(f(x))

也就是说，数字不再保存为整数对象，而是保存为“重复应用函数的次数”。

布尔值也类似：

true  = 选择第一个分支
false = 选择第二个分支

这个视角把“值是什么”改成“值能做什么”。在 lambda 演算里，只要函数和调用足够表达这些行为，就可以构造出数字、布尔值和条件选择。

Church 布尔值

Church boolean 的定义很短。

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 接收两个值，返回第二个。条件表达式可以直接写成：

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"。条件判断不需要特殊语法，只是把布尔函数应用到两个候选分支上。

模式提炼：布尔值是选择器

boolean = choose(first, second)

这个模式在工程中并不陌生。策略对象、回调、分支选择器都可以把“状态值”改写成“选择行为”。布尔值不必总是先变成 if，也可以作为一个可调用对象决定后续路径。

Church 数字

Church numeral 把自然数定义成函数重复次数。

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：

def INCREMENT(n: ChurchNumeral[T]) -> ChurchNumeral[T]:
    return lambda f: lambda x: f(n(f)(x))

n(f)(x) 表示执行 f 共 n 次。外层再包一层 f(...)，就变成执行 n + 1 次。

于是可以构造：

ONE = INCREMENT(ZERO)
TWO = INCREMENT(ONE)
THREE = INCREMENT(TWO)

用 Church 数字构造数字

Church 数字也可以“驱动”另一个函数。TWO(INCREMENT)(ZERO) 的含义是：从 ZERO 开始，把 INCREMENT 执行两次。

TWO(INCREMENT)(ZERO)
  = INCREMENT(INCREMENT(ZERO))
  = TWO

这就是“数据作为行为”的味道。TWO 本身不保存整数 2，它保存的是“执行两次”的能力。把这个能力作用在 INCREMENT 和 ZERO 上，就得到 Church 数字二。

加法也可以用同样方式实现。

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 值观察结果

为了让输出可读，可以写两个转换函数。

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，观察它执行了几次。

完整示例

完整代码如下。

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))

运行结果：

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 只做选择：

true: True
false: False
if true: left
if false: right

TRUE 和 FALSE 的差别只在于返回第一个参数还是第二个参数。IF 没有实现新的控制结构，只是把条件函数应用到两个分支上。

后六行说明 Church numeral 是重复次数：

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 编码会很别扭，因为泛型和函数式接口语法较重。但它提供了一个清晰的抽象：数据结构不一定靠字段保存，也可以靠统一接口暴露行为。策略模式、访问者模式、解释器模式都能看到这个思路。

模式提炼：数据表示的抽象层

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，比较类型声明的复杂度。

系列导航

• 上一篇：写一个 lambda 规约器
• 下一篇：通用性：一种机器怎样模拟另一种机器
• 系列入口：重读《计算的本质》：给 Java 程序员的可计算性入门

参考资料

• Understanding Computation 官方目录
• Tom Stuart/computationbook 示例代码仓库
• Python 文档：typing.TypeVar
• Java 文档：Function