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

对 I 算子，实际上没有太多可以说的，它并不是非常有趣（尽管在 lambda 演算中 I 可以和其他算子组合出其他有趣的算子，但本文不讨论，如有兴趣可以阅读 以函数为中心：lambda 演算和组合子逻辑 中的组合子逻辑一节）。

在 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）。x(x) 的自指并不是 x 函数调用了自身，而是 x 的参数中捕获了自身，如果 x 内部会把参数当作函数进行执行，那么就会发生递归。

由于输入 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 中会导致死循环，无法作为算子，而在 lambda 演算理论中，由于只关注符号形式，所以即便不会终止的表达式也可以称为算子)

不过我还是决定抛开这些简单大写字母，给它取一个比较直观的名字，由于 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) 
  

可以看到，lambda 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
  

首先展开 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), 也就是说，尽管 left 和 right 是形式相同的公式，但执行一次之后 left 就不见了，是 right 真正陷入了递归，而不是 left 。

left 更像是一个启动器的作用，只负责多米诺骨牌第一次推动，真正的多米诺骨牌是 right.

因此要对无限循环进行控制，比较好的入手点应该是修改 right，当我们把单变量函数 right 传入 left 后，left 中的 x(x) 或者 function_copy(data_copy) 首先就要对 right 函数进行一次调用，因此如果 right 中执行的代码和传入的参数无关，比如 lambda y:1, 那么 left(lambda y:1) 就是纯粹把 right 函数中的内容执行一遍：

left(lambda y:1)

1

或者：

left(lambda y: sum([x for x in range(10)]))

45

这种情况无论是执行 right(0), right(1), 或者 right(right), 由于函数体和参数无关，因此结果都一样，一次性执行完成。

如果 right 是以下函数

right = lambda x:x(x)

由前文分析知道，left(right) 会导向 right(right) 从而不断递归。

但假设函数 right 内部有一个全局的统计 right 执行次数的属性 right.cnt, 就可以把 right 改成：

right1 = lambda x: "stop" if x.cnt == 100 else x(x)

这种情况下可以控制循环次数,在 python 中，由于函数也是对象（是一种特殊类的实例），可以给函数加上属性，例如以下用 decorator 来实现

def cnt_decorator(f):
    def inner(*args):
        inner.cnt += 1
        return f(*args)
    inner.cnt = 0
    return inner

right2 = cnt_decorator(right1)

以上代码对 right1 进行装饰，给它包装了一个 cnt 属性，每次执行一次调用，计数器就会 +1, 这个原理和介绍算子一节中用到的 printter 例子是类似的。

接着用 left 去启动 right2:

(left)(right2)

stop

可以看到，这里成功停止住了，查看 cnt 属性：

right2.cnt

100

right(right) 能够停住的原因在于，right 中的自指结构部分 x(x) 被一个 if 判断阻挡了，每次执行 right(right) 的时候，必须先通过 if 条件判断，这表明 right 中可以划分出明确的两部分：非自指部分和自指部分。

注意我们并不是用第一节提到的递归函数中的 basecase 和递归分支来描述这两部分，因为 right 并不是我们一般所理解的递归函数，它代码里的 x(x) 中 x 并不是对函数本身的引用，而是对参数的引用，这里 x(x) 的自指不是对 right 函数自身的“指向”，而是函数 x 能够引用到参数自身，所以此处我们只谈论自指。

总的来说，根据以上的尝试发现，只要有 left, 然后改造 right，就可以实现可控递归了，不过由于函数属性是 python 内置的，因此要考虑如何把 right.cnt 变成普通函数里的对象，这种情况几乎没有多少选择，你只能把它放到 right 的参数里：

right3  = lambda x, n: "stop" if n == 0 else x(x, n-1)

由于 left 要执行 x(x) ，它只能接收单参数函数，所以和 right3 并不兼容，一种方法是将 left 中 x(x) 参数扩充为两个 x(x, n)，以符合 right3 有两个参数的要求，并且把初始值硬编码在 left 中：

(lambda f: f(f, 10))(right3)

stop

