s sllt
← All posts
· 12 min read ·
#python #lambda-calculus #church-encoding #lambda

使用Python模拟Lambda演算

目录 · Table of Contents

我们将从下面这段程序开始：

python
1for i in range(1, 20):
2 if i % 3 == 0 or i % 5 == 0:
3 print(i)

这段程序会打印出 1 到 19 之间能被 3 或 5 整除的数字：

text
13
25
36
49
510
612
715
818

如果我们定下一个极端的限制：不允许使用 Python 内置的数字、布尔值、列表，不允许使用 +、-、%、==、or 等运算符，也不允许使用 if、for、range 甚至 def 具名函数——唯一允许使用的只有单参数的匿名函数 lambda x: ... 以及函数调用 f(x)，还能实现上面这段程序吗？

这正是阿隆佐·邱奇（Alonzo Church）在 20 世纪 30 年代提出 Lambda 演算（λ-calculus） 时所展示的核心思想：在只有“函数定义”与“函数调用”的世界里，函数本身就足以编码自然数、布尔值、算术运算、条件分支、递归乃至数据结构。这种仅用函数来构造数据与控制流的方法称为邱奇编码（Church Encoding）。

接下来，我们就以开头的 3 行代码为主线，每用 lambda 造出一个零件，就立刻替换掉原程序中的一部分，直到整段程序的计算过程完全由函数构成。

完整代码可以在文末查看，也可以直接下载 lambda_calculus.py。

1. 数字与基础算术

用“调用次数”表示自然数

数字的本质可以简单地描述为某一个动作的重复次数。比如“吃了 6 个苹果”，6 就代表重复执行了 6 次“吃”这个动作。同样地，在程序里，我们可以用某个函数 p 被调用了几次来表示数字。

比如数字 1 表示对初始值 x 调用 1 次 p：

python
1def one(p, x):
2 return p(x)

依照同样的定义，数字 2 就是调用 2 次 p：

python
1def two(p, x):
2 return p(p(x))

那么如何表示 0 呢？传入函数 p 但一次都不调用，直接返回 x，就表示 0 了：

python
1def zero(p, x):
2 return x

在 Lambda 演算中，每个函数只接收一个参数。如果要接收多个参数（例如 p 和 x），就让外层函数先接收 p，并返回一个接收 x 的新函数（即柯里化，Currying）。用 Python 的 lambda 表达式写出来就是：

python
1ZERO = lambda p: lambda x: x
2ONE = lambda p: lambda x: p(x)
3TWO = lambda p: lambda x: p(p(x))
4THREE = lambda p: lambda x: p(p(p(x)))

调用时依次传入两个参数即可，例如 THREE(p)(x) 会先算出 THREE(p) 得到一个新函数，再把 x 传进去，最终返回 p(p(p(x)))。

辅助函数 to_integer

由于 ZERO、ONE、TWO 本质上都是函数，直接打印它们只会看到 <function <lambda> at 0x...>。为了验证这些函数的确表示对应的数字，也为了让它们能暂时嵌回原 Python 程序中充当“脚手架”，我们可以写一个辅助函数 to_integer，把 lambda x: x + 1 当作 p、0 当作初始值 x 传进去：

python
1to_integer = lambda n: n(lambda x: x + 1)(0)

一个数字 n 内部把 p 调用了多少次，0 就会被加一多少次：

python
1>>> to_integer(ZERO)
20
3>>> to_integer(THREE)
43

后继、加法与乘法

如果继续按上面的方式手写原程序里用到的 5 和 20，代码会变成这样：

python
1FIVE = lambda p: lambda x: p(p(p(p(p(x)))))
2
3TWENTY = lambda p: lambda x: p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(p(x))))))))))))))))))))

