从零开始的 λ 演算

15 minute read

这是我在看完 PyCon 2019 演讲「Lambda Calculus from the Ground Up」之后做的一个文字版,原视频在 https://youtu.be/pkCLMl0e_0k 。另见官网中的 介绍,这里提供一个翻译。

最近关于编程风格的指南层出不穷。但是如果我们把风格限制为只允许出现单参数的函数会发生什么呢?没有模组,没有类,没有控制流,没有数据结构,甚至连整数、正则表达式等内建类型都没有,只有函数。用这种风格能写出程序吗?令人惊讶的是,答案是肯定的。在这个教程中,你将学到如何从零开始在 Python 中推导 λ 演算。

你不会在这个教程中学到有实际用处的东西。没有打包,没有工具,没有库,没有部署,也没有神奇的 Python 编程技术。你也不会学到会被你用在实际项目上的东西。但是你将获得很多乐趣,将感到惊叹,并学习一些基础的计算机科学,这是你进一步探索函数式编程、类型理论、编程语言等话题的起点。

规则

如上介绍所说,我们只允许函数调用,或者参数替换这一种操作。以下列举一些不被允许的操作:

def f(x):
    return x + 1  # 不允许使用数字和运算符 +

def f(x, y):
    ...  # 只允许单个参数

以下是一些合法的操作,但是他们好像没什么意义:

def f(x):
    return x

def f(x):
    return x(x)

def f(x):
    def g(y):
        return x(y)
    return g

所以在这样的一个如此抽象的系统中,我们可以做些什么?

