如何用JavaScript实现一门编程语言 - yield 进阶

[llwanghong]

整篇译文的目录章节如下：

• 前言
• λanguage描述
• 写一个解析器（Parser）
  • 字符流（Character Stream）
  • 标记流（Token Stream）
  • AST
  • 解析器
• 简单的解释器（Interpreter）
  • 我们得到了什么
  • 增加新的结构
  • 我们有多快？
• CPS求值器（CPS Evaluator）
  • 保护堆栈
  • Continuations
  • Yield进阶
• 编译成JS
  • JS代码生成器
  • CPS转换器
  • 示例及改进
  • 优化器
• 总结
• 真实示例

Yield进阶

首先，我们通过一些使用示例来认识yield。

foo = with-yield(λ(yield){
  yield(1);
  yield(2);
  yield(3);
  "DONE";
});

println(foo());  # prints 1
println(foo());  # prints 2
println(foo());  # prints 3
println(foo());  # prints DONE

调用后，yield会停止函数的执行并返回一个值。到目前非常类似return。当你再次调用函数，会从停止处重新开始执行，就像上面示例中展示的。示例会打印1，2，3，DONE。

一个更真实的用例：

fib = with-yield(λ(yield){
  let loop (a = 1, b = 1) {
    yield(b);
    loop(b, a + b);
  };
});

## print the first 50 fibonacci numbers
let loop (i = 0) {
  if i < 50 {
    println(fib());
    loop(i + 1);
  };
};

fib函数包含了一个无限循环。没有结束的条件。但yield会中断循环并返回当前的数。再次调用函数会从上次停止的地方继续执行，所以我们只需要调用函数50次既可以打印前50个数。

这个程序也会比双递归版本的fib实现快很多，因为其内部会保存前两个值，可以直接计算出下个值并返回。

一次失败的实现尝试

我不会浪费你的时间来做一次失败的尝试，除非能从中得到有价值的经验，所以请忍耐一下。

为了实现yield看起来我们需要保存函数初始的continuation。这样我们才能提前退出，就像 return 的行为一样。然而，真正从yield中返回之前，我们同样需要保存yield自身的continuation，这样后续才能返回到函数中yield接下来要执行的位置。至少看起来应该是这样。我们就按这个思路来尝试实现：

with-yield = λ(func) {
  ## with-yield returns a function of no arguments
  λ() {
    CallCC(λ(kret){        # kret is the "return" continuation
      let (yield) {

        ## define yield
        yield = λ(value) { # yield takes a value to return
          CallCC(λ(kyld){  # kyld is yield's own continuation…
            func = kyld;   # …save it for later
            kret(value);   # and return.
          });
        };

        ## finally, call the current func, passing it the yield.
        func(yield);
      };
    });
  };
};

上面是我首次尝试实现yield并且一切看起来都很合理。但当我们用这个定义来运行文中第一个示例，将会进入死循环。如果你愿意可以尝试一下下面的代码，做好需要刷新页面的准备（实际上这里我修改了Execute重清空堆栈的逻辑，使用setTimeout而不是异常捕获的方式，这样你的浏览器就不会被冻结住）。运行后你就会发现首先打印出1，2，3，接着就是打印无穷的“DONE”。

with-yield = λ(func) {
  λ() {
    CallCC(λ(kret){
      let (yield) {
        yield = λ(value) {
          CallCC(λ(kyld){
            func = kyld;
            kret(value);
          });
        };
        func(yield);
      };
    });
  };
};

foo = with-yield(λ(yield){
  yield(1);
  yield(2);
  yield(3);
  "DONE";
});

println(foo());
println(foo());
println(foo());
println(foo());

陷入无限循环的原因很隐晦。但如果你想看一些更离奇的行为，编辑上面代码并将最后四行println改成下面这样：

println(foo());
foo();

输出竟然完全一样。再次提醒：你需要这个示例运行后刷新页面，否则它会一直运行下去，直到耗光你电脑的电源和内存。

这里先直白解释一下发生死循环的原因，帮助理解原文。

首先，执行第一行println其中的foo时，最终会第一次调用到func(yield)，这时func是最初传入with-yield的函数，所以整体函数后续cps是第一个println处开始直至后续程序；