手写 20 层括号已经让人眼花缭乱了。与其数括号，不如直接用函数实现“加一”和算术运算：

  • 后继函数 SUCC（加 1）：既然 n(p)(x) 已经调用了 n 次 p，那么在结果外面再套一层 p(...)，就等于调用了 n + 1 次：

    python
    1SUCC = lambda n: lambda p: lambda x: p(n(p)(x))

  • 加法 ADD（m + n）：对数字 m 重复调用 n 次“加 1”函数 SUCC，得到的就是 m + n：

    python
    1ADD = lambda m: lambda n: n(SUCC)(m)

  • 乘法 MULTIPLY（m * n）：n(p) 是一个“把 p 调用 n 次”的新函数；再把 n(p) 传给 m，相当于将“调用 n 次 p”这个动作重复执行 m 次，一共调用 m * n 次：

    python
    1MULTIPLY = lambda m: lambda n: lambda p: m(n(p))

  • 幂运算 POWER（m ** n）：将 m 自身重复应用 n 次：

    python
    1POWER = lambda m: lambda n: n(m)

有了 SUCC 和 MULTIPLY，我们就不需要手写长串嵌套括号了：

python
1ONE = SUCC(ZERO)
2TWO = SUCC(ONE)
3THREE = SUCC(TWO)
4FOUR = SUCC(THREE)
5FIVE = SUCC(FOUR)
6TEN = MULTIPLY(TWO)(FIVE)
7TWENTY = MULTIPLY(FOUR)(FIVE)
8
9>>> to_integer(TWENTY)
1020
11>>> to_integer(ADD(TEN)(FIVE))
1215

第一次替换：消灭数字字面量

现在，我们可以把原程序里的所有数字都替换成刚刚定义的 lambda 函数：

python
1for i in range(to_integer(ONE), to_integer(TWENTY)):
2 if i % to_integer(THREE) == to_integer(ZERO) or i % to_integer(FIVE) == to_integer(ZERO):
3 print(i)

运行结果与原程序完全一致。

2. 布尔值、条件分支与逻辑运算

布尔值的本质是“二选一”

接下来我们要替换程序中的布尔值、if 和 or。

先思考一个问题：我们在程序里为什么需要 True 和 False？归根结底，布尔值的唯一用途就是在两个分支中做出选择——如果为真就选第一个分支，如果为假就选第二个分支。

因此，我们可以直接把布尔值定义成接收两个参数、并返回其中一个参数的选择函数：

python
1TRUE = lambda x: lambda y: x
2FALSE = lambda x: lambda y: y
  • TRUE 接收两个参数 x 和 y，永远返回第一个参数 x；
  • FALSE 接收两个参数 x 和 y，永远返回第二个参数 y。

同样写一个辅助函数 to_boolean 来观察它们：

python
1to_boolean = lambda b: b(True)(False)
2
3>>> to_boolean(TRUE)
4True
5>>> to_boolean(FALSE)
6False

条件选择 IF

既然 TRUE 和 FALSE 自己就已经会做“二选一”了，那么 IF(b)(x)(y) 要做的事情其实非常简单——直接把真分支 x 和假分支 y 交给布尔值 b 去选：

python
1IF = lambda b: lambda x: lambda y: b(x)(y)

仔细看 lambda x: lambda y: b(x)(y)：它接收 x 和 y 并原封不动地传给 b，这和 b 本身的行为完全等价（在 Lambda 演算中称为 η-归约）。因此 IF 可以直接化简为恒等函数：

python
1IF = lambda b: b
2
3>>> IF(TRUE)("happy")("sad")
4'happy'
5>>> IF(FALSE)("happy")("sad")
6'sad'

逻辑运算：NOT、AND、OR

理解了布尔值就是“选择器”之后，逻辑取反、逻辑与、逻辑或就完全不需要死记硬背，顺着“怎么选”就能写出来：

  • NOT(b)：如果 b 为真，就选第 1 个参数 FALSE；如果 b 为假，就选第 2 个参数 TRUE：

    python
    1NOT = lambda b: b(FALSE)(TRUE)

  • AND(a)(b)：如果 a 为真，最终结果取决于 b（选第 1 个参数 b）；如果 a 为假，结果必定为假（选第 2 个参数 FALSE）：

    python
    1AND = lambda a: lambda b: a(b)(FALSE)

  • OR(a)(b)：如果 a 为真，结果必定为真（选第 1 个参数 TRUE）；如果 a 为假，最终结果取决于 b（选第 2 个参数 b）：

    python
    1OR = lambda a: lambda b: a(TRUE)(b)