布尔值(18:27

首先来构造布尔值和布尔运算。可以借用选择器的概念来构造布尔值。TRUE 选择两个值中的第一个,而 FALSE 选择第二个。注意这里的 TRUEFALSE 并不是一个具体的值,而是一种行为。

def TRUE(x):
    return lambda y: x

def FALSE(x):
    return lambda y: y
>>> TRUE('5v')('gnd')
'5v'
>>> FALSE('5v')('gnd')
'gnd'

接下来是布尔运算 NOT, ANDOR。注意到 NOT 的参数应该是 TRUE 或者 FALSE,它们都是需要两个输入的函数(柯里化的)。然后根据 TRUEFALSE 在两个值中的选择情况便可构造出 NOT

def NOT(x):
    return x(FALSE)(TRUE)

对于 AND,在它的第一个参数为 TRUE 的时候,值就等于第二个参数;在第一个参数为 FALSE 的时候,值为 FALSE(也就是它的第一个参数)。OR 可以根据类似的思想写出:

def AND(x):
    return lambda y: x(y)(x)

def OR(x):
    return lambda y: x(x)(y)
布尔运算演示
>>> NOT(TRUE)
<function FALSE(x)>
>>> NOT(FALSE)
<function TRUE(x)>
>>> AND(TRUE)(TRUE)
<function TRUE(x)>
>>> AND(TRUE)(FALSE)
<function FALSE(x)>
>>> AND(FALSE)(TRUE)
<function FALSE(x)>
>>> AND(FALSE)(FALSE)
<function FALSE(x)>
>>> OR(TRUE)(TRUE)
<function TRUE(x)>
>>> OR(TRUE)(FALSE)
<function TRUE(x)>
>>> OR(FALSE)(TRUE)
<function TRUE(x)>
>>> OR(FALSE)(FALSE)
<function FALSE(x)>

数字(34:45

因为我们能够做的只有函数调用,所以可以尝试用调用函数的次数表示数字,比如 TWO(f)(x) 的含义是以 x 为初始值,调用 f 两次:

ONE = lambda f: lambda x: f(x)
TWO = lambda f: lambda x: f(f(x))
THREE = lambda f: lambda x: f(f(f(x)))
FOUR = lambda f: lambda x: f(f(f(f(x))))

零表示为调用函数零次,即不调用函数:

ZERO = lambda f: lambda x: x

为了能够方便地展示我们的系统中的数字,在此写一个函数用来将系统中的数字转为 Python 中的一个 int。这个函数并不在 λ 演算系统中,只是为了方便地查看系统中的数字。

def toint(n):
    return n(lambda x: x + 1)(0)
>>> toint(THREE)
3

加法和乘法(50:02

使用 Peano 公理 的思想,先实现一个数字的后继。

SUCC = lambda n: lambda f: lambda x: f(n(f)(x))

在这个实现中,SUCC 的返回值是一个数(因为拥有 lambda f: lambda x: xxx 这样的「接口」),而这个返回的数是以 x 为初始值调用了 n 次函数 f(用 n(f)(x) 表示)后又多调用了 f 一次的结果,所以表示 n + 1。

>>> toint(SUCC(THREE))
4

有了 SUCC 就可以实现加法了。x + y 就是在 x 的基础上调用 ySUCC。而数字的行为正好是调用某个函数多少次。

ADD = lambda x: lambda y: y(SUCC)(x)

乘法就是将「调用函数 f x 次」(即 x(f) 这个行为)重复 y 次:

MUL = lambda x: lambda y: lambda f: y(x(f))

从上面的定义可以看出乘法就是用函数的复合,即 MUL x y = y ∘ x

加法和乘法的演示:

>>> toint(ADD(FOUR)(THREE))
7
>>> toint(MUL(FOUR)(THREE))
12

二元组(2:03:49

为了实现减法,我们需要先实现二元组。

CONS(a)(b) 将会返回一个「选择器」,这个选择器根据给它的参数选择 ab 中的一个。这里的函数名借用了 Lisp 中的名字。

CONS = lambda a: lambda b: (lambda s: s(a)(b))
CAR = lambda p: p(TRUE)
CDR = lambda p: p(FALSE)
>>> p = CONS(2)(3)
>>> CAR(p)
2
>>> CDR(p)
3

这里的 CONS 接受两个参数并构造了一个二元组,CARCDR 分别取二元组中的第一个和第二个值。

减法(2:12:15

下面借助二元组来实现一个数的前驱。我们可以从 (0, 0) 开始增加,(1, 0), (2, 1) …… 二元组的第二个数是第一个数的前驱,而第一个数就是增加的次数。

T = lambda p: CONS(SUCC(CAR(p)))(CAR(p))
>>> a = FOUR(T)(CONS(ZERO)(ZERO))
>>> toint(CAR(a))
4
>>> toint(CDR(a))
3

上面的 a 是从 (0, 0) 开始执行了函数 T 4 次后的结果,它本身是一个二元组,第二个值就是 4 的前驱 3。于是实现前驱的方式为从 CONS(ZERO)(ZERO) 开始执行函数 T n 次,再取二元组的第二个值:

PRED = lambda n: CDR(n(T)(CONS(ZERO)(ZERO)))
>>> a = FOUR(THREE)
>>> toint(a)
81
>>> b = PRED(a)
>>> toint(b)
80

然后仿造加法构造减法:

SUB = lambda x: lambda y: y(PRED)(x)
>>> a = SUB(FOUR)(TWO)
>>> toint(a)
2

判断一个数是否为零(2:24:12

由于 ZERO 的行为是直接返回第二个输入,所以下面的第二个括号中为 TRUE。而其它的数都会调用第一个输入,所以直接让这个输入返回 FALSE

ISZERO = lambda n: n(lambda _: FALSE)(TRUE)
>>> ISZERO(ZERO)
<function TRUE(x)>
>>> ISZERO(ONE)
<function FALSE(x)>

递归(2:30:13

我们已经有了 AND, SUCC, ADD, CONS, CARISZERO 等等函数,现在我们要来挑战写出阶乘函数。阶乘在普通 Python 中的一种写法是

fact = lambda n: 1 if n == 0 else n * fact(n-1)

它只用了判断是否为零,乘法和减法三种操作。把它转化为 λ 演算中的形式,得到

FACT = lambda n: ISZERO(n) \
                 (ONE) \
                 (MUL(n)(FACT(PRED(n))))

但是这个实现有问题:

>>> FACT(THREE)
RecursionError: maximum recursion depth exceeded

惰性求值(2:34:40

原因是 Python 函数不是惰性求值(lazy)的,递归发生在 ISZERO 判断之前。为了规避这个限制,我们实现以下的 lazy 版本

L_TRUE = lambda x: lambda y: x()
L_FALSE = lambda x: lambda y: y()
L_ISZERO = lambda n: n(lambda _: L_FALSE)(L_TRUE)

FACT = lambda n: L_ISZERO(n) \
                 (lambda: ONE) \
                 (lambda: MUL(n)(FACT(PRED(n))))
>>> a = FACT(THREE)
>>> toint(a)
6

避免引用自己(2:47:30

目前还有一个问题,在 λ 演算中没有全局变量,没有把值「存储」在一个变量中的概念。而我们在 FACT 的定义中使用了 FACT 这个名字。

我们也用了 ISZEROONE 等等名字啊?

事实上这些名字不需要存储的概念。可以把所有出现了 ONE 的地方换成它的定义(相当于 :%s/\<ONE\>/(lambda f:lambda x:f(x))/g)而程序还是会正确运行。而不能换 FACT 的原因是它的定义本身就使用了 FACT 这个名字。

如何在实现 FACT 的时候不引用它自己的名字?为了方便先用 fact 函数来试验,我们不希望在下面的实现中出现 fact

fact = lambda n: 1 if n == 0 else n * fact(n-1)
#                                     ^^^^ bad

一种方式是把 fact 作为参数传进去,但是这样还是用了 fact 这个名字,而且这个写法在 fact 还没定义的时候就使用了它。

fact = (lambda f: lambda n: 1 if n == 0 else n * f(n-1)) \
       (fact)
#       ^^^^ ?

解决方案是直接复制粘贴,而不是把自己的名字传进参数:

fact = (lambda f: lambda n: 1 if n == 0 else n * f(n-1)) \
       (lambda f: lambda n: 1 if n == 0 else n * f(n-1))

我们还需要修正一下 f 的调用方法(因为需要先传入 f 再传入 n)。下面是最终的结果:

fact = (lambda f: lambda n: 1 if n == 0 else n * f(f)(n-1)) \
       (lambda f: lambda n: 1 if n == 0 else n * f(f)(n-1))
#                                                ^^^^
>>> fact(4)
24

可以把 fact 直接换成它的定义:

>>> (lambda f: lambda n: 1 if n == 0 else n * f(f)(n-1)) \
... (lambda f: lambda n: 1 if n == 0 else n * f(f)(n-1))(4)
24

不动点(3:00:38

以上的实现有一点不好,它把一个很长的括号重复了两次。我们也可以借助不动点实现 fact

回到之前尝试实现 fact 的时候,

fact = (lambda f: lambda n: 1 if n == 0 else n * f(n-1))(fact)

如果把中间的部分抽出来

R = lambda f: lambda n: 1 if n == 0 else n * f(n-1)

那么 fact = R(fact),即 factR 的一个不动点。如果有一个可以计算不动点的函数,就可以得到 fact 了。

假设这个函数存在,设它为 Y。那么有 Y(R) = R(Y(R))。变形:

Y(R) = (lambda x: R(x))(Y(R))

仿照上一节中的做法,把括号中的表达式复制一遍,再修正一下 x 的调用方法:

Y(R) = (lambda x: R(x))(lambda x: R(x))
Y(R) = (lambda x: R(x(x)))(lambda x: R(x(x)))

那么我们就得到了 Y

Y = lambda f: (lambda x: f(x(x)))(lambda x: f(x(x)))

Y 组合子(3:13:20

这里的 Y 就是著名的 Y 组合子(Y combinator)。但是

>>> R = lambda f: lambda n: 1 if n == 0 else n * f(n-1)
>>> fact = Y(R)
RecursionError: maximum recursion depth exceeded

要解决这个问题,可以把 x(x) 换成 lambda z: x(x)(z),它可以延后 x 的求值。

Y = lambda f: (lambda x: f(lambda z: x(x)(z)))(lambda x: f(lambda z: x(x)(z)))
>>> R = lambda f: lambda n: 1 if n == 0 else n * f(n-1)
>>> fact = Y(R)
>>> fact(4)
24

Y 用在其它函数上:

>>> fib = Y(lambda f: lambda n: 1 if n <= 2 else f(n-1) + f(n-2))
>>> fib(10)
55

实现 FACT

>>> FACT = Y(
...     lambda f: lambda n: L_ISZERO(n) \
...                         (lambda: ONE) \
...                         (lambda: MUL(n)(f(PRED(n))))
... )
>>> a = FACT(FOUR)
>>> toint(a)
24

本文中的代码已整理到 Gist 上。

补充

惰性求值 一节中也可以使用另一种方法。参考 Y 组合子 一节,用 lambda x: f(x) 代替 f,这样不需要新定义 lazy 版本的函数。因为万物皆是函数,所以不需要担心 f(x) 因为 f 不是函数而出错。

FACT = lambda n: ISZERO(n) \
                 (lambda x: ONE(x)) \
                 (lambda x: MUL(n)(FACT(PRED(n)))(x))
FACT = Y(
    lambda f: lambda n: ISZERO(n) \
                        (lambda x: ONE(x)) \
                        (lambda x: MUL(n)(f(PRED(n)))(x))
)

总结

  • 这里推导的 λ 演算没有什么实际用途,没有谁会用这里的 λ 演算写一个现实中使用的程 序;
  • 但是 λ 演算的思想在函数式语言中随处可见,非函数式语言也都在慢慢吸收函数式语言 中的一些的思想和概念;
  • λ 演算就像机器语言一样。现在绝大多数人都在写高级语言,但是高级语言在某种程度上 是机器语言的抽象,了解一些机器语言或者汇编的知识有助于写出更好,效率更高的代 码。类似地,了解 λ 演算对理解和运用函数式语言和其它语言中的函数式元素是很有 益的。