Lambda演算之Y-Combinator的推导

上一节中，我们讲到了如何使用λ演算来描述自然数，可以看出λ演算的表现力确实非常强大，然而遗憾的是，由于lambda演算中使用的都是匿名函数，所以它无法很直观地表述递归。 如果缺少了递归，λ演算的能力无疑会大打折扣。

所有基于λ演算的语言中，其实都是支持对过程进行命名的，那为什么这里我们还需要探讨匿名函数的递归呢？

为了保持纯洁性，我们希望仅仅通过λ演算的规则本身来解决递归的问题。

部分语言对过程的命名必须等到该过程定义完成后才可以进行，这个时候我们必须找到一种方式使其能够很容易地获得递归的能力。

传统定义方式，不过这个方式不符合我们的需求，因为它使用到了函数自身fact。

几乎所有的问题解决过程都可以通过分层来解决，既然它不允许我们直接使用fact，那我们是不是可以直接把fact作为函数传入呢？

为了后续处理方便，我们先对该函数进行currying。

((self self) (dec n)) 是不是有点丑陋，我们知道λ演算是数学家们搞出来的，他们对构造形式是有很严重的洁癖的。既然我们就是函数本身，为什么还需要(self, self)这样多此一举呢。 如果我们的定义能变成下面这样就比较完美了。

或者换成二元形式

这样也许更符合数学家们的口味，但是该函数是无法被直接执行的，这个使我们暂时假定的factorial的理想函数形式。为了构造这个理想函数形式，我们不妨把它变成(f (dec n))，下面我们试着把(self self)拎出来，用作参数f传入。

我们来看fac-gen的形式，其等价于

是不是和我们理想中的fact形式已经很接近了，当然其中有一个自由变量n，没关系，我们给他加个帽子。

这次的fac-gen和我们的理想函数形式非常像了，换成二元就是

这正是我们找寻的理想形式。

让我们把fac-gen抽出来，作为一个单独的函数，它刚好就是我们要构造的factorial函数的理想形式，并给出fact7函数的定义。

其实这个时候，fact7和factorial的计算过程已经没有什么关系了，换而言之，其实它可以更通用一些。

fact8其实和factorial的计算过程没有任何关系，所以我们不妨给它换个名字

事实确是如此，该函数有一种神奇的能力，它不仅使可以计算factorial，它事实上可以计算所有形如factorial理想形式的函数递归。

我们看下我们的调用，都是形如：(((y *-gen) (y *-gen)) n)的形式，还是相当丑陋的，我们不如精简下，简化其调用过程。

去除letfn，把self使用f替换。

说了这么多，这个东西和y combinator又有什么关系？其实，我们最终得出的y函数，其实就是我们所要苦苦找寻的y combinator函数，它具有性质y(f) = f(y(f)) = f(f(y(f)))。

函数f的不动点是一个值x使得f(x) = x。例如，0和1是函数f(x) = x**2的不动点，因为0**2 = 0而1**2 = 1。鉴于一阶函数（在简单值比如整数上的函数）的不动点 是个一阶值，高阶函数f的不动点是另一个函数g使得f(g) = g。那么，不动点算子是任何函数fix使得对于任何函数f都有 f(fix(f)) = fix(f).

在无类型lambda演算中众所周知的（可能是最简单的）不动点组合子叫做y组合子。它是haskell b. curry发现的，定义为y = λf.(λx.f (x x)) (λx.f (x x))用一个例子函数g来展开它，我们可以看到上面这个函数是怎么成为一个不动点组合子的：

根据定义得出的函数如下，但是它毫无用武之地，当把参数应用到它之上时，它将会进入无穷递归。

当该函数应用到f上时，当有

由于此处总是eager load，故此函数会进入无穷递归。

有没有办法让(f (x x))不展开呢? 可以，只需要加个lambda就可以使其变成lazy load。

由于新增的lambda没有参数，故在clojure中我们调用的函数也不能有参数，但是已经可以实现递归了，下面的例子会进入无穷递归。

让我们给他加入参数，以便做支持更多的调用场景。

上面的代码实现有明显重复的地方，根据dry原则，我们稍稍对源代码进行下改造。

我们根据y combinator也同时得出了y函数的定义，和我们之前根据factorial推演得出的结果一模一样。

让我们来证明下，我们的y确实是一个通用的不动点组合子。

<a href="http://jameszhan.github.io/2014/09/10/lambda-church-number.html">lambda演算之自然数</a>

<a href="https://raw.githubusercontent.com/jameszhan/rhea/master/codes/clojure/calculation/deriving_y_combinator.clj">y-combinator演算示例代码</a>