验证一下：

python
1>>> to_boolean(NOT(TRUE))
2False
3>>> to_boolean(AND(TRUE)(FALSE))
4False
5>>> to_boolean(OR(FALSE)(TRUE))
6True

3. 判零、有序对与大小比较

判零函数 IS_ZERO

原程序里有 i % 3 == 0。怎样判断一个数字 n 是不是 ZERO？

回顾数字的定义：n(p)(x) 会从初始值 x 出发，把函数 p 重复调用 n 次。 如果我们把初始值 x 设为 TRUE，而把函数 p 设为 lambda _: FALSE（不管传入什么，永远返回 FALSE）：

  • 当 n 是 ZERO 时，p 一次都不会被调用，直接返回初始值 TRUE；
  • 当 n 大于 0 时，p 至少被调用一次，结果就永远变成了 FALSE。
python
1IS_ZERO = lambda n: n(lambda _: FALSE)(TRUE)
2
3>>> to_boolean(IS_ZERO(ZERO))
4True
5>>> to_boolean(IS_ZERO(THREE))
6False

用有序对（Pair）巧妙实现“减一”

除了判零，后面的取余 % 和区间 range 都需要比较两个数的大小（m <= n）。 由于我们只表示自然数（最小为 0，没有负数），如果定义减法 m - n 在不够减时返回 0，那么 m <= n 就等价于 m - n == 0！

而减法 SUB(m)(n) 就是对 m 重复调用 n 次“减一”函数（前驱函数 PRED）。 问题是：加一（SUCC）很容易，只要多调用一次 p；但“减一”（PRED）该怎么做？ 一个数字 n 只知道把函数重复执行 n 次，一旦执行了，我们没法让时光倒流去“撤销最后一次调用”。

数学家斯蒂芬·克莱尼（Stephen Kleene）在看牙医时想出了一个极其漂亮的方法——用有序对（Pair）做滑动窗口。

我们先造出最基础的复合数据结构 PAIR。它把两个值 x 和 y 保存在闭包里，等待一个选择器函数 f（比如 TRUE 或 FALSE）来取出左边或右边的值：

python
1PAIR = lambda x: lambda y: lambda f: f(x)(y)
2LEFT = lambda p: p(TRUE)
3RIGHT = lambda p: p(FALSE)
4
5>>> LEFT(PAIR("hello")("world"))
6'hello'
7>>> RIGHT(PAIR("hello")("world"))
8'world'

现在，想象一个装有两个数字的滑动窗口 (左, 右)，初始状态是 (0, 0)。 我们定义一个滑动函数 SLIDE：每次接收当前有序对 (a, b)，返回一个新的有序对 (b, b + 1)（即把原来的右值移到左边，右边放上“右值 + 1”）：

python
1SLIDE = lambda p: PAIR(RIGHT(p))(SUCC(RIGHT(p)))

看看从 (0, 0) 开始，连续调用 SLIDE 会发生什么：

text
1调用 0 次： (0, 0) -> 左边是 0
2调用 1 次： (0, 1) -> 左边是 0
3调用 2 次： (1, 2) -> 左边是 1
4调用 3 次： (2, 3) -> 左边是 2
5...
6调用 n 次： (n-1, n) -> 左边恰好是 n - 1！

也就是说，让数字 n 对初始有序对 PAIR(ZERO)(ZERO) 重复执行 n 次 SLIDE，最后取左边的元素，就得到了 n - 1（且 0 的前驱依然是 0）：

python
1PRED = lambda n: LEFT(n(SLIDE)(PAIR(ZERO)(ZERO)))
2SUB = lambda m: lambda n: n(PRED)(m)
3
4>>> to_integer(PRED(FIVE))
54
6>>> to_integer(SUB(TWENTY)(FIVE))
715
8>>> to_integer(SUB(THREE)(FIVE))
90

小于等于 LEQ 与相等 EQ

有了减法 SUB 和判零 IS_ZERO，大小比较就水到渠成了：

  • 小于等于 LEQ（m <= n）：检查 m - n 是否为 0；
  • 相等 EQ（m == n）：同时满足 m <= n 且 n <= m。