其次，只有在yield中才会对func重新赋值更新，所以func最后更新至“DONE”之前，就不再变化，即此后执行只会输出“DONE”，并且结合上面一点，执行完之后会跳到第一行println处重新执行整个程序。所以只要执行足够的次数（大于等于代码中yield个数），将程序执行到“DONE”处，即会跳回到第一行println开始死循环，不停地输出“DONE”；

最后，其实只需要两行println就可以“消费”完yield，因为func中能引用到的kret以及yield实际都是第一次定义的，并不是后续定义的，这一块可能需要多断点执行几次好好理解一下，所以只要执行yield其实总会跳到第一行println处打印结果，然后执行第二行foo()，消费下一条yield，但yield中会kret重新回到第一行println，依此往复，直至“DONE”。

确实有点绕，结合下面的原文解释，再反复理解一下:)

问题1：yield永远不再更新

需要注意的一个问题是为第一个yield保存的continuation（按照with-yield的实现，kyld将是接下来要调用的函数）会进行下面的计算：

  yield(2);
  yield(3);
  "DONE";

但保存的continuation中yield是什么？跟第一个yield一样，实际会返回到之前保存的第一个kret continuation，将会从那里开始执行并打印结果，这就产生了一个循环。幸运的是有一个简单的修复方法。已足够清晰，我们应该仅创建一次yield，因为第一次函数调用后其创建的yield没办法再更新了（相当于闭包在函数内部创建的变量，外面引用不到，也改变不了）；为了能返回到恰当的退出点，我们维护了一个新的return变量：

with-yield = λ(func) {
  let (return, yield) {
    yield = λ(value) {
      CallCC(λ(kyld){
        func = kyld;
        return(value);       # return is set below, on each call to the function
      });                    # it's always the next return point.
    };                       #
    λ(val) {                 #
      CallCC(λ(kret){        #
        return = kret;       # <- here
        func(val || yield);
      });
    };
  };
};

此外，认识到除了第一次之外，其它每次都将yield传给func函数没有意义，改进的新版本允许调用时传递一个值（除了第一次）。这个值将作为yield自身的返回值。

下面代码同样使用foo示例，但仅执行三次println(foo())：

with-yield = λ(func) {
  let (return, yield) {
    yield = λ(value) {
      CallCC(λ(kyld){
        func = kyld;
        return(value);
      });
    };
    λ(val) {
      CallCC(λ(kret){
        return = kret;
        func(val || yield);
      });
    };
  };
};

foo = with-yield(λ(yield){
  yield(1);
  yield(2);
  yield(3);
  "DONE";
});

println(foo());
println(foo());
println(foo());

看起来像是可以正确执行了。对比第一版有显著的改进，“print(foo()); foo()”代码不会再死循环了。但如果再增加一行println(foo())会怎么样？会再次发生循环！

问题2：WTF?

这次发生循环的原因会更加深奥一点。与我们continuation不受限的本性（unlimited nature）有关：它们涵盖了程序全部的后续计算行为，恰巧也包含了第一次调用foo()的返回。当从它返回时会发生什么？ — 所有一切又重新执行了一遍：

println(foo()); ## yield 1 <----------------- HERE -------------------+
println(foo()); ## yield 2                                            |
println(foo()); ## yield 3                                            |
println(foo()); ## we reached "DONE", so the first foo() RETURNS -->--+

我们看一下with-yield中的这行代码：

        func(val || yield);
        #...

当通过调用yield退出func函数时，会调用一个continuation，所以并不会执行到#... 这行。但当结束时，到达了函数结尾处（DONE这行），func函数此时将等效于一个返回"DONE"给其初始continuation（即func初始定义函数的continuation）的函数，这个continuation将调用第一个println。第二行的foo()只是循环了一下，所有"DONE"行都是第一行print打印出来的。可以通过下面的代码来验证一下：

println(foo());
println("bar");
println(foo());
println(foo());
foo();

上面的输出是：1, bar, 2, 3, DONE, bar, DONE, bar, ....

所以一个可能的修复方式，当“自然”返回时（简单地说就是“结束了”）必须将func设置为其它某值。我们就将其设置为返回“no more continuations”的空函数（什么都不会做）。

        val = func(val || yield);
        func = λ() "NO MORE CONTINUATIONS";
        kret(val);

现在不会再循环了，但当运行下述代码时会再次感到困惑：

