Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

在 JavaScript 中用匿名函数(箭头函数)写出递归的方法 #7

Open
Lucifier129 opened this issue Jul 28, 2015 · 11 comments

Comments

@Lucifier129
Copy link
Owner

前言

今天看 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 CombinatorJavaScript 实现,对这门正在越变越好的语言抱以更多的敬畏之情,写起 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 魔术函数为什么是那样,但是,我们把它构造了出来。

同时,我们注意到,magicfactory 参数,好像没有存在的必要了,因为作用域内只存在唯一一个 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) 似乎一模一样,仅仅是 magicself 名字不同。

嗯?前者不就是把 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,不代表你有多厉害
  • 只是站在巨人的肩膀上
  • 背下函数也是值,可传参的定律,却不知道背后的原理就是λ演算
  • 就像还没学到微积分的高中生自己开创了微积分初步
  • 自比牛顿太幼稚,微积分原理与应用衍化成耳熟能详的说辞围绕着你
  • 没有这些弱启发,买菜还在数指头
  • 数学多美妙
@antife-yinyue
Copy link

👍

@JokerQyou
Copy link

,这样创建出来的捷成函数

应为

,这样创建出来的阶乘函数

@Lucifier129
Copy link
Owner Author

@JokerQyou 感谢指出。已改正。

@MephistoMMM
Copy link

//定义时就工厂化,生产出阶乘函数
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 
//我的电脑低性能,求原谅

实在不明,求解答

@Lucifier129
Copy link
Owner Author

@MephistoMMM 你的思路非常不错。

//这个 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 所处的大背景,这篇文章是为了让更多人能在在这么个背景下,重新审视这门语言。

@myst729
Copy link

myst729 commented Jul 30, 2015

@Lucifier129

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

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

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

@MephistoMMM
Copy link

@myst729

发现了,还真是这样~~
谢谢提醒

@Lucifier129
Copy link
Owner Author

@myst729 对的~文章的目的不是简化Y,是从朴素理念出发,最后构造出Y Combinator

@iwestlin
Copy link

iwestlin commented Mar 4, 2017

好文,找了很多篇讲 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才能满足这个……“结合律”?

@monkingxue
Copy link

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

@kkkelicheng
Copy link

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 表达式引用错误

请问,“那只是 JS 引擎给我们的语法糖”。具体是什么语法糖。我也好奇 fact 为什么能在定义完成之前直接引用自身。有没有资料或者参考

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

8 participants