第 12 章项目：一种编程语言

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

构建你自己的编程语言，说起来容易做起来难，但收获颇丰（只要你不过于追求复杂）。

本章主要想说明的是，构建你自己的语言，并不存在什么神奇的魔法。我常常觉得，人类的一些发明创造，无比巧妙复杂，我永远也无法理解。但只要稍微阅读研究，亲身尝试，往往就会发现，其实也没那么神秘。

我们将构建一种名为 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);
  let 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) {
  let first = string.search(/\S/);
  if (first == -1) return "";
  return string.slice(first);
}

由于 Egg 像 JavaScript 一样允许在元素之间放置任意数量的空白字符，我们必须反复从程序字符串的开头删除空白字符。这就是 skipSpace 函数的用武之地。

在跳过任何前导空格后，parseExpression 使用三个正则表达式来识别 Egg 支持的三个原子元素：字符串、数字和词。解析器根据匹配的类型构建不同类型的数据结构。如果输入不匹配这三种形式之一，那么它就不是一个有效的表达式，解析器会抛出一个错误。我们使用 SyntaxError 而不是 Error 作为异常构造函数，它是另一种标准错误类型，因为更具体一些——它也是在尝试运行无效 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] != ")") {
    let 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) {
  let {expr, rest} = parseExpression(program);
  if (skipSpace(rest).length > 0) {
    throw new SyntaxError("Unexpected text after program");
  }
  return expr;
}

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

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

评估器

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

const specialForms = Object.create(null);

function evaluate(expr, scope) {
  if (expr.type == "value") {
    return expr.value;
  } else if (expr.type == "word") {
    if (expr.name in scope) {
      return scope[expr.name];
    } else {
      throw new ReferenceError(
        `Undefined binding: ${expr.name}`);
    }
  } else if (expr.type == "apply") {
    let {operator, args} = expr;
    if (operator.type == "word" &&
        operator.name in specialForms) {
      return specialForms[operator.name](expr.args, scope);
    } else {
      let op = evaluate(operator, scope);
      if (typeof op == "function") {
        return op(...args.map(arg => evaluate(arg, scope)));
      } else {
        throw new TypeError("Applying a non-function.");
      }
    }
  }
}

评估器为每种表达式类型都有代码。字面量值表达式产生它的值。（例如，表达式 100 只是评估为数字 100。）对于绑定，我们必须检查它是否确实在范围内定义，如果是，则获取绑定的值。

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

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

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

这确实是解释 Egg 所需的一切。就这么简单。但如果不对一些特殊形式进行定义，也不向环境添加一些有用的值，你目前还无法在这门语言中做太多事情。

特殊形式

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

specialForms.if = (args, scope) => {
  if (args.length != 3) {
    throw new SyntaxError("Wrong number of args to if");
  } else if (evaluate(args[0], scope) !== false) {
    return evaluate(args[1], scope);
  } else {
    return evaluate(args[2], scope);
  }
};

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

Egg 在处理 `if` 条件值方面也与 JavaScript 不同。它不会将零或空字符串视为假，只有明确的 `false` 值才会被视为假。

我们将 `if` 表示为特殊形式而不是普通函数的原因是，所有函数参数都在函数调用之前被求值，而 `if` 应该只根据第一个参数的值求值第二个或第三个参数中的一个。

`while` 形式类似。

specialForms.while = (args, scope) => {
  if (args.length != 2) {
    throw new SyntaxError("Wrong number of args to while");
  }
  while (evaluate(args[0], scope) !== false) {
    evaluate(args[1], scope);
  }

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

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

specialForms.do = (args, scope) => {
  let value = false;
  for (let arg of args) {
    value = evaluate(arg, scope);
  }
  return value;
};

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

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

环境

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

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

const topScope = Object.create(null);

topScope.true = true;
topScope.false = false;

我们现在可以评估一个简单表达式，该表达式否定一个布尔值。

let prog = parse(`if(true, false, true)`);
console.log(evaluate(prog, topScope));
// → false

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

for (let op of ["+", "-", "*", "/", "==", "<", ">"]) {
  topScope[op] = Function("a, b", `return a ${op} b;`);
}

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

topScope.print = value => {
  console.log(value);
  return value;
};

这给了我们足够的初级工具来编写简单的程序。以下函数提供了一种方便的方法来解析程序并在新的作用域中运行它

function run(program) {
  return evaluate(parse(program), Object.create(topScope));
}

我们将使用对象原型链来表示嵌套作用域，以便程序可以在不改变顶层作用域的情况下将绑定添加到其本地作用域。

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 = (args, scope) => {
  if (!args.length) {
    throw new SyntaxError("Functions need a body");
  }
  let body = args[args.length - 1];
  let params = args.slice(0, args.length - 1).map(expr => {
    if (expr.type != "word") {
      throw new SyntaxError("Parameter names must be words");
    }
    return expr.name;
  });

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

Egg 中的函数拥有自己的本地作用域。由 `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 程序，使用 `Function` 在其上调用 JavaScript 编译器，然后运行结果。如果做得正确，这将使 Egg 运行得非常快，同时仍然非常容易实现。

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

作弊

当我们定义 `if` 和 `while` 时，您可能注意到它们或多或少是 JavaScript 自己的 `if` 和 `while` 的简单包装。同样，Egg 中的值只是普通的 JavaScript 值。

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

在完成事情方面，作弊比自己做所有事情更有效。虽然本章中的玩具语言没有做任何 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(...values)` 用于构造包含参数值的数组，`length(array)` 用于获取数组的长度，以及 `element(array, n)` 用于从数组中获取第 n 个元素。

// Modify these definitions...

topScope.array = "...";

topScope.length = "...";

topScope.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) {
  let 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`。此结构既可以定义新的绑定，也可以为现有的绑定赋予新值。

这种歧义会导致问题。当您尝试为非局部绑定赋予新值时，最终将定义一个具有相同名称的局部绑定。某些语言的设计就是如此，但我一直觉得这是一种处理范围的笨拙方式。

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

到目前为止，将作用域表示为简单对象的技巧使事情变得很方便，但在这一点上会阻碍您的前进。您可能希望使用 Object.getPrototypeOf 函数，该函数返回对象的原型。还要记住作用域不会从 Object.prototype 派生，因此如果您想对它们调用 hasOwnProperty，则必须使用以下笨拙的表达式

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

specialForms.set = (args, scope) => {
  // 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