此时执行一步后得到的是 right3(right3, 10), 作为函数的 right3 先检查 if 条件，发现 n==0 不成立，于是继续执行 right3(right3, 9), 以此不断减少第二个参数，直到 right3(right3, 0) 时返回 "stop".

但 lambda 演算中要求的函数参数都只是一个，为此我们要对 right 部分进行 curry 化，这是把多变量函数转换成嵌套的单变量函数的手段。

以下例子中，双变量函数 add(x,y) 等价于 addx(x)(y), addx 是单变量函数，它应用一次后返回一个单变量函数，因此可以对返回值继续进行函数调用：

def add(x, y):
    return x + y

def addx(x):
    return lambda y: x+y
# 等价于:
# addx = lambda x:lambda y:x+y

print(add(1,2), addx(1)(2))

3 3

当对 right3 进行 curry 化之后，left 又可以回到最初 omega 算子的形式，完全不用做任何修改：

right4  = lambda x: lambda n: "stop" if n == 0 else x(x)(n-1)
left(right4)(3)

stop

注意这里我们把双参数函数的定义 lambda x,n 变成了嵌套的 lambda x:lambda n 结构，然后原本 x(x,n-1) 的执行方式变成了 x(x)(n-1)

left(right4) 进行一次应用之后的结果是 right4(right4) ，把左侧作为函数的 right4 展开并代入右侧实参后结果如下：

lambda n: "stop" if n == 0 else right4(right4)(n-1)

它是一个以 n 为参数的单变量函数，要通过 left(right4)(n) 去调用，这与 right2 、right3 的行为很不一样，left(right2) 和 left(right3) 都是直接进入递归，初始参数必须被编码在其他地方（比如 python 函数属性初始值或者改造后的 left 中），但 left(right4) 返回的是函数，这意味着 left 已经从一个函数启动器变成了真正的算子了，它接受函数后不是一股脑执行下去，而是返回一个函数供用户继续传入特定的 n。

假设传入 10, 那么由于 n==0 不成立，于是执行 right4(right4)(9) ， 这是一个比 right4(right4)(10) 更接近 basecase 的节点，依次执行下去，当到 right4(right4)(0) 的时候 if 语句阻断的自指部分的执行，于是返回 "stop" 。

因此， right4 被 left 装饰后就可以当作普通的 python 递归函数来使用了。

至此，我们在 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

left(fib) 可以看作是用 left 对 fib 进行加工，因此这延伸出了装饰器的写法（当然装饰器只能用在 def 这种有名字的函数定义语法前，而既然有名字实际就不需要实现 x(x) 形式的递归函数了，不过这里只是进行展示）：

@left
def fib_rec(x):
    return lambda n: n if n <= 2 else x(x)(n-1) + x(x)(n-2)

