【第2600期】如何用JavaScript实现一门编程语言 - 简单的解释器（Interpreter）

今天继续分享《如何用JavaScript实现一门编程语言》其中的简单的解释器。今日前端早读课文章由@Hong翻译授权分享。

这是《如何用JavaScript实现一门编程语言》专题，是较完整的关于如何使用JavaScript实现一门编程语言的博文。该系列是UglifyJS作者本人所著，声称是简单的教程，但里面很多概念思考还是很值得学习，比如对continuation的讨论，yield以及reset/shift等的实现讨论等。

正文从这开始~~

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

总结一下：目前为止我们写了3个函数：InputStream，TokenStream和parse。我们可以通过下面的方式得到一块代码的AST：

var ast = parse(TokenStream(InputStream(code)));

实现解释器要比解析器简单。仅仅需要遍历AST，按正常顺序执行表达式即可。

环境

准确执行的关键是能够正确地维护环境 - 一个持有各种变量绑定的结构体。环境会作为我们求值函数的一个参数。每次遇到一个 lambda 节点，我们必须用新变量（函数参数）来扩展环境，并使用运行时传入的值来初始化这些变量。如果参数将外层作用域（这里我会交换地使用作用域scope和环境environment两个词）的同名变量覆盖了，我们必须在函数结束时小心地将变量恢复为之前的值。

实现上述机制最简单的方式就是利用JavaScript的原型继承（prototype inheritance）。当进入一个函数时，我们创建一个新的环境，其原型设置为外层环境（父辈环境），函数体基于新的环境来求值。这样当退出函数时，我们不需要做任何事情 - 外层环境（env）已经包含了可能被覆盖的任何同名变量绑定，不用再做任何恢复操作。

下面是环境（Environment）对象的定义：

function Environment(parent) {
    this.vars = Object.create(parent ? parent.vars : null);
    this.parent = parent;
}
Environment.prototype = {
    extend: function() {
        return new Environment(this);
    },
    lookup: function(name) {
        var scope = this;
        while (scope) {
            if (Object.prototype.hasOwnProperty.call(scope.vars, name))
                return scope;
            scope = scope.parent;
        }
    },
    get: function(name) {
        if (name in this.vars)
            return this.vars[name];
        throw new Error("Undefined variable " + name);
    },
    set: function(name, value) {
        var scope = this.lookup(name);
        // let's not allow defining globals from a nested environment
        if (!scope && this.parent)
            throw new Error("Undefined variable " + name);
        return (scope || this).vars[name] = value;
    },
    def: function(name, value) {
        return this.vars[name] = value;
    }
};

一个环境对象有一个父辈属性parent指向父辈作用域。对于全局作用域（global scope）这个属性是null。环境对象上还有一个vars属性持有各种变量绑定。为了能通过原型继承得到当前的变量绑定，对于顶层全局作用域，vars初始化为Object.create(null)，对于子作用域，会初始化为Object.create(parent.vars)。

环境对象支持下面这些方法：

• extend() — 创建一个子作用域。

• lookup(name) — 寻找给定名字的变量所定义的作用域。

• get(name) — 得到变量的当前值。如果变量未定义会抛出一个错误。

• set(name, value) — 设置一个变量的值。需要寻找变量定义的真实作用域。如果没有找到该作用域，并且也不在全局作用域，会抛出错误。

• def(name, value) — 在当前作用域上创建一个变量。

求值函数（evaluate function）

现在有了环境，我们可以来处理主要的问题了。函数是一个大的switch语句，通过节点类型调度执行各节点的求值逻辑。我来一一解说每一种情况。

