从 x(x) 到 Y : 用 python 构建和理解 Y 算子（Y combinator）

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

由于输入 f 的是单参数函数，因此先尝试把最常见的 print 传给它看看结果：

f(print)

<built-in function print>

以上执行了 print(print), print 打印出了自己（的描述），从这个例子已经有了"自己操作自己" 的感觉，应该趁着感觉没有消退给 f 取一个更能有代表性的名字。

如果是中文，那么把 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)
  

  
  RecursionErrorTraceback (most recent call last)
  <ipython-input-208-eac5c6a85200> in <module>
  ----> 1 apply_self(apply_self)
  
  <ipython-input-23-dc13f62ac9e4> in <lambda>(x)
  ----> 1 f = lambda x:x(x)
  
  ... last 1 frames repeated, from the frame below ...
  
  <ipython-input-23-dc13f62ac9e4> in <lambda>(x)
  ----> 1 f = lambda x:x(x)
  
  RecursionError: maximum recursion depth exceeded
  

上节中实际已经获得了可控的递归，而引入 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 中）

为了更容易看清问题，这里总结到目前为止的进展：

1. 从最简单的 lambda x:x 变换到带自指结构的 lambda x:x(x)
2. 发现 (lambda x:x(x))(lambda x:x(x)) 执行一步之后还是会得到 (lambda x:x(x))(lambda x:x(x)) 从而陷入无限递归
3. 看到了 lambda x:x(x) 所带来的无法掌控的递归能力，因此寻求对递归的控制。于是分解了 (lambda x:x(x))(lambda x:x(x)) ，把它写成 left(right) 的形式，并且发现 right 才是真正"多米诺骨牌", left 只是第一推动力
4. 继续分析 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).
5. 为了追求简洁的美感，本节想把递归结构全部放到 left 中去，使得 right 只剩下计算，因此打算丢弃其中的 x(x)(n-1) 结构，替换成普通的 x(n-1), 这导致自指消失了。
6. 为了达到目的，可以选择改造 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 一样），为此要观察如何能把纯计算过程抽取出来， 为了抽出计算过程，实际要对递归结构有更强的控制力（想象黑客帝国的场景，只要控制力足够强，把时间慢下来，子弹都可以躲避，也就是可以随意处置数据）

以 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 的关键

目前为止讨论过的几个典型带自指(递归)函数：

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