fib_rec(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 部分则替换掉需要递归的函数调用, 自指的魅力在这里展现地淋漓尽致。

以有涯随无涯，x(x) 已

– omega

上节中实际已经获得了可控的递归，而引入 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: lambda n 替换成 def x(n): 就得到了标准的非匿名函数递归定义：

def x(n):
    return n if n <= 2 else x(n-1) + x(n-2)

x(10)

89

但由于 x(x) 这种自指结构没有了，那么负责”递归“的所有的负担被集中到 Y 中，可以猜测， Y 中要有更复杂的 x(x) 或其他自指性质的结构才行。

然而为了改造 left ， 还是要回到 right ，因为真正的计算和递归结构都在 right 中，比如说，当暂时不考虑合理性的情况下，如果对 fib2 执行以下操作：

fib2(x(x))

（这个式子是不合法的，因为 x(x) 在全局环境下是未定义的）

那么将参数代入 fib2 展开一次之后得到的就是:

lambda n: n if n <= 2 else x(x)(n-1) + x(x)(n-2)

只要再加上 lambda x: 就回到了 fib 的定义：

fib = lambda x: lambda n: n if n <= 2 else x(x)(n-1) + x(x)(n-2)

也就是说以下函数似乎等价于 fib:

lambda x:fib2(x(x))

（这个式子是合法的，因为 x(x) 放在 lambda x 函数中，尽管不知道 x(x) 是什么）

因此 left(lambda x:fib2(x(x))) 就得到了一个递归函数，而且 fib2 还可以替换成以下形式的 sumn2

sumn2 = lambda x: lambda n: 0 if n == 0 else n + x(n-1)

lambda x:sumn2(x(x)) 从“形式上”等价于 sumn:

sumn = lambda x: lambda n: 0 if n == 0 else n + x(x)(n-1)

这意味着 left(lambda x:fib2(x(x))) 中 fib2 替换成 sumn2 就能得到求前 n 项和的递归函数，表明 fib2 是可以灵活替换的，因而它可以被抽取出来作为一个可定制的参数：

X = lambda f: left(lambda x:f(x(x)))

看上去执行 X(fib2) 或者 X(sumn2) 都会得到一个递归函数，似乎它就是我们追求的 Y 算子，但实际上，尝试去执行以下式子，会无限递归：

left(lambda x:fib2(x(x)))

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
Cell In[72], line 1
----> 1 left(lambda x:fib2(x(x)))

Cell In[21], line 1, in <lambda>(y)
----> 1 left = lambda y:y(y)
      2 right = lambda x:x(x)

Cell In[72], line 1, in <lambda>(x)
----> 1 left(lambda x:fib2(x(x)))

Cell In[72], line 1, in <lambda>(x)
----> 1 left(lambda x:fib2(x(x)))

    [... skipping similar frames: <lambda> at line 1 (2973 times)]

Cell In[72], line 1, in <lambda>(x)
----> 1 left(lambda x:fib2(x(x)))

RecursionError: maximum recursion depth exceeded

将 fib2 替换成 sumn2 或者其他任何函数都会如此，这是将其称为 X 而不是 Y 的原因。

为什么 left(lambda x:fib2(x(x))) 会无限递归？ 是 fib2 导致的吗？

并不是，刚说过替换成 sumn2 或者其他任何函数都会无限递归，如果把 fib2 删除是什么呢？

非常眼熟，它实际就是 left(lambda x:x(x)) ，也就是 apply_self(apply_self) ，它是不可控递归的根源。

如果把 lambda x:fib2(x(x)) 记为 fibxx，

fibxx = lambda x:fib2(x(x))

那么对 left(lambda x:fib2(x(x))) 展开一次的结果是：

fibxx(fibxx)

再把作为函数的左侧 fibxx 展开，将参数 fibxx 代入，得到的是：

fib2(fibxx(fibxx))

继续把函数调用 fibxx 展开：

fib2(fib2(fibxx(fibxx)))

可以看到，这里 fib2 永远无法执行到，实际上它连函数的参数都计算不完，这种情况比前文讨论的 apply_self(apply_self) 更加抓狂，因为你额外有一个 fib2 马上要执行的预期，而终点似乎就在眼前了，这有点像古希腊思想家芝诺提到的悖论，当你要走到 100 米外终点线的时候，先要走到距离终点 50 米的地方， 然后距离 25 米、12.5 米，如此二分下去，终点就在眼前，但你就是到不了。而这里的情况看上去更糟糕，越执行下去反而有更多的 fib2 要被执行，不是无限接近终点，而是无限远离。

前一章通过在 x(x) 之前用 if else 结构阻挡了 x(x) 的执行，使得递归变得“有条件”，即可控，这是因为 if 语句如果成立，else 后的表达式是不会计算的，但给 x(x) 套上一个函数变成 fib2(x(x))，并不会阻止 x(x) 的执行，因为 python 中函数调用的规则是，先对函数参数进行计算，然后把计算结果代入到函数，所以给 1/0 表达式套上一个正常的函数并不会减轻 1/0 的异常，比如以下函数自称永远返回 1, 因为传入任何参数都是返回 1, 但传入 1/0 却抛出异常：

def always_return_1(x):
    return 1

always_return_1(1/0)

---------------------------------------------------------------------------
ZeroDivisionError                         Traceback (most recent call last)
Cell In[73], line 4
      1 def always_return_1(x):
      2     return 1
----> 4 always_return_1(1/0)

ZeroDivisionError: division by zero

这里的问题不在于 always_return_1 本身，而是其背后 python 解释器的运行规则，当调用 always_return_1 的时候，并不一定能真的执行到函数内部，有可能在参数求值上就陷入异常或者无限循环了。

所以，给一个异常的表达式套上 always_return_1 不能解决表达式异常的问题，但用 if else 却可以：

1 if 1==1 else 1/0

1

这就是为什么我们不能用函数去实现 if else 的原因：

def if_else(if_, else_):
    return 1 if if_ else else_

if_else(1==1, 1/0)

---------------------------------------------------------------------------
ZeroDivisionError                         Traceback (most recent call last)
Cell In[78], line 4
      1 def if_else(if_, else_):
      2     return 1 if if_ else else_
----> 4 if_else(1==1, 1/0)

ZeroDivisionError: division by zero

对于函数， if_, else_ 一定会被求值，然后传入到函数体内部，所以 if_else(1==1, 1/0) 它不能等价于 1 if 1==1 else 1/0

这也是用 if else 可以阻挡 x(x) 无限递归的原因。

既然如此，我们是否可以在 lambda x:fib2(x(x)) 中 x(x) 前面添加上 if else 呢？就像上一章从不可控到可控递归一样？

当然可以，我们可以遵循前一章的思路，先模仿 right2 把 fibxx 扩展为 fibxx2 （这里我们把 x.cnt 设置为 1 时停止，更容易展示）

fibxx2 = lambda x: fib2("stop" if x.cnt==1 else x(x))

它在 left(fibxx2) 得到 fibxx2(fibxx2), 把函数调用展开一次就是

fib2("stop" if x.cnt==1 else fibxx2(fibxx2))

此时由于已经调用了一次 fibxx2, x.cnt 已经是 1 了，于是执行 fib2("stop"), fib2 定义如下：

fib2 = lambda x: lambda n: n if n <= 2 else x(n-1) + x(n-2)

fib2("stop") 返回的是：

lambda n: n if n <= 2 else "stop"(n-1) + "stop"(n-2)

可以预期，如果输入参数小于等于 2 那么返回参数本身：

fibxx2 = cnt_decorator(fibxx2)
left(fibxx2)(2)

2

如果输入参数大于 2，执行 "stop"(n-1) 会报错（注意这里每次要重新装饰 fibxx2, 使得 cnt 初始值为 0）

fibxx2 = cnt_decorator(fibxx2)
left(fibxx2)(3)

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[101], line 2
      1 fibxx2 = cnt_decorator(fibxx2)
----> 2 left(fibxx2)(3)

Cell In[29], line 1, in <lambda>(n)
----> 1 fib2 = lambda x: lambda n: n if n <= 2 else x(n-1) + x(n-2)

TypeError: 'str' object is not callable

这确实可以防止无限递归，但不符合初衷，我们想要的是把 x(n-1) 形式变成 x(x)(n-1) 形式从而可以输入到 left 里获得递归函数，这里却用 if else 把 x(x) 结果按条件替换成了 "stop", 或者其他递归计算的终点（比如求 fibnacci 最终返回的就是一个整数），这是偷换概念了，我们希望有另一种避免闷头执行 x(x) 的方式，同时保持它的函数性质，最终期望的是能执行 x(x)(n-1) 这样的递归语句，朝着子问题更近一步。

X 实际和 left(right) 非常相似，它仅仅是在后者的基础上添加了一个可以输入的函数选项，并把函数应用到 right 中的 x(x) 上：

# left(right)
(lambda x:x(x))(lambda x:x(x))
# X 
lambda f:(lambda x:x(x))(lambda x:f(x(x)))

在 lambda 演算中，它并不会导致无限递归，这是因为 lambda 演算是数学家的发明，数学家们更多是在需要的时候去化简公式，而不是上来就直接化简，比如对于以下公式：

(lambda x: x+2321-1923)(1923-2321)

如果一上来就计算 1923-2321, 那计算出结果之后代入函数还要计算一遍 x+2321-1923, 但如果先观察式子， 发现可以代入之后从表达式上进行化简，那么就不需要先对 1923-2321 求值，而是直接代进去，最后得到 0 。

当然，lambda 演算对函数求值的规则没有智能到根据当前“是否方便”进行求值，它实际采用的是另一个极端，即函数应用时先把参数按语法形式下原封不动地代入，这类似 C 的宏替换，不过会带括号，以避免歧义，因为 lambda 演算是纯函数式，没有赋值语句导致的状态变化，所以这种替换不会有任何副作用，而如果是 C 语言，假设有以下函数

int double(x){
    return x+x;
}

调用 double(b++) 时，如果把 b++ （加上括号）代入函数，执行的就是 (b++)+(b++), 这会导致 b 自加两次，大概率不符合预期，这也是为什么 lambda 演算不引入赋值语句的原因，这可能导致意想不到的状态变化，让描述变得复杂。

对于 X(fib2)(n), 代入后展开表达式的前 3 步如下：

(lambda x:x(x))(lambda x:fib2(x(x)))(n) #1
(lambda x:fib2(x(x)))(lambda x:fib2(x(x)))(n) #2
fib2((lambda x:fib2(x(x)))((lambda x:fib2(x(x)))))(n) #3

接下来要执行的第四步就是 lambda 演算和 python 差别的体现，前文分析过 python 中这里会对 fib2 第一个参数继续求值从而导致无限循环，但 lambda 演算中，不会对第一个参数里的表达式求值化简（越化简越复杂），而是直接代入到 fib2 中，并且再代入 n （因为 fib2 需要两个参数），fib2 内的 if else 语句得以执行，如果 n 是终止状态，那么递归就结束了，如果不是，则第一个参数的表达式

(lambda x:fib2(x(x)))((lambda x:fib2(x(x)))))

