在 JavaScript 中用匿名函数（箭头函数）写出递归的方法

Question

今天看 Mozilla 出品的 ES6 In Depth ,看到 Arrow functions(中文翻译)，其中一段让人讶异。

Using arrows to pierce the dark heart of computer science

「使用箭头来刺穿计算机的黑暗心脏」

里面提到λ (lambda)表达式、阿隆佐·邱奇（Alonzo Church）、阿兰·图灵（Alan Turing），这些耳熟能详的名词原来与我们写 JavaScript 的人这么近，这激发了我极大的探索兴趣。

最后搜索到刘未鹏2006年的一篇文章《康托尔、哥德尔、图灵——永恒的金色对角线(rev#2)》，奇妙的从 ES2015 延伸到了计算机的起源以及现代数学史的开端。

我看到了它，却不敢相信它。——康托尔

计算机是数学家一次失败思考的产物。——无名氏

原来我们轻易写下的每一个匿名函数，里面都蕴涵简单而又玄妙的数学原理。

原来用匿名函数实现的递归，动用了如此深刻的数学法则。

希望每个前端工程师都能认真阅读刘未鹏的文章，理解 Y Combinator 的 JavaScript 实现，对这门正在越变越好的语言抱以更多的敬畏之情，写起 ES2015 来或许有更好的编程体验。

注：本文部分代码将用 ES2015 编写，要跑起来可能得先用Babel编译为 ES5。

正文

我们用递归的方式实现阶乘函数，并且从朴素思路出发，最后一步步抵达Y Combinator。

首先，用最简单的命名函数递归方式，如下：

function factorial(n) {
    return n < 2 ? 1 : n * factorial(n - 1)
}

factorial(3) // => 6

第二种方式，用变量缓存匿名函数的值：

let fact = n => n < 2 ? 1 : n * fact(n - 1)

fact(4) // => 24

看，我们用匿名函数实现了递归，全剧终......

不，那只是 JS 引擎给我们的语法糖。实际上，所谓的「用 lambda 表达式写出递归」，不能在 lambda 定义完成之前直接引用自身。我们做如下假设：

let fact = n => n < 2 ? 1 : n * fact(n - 1) //抛出错误： lambda 表达式引用错误

在这个基础上，继续探索我们的话题。

如果 lambda 表达式不能直接在函数体内显示引用自身，那么我们就得隐式地调用自身；因为我们不是用循环来模拟递归，我们就是要让 lambda 表达式反复执行一段相同代码。

其中一个策略是，将 lambda 表达式作为参数之一传入其自身。（函数也是值）

//并不直接引用自身，引用 self 函数，调用时将自己传入即可
let fact = (self, n) => n < 2 ? 1 : n * self(self, n - 1)

//调用时，将自身作为第一个参数传入
fact(fact, 5) // => 120

OK,我们现在的确实现了具有递归效果的 lambda 表达式，但是，太难看了。没有人希望自己的阶乘函数有多余的参数，我们的目标是，fact(n)。

为了达到参数纯净化目的，我们可以包裹一层工厂函数，封装肮脏的冗余传参行为。

//并不直接引用自身，引用 self 函数，调用时将自己传入即可
let fact = (self, n) => n < 2 ? 1 : n * self(self, n - 1)

//柯里化工厂函数，砍掉第一个参数
let factory = f => n => f(f, n)

//改造 fact
fact = factory(fact)

//参数纯净化
fact(6) // => 720

虽然现在我们达到了在调用时参数纯净化的目标，但仍有些不美。定义 fact 时，我们还在 self(self, n - 1)， 方式不够直观，我们期望能用下面的方式代替。

//定义时就工厂化，生产出阶乘函数
let factory = self => n => n < 2 ? 1 : n * self(n - 1)

在函数被定义之后，我们才拿到其引用；也就是说，不可能在生产/创建一个函数时，把它自己传参进去。也就是说，对于上面的工厂函数 factory 而言，self === factory(self)永远不可能为真。不过，没关系。我们有软件工程里的黄金定律：

任何问题都可以通过增加一个间接层来解决。

既然无法让一个阶乘函数反复调用自身，那就让 factory 在需要时反复生产出虽然不是同一个，但效果等价的、新的阶乘函数。我们设想有以下特征的 Y 函数：

//定义时就工厂化，生产出阶乘函数
let factory = self => n => n < 2 ? 1 : n * self(n - 1)

//暂时不管 Y 函数的内部实现，假定它能够返回正确的阶乘函数。
let fact = Y(factory)

fact(6) // => 720

在知道Y函数的功能与行为后，我们再根据已知条件，把它构造出来。

首先，Y 函数一定返回阶乘函数，那么它的可能形式如下，

let Y = factory => {
    //Y 返回一个函数，其参数为 n，返回值为 n 的阶乘
    return n => { //求阶乘 }
}

其次，Y 一定调用了 factory 函数两次以上

let Y = factory => {
    let magic // 魔术函数，可以从 factory 中取出阶乘函数
    return n => factory(magic(factory))(n)
}

magic 函数从 factory 取出新的阶乘函数，作为参数又传入 factory，这样创建出来的阶乘函数，里面的 self 就是另一个阶乘函数。

到这里，我们只需要探究 magic 应该是什么代码形式。

let Y = factory => {
    //从 magic 的调用方式来看，它接受 factory 作为参数，返回一个新的阶乘函数
    let magic = factory => n => factory(magic(factory))(n)
    return n => factory(magic(factory))(n)
}

可惜，上面复用 magic 函数，也只是语法糖，我们不能在 magic 定义完成前显式引用它。

诶？

那么就再增加中间层，隐式引用呗。说做就做。

let Y = factory => {
    //就像之前做过的那样，把自己作为参数传入自己
    let magic = (self, factory) => n => factory(self(self, factory))(n)
    return n => factory(magic(magic, factory))(n)
}

//定义时就工厂化，生产出阶乘函数
let factory = self => n => n < 2 ? 1 : n * self(n - 1)

//测试我们构造出来的 Y 函数
let fact = Y(factory)

fact(7) // => 5040

惊！！，我们竟然成功了。虽然我们不知道 magic 魔术函数为什么是那样，但是，我们把它构造了出来。

同时，我们注意到，magic 的 factory 参数，好像没有存在的必要了，因为作用域内只存在唯一一个 factory。

let Y = factory => {
    //砍掉多余的 factory 参数
    let magic = self => n => factory(self(self))(n)
    return n => factory(magic(magic))(n)
}

//定义时就工厂化，生产出阶乘函数
let factory = self => n => n < 2 ? 1 : n * self(n - 1)

//测试我们构造出来的 Y 函数
let fact = Y(factory)


console.log(fact(8)) // => 40320

神奇。magic 魔术函数果然很魔术，在外部 magic(magic) 自己调用自己， 在内部self(self)，就实现了递归？

同时，我们又注意到一点，n => factory(magic(magic))(n)的形式跟n => factory(self(self))(n) 似乎一模一样，仅仅是 magic 跟 self 名字不同。

嗯？前者不就是把 magic 自身作为参数传递进自身的返回函数吗？

magic(magic) 是把自己传参进去，那么self === magic。

原来 self(self) 自调用的函数，就是magic自身。

于是，我们得到：

let Y = factory => {
    //砍掉多余的 factory 参数
    let magic = self => n => factory(self(self))(n)
    //返回阶乘函数
    return magic(magic)
}

//定义时就工厂化，生产出阶乘函数
let factory = self => n => n < 2 ? 1 : n * self(n - 1)

//测试我们构造出来的 Y 函数
let fact = Y(factory)

console.log(fact(9)) // => 362880

看到最终的产物，让人惊呆了。这是什么黑魔法？

仔细一看，原来它就是 lambda 演算的 JavaScript 实现

// λ演算的写法
fix = λf.(λx.f(λv.x(x)(v)))(λx.f(λv.x(x)(v)))

// ES6的写法
const fix = f => (x => f(v => x(x)(v)))
               (x => f(v => x(x)(v)));

它不仅适用于阶乘函数的递归处理，任意递归工厂函数经过Y函数后，都能得到真正的递归函数。

let count = Y(self => x => {
    console.log(x++);
    x < 100 && self(x)
})

count(0) // 输出0 ~ 99

尾声

在这篇文章中，我们有意识地用到的特性只有一个：

函数也是值，可以作为参数传递

我们利用它，让一个函数自己调用自己，然后不断美化美化、简化简化，竟然就构造出了Y Combinator。

然而：

• 从函数也是值，可传参中，反推出Y Combinator，不代表你有多厉害
• 只是站在巨人的肩膀上
• 背下函数也是值，可传参的定律，却不知道背后的原理就是λ演算
• 就像还没学到微积分的高中生自己开创了微积分初步
• 自比牛顿太幼稚，微积分原理与应用衍化成耳熟能详的说辞围绕着你
• 没有这些弱启发，买菜还在数指头
• 数学多美妙

Answer 1

其实这里由于λ演算中，对于函数是延迟求值的，而对于 JS 这种 call by value 的语言来说，是必须先求值再作为实参传入函数的。所以在 JS 中利用 v => f(x(x))(v) 这种方式来进行对 x 延迟求值，而在λ演算中，直接 f(v=>x(x)(v))，这里的 x 表达式并不会立即求值。注意在 JS 中如果是λ中的这种写法会引起 stack crash。

Answer 2

好文，找了很多篇讲 YC 的，这篇最好懂。多谢博主。
最后有个问题，我把

let Y = factory => {
    let magic = self => n => factory(self(self))(n)
    return magic(magic)
}

手动转化为 es6 箭头函数，结果如下：

let Y = f =>
(x => v => f(x(x))(v))
(x => v => f(x(x))(v))

这和 λ演算 的写法不太一样啊，λ演算是

f =>
(x => f(v => x(x)(v)))
(x => f(v => x(x)(v)))

问题就出在 v => f(x(x))(v)与f(v => x(x)(v))是否等价，感觉大部分情况都不等价，似乎只有某一类特定的f才能满足这个……“结合律”？

Answer 3

//这样Y就变得非常简单了
let Y = f => f(f)

//但这样 factory 就变得复杂了
let factory = self => n => n < 2 ? 1 : n * self(self)(n-1)

我觉得这里的问题好像不是谁简单谁复杂，而是这样的 Y 似乎不再具备 Y 组合子的特性了？就这篇文章的目的来说，这应该不是一个可接受的状况。

Answer 4

你的思路非常不错。

//这个 self 指的是阶乘函数自身，只是一个语义提示
let factory = self => n => n < 2 ? 1 : n * self(n - 1)

//也可以换成这样
let factory = fact=> n => n < 2 ? 1 : n * fact(n - 1) //这样做，很难反映出 fact 就是 factory 生产出来的。


//这样Y就变得非常简单了
let Y = f => f(f)

//但这样 factory 就变得复杂了
let factory = self => n => n < 2 ? 1 : n * self(self)(n-1)

至于性能测试，这篇文章的内容，不是为了投入实际生产，不是一个实用技巧。

更像是一个科普资讯，展现 js 里的匿名函数跟函数式语言里的 lambda 表达式的关系，以及跟计算机里的 lambda 跟图灵机，跟数学里的 lambda 演算，跟哥德尔不完备定理，跟康托尔的集合论之间存在的千丝万缕的联系。

这是 JavaScript 所处的大背景，这篇文章是为了让更多人能在在这么个背景下，重新审视这门语言。

Answer 5

//定义时就工厂化，生产出阶乘函数
let factory = self => n => n < 2 ? 1 : n * self(n - 1)

我觉得这里不太对，这里说的factory是一个生成lambd函数的工厂，而真正需要形成递归的是 其生成的lambd函数，但是 这里的self指的是factory而不是 其生成的lambda函数，及这里的self需要替换成 需要递归的lambda函数——>最简单的方式：

let factory = self => n => n<2 ? 1 : n*self(self)(n-1)

//这样Y就变得非常简单了，
let Y = f => f(f)

---

还有，我有一样东西想不明白，为什么要执着于用lambda函数做递归？
我简单用ES5测了一下，三种方式的时间消耗量：

var f1 = function (s) {
  return function (n) {
    return n<2 ? 1: n*s(s)(n-1)
  }
}

//your function
var f2 = function (s) {
  return function (n) {
    return n<2 ? 1: n*s(n-1)
  }
}

var simpleY = function (f) {
  return f(f);
}

//your Y
var Y = function (factory) {
  var magic = function (self) {
    return function (n) {
      return factory(self(self))(n)
    }
  }
  return magic(magic)
}

var e1 = simpleY(f1)
var e2 = Y(f2)

function normal(n){
  return n < 2 ? 1: n*normal(n-1)
}


function player(f, n, loop){

  for(var i=0;i< loop;i++){
    f(n)
  }
}

var start = new Date()
player(normal, 1000, 10000)
var end1 = new Date()
player(e1, 1000, 10000)
var end2 = new Date()
player(e2, 1000, 10000)
var end3 = new Date()
console.log(end1 - start)
console.log(end2 - end1)
console.log(end3 - end2)

//result：
//136
//558
//1382 
//我的电脑低性能，求原谅