python
1LEQ = lambda m: lambda n: IS_ZERO(SUB(m)(n))
2EQ = lambda m: lambda n: AND(LEQ(m)(n))(LEQ(n)(m))
3
4>>> to_boolean(LEQ(THREE)(FIVE))
5True
6>>> to_boolean(EQ(FIVE)(FIVE))
7True
8>>> to_boolean(EQ(THREE)(FIVE))
9False

4. 递归、Z 组合子与取余运算

接下来要替换原程序里的取余运算 i % 3 和 i % 5。

在没有内置除法和取余运算符的情况下，求 m % n 最直接的办法是重复相减：只要除数 n <= m，就从 m 中减去一个 n，然后对剩下的数继续取余；当 m < n 时，剩下的 m 就是余数。

如果用普通 Python 函数来写，它是一个非常简单的递归函数：

python
1def mod(m, n):
2 if n <= m:
3 return mod(m - n, n)
4 else:
5 return m

但如果我们直接把它改写成 lambda：

python
1# 错误示范！
2MOD = lambda m: lambda n: IF(LEQ(n)(m))(MOD(SUB(m)(n))(n))(m)

这段代码不仅违反了“不依赖变量名自引用”的规则，而且在 Python 里一运行就会立刻无限递归崩溃！原因有两个，我们逐一解决。

障碍一：Python 的及早求值与惰性分支

Python 采用严格求值（应用序，Applicative Order）：在调用任何函数之前，Python 会先把括号里的实参全部算出来。

当我们写下 IF(条件)(真分支)(假分支) 时，还没等 IF 根据条件做出选择，Python 就已经把 真分支 和 假分支 统统执行了一遍！而在 MOD 中，真分支 包含递归调用 MOD(SUB(m)(n))(n)，这会导致不管 LEQ(n)(m) 是真是假，递归都会永无止境地进行下去。

解决办法是延迟求值（Thunk）：把两个分支都用一层 lambda _: ... 包裹成函数。函数定义本身不会立即执行内部代码；等 IF(条件) 选出正确的那个分支函数之后，我们在最末尾再传一个占位的参数（例如 (ZERO)）去触发它：

python
1IF(LEQ(n)(m))(
2 lambda _: ... # 只有条件为 TRUE 时才会被调用
3)(
4 lambda _: m # 只有条件为 FALSE 时才会被调用
5)(ZERO)

障碍二：匿名函数如何递归（从自应用到 Z 组合子）

在纯粹的 Lambda 演算中，所有函数都是匿名的，函数体内部不能通过全局变量名 MOD 来调用自己。那没有名字的函数怎么递归？

第一步：把自己当作参数传给自己。 既然不能从外部作用域找名字，我们可以给函数多加一个参数 self，在调用时把函数自己传进去：

python
1MOD_STEP = lambda self: lambda m: lambda n: IF(LEQ(n)(m))(
2 lambda _: self(self)(SUB(m)(n))(n)
3)(
4 lambda _: m
5)(ZERO)
6
7>>> to_integer(MOD_STEP(MOD_STEP)(TWENTY)(THREE))
82

看，MOD_STEP 内部完全没有引用任何外部函数名，仅仅靠 self(self) 就实现了递归！

第二步：把 self(self) 抽离成通用工具——Z 组合子。 每次写递归函数都要手动传 self(self) 有些繁琐。在 Lambda 演算中，可以把这种“自我复制并传入”的模式提取成一个高阶函数，也就是著名的 Y 组合子（Y Combinator）：

text
1Y = λf. (λx. f (x x)) (λx. f (x x))

不过，和前面的 IF 一样，如果直接在严格求值的 Python 中写 f(x(x))，x(x) 会立刻无限展开。我们只需用同样的技巧，把 x(x) 用一层 lambda y: x(x)(y) 包起来延迟执行，就得到了适用于严格求值语言的 Z 组合子（Z Combinator）：

python
1Z = lambda f: (lambda x: f(lambda y: x(x)(y)))(lambda x: f(lambda y: x(x)(y)))

有了 Z 组合子，任何需要递归的函数只需写成 Z(lambda recurse: ...)，在函数体内直接调用 recurse 即可：

