趣味编程：在JavaScript中实现简单的yield功能（1 - yield与yieldSeq）
2010-06-10 09:36 by 老赵, 2834 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，要求生成一个无限的序列，那么可以怎么做？如果使用递归的思路来思考这个问题，则它可以分解为两个步骤：
- 输出n；
- 依次输出numSeq(n + 1)中的每个元素。
同样，range方法也可以分解为：
- 如果minInclusive大于等于maxInclusive，则返回一个空序列。
- 输出minInclusive。
- 依次输出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来说，能够使用循环会更为直观一些。那么，我们又该如何实现呢？
这又是一个值得讨论话题了，我原本打算一篇写完，但是发现篇幅有些太长，那还是分开进行吧。而且，这还需要从其他一些东西谈起，我们下次再继续吧。
相关文章
- 趣味编程：在JavaScript中实现简单的yield功能（问题）
- 趣味编程：在JavaScript中实现简单的yield功能（1 - yield与yieldSeq）
这种太狡诈了呀