with-yield = λ(func) {
  let (return, yield) {
    yield = λ(value) {
      CallCC(λ(kyld){
        func = kyld;
        return(value);
      });
    };
    λ(val) {
      CallCC(λ(kret){
        return = kret;
        val = func(val || yield);
        func = λ() "NO MORE CONTINUATIONS";
        kret(val);
      });
    };
  };
};

foo = with-yield(λ(yield){
  yield(1);
  yield(2);
  yield(3);
  "DONE";
});

println(foo());
println(foo());
println(foo());
println(foo());

我们本期望输出1，2，3，DONE，但同时也输出了三次“NO MORE CONTIUATIONS”。为了弄清楚原因，我们按下面的方式尝试交错输出：

print("A. "); println(foo());
print("B. "); println(foo());
print("C. "); println(foo());
print("D. "); println(foo());

## and the output is:
A. 1
B. 2
C. 3
D. DONE
B. NO MORE CONTINUATIONS
C. NO MORE CONTINUATIONS
D. NO MORE CONTINUATIONS
***Result: false

上述输出意味着问题依旧存在：函数正常退出仍然会返回到第一个continuation处；但因函数func目前是空操作，"B."行代码不会触发循环。

原因还是比较绕，原文解释较少，这里面再补充解释下，梳理下执行流程。

一个大的原则还是抓住第一次foo执行。当第一次执行foo时，执行到 val = func(val || yield); 时，func的continuation为with-yield初始化使用的函数整体执行完毕的全部后续行为，所以不管后续程序如何执行，以及kret/return如何赋值，当func被kyld赋值DONE行的continuation后，都会执行完然后跳到 val = func(val || yield); 进行val的赋值及后续行为，接着就是func赋值为空函数等，返回到第一行的println，打印出DONE，后续println都会打印出空函数的返回，即NO MORE CONTINUATIONS。

我们的实现仍然有用，考虑到函数永远不结束仅通过yield退出的情况。下面是一个Fibonacci的例子：

with-yield = λ(func) {
  let (return, yield) {
    yield = λ(value) {
      CallCC(λ(kyld){
        func = kyld;
        return(value);
      });
    };
    λ(val) {
      CallCC(λ(kret){
        return = kret;
        val = func(val || yield);
        func = λ() "NO MORE CONTINUATIONS";
        kret(val);
      });
    };
  };
};

fib = with-yield(λ(yield){
  let loop (a = 1, b = 1) {
    yield(b);
    loop(b, a + b);
  };
});

## print the first 50 fibonacci numbers
let loop (i = 0) {
  if i < 50 {
    println(fib());
    loop(i + 1);
  };
};

但如果我们想要一个可靠的实现（函数结束时不会返回到第一次调用的位置），需要引入另一个概念叫做“delimited continuations”。

Delimited continuations: reset 和 shift

我们将通过两个其它的操作符reset和shift来实现yield。它们提供了“delimited continuations” — 那些像普通函数一样返回的continuations。 reset会创建一个“执行帧”（可理解为reset执行时刻的所有上下文信息），shift仅能获取到这个“执行帧”之后的continuation（即reset之后的计算行为），而不是像CallCC那样可以获取到“整个程序的未来计算行为”。

reset和shift都接收一个函数参数。reset函数执行期间，我们能够通过调用shift来给reset的调用位置返回一个值。

首先来看下with-yield会变成什么样：

with-yield = λ(func) {
  let (yield) {
    ## yield uses shift to return a value to the innermost
    ## reset call. before doing that, it saves its own
    ## continuation in `func` — so calling func() again will
    ## resume from where it left off.
    yield = λ(val) {
      shift(λ(k){
        func = k;  # save the next continuation
        val;       # return the currently yielded value
      });
    };
    ## from with-yield we return a function with no arguments
    ## which uses reset to call the original function, passing
    ## to it the yield (initially) or any other value
    ## on subsequent calls
    λ(val) {
      reset( λ() func(val || yield) );
    };
  }
};

注意现在每次函数调用都内嵌在reset中。这可以确保我们不会涵盖程序整体的continuation（即程序全部的后续行为），而仅仅是reset之后的行为。按照定义，现在不可能再发生循环了。当函数正常结束，程序就会继续执行而不会返回到第一次调用的位置。