python
1MOD = Z(
2 lambda recurse: lambda m: lambda n: IF(LEQ(n)(m))(
3 lambda _: recurse(SUB(m)(n))(n)
4 )(
5 lambda _: m
6 )(ZERO)
7)
8
9>>> to_integer(MOD(TWENTY)(THREE))
102
11>>> to_integer(MOD(TWENTY)(FIVE))
120

再顺手定义判断整除的函数 IS_DIVISIBLE_BY（余数是否为 0）：

python
1IS_DIVISIBLE_BY = lambda d: lambda n: IS_ZERO(MOD(n)(d))

5. 列表与区间 RANGE

现在回头看最初的程序：数字、%、== 0、or、if 的替代品都已经齐备，只剩下 range(1, 20) 和 for 循环了。为了替换它们，我们需要用函数构造出列表（链表）。

用有序对构造链表

前面在第 3 节我们已经实现了有序对 PAIR、LEFT 和 RIGHT。链表可以自然地建立在 PAIR 之上。

我们可以把链表的每个节点表示成两层 PAIR：

text
1PAIR(是否为空)(PAIR(当前首元素)(剩余子链表))
  • 空列表 EMPTY：第一个位置放 TRUE 表示列表为空（第二个位置放什么都可以，我们放 TRUE）；
  • 在头部插入元素 UNSHIFT：接收原列表 l 和新元素 x，返回一个新节点——第一个位置放 FALSE（表示非空），第二个位置放 PAIR(x)(l)；
  • 判空 IS_EMPTY：直接取外层 PAIR 的左值 LEFT；
  • 取首元素 FIRST：先用 RIGHT 取出内层 PAIR，再用 LEFT 取出首元素；
  • 取剩余列表 REST：先用 RIGHT 取出内层 PAIR，再用 RIGHT 取出剩余列表。
python
1EMPTY = PAIR(TRUE)(TRUE)
2UNSHIFT = lambda l: lambda x: PAIR(FALSE)(PAIR(x)(l))
3IS_EMPTY = LEFT
4FIRST = lambda l: LEFT(RIGHT(l))
5REST = lambda l: RIGHT(RIGHT(l))

写一个辅助函数 to_list，方便把我们的链表转换成 Python 列表来观察：

python
1def to_list(l):
2 result = []
3 while not to_boolean(IS_EMPTY(l)):
4 result.append(FIRST(l))
5 l = REST(l)
6 return result

测试一下构造列表 [1, 2, 3]：

python
1>>> my_list = UNSHIFT(UNSHIFT(UNSHIFT(EMPTY)(THREE))(TWO))(ONE)
2>>> [to_integer(x) for x in to_list(my_list)]
3[1, 2, 3]

实现区间函数 RANGE

有了链表和 Z 组合子，我们可以递归地生成从 m 到 n（包含首尾）的数字列表：

  • 如果 m <= n，就先递归生成 m + 1 到 n 的列表，再用 UNSHIFT 把 m 插到最前面；
  • 否则返回 EMPTY。
python
1RANGE = Z(
2 lambda recurse: lambda m: lambda n: IF(LEQ(m)(n))(
3 lambda _: UNSHIFT(recurse(SUCC(m))(n))(m)
4 )(
5 lambda _: EMPTY
6 )(ZERO)
7)
8
9>>> [to_integer(x) for x in to_list(RANGE(ONE)(FIVE))]
10[1, 2, 3, 4, 5]

原程序中的 range(1, 20) 包含 1 到 19，用我们的函数表示就是 RANGE(ONE)(PRED(TWENTY))。

第二次替换：接管区间、取余与逻辑判断

现在，把 RANGE、MOD、IS_ZERO 和 OR 全部换进原程序中：

python
1for i in to_list(RANGE(ONE)(PRED(TWENTY))):
2 if to_boolean(OR(IS_ZERO(MOD(i)(THREE)))(IS_ZERO(MOD(i)(FIVE)))):
3 print(to_integer(i))