会在递归分支中被当作函数应用到 n-1 或其他更小的参数上（fib2 里要执行 f(n-1), f(n-2)），这又回到第二行，这不过在更小的 n 上递归。

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

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 部分里包含了一个自指结构。
5. 为了追求简洁的美感，想把导致递归的自指结构全部放到 left 中去，丢弃其中的 x(x)(n-1) 结构，替换成普通的 x(n-1), 这导致直接的自指结构消失了，不过从“感觉上”，似乎把 x(x) 以参数形式传给 lambda x:... x(n-1), 再加上 lambda x: 头就能回到原本的 right, 但实际中我们又回到了 (lambda x:x(x))(lambda x:x(x)) 形式，只不过是给右侧 x(x) 套上了一个函数： (lambda x:x(x))(lambda x:f(x(x))), 重新回到了不可控的递归问题。
6. 上节还尝试把 if else 结构重新放进去拦截危险的 x(x), 但这偏离了初衷，我们希望 x(x) 不是被 if else 按条件引导成递归终点的 basecase （本文例子中，这一般是一个字符串或者整数）, 而是把它以某种静态的函数对象方式传递给 right 使得它能执行类似 x(x)(n-1) 的递归分支

为此，我们要在 if else 基础上寻求对 x(x) 拥有更强的控制力，核心是把 x(x) 这个动态递归过程变成静止的函数对象（想象黑客帝国的场景，只要控制力足够强，把时间慢下来，可以空手抓子弹）

