如何用JavaScript实现一门编程语言 - CPS转换器

[llwanghong]

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

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

CPS转换器（transformer）

作者原文提到的bug此译文中已修复，主要是指在解释器，CPS求值器及CPS编译器章节中：像 a() && b() 或者 a() || b() 的表达式两侧都会求值。这样处理是不对的，是否对 b() 求值依赖 a() 的求值结果。通过将 || 及 && 两个二元操作符的处理逻辑替换为 if 表达式来修复。

转换代码为CPS形式

为了能够使用不受限制的递归和continuation，我们将像在解释器章节中做的一样：实现一个“CPS求值器”。求值器本身是按照continuation-passing-style形式编写，接收一个计算表达式和一个接收结果的回调函数。但这里我们只进行编译，而不会求值，所以这个回调函数指代什么并不特别明显。

下面是本篇代码的一些转换示例。选择通过λanguage语言而不是AST进行表达，因为这样更容易理解，但需要澄清一点：CPS转换器接收一个AST输入，并返回一个兼容且等价的AST输出，区别在于输出的AST是CPS形式的。它并不会返回一个字符串形式的λanguage或JavaScript程序，这是代码生成器完成的。

在下面示例中，TC代表“toplevel continuation” — 它将接收整个程序的结果。你可以认为其是“最后的返回”。

实现

to_cps函数将接收一个AST以及一个回调函数作为输入。程序主入口点看起来像下面这样： 

function to_cps(exp, k) {
    return cps(exp, k);

    function cps(exp, k) {
        switch (exp.type) {
          case "num"    :
          case "str"    :
          case "bool"   :
          case "var"    : return cps_atom   (exp, k);

          case "assign" :
          case "binary" : return cps_binary (exp, k);

          case "let"    : return cps_let    (exp, k);
          case "lambda" : return cps_lambda (exp, k);
          case "if"     : return cps_if     (exp, k);
          case "prog"   : return cps_prog   (exp, k);
          case "call"   : return cps_call   (exp, k);

          default:
            throw new Error("Dunno how to CPS " + JSON.stringify(exp));
        }
    }

    // NOTE, the functions defined below must be placed here.
}

看起来和代码生成器类似，但所有函数都接收一个额外的k参数，它将编译程序的剩余部分 — continuation。k返回的AST作用于当前表达式的值，因此需要将值传给k — 但需要比CPS求值器中更抽象的方式来思考：这里我们并没有运行程序，仅仅是进行编译。所以我们操作的不是值，而是代表值和运算的AST。

所以cps_*函数必须调用k（或者将其传递下去）来“执行”程序的剩余部分（事实上是编译剩余程序并得到代表当前节点continuation的AST节点），但它们也必须返回当前调用表达式的AST节点。这是与CPS求值器的另一个不同点，CPS求值器对所有分支都返回undefined，而这里我们返回AST。希望解释完所有cps_*转换器后这些描述会变得清晰。

原子值Atomic values

我们将那些不需要依赖其它代码就可以求值的值称为“原子值”。它们既可以是常量，也可以是变量。我们直接将当前AST节点传给continuation（并返回其结果！）。

function cps_atom(exp, k) {
    return k(exp);
}

binary 和 assign

对于二元运算，我们必须在编译left和right后才能调用其continuation，所以按照这个顺序分别编译，最后将代表等价二元操作的AST节点传给k进行调用（但此时left和right已经是求值后的原子结果）：

function cps_binary(exp, k) {
  return cps(exp.left, function(left) {
    if (exp.operator === '&&') {
      if (left.value === false) {
        return k(left);
      }
      return cps(exp.right, function(right) {
        return k(right);
      });
    } else if (exp.operator === '||') {
      if (left.value === true) {
        return k(left);
      }
      return cps(exp.right, function(right) {
        return k(right);
      });
    }
    return cps(exp.right, function(right) {
      return k({
        type:     exp.type,
        operator: exp.operator,
        left:     left,
        right:    right
      })
    });
  });
}

let节点

我们将let节点转换为立即调用函数表达式（IIFE），然后针对IIFE进行CPS转换。这意味着CPS转换后在AST节点中不会有let节点了（意味着代码生成器中可以将js_let删掉）。

