第 11 章

项目：一种编程语言

评估器，它决定编程语言中表达式的含义，仅仅是另一个程序。

当一个学生问大师关于数据和控制循环的本质时，元马回答说：“想想一个编译器，它自己编译自己。”

构建你自己的编程语言出奇地容易（只要你不设定过高的目标），并且非常有启发性。

我在本章中主要想说明的是，构建自己的语言并不需要什么魔法。我经常觉得，人类的一些发明是如此聪明复杂，我永远无法理解它们。但是通过一点阅读和摸索，这些东西往往变得相当平凡。

我们将构建一种叫做 Egg 的编程语言。它将是一种微小的、简单的语言，但功能强大到足以表达你能想到的任何计算。它还将允许基于函数的简单抽象。

解析

编程语言最直观的组成部分是其语法或符号。解析器是一个程序，它读取一段文本并生成一个反映该文本中包含的程序结构的数据结构。如果文本不构成有效的程序，解析器应该抱怨并指出错误。

我们的语言将拥有简单且统一的语法。Egg 中的一切都是表达式。表达式可以是变量、数字、字符串或应用。应用用于函数调用，但也用于诸如if或while之类的构造。

为了使解析器保持简单，Egg 中的字符串不支持诸如反斜杠转义之类的任何内容。字符串仅仅是双引号括起来的、不包含双引号的一系列字符。数字是一系列数字。变量名可以包含任何不是空格并且在语法中没有特殊含义的字符。

应用就像在 JavaScript 中那样编写，在表达式后面加上括号，并在括号之间包含任意数量的参数，用逗号分隔。

do(define(x, 10),
   if(>(x, 5),
      print("large"),
      print("small")))

Egg 语言的统一性意味着在 JavaScript 中充当运算符（例如>）的东西在该语言中是普通变量，应用方式与其他函数相同。而且由于语法没有块的概念，我们需要一个do构造来表示按顺序执行多个操作。

解析器将用于描述程序的数据结构将由表达式对象组成，每个表达式对象都有一个type属性，表示它的表达式类型，以及其他属性来描述其内容。

类型为"value"的表达式表示文字字符串或数字。它们的value属性包含它们表示的字符串或数字值。类型为"word"的表达式用于标识符（名称）。这样的对象具有一个name属性，该属性保存标识符的名称（作为字符串）。最后，"apply"表达式表示应用。它们具有一个operator属性，它引用正在应用的表达式，以及一个args属性，它引用一个参数表达式的数组。

前面的程序中的>(x, 5)部分将表示为：

{
  type: "apply",
  operator: {type: "word", name: ">"},
  args: [
    {type: "word", name: "x"},
    {type: "value", value: 5}
  ]
}

这样的数据结构称为语法树。如果你将对象想象成点，将它们之间的链接想象成这些点之间的线，它就会呈现出树状形状。表达式包含其他表达式，而其他表达式又可能包含更多表达式，这与分支不断分叉的方式类似。

将此与我们在第 9 章中为配置文件格式编写的解析器进行对比，该解析器具有简单的结构：它将输入分成行并逐行处理。一行只允许有几种简单的形式。

在这里，我们必须找到一种不同的方法。表达式并没有分成行，它们具有递归结构。应用表达式包含其他表达式。

幸运的是，这个问题可以通过编写一个解析函数来优雅地解决，该函数以反映语言递归本质的方式递归。

我们定义了一个名为parseExpression的函数，它接受一个字符串作为输入并返回一个对象，该对象包含字符串开头处的表达式的结构数据以及解析该表达式后剩余的字符串部分。当解析子表达式（例如应用的参数）时，可以再次调用此函数，它将产生参数表达式以及剩余的文本。该文本可能依次包含更多参数，也可能是结束参数列表的右括号。

这是解析器的第一部分：

