Hello World
Spiga

趣味编程:在JavaScript中实现简单的yield功能(1 - yield与yieldSeq)

2010-06-10 09:36 by 老赵, 1582 visits

上文我谈到了迭代器及其生成器,即C#或Python中的yield功能,它们极大地简化了创建一个迭代器的工作,让代码的语义和可读性有了很大提高。虽然在JavaScript 1.7中已经有了相同的功能,可惜目前我们还无法用到这种强大的能力。那么,我们能不能为JavaScript提供如C#中一样的功能?在文章的评论里许多朋友也给出了他们的解决方案,也让我获得了许多启发。因此,我也打算在以后的文章中总结一下各位的做法。不过在这篇文章里,我先来阐述一下我个人的想法。

实现简单的yield功能

先从简单的做起,例如实现C#中的这样一个迭代器:

// C#
public static IEnumerable<int> OneToThree()
{
    yield return 1;
    yield return 2;
    yield return 3;
}

在执行阶段,代码自然不会像表面上那样“一蹴而就”,从逻辑上讲它们是“一个阶段一个阶段”进行下去的。调用OneToThree时,方法中的代码不会执行;在迭代器的MoveNext方法第一次被调用时,代码才从头执行至第一个yield return处,便立即并返回;接下来每次调用MoveNext时,都会从上一个yield return的下一行代码开始继续执行下去,直到下一个yield return,或是方法结束为止。

在JavaScript中,我们自然无法让方法从某一行代码处立即返回,并且在需要的时候立即执行下去。因此我们要做的只能是,让代码在需要停止的地方“立即返回”,真正地返回,不留情面的返回。那么,yield之后的接下去的代码又该怎么办呢?那就必须用一种“回调”的方式来“继续”我们的工作了。因此,我们的“开发模式”大约是这样的:

// JavaScript
function oneToThree() {
    return $yield(1, function () {
    return $yield(2, function () {
    return $yield(3);

    });
    });
}

这段代码其实就体现了我们上面描述的编程模式。这里虽然有好几行代码,但事实上oneToThree的第一行代码便是个return,它会立即返回$yield方法的执行结果。我们为第一个$yield方法调用传递了两个参数,一是0,表示迭代器要输出的值,而第二个参数则是个回调函数,表示需要继续执行的代码,其中包含了第二个return $yield,此时又有一个回调函数,包含了最后一个return。我们就是利用了这种方法实现了简单的yield功能。

很显然,我在这里强制破坏了JavaScript的缩进规则,让三句return $yield看上去是平行的,而不是嵌套的关系。同时,我将每个函数调用或是回调函数的大小括号放在了最后,远离主体代码。如果您的眼睛略有近视,或者像我一样能够“屏蔽”其他“架子代码”,就能感受到这种做法的美妙。

至于实现,感觉还是比较容易的:

// JavaScript
function $yield(value, rest) {
    return {
        value: value,
        _rest: rest,
        next: $yield._next
    };
}
$yield._next = function () {
    if (this._rest) {
        return this._rest();
    } else {
        return null;
    }
}

说实话,这也就是单向链表罢了。只不过这个单向链表的next指针不是一个普通的引用,而是在需要的时候,根据一个回调函数获得的。“在需要的时候”,这便是“延迟”,这为我们生成“无限”序列奠定了基础。

循环?递归!

那么现在就有个问题了,比如说,在之前C#里的Infinite或Range方法中利用到了循环,那么在上面的yield模式中也可以这样吗?显然不行,JavaScript遇到return就直接跳出方法了,虽然我们可以执行回调函数,但是我们做不到让代码跟着循环一遍遍地前进。

“不能使用循环”,这个问题其实很普通,也很容易解决,因为“循环”本来就不是每种编程范式都拥有的东西。“循环”则意味着要改变某个状态,这是个“副作用”,因此在一些无副作用的函数式编程语言来说,便从来就没有“循环”这种东西。不过大家过的还都是好好的,因为我们还有“递归”。假如我们要编写一个numSeq方法,给定一个n,要求生成一个无限的序列,那么可以怎么做?如果使用递归的思路来思考这个问题,则它可以分解为两个步骤:

  1. 输出n;
  2. 依次输出numSeq(n + 1)中的每个元素。

同样,range方法也可以分解为:

  1. 如果minInclusive大于等于maxInclusive,则返回一个空序列。
  2. 输出minInclusive。
  3. 依次输出range(minInclusive + 1, maxInclusive)中的每个元素。

所以,我们需要的是“依次输出每个序列”这样一个功能,在这里我把它称作是$yieldSeq。这样我们便可以写出这样numSeq函数:

function numSeq(n) {
    return $yield(n, function () {
    return $yieldSeq(numSeq(n + 1));

    });
}

由于没有递归出口,numSeq将会生成一个无限的序列,但是其中每个元素都是“按需”生成的,我们可以仅仅打印出其中N项:

// print 0 .. 9
for (var iter = numSeq(0); iter; iter = iter.next()) {
    document.write(iter.value + "<br />");
    if (iter.value >= 9) return;
}

与$yield相同,$yieldSeq返回的也是一个序列,它们之间的区别是:yield返回的序列包含单个元素和剩下的部分,而$yieldSeq返回的是“一个序列中的所有元素”,再接上剩余的部分:

function $yieldSeq(iter, rest) {
    if (!rest) return iter;
    if (!iter) return rest();

    return {
        value: iter.value,
        _iter: iter,
        _rest: rest,
        next: $yieldSeq._next
    };
}
$yieldSeq._next = function () {
    return $yieldSeq(this._iter.next(), this._rest);
}

现在我们便可以使用$yieldSeq来写出rangeSeq这样的函数了:

function rangeSeq(minInclusive, maxExclusive) {
    if (minInclusive >= maxExclusive) return null;

    return $yield(minInclusive, function () {
    return $yieldSeq(range(minInclusive + 1, maxExclusive));

    });
}

甚至是个斐波那契数列:

function fibSeq() {
    function fibSeq$(a, b) {
        var next = a + b;
        return $yield(next, function () {
        return $yieldSeq(fibSeq$(b, next));

        });
    }

    return $yield(0, function () {
    return $yield(1, function () {
    return $yieldSeq(fibSeq$(0, 1));

    });
    });
}

在fibSeq内部我们定义了一个fibSeq$函数,它的作用是输出a、b两项以后的“无限长”的序列。因此在fibSeq方法中,我们先yield出去0和1两个元素,再依次输出fibSeq$序列中的元素。得到了无限长的斐波那契数列之后,我们便可以做一些有趣的事情了,例如500以内的元素之和:

var sum = 0;
for (var iter = fibSeq(); iter; iter = iter.next()) {
    if (iter.value <= 500) {
        sum = sum + iter.value;
    } else {
        break;
    }
}

document.write(sum + "<br />");

但是这么做实在太丑,因为我们还少了许多必要的基础元素,如果我们的目标是写出这样的代码:

var sum = toIter(fibSeq()).takeWhile(function (i) { return i <= 500; }).sum();

那么您可以实现toIter及takeWhile吗?此外,take,skip,where,filter等常见功能,您可以一并实现吗?其实这就十分简单了,就留给感兴趣的朋友工作之余用来放松神经吧。

可是我还是想要循环……

说实话,我喜欢“递归”的方式,毕竟这是种可读性更好的,无副作用的声明式解法;与此相对,“循环”是一种描述“how to do”,依赖可变状态的命令式解法。不过,毕竟JavaScript主要还是一门命令式的编程语言,它的特性并不能写出十分优雅的函数式代码。而且,从上面一些例子中看,如numSeq,rangeSeq来说,能够使用循环会更为直观一些。那么,我们又该如何实现呢?

这又是一个值得讨论话题了,我原本打算一篇写完,但是发现篇幅有些太长,那还是分开进行吧。而且,这还需要从其他一些东西谈起,我们下次再继续吧。

相关文章

Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