function evaluate(exp, env) {
    switch (exp.type) {

对于常量节点，直接返回它们的值：

case "num":
    case "str":
    case "bool":
        return exp.value;

从环境中取出变量的值。记住 var 节点的value属性记录了变量的名字。

case "var":
    return env.get(exp.value);

对于赋值节点，我们需要检查左侧是否是一个 var 节点（如果不是，则抛出一个错误；我们现在还不支持其他类型节点的赋值）。然后可以使用env.set来给变量设置值。注意变量值需要事先通过递归调用求值函数来得到。

case "assign":
    if (exp.left.type != "var")
        throw new Error("Cannot assign to " + JSON.stringify(exp.left));
    return env.set(exp.left.value, evaluate(exp.right, env));

一个二元表达式 binary 节点需要应用一个操作符到两个操作数上。我们后面会来写apply_op函数，相当简单。同样，我们需要递归调用求值函数来计算左右操作数：

case "binary":
    var left = evaluate(exp.left, env);
    if (exp.operator === "&&") {
        return left !== false && evaluate(exp.right, env);
    }
    if (exp.operator === "||") {
        return left !== false ? left : evaluate(exp.right, env);
    }
    return apply_op(exp.operator,left,evaluate(exp.right, env));

一个函数 lambda 节点实际是通过一个JavaScript闭包实现，所以在JavaScript中可以像普通函数一样调用。写了一个make_lambda函数，后续会进行定义：

case "lambda":
    return make_lambda(env, exp);

if 节点求值很简单：首先对条件condition求值。如果值不是 false，则继续对 then 分支求值。否则，如果有 else 分支，则对其求值，否则返回 false。

case "if":
    var cond = evaluate(exp.cond, env);
    if (cond !== false) return evaluate(exp.then, env);
        return exp.else ? evaluate(exp.else, env) : false;

prog 节点是一个表达式序列。按顺序对每个表达式求值，并返回最后一个表达式的值。如果表达式序列为空，则返回值为false。

case "prog":
    var val = false;
    exp.prog.forEach(function(exp){ val = evaluate(exp, env) });
    return val;

call 节点求值需要调用一个函数。首先对func属性求值，应该返回一个普通的JS函数，接着对args属性求值，并传给前面返回的函数来调用。

case "call":
    var func = evaluate(exp.func, env);
    return func.apply(null, exp.args.map(function(arg){
        return evaluate(arg, env);
    }));

永远不应该执行到这里，只有当我们解析器中增加了新的节点类型，并且忘记更新求值函数，才会执行到这个分支，抛出一个清晰的错误。

default:
    throw new Error("I don't know how to evaluate " + exp.type);
    }
}

上面就是求值函数的核心，正如你所看到的，是不是相当简单。我们还需要写两个函数，首先开始最简单的apply_op：

function apply_op(op, a, b) {
    function num(x) {
        if (typeof x != "number")
            throw new Error("Expected number but got " + x);
        return x;
    }
    function div(x) {
        if (num(x) == 0)
            throw new Error("Divide by zero");
        return x;
    }
    switch (op) {
      case "+"  : return num(a) + num(b);
      case "-"  : return num(a) - num(b);
      case "*"  : return num(a) * num(b);
      case "/"  : return num(a) / div(b);
      case "%"  : return num(a) % div(b);
      // pre-process in evaluate avoid imporperly expression evaluation
      // for a() && b() or a() || b()
      // case "&&": return a !== false && b;
      // case "||": return a !== false ? a : b;
      case "<"  : return num(a) < num(b);
      case ">"  : return num(a) > num(b);
      case "<=" : return num(a) <= num(b);
      case ">=" : return num(a) >= num(b);
      case "==" : return a === b;
      case "!=" : return a !== b;
    }
    throw new Error("Can't apply operator " + op);
}

函数接受操作符和参数。通过一个swtich语句来来应用操作符。不像JavaScript，将任意操作符应用到任意参数进而判断操作是否合理，我们要求数字型操作符的操作数需要是数字，除数不能是0，通过使用num和div小工具函数来保证这些。对于字符串我们将会定义其它的工具函数。

make_lambda

make_lambda函数有一点巧妙：

function make_lambda(env, exp) {
    function lambda() {
        var names = exp.vars;
        var scope = env.extend();
        for (var i = 0; i < names.length; ++i)
            scope.def(names[i], i < arguments.length ? arguments[i] : false);
        return evaluate(exp.body, scope);
    }
    return lambda;
}

正如你看到的，make_lambda返回一个引用了环境对象和将要求值表达式的普通JavaScript函数。闭包创建的时候什么都不会做，但当被调用时，在创建时保存的环境对象将会由函数参数/传值所扩展（如果传递的值少于函数表达式定义时的参数个数，未被赋值的参数将初始化为 false）。接着在新的作用域下对表达式的函数体进行求值。

原始功能函数（Primitive functions）

你可能察觉到 λanguage 语言没有提供与外界交互的方式。某些代码示例中使用了print和println函数，但是它们还未定义。这些需要定义为原始功能函数（也就是说，我们通过JavaScript实现它们，并插入到全局环境）。

所有功能汇集到一起，有了下面的测试程序：

// some test code here
var code = "sum = lambda(x, y) x + y; print(sum(2, 3));";

// remember, parse takes a TokenStream which takes an InputStream
var ast = parse(TokenStream(InputStream(code)));

// create the global environment
var globalEnv = new Environment();

// define the "print" primitive function
globalEnv.def("print", function(txt){
  console.log(txt);
});

// run the evaluator
evaluate(ast, globalEnv); // will print 5

下载

可以下载到目前为止的代码lambda-eval.js。能够在NodeJS下执行 - 将代码传入标准输入来求值，例如：

lambda-eval.js:https://llwanghong.github.io/assets/js/js_lambdalang_implement/interpreter/lambda-eval.js

echo 'sum = lambda(x, y) x + y; println(sum(2, 3));' | nodelambda-eval1.js

关于本文
译者：@Hong
译文：https://zhuanlan.zhihu.com/p/452614640
作者：@Mihai Bazon
原文：https://lisperator.net/pltut/eval1/

相关阅读

欢迎自荐投稿，前端早读课等你来。