注意看这段代码：此时的循环变量 i 已经不再是 Python 的 int，而是纯粹的邱奇数！整个条件判断与取余运算完全在 lambda 的世界里完成，只剩下最外层的 for ... in to_list(...) 和 if to_boolean(...) 还在借用 Python 的语法。

6. 高阶遍历与最终组合

最后一步，我们把仅剩的 Python for 循环和 if 语句也替换成列表的高阶函数。

FILTER、MAP 与 EACH

在函数式编程中，“遍历列表并挑选出满足条件的元素”就是 FILTER：

  • 如果列表 l 为空，返回 EMPTY；
  • 如果首元素 FIRST(l) 满足条件 f(FIRST(l))，就将它保留在结果列表头部，并继续过滤剩余列表 REST(l)；
  • 否则跳过首元素，直接过滤 REST(l)。
python
1FILTER = Z(
2 lambda recurse: lambda f: lambda l: IF(IS_EMPTY(l))(
3 lambda _: EMPTY
4 )(
5 lambda _: IF(f(FIRST(l)))(
6 lambda _: UNSHIFT(recurse(f)(REST(l)))(FIRST(l))
7 )(
8 lambda _: recurse(f)(REST(l))
9 )(ZERO)
10 )(ZERO)
11)

同样地，我们可以实现映射函数 MAP 和依次对每个元素执行动作的遍历函数 EACH：

python
1MAP = Z(
2 lambda recurse: lambda l: lambda f: IF(IS_EMPTY(l))(
3 lambda _: EMPTY
4 )(
5 lambda _: UNSHIFT(recurse(REST(l))(f))(f(FIRST(l)))
6 )(ZERO)
7)
8
9EACH = Z(
10 lambda recurse: lambda l: lambda f: IF(IS_EMPTY(l))(
11 lambda _: ZERO
12 )(
13 lambda _: (lambda _: recurse(REST(l))(f))(f(FIRST(l)))
14 )(ZERO)
15)

最终形态

现在，最初的 3 行 Python 程序终于可以彻底摆脱 range、%、==、or、if 和 for 了：

python
1IS_DIVISIBLE_BY = lambda d: lambda n: IS_ZERO(MOD(n)(d))
2WANTED = lambda n: OR(IS_DIVISIBLE_BY(THREE)(n))(IS_DIVISIBLE_BY(FIVE)(n))
3
4NUMBERS = RANGE(ONE)(PRED(TWENTY))
5RESULT = FILTER(WANTED)(NUMBERS)
6
7EACH(RESULT)(lambda n: print(to_integer(n)))

运行它，依然会打印出熟悉的：

text
13
25
36
49
510
612
715
818

如果连变量名都不允许用呢？

你可能会问：上面的代码里不是还用了 ZERO = ...、SUCC = ...、MOD = ... 这些 Python 变量赋值语句吗？

其实，我们给函数起大写名字纯粹是为了人类阅读方便。因为有了 Z 组合子，上面定义的每一个函数都是非自引用的；而在 Lambda 演算中，先绑定变量 NAME = expr 再在 body 中使用 NAME，完全等价于一次匿名函数调用：

python
1(lambda NAME: body)(expr)

如果我们把所有大写名字全部按定义展开（内联替换），整段程序就会化为一个只包含 lambda、参数名和括号的单一表达式（仅在最外层用 print 和 to_integer 观察结果）：