29 条回复

  1. 链接

    韦恩卑鄙 @waynebaby 2010-06-10 10:31:57

    这种太狡诈了呀

  2. fw
    123.124.137.*
    链接

    fw 2010-06-10 10:43:49

    // JavaScript
    function oneToThree() {
        return $yield(1, function () {
        return $yield(2, function () {
        return $yield(3);
    
        });
        });
    }
    

    这个写法。。如果函数稍微复杂一点。。就是比fib那个在复杂一点,会很悲剧的呀。尤其是不能 ctrl+k+d。 话说回来,有人和我一样有ctrl+k+d强迫症么?

  3. 链接

    装配脑袋 2010-06-10 10:45:10

    这边评论贴代码的语法到底是什么啊。。还是不懂=_=b

  4. 老赵
    admin
    链接

    老赵 2010-06-10 10:45:36

    @韦恩卑鄙: 这种太狡诈了呀

    其实这是种有更广泛意义的做法,下次会提到的……

  5. 老赵
    admin
    链接

    老赵 2010-06-10 10:49:52

    @fw: 这个写法。。如果函数稍微复杂一点。。就是比fib那个在复杂一点,会很悲剧的呀。尤其是不能 ctrl+k+d。 话说回来,有人和我一样有ctrl+k+d强迫症么?

    对的,不能格式化,而且很多编辑器是自动格式化的,所以最好还是让程序员可以写成这样的代码:

    function oneToThree() {
        $yield(1);
        $yield(2);
        $yield(3);
    }
    

    然后,我们先oneToThree.toString(),再修改字符串(这个替换好像并不复杂),再eval成一个新函数,hmmm……

  6. 老赵
    admin
    链接

    老赵 2010-06-10 10:50:08

    @装配脑袋: 这边评论贴代码的语法到底是什么啊。。还是不懂=_=b

    脑袋看帮助呀。

  7. kusk
    114.245.170.*
    链接

    kusk 2010-06-10 10:57:08

    用递归代替循环在实际应用中有一个前提,即该语言实现了尾递归优化。否则当迭代次数充分多时,递归会有栈溢出的问题(而循环不会)。

  8. 老赵
    admin
    链接

    老赵 2010-06-10 11:03:21

    @kusk: 用递归代替循环在实际应用中有一个前提,即该语言实现了尾递归优化。否则当迭代次数充分多时,递归会有栈溢出的问题(而循环不会)。

    这个说法半对半错吧,其实还要就事论事,比如你觉得在我这个程序中会有递归溢出问题嘛?

  9. 链接

    装配脑袋 2010-06-10 11:25:18

    如果有很好的ExpressionTree机制应该也能做出好看的Yield来。

  10. 链接

    装配脑袋 2010-06-10 11:26:04

    要么,就做成真·Coroutine。让这个过程真的和For each协同。需要在Runtime上做一些Hack.

  11. 链接

    clk_z 2010-06-10 13:13:36

    我是来长见识的,顺便帮老赵顶一下!

  12. 链接

    Ivony 2010-06-10 13:24:39

    老赵,你这个很不美观啊,至少也要,让他可以排版啊。。。。。

    function oneToThree() {
        $yield
        ( function() { return 1; } )
        ( function() { return 2; } )
        ( function() { return 3; } );
    
    }
    
  13. 老赵
    admin
    链接

    老赵 2010-06-10 13:41:36

    @Ivony

    这个写起来就啰嗦了啊,function太麻烦。我的想法是提供一种方式,然后反正最后要从漂亮的写法上来解析的,就像我上面说的那样。

  14. 链接

    Ivony 2010-06-10 13:56:46

    呃,我好像忘了一件事儿,如果是那样,在( function() { return 1; } ) 这里面var定义的变量就不能穿透到( function() { return 2; } )这里面了。。

    不过老赵的方案也要处理var提前解析的问题,所以估计最后都会是将所有var提到最外的闭包。

    简单的说就是假设有这样的代码:

    j = 1;
    yield return j;
    var j;
    
    i = 0;
    yield return i;
    var i;
    

    根据JavaScript的语法,var放在哪里都一样,换言之这段代码等同于:

    var j = 1;
    yield return j;
    
    var i = 0;
    yield return i;
    

    然而老赵直接解析后会成为:

    j = 1;
    return $yield( j, function(){
    var j;
    
    i = 0;
    return $yield( i, function(){
    var i;
    
    });
    });
    

    这显然不对,解决的办法是将var变量全部提到函数顶端:

    var j;
    var i;
    
    j = 1;
    return $yield( j, function(){
    
    i = 0;
    return $yield( i );
    
    });
    

    如果都把var提前的话,那我的写法也就能穿透了

  15. 老赵
    admin
    链接

    老赵 2010-06-10 14:29:11

    @Ivony

    var放错地方的代码我打算就不关心了,在程序里避免既正常也容易吧。

    在我看来,这段“程序员写的”代码:

    var j = 1;
    return $yield(j);
    
    var i = 0;
    return $yield(i);
    

    最终应该解析为这样才对:

    var j = 1;
    return $yield(j, function() {
    
    var i = 0;
    return $yield(i, function() {
    
    });
    });
    

    其实这里就是个monad,整套语法结构都是可以正常解析的,似乎没有作用域问题。事实上我这里的一个参考就是F#里的“计算表达式(Computation Expressions)”,下次会提到的。

  16. zzfff
    113.141.29.*
    链接

    zzfff 2010-06-10 20:59:49

    @装配脑袋: 如果有很好的ExpressionTree机制应该也能做出好看的Yield来。

    ET v2里还真有YieldExpression...

  17. zzfff
    113.141.29.*
    链接

    zzfff 2010-06-10 21:04:00

    装配脑袋这样聪明的人都不会贴代码,我很欣慰...

  18. 老赵
    admin
    链接

    老赵 2010-06-10 21:15:46

    @zzfff: 装配脑袋这样聪明的人都不会贴代码,我很欣慰...

    脑袋只是没找到帮助,现在已经会了且找到一些bug,haha

  19. vczh
    58.38.60.*
    链接

    vczh 2010-06-11 02:31:08

    - -b就是我上一篇文章的回帖里面那个可怜的程序的翻版嘛……令$yield(a,b) == [a,b]

  20. 看看
    222.92.42.*
    链接

    看看 2010-06-11 10:01:01

    问个和主题无关的,刚看F#中的List相关实现,有个疑问。如下明明F#也支持过程式语法,为什么全用递归来完成循环,难倒只是因为他是函数式语言吗。

  21. 老赵
    admin
    链接

    老赵 2010-06-11 10:10:18

    @看看

    F#是函数式编程语言,自然用函数式的方式比较好。而且函数式编程的“声明性”一半也比过程式的来的强。

  22. 链接

    mfjt55 2010-06-11 10:18:36

    用Google登录后来看看,不知是不是这样登录后就可以修改评论了。

    继续上面的问题再请教下,用递归相对循环来说,递归一层就要额外的空间,不知是不是,还有看前面您的文章,F#的List的结构和C#的是不一样的,不知是不是专门用来递归的?

  23. 老赵
    admin
    链接

    老赵 2010-06-11 10:33:13

    @mfjt55: 用递归相对循环来说,递归一层就要额外的空间

    所以有“尾递归优化”。

    F#里的数据结构,都是为函数式编程设计的,不能和C#混为一谈。我不明白什么叫做“专门用来递归”的,其实这些都是基础,您可以先找些基本资料多了解一下。

  24. 看看
    222.92.42.*
    链接

    看看 2010-06-11 11:02:29

    哦,谢谢指出相关方向,刚入行的小菜。

  25. 链接

    mfjt55 2010-06-11 11:04:17

    晕,又变成没登录的了,没有点登录并记住我,太粗心大意了。。。。。。

  26. Tianium
    114.93.104.*
    链接

    Tianium 2010-06-11 21:02:20

    老赵,可以这么叫吧,关注你的博客和 Twitter 有段时间了,这篇文章提得问题还蛮有趣的,合理利用 Javascript 闭包,我可以把使用代码简化到如下,你看还能符合你的要求把:

    var fibSeq = function() {
        var yield = function() {
            // implement yield, yield.loop and yield.exec
        }();
    
        yield(0);
        yield(1);
    
        var d1 = 0;
        var d2 = 1;
        yield.loop(function() {
            var next = d1 + d2;
            d1 = d2;
            d2 = next;
            return next;
        });
    
        return yield.exec; // exec is a function;
    }();
    
  27. 链接

    Tianium 2010-06-11 21:31:47

    刚才由于没调试,所以没把 yield 的实现贴上来,yield 的实现如下:

    var yield = function() {
        var session = [];
        var impl = function(expr) {
            session.push(expr);
        };
        impl.exec = function() {
            if (session.length) {
                var expr = session.shift();
                return expr instanceof Function ? expr() : expr;
            }
         };
         impl.loop = function(func) {
            impl(function() {
                impl.loop(func);
                return func();
            });
        };
        return impl;
    }();
    

    主要是考虑到 C# 的实现等于在函数重入时恢复了以前的执行状态,我这里用 Javascript 闭包模拟这种状态保存,同时利用一个数组做"队列"模拟 yield 实现。 这里吧 yield 实现放在函数里,是考虑到每个函数需要一个队列,如果要使使用 yield 的代码更简洁,也可以提出去,但就需要做些额外的工作了。

  28. curise
    211.160.163.*
    链接

    curise 2010-07-30 11:00:41

    为什么没次看你的文章我都有点看得很迷糊的感觉呢

  29. 链接

    宁 王 2014-11-28 15:35:45

    还是不太懂yieldSeq这个方法。

    function fibSeq(){
        function fibSeq$(a,b){
            var next = a+b;
            return $yield(next,function(){
                return fibSeq$(b,next)
            })
        }
        return $yield(0,function(){
            return $yield(1,function(){
                return fibSeq$(0,1)
            })
        })
    }
    

    看了下实现,代码改成这样应该也是能够正确运行的。 那么问题来了,$yieldSeq方法,第二个参数reset到底有啥用...

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我