使用continuation生成Javascript代码背后的诀窍是什么？

Question

我正在寻找一种方法来添加到Javascript非常特殊的非抢占式多线程形式.Mozilla的Javascript 1.7支持使用本机协同程序yield,但我不想使用特定于浏览器的解决方案.我看到有几个continuation或coroutines的实现,基于将带注释的Javascript代码转换为普通的Javascript.一些例子是StratifiedJS,Narrative Javascript和jwacs.

我不需要一个功能齐全的模拟Javascript异步调用框架; 我只是需要它来实现我想要实现的非常具体的用法.因此,上面的库对我来说太过分了.

有人能指出这种预处理器使用的基本"技巧"(或技巧)吗？是否有一些特殊的语言破解可以在Javascript中实现延续,代价是生成一些额外的代码？欢迎任何相关的参考.

Answer 1

这是继续传递风格.

Javascript是Lisp但是作为语法穿着C的衣服.

因为Javascript是一种功能性语言,所以真正疯狂的技巧是可能的,比如延续传递风格.但这些技巧令人头疼.

在摘要中,延续是下一步做什么的概念 - 作为可以调用的东西提供,就像一个函数一样.我有时也会将continuation视为已保存的调用帧堆栈:您可以将一堆函数调用保存为执行状态,然后返回或稍后"调用"此状态.

有人证明,通过将代码转换为延续传递风格,您可以获得延续的力量.哇!这真是令人印象深刻:

只是一个源代码转换,你就拥有了延续的力量.

现在,Javascript的问题是它的C语法.使用C语法进行源代码转换很困难.使用Lisp语法会更容易,但仍然很乏味且容易出错.

我们很幸运,一些非常聪明的人为我们做了艰苦的工作.这项艰苦的工作需要使用Javascript解析器,因为这种转换究竟意味着什么？在摘要中,它意味着重新排序操作的顺序,使得首先真正完成的操作首先出现.

f(g(a + x))

加入a + x首先做了,那么函数调用g(),然后f().有三个子表达式.在CPS变换中,子表达式的结果被传递给延续.这涉及创建许多内部辅助函数作为临时延续.这可能会变得复杂和繁琐,我们将在下面看到.

在http://en.wikipedia.org/wiki/Continuation-passing_style中有一个示例函数

(define (pyth x y)
  (sqrt (+ (* x x) (* y y))))

转换为

(define (pyth& x y k)
  (*& x x (lambda (x2)
      (*& y y (lambda (y2)
               (+& x2 y2 (lambda (x2py2)
                          (sqrt& x2py2 k))))))))

这对应于Javacript

function pyth(x, y) {
    return Math.sqrt(x * x + y * y);
}

但*,+和Math.sqrt()不是CPS有意义的功能.

但是,为了示例,假设*,+和Math.sqrt()是Web服务.这很重要,因为Javascript Web服务调用是异步的.使用异步调用的每个人都知道将它们的结果组合起来会有多复杂.使用预处理库或生成器,可以更轻松地处理异步结果.

那么让我们以不同的方式编写示例:

function pyth(x, y) {
    return sqrt(add(mul(x, x), mul(y, y)));
}

那么CPS转换可能如下所示:

function pyth_cps(x, y, k) {
  mul_cps(x, x, function(x2) {
    mul_cps(y, y, function(y2) {
      add_cps(x2, y2, function(x2py2) {
        sqrt_cps(x2py2, k);
      })
    })
  });
}

我们看到结果代码从里到外被撕裂并且变得难以理解.每个功能都被转换.他们都得到了一个神奇的参数k.这是延续.在javascript中,它是一个获取操作结果的函数.在调用堆栈k的深处某处调用.在我们的例子中,在这里没有显示的sqrt()的CPS变换.

另请注意,CPS转换函数永远不会返回.他们只是用计算结果调用延续.这可能导致堆栈耗尽.所有Javascript CPS变换器都需要处理这个问题.在Scheme中,这不是必需的,因为所有调用都是尾调用.尾调用不需要额外的调用帧.在Javascript中,需要蹦床或类似的技术.而不是直接调用continuation,调用一个帮助器并将结果和延续传递给它.帮助程序在无限循环中运行,始终调用并返回并避免堆栈耗尽.

那么,为什么这个CPS给我们延续的力量呢？那是因为延续只是接下来要做的事情.如果我们总是随身携带这个概念作为附加参数k并且总是将当前表达式的结果传递给它,那么我们已经在代码中实现了这个概念.然而,正如我们所看到的,这种"总是随身携带"很难实现.

这是一个陡峭的代价,即使我们让源代码预处理器做了艰苦的工作.我们为什么要使用延续？抽象控制流是可能的.Seaside是一个Web应用程序框架,它使用continuation来抽象出浏览器的无状态请求流.用户交互可以简洁地建模 - 人们不再在请求中思考,而是在交互流程中.这只是延续力量的众多例子之一.对许多人来说,这种力量似乎也很奇怪,有些可怕.