python
1(lambda Z:
2 (lambda TRUE: lambda FALSE:
3 (lambda PAIR: lambda LEFT: lambda RIGHT:
4 (lambda ZERO: lambda SUCC:
5 (lambda ONE: lambda TWO: lambda THREE: lambda FOUR: lambda FIVE:
6 (lambda TWENTY:
7 (lambda PRED: lambda SUB: lambda IS_ZERO:
8 (lambda LEQ:
9 (lambda MOD: lambda RANGE: lambda FILTER: lambda EACH:
10 EACH(
11 FILTER(
12 lambda n: (IS_ZERO(MOD(n)(THREE)))(TRUE)(IS_ZERO(MOD(n)(FIVE)))
13 )(RANGE(ONE)(PRED(TWENTY)))
14 )(lambda n: print(n(lambda x: x + 1)(0)))
15 )(
16 Z(lambda r: lambda m: lambda n: LEQ(n)(m)(lambda _: r(SUB(m)(n))(n))(lambda _: m)(ZERO))
17 )(
18 Z(lambda r: lambda m: lambda n: LEQ(m)(n)(lambda _: PAIR(FALSE)(PAIR(m)(r(SUCC(m))(n))))(lambda _: PAIR(TRUE)(TRUE))(ZERO))
19 )(
20 Z(lambda r: lambda f: lambda l: LEFT(l)(lambda _: PAIR(TRUE)(TRUE))(lambda _: f(LEFT(RIGHT(l)))(lambda _: PAIR(FALSE)(PAIR(LEFT(RIGHT(l)))(r(f)(RIGHT(RIGHT(l))))))(lambda _: r(f)(RIGHT(RIGHT(l))))(ZERO))(ZERO))
21 )(
22 Z(lambda r: lambda l: lambda f: LEFT(l)(lambda _: ZERO)(lambda _: (lambda _: r(RIGHT(RIGHT(l)))(f))(f(LEFT(RIGHT(l)))))(ZERO))
23 )
24 )(lambda m: lambda n: IS_ZERO(SUB(m)(n)))
25 )(
26 lambda n: LEFT(n(lambda p: PAIR(RIGHT(p))(SUCC(RIGHT(p))))(PAIR(ZERO)(ZERO)))
27 )(
28 lambda m: lambda n: n(lambda k: LEFT(k(lambda p: PAIR(RIGHT(p))(SUCC(RIGHT(p))))(PAIR(ZERO)(ZERO))))(m)
29 )(
30 lambda n: n(lambda _: FALSE)(TRUE)
31 )
32 )(lambda p: FOUR(FIVE(p)))
33 )(SUCC(ZERO))(SUCC(SUCC(ZERO)))(SUCC(SUCC(SUCC(ZERO))))(SUCC(SUCC(SUCC(SUCC(ZERO)))))(SUCC(SUCC(SUCC(SUCC(SUCC(ZERO))))))
34 )(lambda p: lambda x: x)(lambda n: lambda p: lambda x: p(n(p)(x)))
35 )(lambda x: lambda y: lambda f: f(x)(y))(lambda p: p(TRUE))(lambda p: p(FALSE))
36 )(lambda x: lambda y: x)(lambda x: lambda y: y)
37)(lambda f: (lambda x: f(lambda y: x(x)(y)))(lambda x: f(lambda y: x(x)(y))))

你可以把上面这整段表达式直接粘贴进 Python 解释器运行——除了最后一行用来把结果打印到屏幕上的 print(n(lambda x: x + 1)(0))，整段计算过程里没有任何数字、布尔值、运算符、条件语句或循环，却完整地算出了 1 到 19 之间所有能被 3 或 5 整除的数。

7. 完整代码

下面是整理后的完整 lambda_calculus.py：

