这篇文章是对前一篇An Online Lambda Interpreter的续写，搞清楚 Y Combinator 这个概念的来龙去脉。当然这两篇文章里的 lambda 演算语法定义实际上并不是标准的定义，具体的标准定义与实现我在这个目录做了单独实现。
Y combinator
问题的提出
如果让你用自己最熟练的编程语言写一个fibonacci(暂不考虑效率问题)，这一定不是问题，下面是一个Python的例子：
def fib(n):
if n < 2:
return n
else:
return fib(n-1)+fib(n-2)
我们现在考虑把它翻译成ELambda的语法：
\n.
(((cond ((less n) 2))
\_.
n
)
\_.
((add
(fib ((sub n) 1)))
(fib ((sub n) 2)))
)
当我们在考虑一个问题，如果不用关注其具体细节，可以把它们抽象一下，这样可以在一定程度上减轻思维负担。比如关于上面的整个函数体，本质上就是一个过程中包含了(fib x)这种形式的调用，因此我们可以把整个函数简记为：
\n.<(fib x)>
现在问题一下就清晰起来了：fib是啥？在我们的理解中它应该就是这个函数自身，但是lambda演算中并没有绑定函数名这种说法。没关系我们可以通过传参的方式来绑定，这是lambda演算的一个常见技巧：
(
\fib.\n.<(fib x)>
\fib.\n.<(fib x)>
)
你看之前不是说fib没有定义不能绑定自身吗，现在我把自己当做参数传给自己，这不就实现了绑定？问题好像得到解决了，不过等等，好像有点儿问题。\fib.\n.<(fib x)>这已经是一个俩参数的函数了，因此函数体里<(fib x)>这种调用方式很显然不合法。这个问题不大，想必你很快就找出了解决方案：
(
\fib.\n.<((fib fib) x)>
\fib.\n.<((fib fib) x)>
)
OK，问题解决。但是，作为强迫症的你会发现，这样一来fib根本就不是真正的递归函数啊，相反(fib fib)才是。
面对这个问题，有有两派分别采取了不同的方案，最终都殊途同归，形成了完美的递归方案。
自顶向下
回过头来看前一个方案：
(
\fib.\n.<(fib x)>
\fib.\n.<(fib x)>
)
我们是想把\fib.\n.<(fib x)>传给\fib.\n.<(fib x)>，天真地以为这样可以形成递归，怎奈所托非人，最后不得不委曲求全。那么我们换一种思维，如果一开始传给\fib.\n.<(fib x)>的如果不是\fib.\n.<(fib x)>，而是一个真正的fibonacci函数(driver_fibonacci)呢？
(
\fib.\n.<(fib x)>
driver_fibonacci
)
什么意思？我们把一个driver_fibonacci传给\fib.\n.<(fib x)>来构成driver_fibonacci，也就是：
driver_fibonacci = (
\fib.\n.<(fib x)>
driver_fibonacci
)
这不是有病吗，我们要寻找的就是driver_fibonacci，我要知道它是啥才能传进去。如果我都已经知道了它是啥，问题不早就解决了吗。不不不，我不是指已经找到，而是说如果有这么一个driver_fibonacci的话，它应该满足这样一个等式：
fixed_point = (g fixed_point)
仔细观察这个形式，我们梦寐以求的driver_fibonacci原来不过是\fib.\n.<(fib x)>的一个不动点而已。
那么不动点怎么求，这里就是大名鼎鼎的Y combinator了：
Y = \f.(\s.(f (s s)) \s.(f (s s)))
这里做个简要证明，很多地方都有：
(Y g)
= (\f.(\s.(f (s s)) \s.(f (s s))) g)
= (\s.(g (s s)) \s.(g (s s)))
= (g (\s.(g (s s)) \s.(g (s s))))
= (g (Y g))
你会发现原来(Y g)正好就构成了g的一个不动点！
因此我们通常看到的带有名称的支持递归的函数定义：
def fib: \x.<(fib x)>
从lambda演算的角度来看，他和：
(Y \fib.\x.<(fib x)>)
没有本质上的区别，一个完美的递归函数就这么构成了。
当然现在的你心里可能更多地会想：fuck，这 Y 怎么来的！
自底向上
好好好，接下来我就要讲，其实你也可以发现Y combinator。还记得我们之前那个“你根本不是司机”的fibonacci函数吗？
(
\fib.\n.<((fib fib) x)>
\fib.\n.<((fib fib) x)>
)
由于这里面的fib根本不是真fib，我们决定给它随便改个名字：
(
\s.\n.<((s s) x)>
\s.\n.<((s s) x)>
)
我们首先要解决的是(s s)，这一坨直接决定了它是不是老司机函数，用fib替换它得到：
(
\s.(\fib.\n.<(fib x)> (s s))
\s.(\fib.\n.<(fib x)> (s s))
)
好现在我们发现这里面有一个很nice的结构\fib.\n.<(fib x)>，也考虑把它提取出来用f替换：
(
\f.(\s.(f (s s)) \s.(f (s s)))
\fib.\n.<(fib x)>
)
看到没，只需要两步，Y combinator就已经出来了，可见它并不是一个什么神秘的不可捉摸的东西。
写在最后
最后有一点需要注意的是，在call-by-value的调用过程中，上面这个Y combinator会造成死循环：
(
\f.(\s.(f (s s)) \s.(f (s s)))
\fib.\n.<(fib x)>
)
=
(
\s.(\fib.\n.<(fib x)> (s s))
\s.(\fib.\n.<(fib x)> (s s))
)
=
(
\fib.\n.<(fib x)>
(
\s.(\fib.\n.<(fib x)> (s s))
\s.(\fib.\n.<(fib x)> (s s))
)
)
=
(
\fib.\n.<(fib x)>
(
\fib.\n.<(fib x)>
(
\s.(\fib.\n.<(fib x)> (s s))
\s.(\fib.\n.<(fib x)> (s s))
)
)
)
(
\fib.\n.<(fib x)>
(
\fib.\n.<(fib x)>
......
(
\s.(\fib.\n.<(fib x)> (s s))
\s.(\fib.\n.<(fib x)> (s s))
)
)
)
这个问题在call-by-name的调用过程中是不会出现的，要解决它你需要对Y combinator中的(s s)做一次eta-expansion。
最后的最后
你看，括号完全不是问题嘛！！！