为了减少回忆和回看负担，这里还列出目前为止讨论过的带有 x(x) 自指结构的函数：

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)

去掉 x(x) 结构的 fib2 函数以及让它重新回到递归时尝试失败的 fibxx 函数：

fib2 = lambda x: lambda n: n if n <= 2 else x(n-1) + x(n-2)
fibxx = lambda x:fib2(x(x))

从 right2 到 right4 是 x(x) 函数化的关键

right2 = lambda x: "stop" if x.cnt == 100 else x(x)
right4 = lambda x: lambda n: "stop" if n == 0 else x(x)(n-1)

不过之前我们是从功能设计角度构造出 right4 的，首先从函数“外部”引入了一个 x.cnt 属性，这在 python 中是可行的，但为了能够以传统函数的方式从参数传入额外的 cnt，把 right2 扩展为 right3:

right3 = lambda x, n: "stop" if n == 0 else x(x, n-1)

然后是为了保持 lambda 演算的单变量形式，于是 curry 化得到了 right4, 但如果直接观察从原始的 right 到 right4

right = lambda x: x(x)
right4 = lambda x: lambda n: "stop" if n == 0 else x(x)(n-1)

它在 right2 的 lambda x: 内部套了一个 lambda n: 函数，或者说，它把 x(x) 变成了 lambda n:x(x)(n-1), 这里删除了 if else ，因为我们已经理解了 if else 的作用，当前的注意力是理解加入额外 lambda 后带来的影响。

