V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
palmers
V2EX  ›  Node.js

这段 javascript 代码没有看明白,请明白的人给我讲解下,非常感谢!

  •  
  •   palmers · 2016-06-08 10:45:08 +08:00 · 5283 次点击
    这是一个创建于 3077 天前的主题,其中的信息可能已经有所发展或是发生改变。

    代码如下:

    //Here's the standard naive factorial:
    
    function fact(n) {
      if (n == 0)
        return 1 ;
      else
        return n * fact(n-1) ;
    }
    //上面这段是没有问题的,下面的看不懂,请大家讲解下,非常感谢!
    
    //Here it is in CPS:
    
    function fact(n,ret) {
      if (n == 0)
        ret(1) ;
      else
        fact(n-1, function (t0) {
         ret(n * t0) }) ;
    }
    

    原文在这里http://matt.might.net/articles/by-example-continuation-passing-style/

    30 条回复    2016-06-12 11:32:12 +08:00
    zztao
        1
    zztao  
       2016-06-08 10:57:57 +08:00 via Android
    这是把函数当参数传入,好像是现在流行的函数式编程
    wuyuchenshishabi
        2
    wuyuchenshishabi  
       2016-06-08 11:03:55 +08:00
    @zztao 只这样没错。,你是黄子韬?
    zztao
        3
    zztao  
       2016-06-08 11:07:21 +08:00 via Android
    原文后面给的那个直接传入一个匿名函数就比较直观看懂,这一个 ret 是一个函数
    malaohu
        4
    malaohu  
       2016-06-08 11:50:56 +08:00
    递归调用。
    FrankFang128
        5
    FrankFang128  
       2016-06-08 12:06:40 +08:00 via Android
    尾递归?
    azh7138m
        6
    azh7138m  
       2016-06-08 12:13:02 +08:00
    > 如果算法本身是非尾递归的,那么, CPS 变换可以将算法改写成尾调用形式,从而可以进行尾调用优化。
    bramblex
        7
    bramblex  
       2016-06-08 12:18:50 +08:00
    首先,我先这篇文章前面东西都懂了,到这个 fact 这里卡住了。

    fact (n, ret) 这个函数,里面的 fact(n-1, function (t0) {ret(n * t0) }) 这段代码的作用是递归构建 continuation 而已。

    楼上的一众基础真差,包括某所谓的 “阿里前端”
    bramblex
        8
    bramblex  
       2016-06-08 12:21:10 +08:00
    @azh7138m

    哎 /w\ 这个是不能尾递归的。因为她的函数栈是没有办法优化掉的。我写了一篇专门讲尾递归的文章~

    在这里~ http://lovearia.me/article/show/9
    loading
        9
    loading  
       2016-06-08 12:30:22 +08:00 via Android
    博大精深
    @bramblex
    bramblex
        10
    bramblex  
       2016-06-08 12:31:54 +08:00 via Android
    @loading 我没说明白…首先,我假设楼主前面的都懂了…卡在 fact 上面了…

    输入法的锅我不背
    chiu
        11
    chiu  
       2016-06-08 12:33:22 +08:00
    首先,我只是 JS 新手,仅从新手角度看这段代码。
    LZ 理解第一段,说明 LZ 理解递归是怎么一回事。
    然后下面的所谓 CPS 代码,用原文代码下面的例子来说:
    fact()的第一个参数 n 传入 5 ,第二个 ret 传入匿名函数 function(n) {console.log(n)};
    第一躺走 n==5 ,走 else , n 变成 n-1 ,即 4 , ret 变成 function(t0) {console.loh(n * t0)};
    在这第一躺中, ret()传入 n*t0 ,并直接通过 console 输出。但这里我们并不知道 t0 是多少,所以需要递归调用 fact()进入到下一趟里,我们就能看到第一躺里的 t0 其实就是第二趟最后传入 ret()的参数((n-1)*t0)。这时第二趟的 t0 又不知道是多少,所以又进入下一趟,直到递归调用 fact()传入的 n==0 , ret()传入 1 ,这个 1 就是上一躺需要的 t0 ,所以最后第一躺 ret()输入的参数是 5*4*3*2*1*1 。

    然后,我不是很理解这种 CPS 写法的意义是什么?望指导。
    bramblex
        12
    bramblex  
       2016-06-08 12:35:45 +08:00 via Android
    @chiu 在 J's 中基本上只在处理异步上意义比较大
    veficos
        13
    veficos  
       2016-06-08 12:37:31 +08:00
    @chiu CPS 的意义在于提取递归过程中函数栈的变量
    Gem
        14
    Gem  
       2016-06-08 12:38:23 +08:00
    ret 这个怎么理解?是什么意思?
    welefen
        15
    welefen  
       2016-06-08 16:01:56 +08:00
    尾递归优化
    XiXiLocked
        16
    XiXiLocked  
       2016-06-08 17:51:10 +08:00
    ret 是一个回调函数 /continuation, 意义是用当前参数算完 fact ,拿返回值接下来做什么
    可以人工运行几遍,或者证明"递归 0 次 ret 是上面的意义,递归 1 次 ret 是上面的意义,。。。递归 n 次...",记得用数学归纳法 注意每次递归 ret 都是一个新函数和前面的不一样。
    举个例子
    fact(2, console.log)//算出 fact(2),打印出来 #2
    fact(1, function(n_2){ console.log(n_2*2);}) //算出 fact(1),送给匿名函数 #1
    fact(0, function(n_1){ function(n_2){ console.log(n_2*2);}(n_1*1)}) //算出 fact(0),送给另一个匿名函数 #0
    function(n_1){ function(n_2){ console.log(n_2*2);}(n_1*1)}(1)//对应于#0 的调用 1=fact(0)
    function(n_2){ console.log(n_2*2);}(1*1)//对应于#1 的调用 1*1=fact(1)
    console.log(2) )//对应于#2 的调用 2=fact(2)
    bramblex
        17
    bramblex  
       2016-06-08 17:54:27 +08:00
    我花点时间完整讲一下吧。

    如前面所说, fact (n, ret) 函数中的

    // fact (n-1, function(t0) {
    // ret(n*t0)
    // })

    就是在构建一个新的 continuation 的过程, 并把原来的再包进去。只要分步把这个函数的 continuation 一步一步展开,那就明白了。

    举个🌰,展开 fact (3, ret) ,
    首先 fact (3, ret) 展开成 fact (2, function(t0){ ret(3 * t0) })
    知道作者为什么设一个 t0 吗?因为还有 t1, t2, t3 ,天生骄傲。(本人 t1 锤粉转黑)
    然后 fact (2, ...) 展开成 fact (1, function(t1){ (function(t0){ret(3*t0})(2*t1) })
    再然后 fact (1, ...) => fact(0, function(t2){ ( function(t1){ (function(t0){ret(3*t0})(2*t1) })(1*t2) })
    最后 fact(0, ...) => (function(t2){(function(t1){ (function(t0){ret(3*t0})(2*t1) })(1*t2) })(1)

    代入所有参数得到 ret(3*2*1*1) 就是结果(马德绕了那么一大圈)

    其实段代码看似 “尾递归优化” ,但是其实跟尾递归优化一点关系都没有,而且前面所说的能优化函数栈也是扯蛋,这只是把 fact 函数调用时候的函数栈转嫁到了 continaution 上了罢了,一点都没有优化。不信我们把这个所谓 “尾递归优化” 的代码转成循环给你们看看结果。转换成循环的方式在我博客里面有 http://lovearia.me/article/show/9

    // function fact(arg_n, arg_ret) {
    // let n = arg_n;
    // let ret = arg_ret;
    //
    // while (true){
    // if (n == 0){
    // ret(1);
    // break;
    // }
    // else{
    // let _n = n;
    // let _ret = ret;
    // n = _n - 1;
    // ret = function(t0){_ret(_n*t0)}; // <= 会在这里爆栈,根本没有任何优化效果
    // continue;
    // }
    // }
    // }

    至于前面有人提到 cps 执行的过程中可以优化函数栈,但是这时候为了递归优化而写成 cps 形式其实是很没有意义的,因为它实质就是尾递归优化,并且还需要很庞大的空间消耗来构建这个 continuation ,这和直接递归几乎没差别。这个 cps 递归只有在类似 haskell 这类惰性求值的语言中才能很好的优化,但是问题是在 haskell 这类惰性求值的语言中根本这种利用 cps 递归的写法本身又没有意义…
    SuperMild
        18
    SuperMild  
       2016-06-08 18:46:37 +08:00 via iPad
    其实楼主那个链接里说得很清楚,这的确不是尾递归,链接里同时给出了尾递归的写法。

    这个就是 CPS ,基本上就是硬生生多套了一层函数形成 callback 的形式,在 javascript 这样写的作用是避免 blocking ,把原来想直接执行的内容塞进函数里扔去执行,根据 js 天生异步的特点,就不会卡死了。
    palmers
        19
    palmers  
    OP
       2016-06-09 00:26:49 +08:00
    @XiXiLocked 谢谢 您的讲解听清楚的 非常感谢!
    palmers
        20
    palmers  
    OP
       2016-06-09 00:28:52 +08:00
    @bramblex 非常感谢! 我 刚接触 js 没多久, 非常感谢对我这个小白的指导, 谢谢 谢谢!~
    bramblex
        21
    bramblex  
       2016-06-09 00:45:47 +08:00
    @palmers

    这个已经不是 js 里面的内容,而属于 “程序语言理论” ( PLT )范畴。虽然不是什么很复杂的东西,但是一般研究程序语言比较深入的人才会接触到。

    然而你刚接触 js 没多久就接触到了这些东西,也确实很强啊。
    fourstring
        22
    fourstring  
       2016-06-09 07:04:43 +08:00
    @bramblex 您好,看了一下您讲解尾递归的那篇文章,有几个问题想问
    首先是您最开始举的那个普通递归的例子:
    const fact = (n) => {
    if (n <= 0) {
    return 1;
    } else {
    return n * fact (n - 1);
    }
    };
    它也在最后一个 return 调用了自己本身,为什么这就不是尾递归呢?
    其次,您使用的“入口环境”是什么意思呢?(没太看明白)
    另外,能否讲解一下进行尾递归时函数栈中的情况?(类似于您文章中“函数栈的作用”一节)
    谢谢!
    fourstring
        23
    fourstring  
       2016-06-09 07:13:15 +08:00
    @bramblex 刚刚去翻了翻维基百科,好像明白了。。。
    非常感谢您的文章!
    bramblex
        24
    bramblex  
       2016-06-09 09:31:15 +08:00 via Android
    bramblex
        25
    bramblex  
       2016-06-09 09:35:12 +08:00 via Android
    @fourstrin

    n * fact (n - 1) 这个并不是调用自身呀,假设把乘号看成一个函数 mul 那么就得到 mul(n, fact(n-1)),并不是自身嘛
    palmers
        26
    palmers  
    OP
       2016-06-09 15:13:00 +08:00
    @bramblex 谢谢 您抬举我了
    fourstring
        27
    fourstring  
       2016-06-09 22:02:34 +08:00
    @bramblex 喔,原来是这样理解,谢谢!
    markx
        28
    markx  
       2016-06-12 09:48:42 +08:00
    请问各位能不能解释一下最后一行不能尾递归优化? 最后一行相当于是 fact(n-1, cb); 嘛
    markx
        29
    markx  
       2016-06-12 09:49:28 +08:00
    @markx 检查了好多遍,却还是打错了……
    请问各位能不能解释一下为什么最后一行代码不能尾递归优化? 最后一行相当于是 fact(n-1, cb); 嘛
    palmers
        30
    palmers  
    OP
       2016-06-12 11:32:12 +08:00
    @markx 因为最后一行 依然形成了串行 表达式(我自己发明的词语) 函数执行完毕后形成的算术表达式是这个样子的:

    `5 * 4 * 3 * 2 * t0 ; 5 * 4 * 3 * 2 *1 * 1` //这是最后两次执行的过程

    我的理解是这样的, 不知道对不对, 请参考.
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2644 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 03:35 · PVG 11:35 · LAX 19:35 · JFK 22:35
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.