reset / shift的实现

这些操作符的实现有很强的技巧性，尽管实现代码很短。做好头疼的准备。我会给出两种解决方案。我不是这个方法的作者，可以告诉你在真正理解它们之前我盯着代码看了很久。我是在Oleg Kiselyov的Scheme程序中发现了这个方法。推荐你阅读这些文章来更多地理解这个令人兴奋的概念。

实现为原始功能函数

在这里将它们实现为原始功能函数。在原始功能函数中，当前continuation是显式的（不需要调用CallCC），这在一定程度上更利于理解到底发生了什么。下面是完整的实现：

var pstack = [];

function _goto(f) {
    f(function KGOTO(r){
        var h = pstack.pop();
        h(r);
    });
}

globalEnv.def("reset", function(KRESET, th){
    pstack.push(KRESET);
    _goto(th);
});

globalEnv.def("shift", function(KSHIFT, f){
    _goto(function(KGOTO){
        f(KGOTO, function SK(k1, v){
            pstack.push(k1);
            KSHIFT(v);
        });
    });
});

关键之处是reset和shift都使用了_goto，它并不是一个“普通”函数。它没有自己的continuation。_goto接收一个普通函数f并给其传入一个continuation（KGOTO）进行调用。f执行过程中捕获的任意continuation（甚至是使用CallCC捕获的）仅能涵盖到这个KGOTO开始的后续计算行为，因为KGOTO上面没有其它计算了（KGOTO保存在pstack堆栈栈顶）。因此，无论f是正常退出，或通过调用一个continuation退出，最终都会去执行KGOTO — 它会从stack中取出下一个continuation，并应用到之前的计算结果上。

reset会在_goto(th)之前将其自身的continuation（KRESET）压入堆栈。如果不这么做，函数退出后程序就会停止，因为_goto后面没有其它代码了。所以当函数以任意方式退出后，KGOTO都会重新返回到KRESET这里继续执行。

最终shift会以KGOTO这个continuation来调用函数，所以如果正常退出则KGOTO将从pstack栈顶恢复执行，并传给其一个SK函数来返回至shift调用的位置（从而使用shift自己的continuation，KSHIFT）。SK是一个delimited continuation — 能够像一个函数一样返回一个值 — 因此我们也需要将它的continuation（k1）压入堆栈。为了说明其中的区别，我在下面引入了一个shift2原始功能函数，和上面的shift一样，除了没有这一行：pstack.push(k1)，试一下这个示例：

println(reset(λ(){
    1 + shift( λ(k) k(k(2)) );
}));

println(reset(λ(){
    1 + shift2( λ(k) k(k(2)) );
}));

shift提供了一个continuation（k），是一个从嵌套层级最近reset开始的delimited continuation。这个例子中continuation就是给shift的结果加1：

1 + [?]

当我们调用k时，我们是用值替换了上面的问号（?）。我们调用两次k(k(2))。提供2并继续执行程序，因此内部的k(2)将返回3。所以紧接着的k(3)将提供一个3，同样会替换问号，生成最终的结果4。

shift2是不对的：内部的k(2)永远不会返回。

CallCC-based

如上所述，如果我们仅有CallCC并且没有办法定义原始功能函数，同样可以实现delimited continuation。下面的代码功能与原始功能函数版本基本相同，但因为没有JS数组，它使用了列表list来维护堆栈（像前面章节曾看过的，我们可以直接使用λanguage实现list，尽管这里是使用原生功能函数方式实现的）。因为需要CallCC来获取current continuation（原生功能函数中是一个显式的参数），所以代码比之前版本稍微长了点。

下面代码中最有技巧性的部分是goto的实现形式及其原因，但我要把发掘的乐趣留给你。

pstack = NIL;

goto = false;

reset = λ(th) {
  CallCC(λ(k){
    pstack = cons(k, pstack);
    goto(th);
  });
};

shift = λ(f) {
  CallCC(λ(k){
    goto(λ(){
      f(λ(v){
        CallCC(λ(k1){
          pstack = cons(k1, pstack);
          k(v);
        });
      });
    });
  });
};

let (v = CallCC( λ(k){ goto = k; k(false) } )) {
  if v then let (r = v(), h = car(pstack)) {
    pstack = cdr(pstack);
    h(r);
  }
};