我们把删除 if else 后的 right4 记为：

xright4 = lambda x:lambda n: x(x)(n-1)

这种情况，由于没有 if 去对自指 x(x) 进行管控，尽管 left(xright4) 返回的是函数，但它是个执行后会陷入无限的递归函数，比如 left(xright4)(0) 展开 left 后是 xright4(xright4)(0), 然后是 xright4(xright4)(-1), xright4(xright4)(-2)… 它比 right 的优势在于，在递归过程中参数状态发生了变化，一旦有了 if else 去拦截某个状态，就可以停下来。

不过，由于 xright4 中 x(x) 预期是一个函数，我们可以直接返回这个对象，而不是 x(x)(n-1)

xright5 = lambda x:lambda n: x(x)
left(xright5)

<function __main__.<lambda>.<locals>.<lambda>(n)>

以上得到的是 lambda n:xright5(xright5), 继续输入任意参数后得到 xright5(xright5), 展开函数一次还是 lambda n:xright5(xright5):

left(xright5)(0)

<function __main__.<lambda>.<locals>.<lambda>(n)>

无论调用多少次，得到的都是 lambda n:xright5(xright5)

left(xright5)(0)(1)(2)(3)(4)

<function __main__.<lambda>.<locals>.<lambda>(n)>

但 python 的 lambda 每次是动态生成，所以尽管形式相同，但它们不是同一个对象：

print(left(xright5)(0)(1)(2)(3)(4) ==  left(xright5)(0))
print(left(xright5)(0)(1)(2)(3)(4) is  left(xright5)(0))

False
False

正如：

gen = lambda :lambda y:1
print(gen() == gen())
print(gen() is gen())

False
False

类似地，如果把 if else 添加回去，我们只是得到了一个按条件停止的单步递归型函数：

right5 = lambda x: lambda n: "stop" if n == 0 else x(x)
left(right5)

<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

可以看到，这种控制几乎已经到了极端，因为可以修改递归过程的状态，以决定递归是否结束，它的关键就来自于 x(x) 是函数而不是过程。

回顾纯粹的 x(x) 变成函数的例子：

right = lambda x:x(x)
xright4 = lambda x: lambda n: x(x)(n-1)
xright5 = lambda x: lambda n: x(x)

由于在 x(x) 前添加了 lambda n:, 它就变成函数了，同样的，由于我们把 x(x)(n-1) 变成 x(x), 原本会执行的函数调用也变成一个待调用的函数，用以下更简单例子来说明：

# 这是 apply 过程(动态)
print(1) 

# 这是 print 函数(静态)
print 

# 这是对 print(1) 函数应用的静态化,加了函数封装
lambda n: print(1) 

把 print(1) 变成 lambda n: print(1) 的操作被称为逆 beta 变换（添加额外的参数 n 是为了满足 lambda 演算里单变量的性质，n 只是一个占位符），这是因为对函数进行调用 (也称 apply 或函数应用) 在 lambda 演算中称为 beta 变换。

现在我们考虑以下函数：

xright6 = lambda x: lambda n: x(x)(n)

它处于 xright4 和 xright5 之间

xright4 = lambda x: lambda n: x(x)(n-1)
xright5 = lambda x: lambda n: x(x)

我们对 x(x) 进行了逆 beta 变换，但又把参数应用到 x(x) 上了，如果 x(x) 是普通函数，比如 print, 那么 lambda n:print(n) 实际和 print 完全等价：

print(2023)
(lambda x: print(x))(2023)

