不动点组合子，Y-Combinator

在程序设计中，一个很早就有的概念就是递归，同时也是最早接触的编程的meme之一，常见的一个递归程序就是阶乘了，让我们看一段代码：

fact 0 = 1
fact n = n * fact (n - 1)

这段代码使用了递归，在n > 0 时递归地调用fact(n-1)来计算，这对于我们是稀松平常的事，递归是具名的，在我们定义完函数之前就已经可以调用了，但是我们往往不想给函数取名，事实上，我们在更多情况下使用的函数只被使用一次，况且也没有ZUN一样的取名姿势水平，在这个时候，我们倾向于使用匿名函数，这个时候要怎么实现递归呢？

JS: 我有一言，请诸位静听

const f = function fact(n){
    return n <= 0 ? 1 : n * fact(n - 1);
}

虽然，fact在函数外面是没有用的，但是，这个简直是耍赖，他还是取了一个名字。

这个问题要回到λ-演算上，其定义是（摘自维基百科）：

λ演算（英语：lambda calculus，λ-calculus）是一套从数学逻辑中发展，以变量绑定和替换的规则，来研究函数如何抽象化定义、函数如何被应用以及递归的形式系统。它由数学家阿隆佐·邱奇在20世纪30年代首次发表。Lambda演算作为一种广泛用途的计算模型，可以清晰地定义什么是一个可计算函数，而任何可计算函数都能以这种形式表达和求值，它能模拟单一磁带图灵机的计算过程；尽管如此，Lambda演算强调的是变换规则的运用，而非实现它们的具体机器。

等等！这有点像定义匿名函数啊，不同的是，λ演算只允许函数接受单个参数，因此就有柯里化（currying），将一个多参函数转换成单参数的函数。

f(x, y)
curry(f) = x => y => f(x, y)
λx.λy.f(x y)

为了达成匿名函数的递归，一个最朴素的方法就是把它本身当作一个参数传递进去。 recur = λf.λx.f(f)(x) recur，现在来改造一下我们的阶乘函数：

const fact = (self => n => n  <= 0 ? 1 : n * self(self)(n - 1))
fact(fact)(5) == 120

形如 f(f) 的东西被用了两遍，而且我还必须在内部用self(self)十分不优雅，如果我想让我的函数变成这样：

而这个fact1里面的self正是上面fact里面的self(self)

那我们就可以：

const fact1 = self => n => n  <= 0 ? 1 : n * self(n - 1)
const f1 = self => fact1(self(self))
// f1(f1)(5) should be 120
const Y = f => {
    let w = self => f(self(self))
    return w(w)
}

当然，以上代码还无法运行，由于js的勤奋求值策略，以上代码会栈溢出。但是我们可以发现本质：

let Y = λf. 
    let w = λ self. f(self(self))
    w(w)

去除名称绑定，将 w(w) 代入，发现Y的定义：

$$ \lambda{f}.(\lambda{w}.w\ w)(\lambda{x}.f(x\ x)) $$

这就是大名鼎鼎的Y组合子，在无类型lambda演算中众所周知的（可能是最简单的）不动点组合子叫做Y组合子。它是Haskell B. Curry发现的，它有一个更加广为人知的形式：

$$ \lambda{f}.(\lambda{x}.f(x\ x))(\lambda{x}.f(x\ x)) $$

这个组合子具有以下性质：

$$ Y f = f(Y f) $$

因此，如果你用的是支持命名绑定的语言，实现Y组合子就简单很多。

def Y[T](fn: (T => T) => T => T): T => T = fn(Y(fn))

这个时候，我们发现，改造后的函数会具有这样的类型：

f :: T => T # original function
f' :: (T => T) => T => T
Y :: ((T => T) => T => T) => T => T

不幸的是，Scala的求值策略也是勤奋求值，同样会遇到栈溢出的问题。

为了解决这个问题，我们要用到η-变换，简单地说，就是

$$ f \to \lambda{x}.f(x) $$

这样推迟了f的求值时机，只有在这个函数被用到的时候才被求值，考虑到Y本身的定义展开就是一个无限的函数，这样做就避免了栈溢出。

def Y[T](fn: (T => T) => T => T): T => T = fn(Y(fn))(_)

在Scala中，f(_)就是x => f(x)的语法糖。

在其他地方，就要稍稍麻烦一点。

其实核心就是推迟f(f)的求值时机，像一个生成自己的生成器一样，惰性求值。

const Y = fn => (f => f(f))(f => fn(s => f(f)(s)))

Y = lambda fn: (lambda u: u(u))(lambda f: fn(lambda s: f(f)(s)))

所以说，取名字是多么重要，不取名字发生了多少麻烦事，但是，这个组合子的发现证明了lambda 演算是图灵完备的，也具有重大意义。