浅谈λ演算与Python中的lambda函数

作者：牛伯雨

Python里有一个十分方便的功能，那就是lambda函数。使用这一功能，可以让代码显得简洁明快，甚至一行搞定很多步运算。在讨论Python的lambda运算之前，我们先来看看它的原型：λ演算。

λ演算

初识λ演算

λ演算十分简洁，比如$\lambda x.x$就是一个lambda项（之后我们进一步讨论lambda项的定义）。

形式简单，内容却很丰富：它可以表示一切函数。借助这一工具，我们可以删繁就简探究两个程序的本质是否是一样的，思考编程与逻辑之间的关系，等等。

λ演算是在1936年由阿隆佐·邱奇首次提出的。在同一年，还有另一项深刻地影响着后世的发明——阿兰·图灵的图灵机。这两个发明是分别被独立地提出的，但是不久之后邱奇的学生克莱尼证明，两者在本质上是相同的，真可谓英雄所见略同。也就是说，凡是能用图灵机计算的函数，都可以用λ演算，反之亦然。

就着图来快速说一下图灵机的基本组成：

1. 一条无限长的条带，上面有被编号的一个接一个的格子；
2. 一个读写头，可以在条带上左右移动，也可以写入提前定义好的有限个符号的其中之一，或读取或删除当前格子里的符号；
3. 一套控制规则，告知图灵机要做什么——写入或删除当前符号，向哪个方向移动读写头，或保持当前状态，亦或进入下一状态；
4. 一个状态寄存器，以寄存图灵机当前状态。

λ演算的句法结构

两个特征

λ演算具有两个显著的特征：首先，λ演算中的函数都是没有名字的，表达一个函数时，需要把它具体的内容写出来，比如$\lambda x.x+5$。这个函数表示，不管你给我一个什么数，我都把这个数加5再输出。

第二点是，λ演算中的一个函数只能接收一个变量。如果我们想写一个接收两个变量的函数，则需要把它写成复合函数的形式，也就是第一个函数的输出结果是紧接着第二个函数的输入变量。
例如，这样一个函数$g(x,y)=x\ast x+y\ast y$在λ演算中应写为$\lambda x.\lambda y.x\ast x+y\ast y$。比如，就这个函数而言，如果x = 5, y = 6，则$g(5,6)=5\ast 5+6\ast 6=25+36=61$；同一过程用λ演算，则是
$(\lambda x.(\lambda y.(x\ast x+y\ast y)6))5$
$=(\lambda x.(x\ast x+6\ast 6))5$
$=(\lambda x.(x\ast x+36))5$
$=5\ast 5+36$
$=25+36$
$=61$
具体的计算过程是β-归约，小括号则能够把运算过程标识得更清楚。我们稍后详细介绍这两点，这一段的主要目的是说明λ演算中的一个函数只能接收一个变量。

写lambda项的三个（递归的）规则

前面我们说过$\lambda x.x$就是一个lambda项，在这一节中我们更加详细地介绍lambda项。

1. 一个单独的变量就是一个有效的lambda变量。比如x。
2. 如果x是一个变量，t是一个lambda项，那么$\lambda x.t$也是lambda项。这一法则又叫“lambda抽象”。
3. 如果t和s都是lambda项，那么ts也是lambda项，这一法则又叫“应用”，就好像把s的值带入t当中。

等价变换lambda项的三个法则

书写出了lambda项后，我们还可以对它进行等价变换，或化简。以下简单介绍化简lambda项的法则。

α-等价

在λ演算中，表示某个变量的符号一般不重要。比如，$\lambda x.x+5$和$\lambda y.y+5$表示相同的函数，他们是α-等价的。

β-归约

简单来说，β-归约就是把一个数带入到lambda项当中。比如$((\lambda x.t)s)$，就是把s带入t中的x。
一个具体例子：$((\lambda x.(y+x))s)$即可变换为$(y+s)$。
在$((\lambda x.(y+x))s)$这个式子中，y是一个“自由变量”。

η-变换

如果当两个函数接收相同的输入时，它们输出相同的结果，那么这两个函数就被认为是等价的，反之也成立。比如说，如果x不在g和k里作为自由变量出现，那么$\lambda x.((gk)x)$ 和$(gk)$等价。

λ演算的书写规范

• 前面我们提到过λ演算中小括号的使用。
  事实上，在λ演算中，应尽量避免使用小括号。但是作为初学者来说，可以写小括号以标明运算步骤。一般来讲，最外层的小括号是没有必要标注的。
• λ演算的应用过程是左结合的，即 $fgx$与$(fg)x$等价。
• lambda抽象的范围是从点“.”开始尽可能向右，直到遇上小括号为止。
• 连续的lambda抽象在写法可以进行缩合，比如$\lambda x.\lambda y.\lambda z.f$可以缩合为$\lambda xyz.f$

Python中的lambda函数

Python中的lambda函数句法相当简单：

lambda argument(s) : expression

比如

lambda x: x + 5

就定义了一个加5的函数。
运行

(lambda x: x + 5)(6)

返回的结果为11，
运行

(lambda x, y: 3 * x + 2 * y)(5, 9)

返回的结果为33。

这个基本句法和我们上面介绍的λ演算的句法是连贯的，当然这里面有一些Python语言本身的特征。

在Python中，lambda函数可以帮助我们一行代码完成某项任务，比如将一个数列中的偶数挑出来：

a = [150, 2, 8, 7, 5, 4, 35, 31, 10, 112]
filtered = list(filter(lambda x: x % 2 == 0, a))

运行后，filtered结果为

[150, 2, 8, 4, 10, 112]

lambda函数的另一个好处是，它可以提供一个简洁的“模版”，我们在具体使用的时候可以很简单地对它进行调整。
比如

def lambdaExample(n):
  return lambda a : a * n

myDoubler = lambdaExample(2) # 定义乘以2的函数

myTripler = lambdaExample(3) # 定义乘以3的函数

这样，myDoubler（5）返回的结果就是10，myTripler（5）返回的结果就是15。