2023
2023

在 lambda 演算中， lambda n:print(n) 可以被化简为 print，这被称为 eta 归约（规则）。

但在 python 中，eta 规约成立吗？

这是一个微妙的问题，大部分情况下是成立的，但严格来说并不成立，因为如果成立，那么以下两个函数输入到 left 后就是等价的

right = lambda x: x(x)
xright6 = lambda x: lambda n: x(x)(n)

但我们知道 left(right) 就是 apply_self(apply_self), 它会立刻陷入无穷递归。而 left(xright6) 呢？由于 lambda n 的存在，它返回的是一个函数，这个函数再输入参数 n 才进入无限递归（和 xright4 一样）

left(xright6)

<function __main__.<lambda>.<locals>.<lambda>(n)>

left(right) 是在 right(right) 上无限循环， left(right6)(n) 是在 xright6(xright6)(n) 上无限循环。

也就是说，这种看似等价的语法装饰在这种情况下具有纯粹的函数化的能力，让 x(x) 变成函数，手动执行后照例陷入递归。

现在回到对 Y 初次尝试的结尾，我们有了

fibxx = lambda x:fib2(x(x))

left(fibxx) 和 left(right) 一样不可控，后者展开一次后是 right(right), 继续展开还是在 right(right) 无限递归, 前者展开一次后是 fibxx(fibxx) ， 再展开是 fib2(fibxx(fibxx)) ， 每展开一次则多出一个 fib2, 如 fib2(fib2(fibxx(fibxx))), 永远执行不到任何一个 fib2

然而如果把其中 x(x) 换成 “eta 等价”的对象

fibxx3 = lambda x:fib2(lambda z: x(x)(z))

left(fibxx3)(n) 得到 fibxx3(fibxx3)(n), 然后得到：

fib2(lambda z: fibxx3(fibxx3)(z))(n)

这里的关键区别在于 fib2 的第一个参数 lambda z: fibxx3(fibxx3)(z) 是一个函数，不会被求值，而如果是 fibxx, 那么 fibxx(fibxx) 求值就陷入无限递归了。

把 fib2 展开后是：

lambda x: lambda n: n if n <= 2 else (lambda z:fibxx3(fibxx3)(z))(n-1) + (lambda z:fibxx3(fibxx3)(z))(n-2)

<function __main__.<lambda>(x)>

其中 (lambda z:fibxx3(fibxx3)(z))(n-1) 真正等价于 fibxx3(fibxx3)(n-1) 了，这是更小规模的的递归调用，是梦寐以求的行为。

left(lambda x: fib2(lambda z: x(x)(z)))(10)

89

我们成功把 x(x) 以 lambda z:x(x)(z) 的方式打包了出来，把一个无限递归的危险对象安全地传给了 fib2, 并且让 fib2 跟随着 x(x) 一起递归：

我能想到最浪漫的事，就是带你一起递归到未知的尽头

– Y

由于 fib2 可以替换成任何递归形式的函数，因此可以抽取成函数的参数：

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

这就是 python 中的 Y 算子了。

Y(fib2)(10)

89

可以把其中 z 换成更通用的 python 中的可变参数（因为有些递归输入的是多个参数），那么得到更通用的 Y:

Y = lambda f: (lambda x:x(x))(lambda x: f(lambda *args: x(x)(*args)))
Y(fib2)(12)

233

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

另外，由于真正的递归是发生在执行 left(right) 之后的 right(right), 所以可以把 left 替换成 right, 它也是 Y 算子，虽然更长，但形式上是两个相同的表达式的重叠：

Y = lambda f: (lambda x: f(lambda *args: x(x)(*args)))(lambda x: f(lambda *args: x(x)(*args)))
Y(fib2)(10)

89

写成 lisp 形式

(define Y 
  (lambda (f) 
    ((lambda (x) (f (lambda (z) ((x x) z)))) 
     (lambda (x) (f (lambda (z) ((x x) z))))))) 

写成 lambda 演算： \[ \lambda f.(\lambda x. (f \lambda z. (x x)z)) (\lambda x. (f \lambda z. (x x)z)) \]