展开完整 lambda_calculus.py
python
1#!/usr/bin/env python3
2"""Simulating Lambda Calculus (Church Encoding) in Python."""
3
4# 1. Numbers & Arithmetic ------------------------------------------------
5
6ZERO = lambda p: lambda x: x
7SUCC = lambda n: lambda p: lambda x: p(n(p)(x))
8
9ONE = SUCC(ZERO)
10TWO = SUCC(ONE)
11THREE = SUCC(TWO)
12FOUR = SUCC(THREE)
13FIVE = SUCC(FOUR)
14
15ADD = lambda m: lambda n: n(SUCC)(m)
16MULTIPLY = lambda m: lambda n: lambda p: m(n(p))
17POWER = lambda m: lambda n: n(m)
18
19TEN = MULTIPLY(TWO)(FIVE)
20TWENTY = MULTIPLY(FOUR)(FIVE)
21
22
23# 2. Booleans & Conditionals ---------------------------------------------
24
25TRUE = lambda x: lambda y: x
26FALSE = lambda x: lambda y: y
27IF = lambda b: b
28
29NOT = lambda b: b(FALSE)(TRUE)
30AND = lambda a: lambda b: a(b)(FALSE)
31OR = lambda a: lambda b: a(TRUE)(b)
32
33
34# 3. Pairs, Predecessor & Predicates -------------------------------------
35
36PAIR = lambda x: lambda y: lambda f: f(x)(y)
37LEFT = lambda p: p(TRUE)
38RIGHT = lambda p: p(FALSE)
39
40SLIDE = lambda p: PAIR(RIGHT(p))(SUCC(RIGHT(p)))
41PRED = lambda n: LEFT(n(SLIDE)(PAIR(ZERO)(ZERO)))
42SUB = lambda m: lambda n: n(PRED)(m)
43
44IS_ZERO = lambda n: n(lambda _: FALSE)(TRUE)
45LEQ = lambda m: lambda n: IS_ZERO(SUB(m)(n))
46EQ = lambda m: lambda n: AND(LEQ(m)(n))(LEQ(n)(m))
47
48
49# 4. Recursion (Z Combinator) & Modulo -----------------------------------
50
51Z = lambda f: (lambda x: f(lambda y: x(x)(y)))(lambda x: f(lambda y: x(x)(y)))
52
53MOD = Z(
54 lambda recurse: lambda m: lambda n: IF(LEQ(n)(m))(
55 lambda _: recurse(SUB(m)(n))(n)
56 )(
57 lambda _: m
58 )(ZERO)
59)
60
61
62# 5. Lists, Range & High-Order List Operations ---------------------------
63
64# A list node is encoded as PAIR(is_empty)(PAIR(head)(tail)).
65EMPTY = PAIR(TRUE)(TRUE)
66UNSHIFT = lambda l: lambda x: PAIR(FALSE)(PAIR(x)(l))
67IS_EMPTY = LEFT
68FIRST = lambda l: LEFT(RIGHT(l))
69REST = lambda l: RIGHT(RIGHT(l))
70
71RANGE = Z(
72 lambda recurse: lambda m: lambda n: IF(LEQ(m)(n))(
73 lambda _: UNSHIFT(recurse(SUCC(m))(n))(m)
74 )(
75 lambda _: EMPTY
76 )(ZERO)
77)
78
79FILTER = Z(
80 lambda recurse: lambda f: lambda l: IF(IS_EMPTY(l))(
81 lambda _: EMPTY
82 )(
83 lambda _: IF(f(FIRST(l)))(
84 lambda _: UNSHIFT(recurse(f)(REST(l)))(FIRST(l))
85 )(
86 lambda _: recurse(f)(REST(l))
87 )(ZERO)
88 )(ZERO)
89)
90
91MAP = Z(
92 lambda recurse: lambda l: lambda f: IF(IS_EMPTY(l))(
93 lambda _: EMPTY
94 )(
95 lambda _: UNSHIFT(recurse(REST(l))(f))(f(FIRST(l)))
96 )(ZERO)
97)
98
99EACH = Z(
100 lambda recurse: lambda l: lambda f: IF(IS_EMPTY(l))(
101 lambda _: ZERO
102 )(
103 lambda _: (lambda _: recurse(REST(l))(f))(f(FIRST(l)))
104 )(ZERO)
105)
106
107
108# 6. Helper Functions (Bridge to Python) ---------------------------------
109
110to_integer = lambda n: n(lambda x: x + 1)(0)
111to_boolean = lambda b: b(True)(False)
112
113
114def to_list(l):
115 """Convert a Church-encoded list into a Python list."""
116 result = []
117 while not to_boolean(IS_EMPTY(l)):
118 result.append(FIRST(l))
119 l = REST(l)
120 return result
121
122
123# 7. Target Program: Numbers in 1..19 divisible by 3 or 5 ----------------
124
125IS_DIVISIBLE_BY = lambda d: lambda n: IS_ZERO(MOD(n)(d))
126WANTED = lambda n: OR(IS_DIVISIBLE_BY(THREE)(n))(IS_DIVISIBLE_BY(FIVE)(n))
127
128NUMBERS = RANGE(ONE)(PRED(TWENTY))
129RESULT = FILTER(WANTED)(NUMBERS)
130
131
132if __name__ == "__main__":
133 EACH(RESULT)(lambda n: print(to_integer(n)))