function cps_let(exp, k) {
    if (exp.vars.length == 0)
        return cps(exp.body, k);
    return cps({
        type: "call",
        args: [ exp.vars[0].def || FALSE ],
        func: {
            type: "lambda",
            vars: [ exp.vars[0].name ],
            body: {
                type: "let",
                vars: exp.vars.slice(1),
                body: exp.body
            }
        }
    }, k);
}

lambda节点

首先很清晰的一点，lambda节点的continuation应该是一个lambda节点，比如代码a = λ(x) x + 1;，对λ节点求值的continuation是将其赋值给a，所以continuation将会接收到一个函数。

但将一个函数转换为CPS形式是什么意思？上面代码示例编译的结果是：TC(a = λ(K, x){ K(x + 1) }); （其中TC是赋值表达式的continuation）。所以lambda节点增加其continuation（K）作为第一个参数，并且其body会被编译成将结果传入K进行调用的方式。我们必须引入一个新的变量（当然不会仅使用K）并确保变量名字不会与程序内其它变量冲突。我们可以很严谨地实现，但这里我们假定通过在变量名前面增加"β_"前缀就可以避免可能的变量冲突（事实上确实可行，因为λanguage语言的解析器中，β不是一个合法的字符）。

所以，一共有下面这些步骤：

• 引入一个唯一的变量名（用cont来存储）。
• 调用cps编译函数体，参数continuation会将最终结果传入cont进行调用。
• 传入一个新lambda节点来调用顶层的k，该节点拥有更新过的参数列表（将cont作为第一个参数）以及转换为CPS形式的函数体。

function cps_lambda(exp, k) {
    var cont = gensym("K");
    var body = cps(exp.body, function(body){
        return { type: "call",
                 func: { type: "var", value: cont },
                 args: [ body ] };
    });
    return k({ type: "lambda",
               name: exp.name,
               vars: [ cont ].concat(exp.vars),
               body: body });
}

gensym函数（代表“generate symbol”）应该返回一个唯一的变量名。

// these are global
var GENSYM = 0;
function gensym(name) {
    if (!name) name = "";
    name = "β_" + name;
    return name + (++GENSYM);
}

与其他cps_*函数相比（除了cps_atom），cps_lambda是唯一一个在函数实现主体而不是其自身continuation中调用后续continuation（k）的函数。正是因为lambda实际上是原子值。

if节点

if的编译比较简单：

function cps_if(exp, k) {
    return cps(exp.cond, function(cond){
        return {
            type: "if",
            cond: cond,
            then: cps(exp.then, k),
            else: cps(exp.else || FALSE, k),
        };
    });
}

所以就是编译condition，并传入将返回恰当AST节点（也是一个if节点）的continuation。continuation中会将k作为编译then/else分支的continuation。我们后面会发现这里会有一点小问题。

call节点

call节点必须先对调用的函数进行转换，然后依次对参数进行转换。我们创建一个数组来存储每个参数对应的AST节点，进而完成call节点的编译输出。我们会将程序剩余部分的continuation作为第一个参数，该continuation是make_continuation基于k生成的。

function cps_call(exp, k) {
    return cps(exp.func, function(func){
        return (function loop(args, i){
            if (i == exp.args.length) return {
                type : "call",
                func : func,
                args : args
            };
            return cps(exp.args[i], function(value){
                args[i + 1] = value;
                return loop(args, i + 1);
            });
        })([ make_continuation(k) ], 0);
    });
}

continuation是一个函数，会将call节点返回的值传给程序的剩余部分（k的编译输出）：

function make_continuation(k) {
    var cont = gensym("R");
    return { type : "lambda",
             vars : [ cont ],
             body : k({ type  : "var",
                        value : cont }) };
}

prog节点

处理很简单：如果表达式序列为空则返回false（也就是说以一个FALSE节点来调用程序剩余部分）。如果仅有一个表达式则以其值来调用程序剩余部分。如果更多则首先编译第一个表达式，然后递归编译剩余的表达式。

function cps_prog(exp, k) {
    return (function loop(body){
        if (body.length == 0) return k(FALSE);
        if (body.length == 1) return cps(body[0], k);
        return cps(body[0], function(first){
            return {
                type: "prog",
                prog: [ first, loop(body.slice(1)) ]
            };
        });
    })(exp.prog);
}

可以注意到prog最终返回的AST包含两个表达式（其中第二个可能是另一个prog）。这跟lists的定义方式很相似。AST与前面的代码生成器仍然兼容，可能会稍长一点。

接下来一节中，我们会看一些CPS转换器的示例并指出其中存在的问题。