function parseExpression(program) {
  program = skipSpace(program);
  var match, expr;
  if (match = /^"([^"]*)"/.exec(program))
    expr = {type: "value", value: match[1]};
  else if (match = /^\d+\b/.exec(program))
    expr = {type: "value", value: Number(match[0])};
  else if (match = /^[^\s(),"]+/.exec(program))
    expr = {type: "word", name: match[0]};
  else
    throw new SyntaxError("Unexpected syntax: " + program);

  return parseApply(expr, program.slice(match[0].length));
}

function skipSpace(string) {
  var first = string.search(/\S/);
  if (first == -1) return "";
  return string.slice(first);
}

因为 Egg 允许在其元素之间使用任意数量的空格，所以我们必须重复地从程序字符串的开头剪掉空格。这就是skipSpace函数的用处。

跳过任何前导空格后，parseExpression使用三个正则表达式来识别 Egg 支持的三个简单（原子）元素：字符串、数字和词。解析器根据匹配的结果构造不同的数据结构。如果输入与这三个形式中的任何一个都不匹配，则它不是有效的表达式，解析器会抛出一个错误。SyntaxError是一种标准的错误对象类型，它会在尝试运行无效的 JavaScript 程序时引发。

然后，我们可以从程序字符串中剪掉我们匹配的部分，并将其与表达式的对象一起传递给parseApply，它会检查表达式是否为应用。如果是，它会解析一个带括号的参数列表。

function parseApply(expr, program) {
  program = skipSpace(program);
  if (program[0] != "(")
    return {expr: expr, rest: program};

  program = skipSpace(program.slice(1));
  expr = {type: "apply", operator: expr, args: []};
  while (program[0] != ")") {
    var arg = parseExpression(program);
    expr.args.push(arg.expr);
    program = skipSpace(arg.rest);
    if (program[0] == ",")
      program = skipSpace(program.slice(1));
    else if (program[0] != ")")
      throw new SyntaxError("Expected ',' or ')'");
  }
  return parseApply(expr, program.slice(1));
}

如果程序中的下一个字符不是左括号，则这不是应用，parseApply只会返回它被赋予的表达式。

否则，它会跳过左括号并为该应用表达式创建语法树对象。然后它会递归地调用parseExpression来解析每个参数，直到找到右括号为止。递归是间接的，通过parseApply和parseExpression相互调用。

因为应用表达式本身可以应用（例如在multiplier(2)(1)中），所以parseApply必须在解析完应用后再次调用自身来检查后面是否跟着另一对括号。

这就是解析 Egg 所需的一切。我们将其包装在一个方便的parse函数中，该函数会在解析完表达式后验证它是否已到达输入字符串的末尾（Egg 程序是一个表达式），并且它会为我们提供程序的结构数据。

function parse(program) {
  var result = parseExpression(program);
  if (skipSpace(result.rest).length > 0)
    throw new SyntaxError("Unexpected text after program");
  return result.expr;
}

console.log(parse("+(a, 10)"));
// → {type: "apply",
//    operator: {type: "word", name: "+"},
//    args: [{type: "word", name: "a"},
//           {type: "value", value: 10}]}

它起作用了！当它失败时，它不会给我们提供非常有用的信息，并且不会存储每个表达式开始的行和列，这在以后报告错误时可能会有所帮助，但它对我们的目的已经足够了。

评估器

我们可以用程序的语法树做什么？当然是用它来运行程序！而这就是评估器所做的事情。你给它一个语法树和一个环境对象，该对象将名称与值相关联，它会评估树所表示的表达式并返回该表达式生成的返回值。

function evaluate(expr, env) {
  switch(expr.type) {
    case "value":
      return expr.value;

    case "word":
      if (expr.name in env)
        return env[expr.name];
      else
        throw new ReferenceError("Undefined variable: " +
                                 expr.name);
    case "apply":
      if (expr.operator.type == "word" &&
          expr.operator.name in specialForms)
        return specialForms[expr.operator.name](expr.args,
                                                env);
      var op = evaluate(expr.operator, env);
      if (typeof op != "function")
        throw new TypeError("Applying a non-function.");
      return op.apply(null, expr.args.map(function(arg) {
        return evaluate(arg, env);
      }));
  }
}

var specialForms = Object.create(null);

评估器为每种表达式类型都有代码。文字值表达式只产生它的值。（例如，表达式100只评估为数字 100。）对于变量，我们必须检查它是否真的在环境中定义，如果是，则获取变量的值。

应用更复杂。如果它们是特殊形式，比如if，我们不会评估任何东西，而只是将参数表达式以及环境传递给处理这种形式的函数。如果它是普通的调用，我们评估运算符，验证它是否是函数，并用评估参数的结果调用它。

我们将使用普通的 JavaScript 函数值来表示 Egg 的函数值。我们将在稍后回到这个问题，届时将定义名为fun的特殊形式。

evaluate的递归结构类似于解析器的结构。两者都反映了语言本身的结构。也可以将解析器与评估器集成在一起，并在解析过程中进行评估，但将它们分开会使程序更易读。

这确实是解释 Egg 所需的一切。它就是这么简单。但如果不定义一些特殊形式并且不向环境中添加一些有用的值，你就无法使用这种语言。

特殊形式

specialForms对象用于定义 Egg 中的特殊语法。它将词语与评估这些特殊形式的函数相关联。它目前是空的。让我们添加一些形式。

specialForms["if"] = function(args, env) {
  if (args.length != 3)
    throw new SyntaxError("Bad number of args to if");

  if (evaluate(args[0], env) !== false)
    return evaluate(args[1], env);
  else
    return evaluate(args[2], env);
};

Egg 的if构造期望正好三个参数。它会评估第一个参数，如果结果不是值false，它会评估第二个参数。否则，第三个参数将被评估。这种if形式与 JavaScript 的三元?:运算符更相似，而不是 JavaScript 的if。它是一个表达式，而不是语句，它产生一个值，即第二个或第三个参数的结果。

Egg 与 JavaScript 在处理if的条件值方面有所不同。它不会将诸如零或空字符串之类的值视为假，而只将精确的值false视为假。

我们需要将if表示为特殊形式的原因是，函数的所有参数都在调用函数之前被评估，而if应该只评估其第二个或第三个参数，具体取决于第一个参数的值。

while形式类似。

specialForms["while"] = function(args, env) {
  if (args.length != 2)
    throw new SyntaxError("Bad number of args to while");

  while (evaluate(args[0], env) !== false)
    evaluate(args[1], env);

  // Since undefined does not exist in Egg, we return false,
  // for lack of a meaningful result.
  return false;
};

另一个基本构建块是do，它从上到下执行所有参数。它的值是由最后一个参数产生的值。

specialForms["do"] = function(args, env) {
  var value = false;
  args.forEach(function(arg) {
    value = evaluate(arg, env);
  });
  return value;
};

为了能够创建变量并赋予它们新值，我们还创建了一种名为define的形式。它期望第一个参数是一个词语，第二个参数是一个表达式，用于生成要分配给该词语的值。由于define像所有事物一样是一个表达式，它必须返回一个值。我们将使其返回分配的值（就像 JavaScript 的=运算符一样）。

specialForms["define"] = function(args, env) {
  if (args.length != 2 || args[0].type != "word")
    throw new SyntaxError("Bad use of define");
  var value = evaluate(args[1], env);
  env[args[0].name] = value;
  return value;
};

环境

evaluate接受的环境是一个对象，其属性名称对应于变量名，属性值对应于这些变量绑定的值。让我们定义一个环境对象来表示全局范围。

为了能够使用我们刚刚定义的if结构，我们必须访问布尔值。由于只有两个布尔值，我们不需要为它们使用特殊的语法。我们只需将两个变量绑定到true和false的值，并使用它们。

var topEnv = Object.create(null);

topEnv["true"] = true;
topEnv["false"] = false;

现在我们可以评估一个简单的表达式，该表达式对布尔值取反。

var prog = parse("if(true, false, true)");
console.log(evaluate(prog, topEnv));
// → false

为了提供基本的算术运算符和比较运算符，我们还将向环境添加一些函数值。为了使代码简短，我们将使用new Function在一个循环中合成一堆运算符函数，而不是单独定义它们。

["+", "-", "*", "/", "==", "<", ">"].forEach(function(op) {
  topEnv[op] = new Function("a, b", "return a " + op + " b;");
});

一种输出值的方法也很有用，因此我们将把console.log封装在一个函数中，并将其称为print。

topEnv["print"] = function(value) {
  console.log(value);
  return value;
};

这给了我们足够的初级工具来编写简单的程序。以下run函数提供了一种编写和运行它们的方法。它创建一个新的环境，解析并评估我们给它的字符串作为一个单独的程序。

function run() {
  var env = Object.create(topEnv);
  var program = Array.prototype.slice
    .call(arguments, 0).join("\n");
  return evaluate(parse(program), env);
}

使用Array.prototype.slice.call是一种技巧，它将类数组对象（如arguments）转换为真正的数组，以便我们可以在其上调用join。它将所有传递给run的参数视为程序的行。

run("do(define(total, 0),",
    "   define(count, 1),",
    "   while(<(count, 11),",
    "         do(define(total, +(total, count)),",
    "            define(count, +(count, 1)))),",
    "   print(total))");
// → 55

这是我们之前多次见过的程序，它计算 1 到 10 的数字之和，用 Egg 表达。它显然比等效的 JavaScript 程序更丑陋，但对于一个用不到 150 行代码实现的语言来说还不错。

函数

没有函数的编程语言确实是一种糟糕的编程语言。

幸运的是，添加fun结构并不难，它将最后一个参数视为函数体，并将之前的参数视为函数参数的名称。

specialForms["fun"] = function(args, env) {
  if (!args.length)
    throw new SyntaxError("Functions need a body");
  function name(expr) {
    if (expr.type != "word")
      throw new SyntaxError("Arg names must be words");
    return expr.name;
  }
  var argNames = args.slice(0, args.length - 1).map(name);
  var body = args[args.length - 1];

  return function() {
    if (arguments.length != argNames.length)
      throw new TypeError("Wrong number of arguments");
    var localEnv = Object.create(env);
    for (var i = 0; i < arguments.length; i++)
      localEnv[argNames[i]] = arguments[i];
    return evaluate(body, localEnv);
  };
};

Egg 中的函数有自己的局部环境，就像 JavaScript 中一样。我们使用Object.create创建一个新对象，该对象可以访问外部环境中的变量（其原型），但也可以包含新变量而不修改该外部范围。

由fun形式创建的函数创建此局部环境并向其中添加参数变量。然后，它在这个环境中评估函数体并返回结果。

run("do(define(plusOne, fun(a, +(a, 1))),",
    "   print(plusOne(10)))");
// → 11

run("do(define(pow, fun(base, exp,",
    "     if(==(exp, 0),",
    "        1,",
    "        *(base, pow(base, -(exp, 1)))))),",
    "   print(pow(2, 10)))");
// → 1024

编译

我们构建的是一个解释器。在评估期间，它直接作用于解析器生成的程序表示。

编译是在解析和运行程序之间添加另一个步骤的过程，该步骤将程序转换为可以更有效地评估的东西，通过尽可能提前完成工作。例如，在设计良好的语言中，对于每个变量的使用，很明显使用的是哪个变量，而不必实际运行程序。这可以用于避免在每次访问变量时都按名称查找变量，并直接从某个预先确定的内存位置获取变量。

传统上，编译涉及将程序转换为机器代码，即计算机处理器可以执行的原始格式。但任何将程序转换为不同表示的过程都可以被认为是编译。

可以编写 Egg 的另一种评估策略，该策略首先将程序转换为 JavaScript 程序，使用new Function在它上调用 JavaScript 编译器，然后运行结果。如果操作正确，这将使 Egg 运行得非常快，同时仍然非常易于实现。

如果您对这个主题感兴趣并愿意花一些时间，我鼓励您尝试实现这样一个编译器作为练习。

作弊

当我们定义if和while时，您可能已经注意到它们或多或少只是 JavaScript 自身if和while的简单包装。类似地，Egg 中的值只是普通的旧 JavaScript 值。

如果您将构建在 JavaScript 之上的 Egg 的实现与直接在机器提供的原始功能上构建编程语言所需的工作量和复杂度进行比较，差异是巨大的。无论如何，这个例子希望让您对编程语言的工作方式有所了解。

在完成工作方面，作弊比自己做所有事情更有效。虽然本章中的玩具语言并没有做任何 JavaScript 做不到的事情，但确实存在编写小型语言有助于完成实际工作的情况。

这种语言不必类似于典型的编程语言。如果 JavaScript 没有配备正则表达式，您可以为这种子语言编写自己的解析器和评估器。

或者想象您正在建造一个巨大的机器人恐龙，需要对其行为进行编程。JavaScript 可能不是最有效的方法。您可能选择使用看起来像这样的语言

behavior walk
  perform when
    destination ahead
  actions
    move left-foot
    move right-foot

behavior attack
  perform when
    Godzilla in-view
  actions
    fire laser-eyes
    launch arm-rockets

这通常被称为领域特定语言，一种专门用于表达狭窄知识领域的语言。这种语言可能比通用语言更具表现力，因为它旨在精确表达其领域中需要表达的内容，除此之外没有其他内容。

练习

数组

通过将以下三个函数添加到顶级范围，为 Egg 添加对数组的支持：array(...)用于构造包含参数值的数组，length(array)用于获取数组的长度，element(array, n)用于从数组中获取第 n 个元素。

// Modify these definitions...

topEnv["array"] = "...";

topEnv["length"] = "...";

topEnv["element"] = "...";

run("do(define(sum, fun(array,",
    "     do(define(i, 0),",
    "        define(sum, 0),",
    "        while(<(i, length(array)),",
    "          do(define(sum, +(sum, element(array, i))),",
    "             define(i, +(i, 1)))),",
    "        sum))),",
    "   print(sum(array(1, 2, 3))))");
// → 6

闭包

我们定义fun的方式允许 Egg 中的函数“闭包”周围的环境，允许函数体使用在定义函数时可见的局部值，就像 JavaScript 函数一样。

以下程序说明了这一点：函数f返回一个函数，该函数将它的参数添加到f的参数，这意味着它需要访问f内部的局部范围才能使用变量a。

run("do(define(f, fun(a, fun(b, +(a, b)))),",
    "   print(f(4)(5)))");
// → 9

回到fun形式的定义，并解释哪种机制导致了这一点。

注释

如果我们能在 Egg 中编写注释，那就太好了。例如，无论何时找到井号 (#)，我们都可以将该行的其余部分视为注释并忽略它，类似于 JavaScript 中的//。

我们不必对解析器进行任何重大更改来支持它。我们只需更改skipSpace以跳过注释，就像它们是空格一样，这样所有调用skipSpace的地方现在也会跳过注释。进行此更改。

// This is the old skipSpace. Modify it...
function skipSpace(string) {
  var first = string.search(/\S/);
  if (first == -1) return "";
  return string.slice(first);
}

console.log(parse("# hello\nx"));
// → {type: "word", name: "x"}

console.log(parse("a # one\n   # two\n()"));
// → {type: "apply",
//    operator: {type: "word", name: "a"},
//    args: []}

修复范围

目前，分配变量值的唯一方法是define。此结构既充当定义新变量的方法，也充当赋予现有变量新值的 方法。

这种歧义会导致问题。当您尝试为非局部变量赋予新值时，您最终会定义一个具有相同名称的局部变量。（某些语言通过设计的方式工作，但我一直认为这是一种处理范围的愚蠢方式。）

添加一个特殊形式set，类似于define，它为变量赋予一个新值，如果变量在内部范围内不存在，则更新外部范围中的变量。如果变量根本没有定义，则抛出ReferenceError（这是另一种标准错误类型）。

将范围表示为简单对象的技术使事情变得方便，但到目前为止，它会有点妨碍你。您可能想要使用Object.getPrototypeOf函数，它返回对象的原型。还要记住，范围不是从Object.prototype派生的，因此如果您想对它们调用hasOwnProperty，您必须使用以下笨拙的表达式

Object.prototype.hasOwnProperty.call(scope, name);

这从Object原型中获取hasOwnProperty方法，然后在范围对象上调用它。

specialForms["set"] = function(args, env) {
  // Your code here.
};

run("do(define(x, 4),",
    "   define(setx, fun(val, set(x, val))),",
    "   setx(50),",
    "   print(x))");
// → 50
run("set(quux, true)");
// → Some kind of ReferenceError