从 x(x) 到 Y : 用 python 构建和理解 Y 算子(Y combinator)
修改历史
- 以函数为中心:lambda 演算和组合子逻辑 文章的引用,从而可以删除部分 lambda 演算背景的解释 添加对
本文记录自己理解 Y combinator 的思路,用 python 一步一步构造出 Y 算子,力求每一步都有合理的直觉和解释,不涉及不动点和数学形式的理论推导(最多会提到一些历史概念)。
1. 匿名函数的执念
在 python 中,可以通过 lambda 关键字来创建匿名函数
例如:
lambda x: print(x)
python 还允许给这个函数取一个名字,然后调用:
my_print = lambda x: print(x)
my_print("hello world")
hello world
而 lambda 演算中,为了追求形式系统的简洁性,只允许使用匿名函数。这个设定显然很不实际,因为命名是一种对更复杂的对象(函数,类,结构体)的"抽象",是编程实践中不可或缺的,否则稍微大一点的程序几乎会无法阅读和编写。
然而,这种追求是出于理论目的,就像欧几里德只选择 5 条公理来构建其几何体系一样。要知道 Lambda 演算最初是 20世纪 30 年代提出,那时候计算机都还没有出现,更不用说编程实践、空间、时间和程序复杂度这些概念了,这完全是逻辑和数学的理论产物,追求的是符号组合的可能性以及美感(或者叫符号复杂度优化?),这一点要先从认知上接受,否则后面很多推理会显得“无意义”。
lambda 演算中对公理简洁性如此执着,甚至连自然数,整数,逻辑运算符都只通过单参数的匿名函数来构建,如有兴趣可阅读 以函数为中心:lambda 演算和组合子逻辑
如果对 lambda 演算本身不是很有兴趣,没有阅读相关材料也不影响对后文的理解,只需要理解 python 中的高阶函数(或者装饰器)和 lambda 函数即可。因为完全可以把推导 Y 算子的过程看作一个习题:
“在 python 中,如果只能使用 lambda 匿名函数,不使用 for, while 循环,如何编写计算第 n 个 fibnacci 数的函数?“
我对 Y 算子的理解是在 lambda 演算中构建"可控"的递归,之所以加上 "可控" 这个修饰词, 是因为在许多资料里提到 Y 算子时都说它是用于构造递归,但这很容易带来困惑,因为并不是只有 Y 算子才能实现匿名函数递归,Y 也不是递归的第一推动者。
后文所有的理解都是一步一步如何从"无递归" 以及 "无法控制的递归" 发展成 "可控的递归"的过程梳理
2. 算子
在真正介绍各类算子之前,先简单理解什么是"算子"(combinator, 也翻译成组合子), 算子在 lambda 演算里有一套定义,例如必须是 close form 的表达式,是一个高阶 lambda 函数等等,但在 python 里,它对应 实际就是一个高阶函数,接受一个函数,返回另一个函数,例如:
def printter(f):
def inner(*args):
print(f"{f} called {args}")
return f(*args)
return inner
@printter
def add(x, y):
return x+y
add(1, 2)
<function add at 0x7fc3e5377dc0> called (1, 2) 3
被以上 printter 装饰过的 add 函数,在每次执行时都会先打印出调用的参数,对某个函数添加 @printter 形式的装饰器,实际就是执行 add = printter(add)
,也就是对输入函数"加工"后输出一个新的函数。
正如数学中的函数无穷无尽,但人们会选出几个或几类基础的函数来分析(如常数函数,对数函数,三角函数),其他复杂函数则是是通过这些初等函数的组合性来获得。Y 就是众多算子中形式比较简单且性质有趣的一种。
有了对算子的理解后,此时阅读文章的你能想到的形式化上最简单的装饰器或者算子是什么?
我想可能是 lambda x:x
, 它接受一个对象并返回这个对象,因此如果输入是函数,它也就返回函数(符合 combinator 的朴素定义)。 在 lambda 演算中, lambda x:x
被称为 I 算子(identity)
3. 自指的出现: lambda x:x(x)
3.1. 引入 lambda x:x(x)
对 I 算子,实际上没有太多可以说的,它并不是非常有趣(尽管在 lambda 演算中 I 可以看作基石,但本文不讨论),在 python 中,它更多时候只能称为一个普通函数,因为可以输入非函数对象,如下例子
(lambda x:x)(1)
1
有什么场景一定要用一个 I 算子作为装饰器吗?
我就是我
– I
如果要找一个比 I 算子更复杂一点也更有趣一点的算子,可能会想到 lambda x:x(x)
因为它只比 I 算子多三个字符(其中左右括号是新的字符),然而它比 I 算子有趣得多。
(从 I 到 lambda x:x(x) 似乎有一点跳跃,但至少比较合理,因为目前我只是找一些简单的算子来观察, 同时以"递归"或者”自指“作为指引,而 x(x) 比较有递归和自指的味道)
为了方便描述,先用 python 的赋值语句给它取一个名字,后文也会在适当的时候展示即使没有名字也可以实现有名字情况下能实现的功能。
f = lambda x:x(x)
如果为了追求形式统一(似乎有点美感),可以用与参数相同的变量来命名:
x = lambda x:x(x)
# or
f = lambda f:f(f)
但目前不是这样做的时候,因为这很容易带来混乱。应该在理解所有细节,并且想炫耀自己的成果时再把名字尽量换成简单且相同的符号,因此本节还是用 f = lambda x:x(x)
来表示。
接着要问, f 在做什么?
首先 f 是一个单变量函数,接收另一个函数 x,而又把 x 自己当作参数传给 x 执行(因此 x 也是单变量函数),也就是说,传给 f 的参数 x 既要是运算符,又是运算对象。
可以用更清晰的方式来编写 f:
def f(x):
# x 先作为函数的副本
function_copy = x
# x 再作为数据的副本
data_copy = x
return function_copy(data_copy)
这里实际有一个小的认知跳跃:你得承认或接受函数和数据是统一的(或者把数据分成动态和静态两部分),就像冯诺伊曼把指令和数据看作同一个东西,函数式编程中把函数作为一等公民,与其他数据类型没有本质区别一样。
x(x) 一部分是能动的主体,另一部分是被动的"引用"(quote), 上例中,以底层运行的视角来看,function_copy(data_copy) 里的 function_copy 是主动部分,它促使执行环境生成新的调用栈,以便执行一整串代码,而 data_copy 是被动部分,只是一个堆内地址(或者只是对本体的 quote)。
自指之所以能导致递归,还有一个重要操作是对信息进行了复制,可复制性是关键,以上每次调用中都进行了自复制(copy 两份),作为比较,量子比特是不具有可复制性质的,因此可复制不是一个理所当然的性质。
由于输入 f 的是单参数函数,因此先尝试把最常见的 print 传给它看看结果:
f(print)
<built-in function print>
以上执行了 print(print), print 打印出了自己(的描述),从这个例子已经有了"自己操作自己" 的感觉,应该趁着感觉没有消退给 f 取一个更能有代表性的名字。
3.2. 取一个好一点的名字
如果是中文,那么把 f 叫做 "自作自受" 似乎不错。
不过,既然连 lambda x:x
如此简单的表达式在 lambda 演算的话语体系中都有一个专门的名字 – I 算子。
显然 lambda x:x(x)
也不会籍籍无名,它实际叫做 omega 算子,希腊字母是 \( \omega \), 但这个词不太直观,不像 I 算子,至少 I 表示”我“,还是比较符合 lambda x:x
的语义,也许 lambda x:x(x)
得叫做 I2I?
(有些资料会把 (lambda x:x(x))(lambda x:x(x))
整个式子称为 omega 算子,但后文会看到这在 python 中会导致死循环,无法作为算子)
不过我还是决定抛开这些简单大写字母,给它取一个比较直观的名字,由于 f 的功能是让某个函数作用在自己身上(自应用),因此这里取名为 apply_self:
apply_self = f
接着的问题是: 什么样的单变量函数可以作为 f 的参数?
先不去构造真正能执行成功的函数,以下罗列几个假想的函数(主要用函数名突出功能)
apply_self(kick) 得到的语义是 kick kick, 然而,一般踢的对象是一个名词,比如踢球,踢毽子,这里踢“踢”是不好理解的 当然可以用代词来表示被踢的对象,于是变成了 kick self, 但这容易导致歧义,因为说"踢自己" 的时候,这个自己表示的是踢的主语,也就是发出踢这个动作的对象,而不是"踢" 本身,套用在本例,kick self 更像是在 kick python 解释器,因为 kick 这个动作是解释器发出的。
这里可以看到,要让 apply_self(x) 执行的结果有点意义,首先 x 需要是一个动词,然后它还需要有某种名词的意义,这个名词能够承受这个动作本身。
当前暂时不去费力思考有哪些这样的动词,以下先随意列出自己想到的一些常用动词,带入到 apply_self 中去
apply_self(kiss) --> kiss kiss apply_self(亲) --> 亲亲 apply_self(抱) --> 抱抱 apply_self(加一) --> 加一加一 apply_self(apply_self) --> apply_self(apply_self) --> 无限递归了 apply_self(print) --> print(print)
可以看到,lamba x:x(x) 算是一个比较有趣的代码,目前尝试出了两种用法:
- x 是一个一次性动作,比如 kick, book, 然后得到 kick(kick), book(book), 或者构造打印出自己的形式,这个过程像是字迷游戏,有智力上的乐趣(和无聊),发现了语言中的一些奇怪用法,似乎没有太多实际用处(其中比较有名的应用是 quine 程序,这部分暂时不在本文中讨论)
x 是 apply_self 自身, 这就导致无限递归,有点哲学意味,但似乎也没有实际用处。然而这个场景说明,实际可以不需要 Y 算子就构造出递归,只不过会构造一个无法控制的无限递归,而 Y 算子就是驯服无限的产物。
栈溢出场景:
apply_self(apply_self)
[0;31m[0m [0;31mRecursionError[0mTraceback (most recent call last) [0;32m<ipython-input-208-eac5c6a85200>[0m in [0;36m<module>[0;34m[0m [0;32m----> 1[0;31m [0mapply_self[0m[0;34m([0m[0mapply_self[0m[0;34m)[0m[0;34m[0m[0;34m[0m[0m [0m [0;32m<ipython-input-23-dc13f62ac9e4>[0m in [0;36m<lambda>[0;34m(x)[0m [0;32m----> 1[0;31m [0mf[0m [0;34m=[0m [0;32mlambda[0m [0mx[0m[0;34m:[0m[0mx[0m[0;34m([0m[0mx[0m[0;34m)[0m[0;34m[0m[0;34m[0m[0m [0m ... last 1 frames repeated, from the frame below ... [0;32m<ipython-input-23-dc13f62ac9e4>[0m in [0;36m<lambda>[0;34m(x)[0m [0;32m----> 1[0;31m [0mf[0m [0;34m=[0m [0;32mlambda[0m [0mx[0m[0;34m:[0m[0mx[0m[0;34m([0m[0mx[0m[0;34m)[0m[0;34m[0m[0;34m[0m[0m [0m [0;31mRecursionError[0m: maximum recursion depth exceeded
4. 可控核聚变(不彻底的 Y)
到目前为止,执行完 x(x) 后,要么是对自己"踢"了一脚,或打印出自己,要么就死循环了。前者是游戏过早结束,后者是游戏陷入 bug(异常), 这说明对 x(x) 这个游戏的控制力都还不足。这就像人们可以利用不可控的核聚变引爆轻弹释放巨大的能量, 但只有可控的核聚变才能带来真正造福人类的能源。
本节是对控制无限递归的尝试。首先展开 apply_self(apply_self)
:
(lambda x:x(x))(lambda x:x(x))
这看上去是两个相同的式子,是 (x)(x) 的形式,然而左边的 (lambda x:x(x)) 和右边的 lambda x:x(x) 其实不是同一个对象,更好的写法应该是:
(lambda y:y(y))(lambda x:x(x))
把以上式子中的 lambda y:y(y)
取名 left, lambda x:x(x)
取名 right
(注:这种能够把 lambda x:x(x) 转换成 lambda y:y(y) 的规则在 lambda 演算中称为 alpha 变换,这对了解编程的人来说几乎是一种隐规则,我想不起在编程中,应该如何形容它,变量替换规则吗?)
left = lambda y:y(y)
right = lambda x:x(x)
因此这里实际是要执行:
left(right)
执行一次之后,才会得到左右两边完全相同的式子:
(lambda x:x(x))(lambda x:x(x))
这里左右两边的 lambda x:x(x) 指向的是同一个 right,是完全相同的对象,也就是
(right)(right)
之后再执行下去每次都会继续得到相同的 (right)(right)
, 也就是说,是 right 真正陷入了自指的递归,而不是 left。
尽管 left 和 right 是形式相同的公式。
left 更像是一个启动器的作用,只负责多米诺骨牌第一次推动,真正的多米诺骨牌是 right.
因此要对无限循环进行控制,比较好的入手点应该是修改 right , 比如说,假设函数 right 内部有一个全局的统计 right 执行次数的属性 right.cnt
, 那么可以把 right 改成:
lambda x: "stop" if x.cnt == 100 else x(x)
这种情况下就可以控制循环次数,在 python 中,由于函数也是对象,可以给函数加上属性,例如以下用 decorator 来实现
right = lambda x: "stop" if x.cnt == 100 else x(x)
def cnt_decorator(f):
def inner(*args):
inner.cnt += 1
return f(*args)
inner.cnt = 0
return inner
right2 = cnt_decorator(right)
以上代码对 right 进行装饰,给它包装了一个 cnt 属性,每次执行一次调用,计数器就会 +1, 这个原理和介绍算子一节中用到的 printter
例子是类似的。
接着用 left 去启动 right2:
(left)(right2)
stop
可以看到,这里成功停止住了,查看 cnt 属性:
right2.cnt
100
right(right) 能够停住的原因在于, right 中的自指结构部分 x(x) 被一个 if 判断阻挡了,每次执行 right(right) 的时候,必须先通过 if 条件判断,这表明 right 中有可能划分出明确的两部分,纯计算部分和纯递归递归,比如以下函数可以完全不进行递归(虽然形式上两部分都有):
pure_compute = lambda x: (2**3-4) if 1 == 1 else x.cnt + x(x)
left(pure_compute)
4
再次提醒, x(x) 是纯递归结构,它的作用一方面是使得 x 作为函数能够执行(构建下一层调用栈,在新的调用栈内触发计算部分),另一方面是把 x 的引用作为数据传到调用栈,使得下一个层级能继续去调用 x(x), 以此重复。
在一般的递归函数中,计算和递归结构是交替或同时进行的,例如用以下是计算前 n 项和 right 函数
sum10 = lambda x: x.cnt if x.cnt == 10 else x.cnt + x(x)
sum10 = cnt_decorator(sum10)
left(sum10)
55
这里计算和递归同时发生在 x.cnt + x(x) 式子中,而在迭代的终点( basecase ),只进行了计算。
总的来说,根据以上的尝试发现,只要有 left, 然后改造 right,就可以实现可控递归了,不过由于函数属性是 python 内置的,因此要考虑如何把 right.cnt 这个属性做成外部参数,一种方法是给 right 添加一个用于计数的参数:
right3 = lambda x, n: "stop" if n == 0 else x(x, n-1)
在这种情况, left 算子需要修改,以符合 right3 有两个参数的要求:
(lambda f: f(f, 10))(right3)
stop
但对 right 部分进行 curry 化之后, left 又可以回到最初 omega 算子的形式,完全不用做任何修改:
right4 = lambda x: lambda n: "stop" if n == 0 else x(x)(n-1)
left(right4)(3)
stop
注意这里是怎么把 n-1 放到 x(x)(n-1) 后的,它实际是从 x(x, n-1) 直接演变过来的,curry 的过程用以下例子展示,其中 add(x,y) 等价于 addx(x)(y)
def add(x, y):
return x + y
def addx(x):
return lambda y: x+y
print(add(1,2), addx(1)(2))
3 3
为了便于对比,以下列出了 right 的三次变化过程:
right2 = lambda x: "stop" if x.cnt == 100 else x(x)
right3 = lambda x, n: "stop" if n == 0 else x(x, n-1)
right4 = lambda x: lambda n: "stop" if n == 0 else x(x)(n-1)
前两个形式理解上应该不会有太多问题,而最后一次变形是有点跳跃的,这里需要注意几点:
- 原本函数只要执行一次就会陷入递归,例如 x(x) 或者 x(x, n-1), 但最后一个式子中,要执行两次,因为 x(x) 返回的是一个函数(以 n 作为参数)
- 由于 x(x) 返回的是函数,所以
left(righ4)
得到的也是函数,因此需要用left(righ4)(n)
才能真正启动 (前两点观察给了我另外一种修改 right 的手段,就是在递归结构中不真正执行代码,而是只执行 x(x) 以返回一个函数,使得递归被延迟,该技巧在后文中讨论) - 这种场景下,left 已经从一个函数启动器变成了真正的算子(combinator: 输入和输出都是函数的函数) 了
至此,我们在 lambda calculus 的标准获得了可控递归的能力,可以根据需求改造 right, 然后放到 left 中获得一个真正可执行的递归函数:
求前 n 个整数的和:
sumn = lambda x: lambda n: 0 if n == 0 else n + x(x)(n-1)
left(sumn)(10)
55
fibnacci
fib = lambda x: lambda n: n if n <= 2 else x(x)(n-1) + x(x)(n-2)
(left)(fib)(10)
89
纯匿名函数写法:
(lambda x:x(x))(lambda x: lambda n: n if n <= 2 else x(x)(n-1) + x(x)(n-2))(10)
89
这是从 0 到 1 的突破🥳!
收获了可控递归的能力,从此只用匿名函数就可以写出(任何?)递归函数。
而所有的秘密都来自于一个小小的 x(x), 它在 left 部分被封装成算子 lambda x:x(x)
,在 right 部分则替换掉需要递归的函数调用, 自指的魅力在这里展现地淋漓尽致,这感觉就像从初等数学到高等数学时,原本 0/0 的无效等式只要加上极限,就变成无穷小量运算,从而巧妙地绕过无穷,很是优雅。 x(x) 堪比微积分中的无穷小量。
以有涯随无涯,x(x) 已
– omega
5. Y: 被驯服的递归
5.1. stop: 目前的进展
上节中实际已经获得了可控的递归,而引入 Y 算子来自于对极简和解耦的执念(当然也可能是偶然获得,没考究过),希望 right 内部的 x(x) 递归结构变得更加简约,从而使得 fib 可以写成以下形式
fib2 = lambda x: lambda n: n if n <= 2 else x(n-1) + x(n-2)
执行时则用 Y 取代 left (或 omega)
Y(fib2)(10)
从 omega 到 Y 的区别在于,递归函数 fib2 更简单且直观(也符合在非匿名函数中写递归的习惯:将 lambda x
替换成 def x:
),所有的负担被统一到 Y 中,可以想象, Y 中要有更复杂的 x(x) 结构才行
然而为了改造 left , 还是要回到 right (因为真正的计算和递归结构都在 right 中)
为了更容易看清问题,这里总结到目前为止的进展:
- 从最简单的
lambda x:x
变换到带自指结构的lambda x:x(x)
- 发现
(lambda x:x(x))(lambda x:x(x))
执行一步之后还是会得到(lambda x:x(x))(lambda x:x(x))
从而陷入无限递归 - 看到了
lambda x:x(x)
所带来的无法掌控的递归能力,因此寻求对递归的控制。于是分解了(lambda x:x(x))(lambda x:x(x))
,把它写成left(right)
的形式,并且发现 right 才是真正"多米诺骨牌", left 只是第一推动力 - 继续分析 right ,发现可以用 if else 来划分开计算和递归结构,因此这个模型可以写成
left([compute if condition then recursive])
, 尽管形式上 recursive 部分被 then 关键词分离了,但从代码上还不知道如何把 recursive 部分完全提取,因为不同的函数 recursive 是不同的,有的是 x(x)(n-1), 有的是 x(x)(n-1) + x(x)(n-2). - 为了追求简洁的美感,本节想把递归结构全部放到 left 中去,使得 right 只剩下计算,因此打算丢弃其中的 x(x)(n-1) 结构,替换成普通的 x(n-1), 这导致自指消失了。
- 为了达到目的,可以选择改造 left, 也可以选择改造 right. 但改造 right 看上去更可行,因为我们已经对 right 做了多次变化并观察其计算过程,目前要做的只不过是继续改造和抽象 right, 使得能够在 right 中把计算和递归结构彻底分离。
回到 fib2 这个函数,除了 basecase (也就是只激活纯计算的场景)能够执行成功,其他情况下是会报错的:
fib2 = lambda x: lambda n: n if n <= 2 else x(n-1) + x(n-2)
apply_self(fib2)(1)
1
x(n-1) 返回的是函数而不是具体的值, 所以非 basecase 会报错,
apply_self(fib2)(3)
TypeErrorTraceback (most recent call last) <ipython-input-145-1aa2a89bb28c> in <module> ----> 1 apply_self(fib2)(3) <ipython-input-144-535fff03b5fd> in <lambda>(n) ----> 1 fib2 = lambda x: lambda n: n if n <= 2 else x(n-1) + x(n-2) 2 apply_self(fib2)(1) TypeError: unsupported operand type(s) for +: 'function' and 'function'
除非能在 fib2 的参数 x 中注入类似 x(x) 的自指结构, 否则 fib2 只有一次性的计算过程(和 kick kick 一样),为此要观察如何能把纯计算过程抽取出来, 为了抽出计算过程,实际要对递归结构有更强的控制力(想象黑客帝国的场景,只要控制力足够强,把时间慢下来,子弹都可以躲避,也就是可以随意处置数据)
5.2. 控制的极端:单步调试型递归
以 right4 函数为例:
right4 = lambda x: lambda n: "stop" if n == 0 else x(x)(n-1)
上一节说过,在等式右边中的 x(x) 实际返回的是一个函数,它是递归的静态版本,或者说是交互版本,因为如果把 x(x)(n-1) 替换成 x(x) 的话,即便执行了 else 后的内容,得到的也只是一个函数而已,不会递归下去, 只有调用者手动再执行一次才行,如下:
right5 = lambda x: lambda n: "stop" if n == 0 else x(x)
left(right5)(2)
<function __main__.<lambda>.<locals>.<lambda>(n)>
只要用户输入参数不是 0, 可以永远执行下去
left(right5)(2)(1)(2)(1)(100)(2023)
<function __main__.<lambda>.<locals>.<lambda>(n)>
用 0 来结束:
left(right5)(2)(1)(2)(1)(100)(0)
stop
可以看到,这种控制几乎已经到了极端,因为可以修改递归过程的状态,以决定递归是否结束。
但这种方式在计算结构和递归结构耦合在一起的情况下很难实现,例如,如果要把 sumn 由
sumn = lambda x: lambda n: 0 if n == 0 else n + x(x)(n-1)
改写成:
sumn2 = lambda x: lambda n: 0 if n == 0 else n + x(x)
left 无法作为正确的启动器:
left(sumn2)(2)
TypeErrorTraceback (most recent call last) <ipython-input-153-862808724cce> in <module> ----> 1 left(sumn2)(2) <ipython-input-152-1a41f18b8027> in <lambda>(n) ----> 1 sumn2 = lambda x: lambda n: 0 if n == 0 else n + x(x) TypeError: unsupported operand type(s) for +: 'int' and 'function'
这是因为 n + x(x)
是一个整数加上一个函数,而在 python 中,原生的(匿名)函数不支持加法,不过在 python 中很可以设计一个支持进行加法的"函数",如下
把 n 和 x(x) 都替换成以下类的实例就可以解决类型冲突的问题,不过这会导致无法再使用 lambda 表达式,过度偏离初衷。
class Add1:
def __init__(self):
self.number = 1024
def __add__(self, other: int):
return self.number + other
def __call__(self, other):
return other + 1
add1 = Add1()
add1 + 2
1026
另外一种做法是,不在这里直接使用 python 原生的 +
进行加法,而是考虑设计一个函数 add3 替换 +
,使得它可以支持整数与另一个"潜在"的整数相加。期望的写法应该是:
sumn3 = lambda x: lambda n: 0 if n == 0 else add3(x(x))(n)
这里 add3 也可以写成双参数形式,如 add3(a,b), 但为了统一成单参数,进行了 curry 化, add3(x(x))(n) 应该返回一个函数(实际就是 sumn3_1(x)),其接收用户输入的整数,如果输入 0, 那么只能 return 0,否则返回 x(x),这样就又继续等待用户输入,同时把目前累加的值打印出来(由于 basecase 就是返回 0, 因此无法在最后返回最终的累加值,因此用打印的方式来处理)。
def add3(recur):
def inner(n):
global cum_sum
cum_sum += n
print(f"sum of history input is: {cum_sum}")
return recur
return inner
cum_sum = 0
left(sumn3)(2)(3)(5)(7)(9)(11)
sum of history input is: 2 sum of history input is: 5 sum of history input is: 10 sum of history input is: 17 sum of history input is: 26 sum of history input is: 37 <function __main__.<lambda>.<locals>.<lambda>(n)>
这里成功实现了一个用户可以单步执行的累加的递归函数,不过引入了额外的全局变量 cum_sum
然而这个例子想告诉自己的是,完全可以把递归的引擎 x(x)
作为参数进行传递,只要 x(x) 返回的是一个函数,而不是无限递归(过程), Y 算子的设计就吸收了这个思想。
在结束本节前,再引入一些让执行过程变成函数的方式,如下:
# 这是 apply 过程(动态)
print(1)
# 这是 print 函数(静态)
print
# 这是对 print 函数的静态化,加了函数封装
lambda : print(1)
# 这是封装后 apply, 等价于 print(1)
(lambda : print(1))()
# 这也是对 print 函数的静态化,加了函数封装, 比上一个多一个参数,但该参数只是装点门面的
lambda x: print(1)
# 这是上一个式子的 apply, 也等价于 print(1)
(lambda x: print(1))(2023)
1 1 1
print(1)
, (lambda : print(1))()
, (lambda x: print(1))(2023)
三者是等价的,这在 lambda 演算中被称为 eta 归约(规则),不过我相信不需要这个抽象的名字也是能够理解的。另外把 print(1) 变成 lambda : print(1)
的操作被称为逆 beta 变换,这是因为对函数进行 apply 在 lamba 演算中称为 beta 变换。
有了这个理解后,我们就可以把 right5 写成如下:
right6 = lambda x: lambda n: "stop" if n == 0 else lambda n: x(x)(n-1)
left(right6)(2)(3)(5)(0)
stop
该写法维持住了 x(x)(n-1) 形式的递归调用结构
同时 sumn3 也可以改成:
sumn4 = lambda x: lambda n: 0 if n == 0 else add3(lambda z: x(x)(z))(n)
cum_sum = 0
left(sumn4)(1)(2)(3)(4)
sum of history input is: 1 sum of history input is: 3 sum of history input is: 6 sum of history input is: 10 <function __main__.<lambda>.<locals>.<lambda>.<locals>.<lambda>(z)>
本节的例子(成功或失败)是为了展示对递归的进行更强的控制的尝试,同时引出了 beta 变换,逆 beta 变换和 eta 变换等概念,这些基本概念以及对递归的控制的思想是构造出 Y 的关键
5.3. 直到未知的尽头
目前为止讨论过的几个典型带自指(递归)函数:
left = lambda y:y(y)
right = lambda x:x(x)
right2 = lambda x: "stop" if x.cnt == 100 else x(x)
right3 = lambda x, n: "stop" if n == 0 else x(x, n-1)
right4 = lambda x: lambda n: "stop" if n == 0 else x(x)(n-1)
fib = lambda x: lambda n: n if n <= 2 else x(x)(n-1) + x(x)(n-2)
手动触发单步递归的函数(没有不同类型之间的运算冲突):
right5 = lambda x: lambda n: "stop" if n == 0 else x(x)
sumn3 = lambda x: lambda n: 0 if n == 0 else add3(x(x))(n)
手动触发单步递归的函数(没有不同类型之间的运算冲突),同时维持 x(x)(n-1) 结构:
right6 = lambda x: lambda n: "stop" if n == 0 else lambda n: x(x)(n-1)
sumn4 = lambda x: lambda n: 0 if n == 0 else add3(lambda z: x(x)(z))(n)
不带自指的函数:
fib2 = lambda x: lambda n: n if n <= 2 else x(n-1) + x(n-2)
为了与 x(x) 中的 x 进行区分 ,fib2 改写成:
fib2 = lambda f: lambda n: n if n <= 2 else f(n-1) + f(n-2)
可以看到,假设 x(x) 是一个函数的话(在 righ4,right5,right6,sumn3, sumn4 中都是),那么 fib2(x(x))
实际等于
lambda n: n if n <= 2 else x(x)(n-1) + x(x)(n-2)
这个结构很像 fib, 只是没有 lambda x:
头部,尝试先手动加上这个头部,于是 lambda x: fib2(x(x))
形式就完全等于 fib:
lambda x: lambda n: n if n <= 2 else x(x)(n-1) + x(x)(n-2)
注意对比 lambda x:fib2(x(x))
和 lambda x:x(x)
为了方便,继续取名:
right_fib = lambda x:fib2(x(x))
right = lambda x:x(x)
left(right) 是会陷入无限递归的,那么 left(right_fib) 呢,也是会无限递归的,这是因为,为了执行 fib2 函数真正的内容,python 先要计算出参数的值 x(x), 而计算 x(x) 会导向 fib2(x(x)), 又得继续计算 x(x), 从而失去控制
这里的核心原因在于 x(x) 并不是一个函数(不符合最初的假设),这个时候我们就要考虑如何把 x(x) 变成函数,这样就不会一只计算下去,从 right2 到 right4 是 x(x) 函数化的关键。这是由于 lambda x:
内部套了一个 lambda n:
而导致的:
right2 = lambda x: "stop" if x.cnt == 100 else x(x)
right3 = lambda x, n: "stop" if n == 0 else x(x, n-1)
right4 = lambda x: lambda n: "stop" if n == 0 else x(x)(n-1)
right3 到 right4 是出于 curry 化考虑的,在极端控制一节中,我们知道,为了阻止函数执行,可以对执行过程执行逆 beta 变换,因此 lambda z:x(x)
或者 lambda :x(x)
也是不会被执行的。
于是,对于 right_fib = lambda x:fib2(x(x))
有两种逆 beta 变换方法:
lambda x: lambda z:fib2(x(x)(z))
# 或者
lambda x: fib2(lambda z: x(x)(z))
<function __main__.<lambda>(x)>
然而,第一种方式,x(x)(z) 还是作为参数传递给 fib2, 为了执行到 fib2 的正文,仍然会陷入无限递归(可以把 fib2 改成简单的 I 来理解):
left(lambda x: lambda z:fib2(x(x)(z)))(2)
RecursionErrorTraceback (most recent call last) <ipython-input-207-d08ef7632b4d> in <module> ----> 1 left(lambda x: lambda z:fib2(x(x)(z)))(2) <ipython-input-207-d08ef7632b4d> in <lambda>(z) ----> 1 left(lambda x: lambda z:fib2(x(x)(z)))(2) ... last 1 frames repeated, from the frame below ... <ipython-input-207-d08ef7632b4d> in <lambda>(z) ----> 1 left(lambda x: lambda z:fib2(x(x)(z)))(2) RecursionError: maximum recursion depth exceeded
第二种方式则可行,因为把 fib2 展开后它就是:
lambda x: lambda n: n if n <= 2 else (lambda z:x(x)(z))(n-1) + (lambda z:x(x)(z))(n-2)
<function __main__.<lambda>(x)>
(lambda z:x(x)(z))(n-1)
部分执行起来等价于 x(x)(n-1)
, 和最初的 fib 是一样(这里 z 只是一个 placeholder, 用来传递 fib2 中的第二个参数 n)
left(lambda x: fib2(lambda z: x(x)(z)))(5)
8
这里我们成功把 x(x) 通过 lambda z:x(x)(z) 的方式打包了出来,把一个无限递归的危险对象安全地传给了 fib2, 并且让 fib2 跟随着 x(x) 一起递归:
我能想到最浪漫的事,就是带你一起递归到未知的尽头
– Y
由于 fib2 函数被完全抽离出来,因此可以替换成任何递归形式的函数,而为了能够让用户指定输入,可以继续逆 beta 变换,并且把 z 参数一般化:
lambda f: left(lambda x: f(lambda *args: x(x)(*args)))
相当于:
lambda f:left(right)
只不过 right 中是可以带上 f 参数的。
这就是 python 中的 Y 算子了:
Y = lambda f: (lambda x:x(x))(lambda x: f(lambda *args: x(x)(*args)))
Y(fib2)(10)
89
写成 lisp 形式
(define Y
(lambda (f)
((lambda (x) (x x))
(lambda (x) (f (lambda (z) ((x x) z)))))))
写成 lambda 演算: \[ \lambda f.(\lambda x.x x) (\lambda x. (f \lambda z. (x x)z)) \]