项目：编程语言

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

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

在本章中，我最想展示的是，创建编程语言并没有什么魔法。我常常觉得，人类的一些发明是如此聪明和复杂，以至于我永远无法理解它们。但通过一些阅读和实验，它们通常会变得相当平庸。

我们将构建一种名为 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一样，是标准定义的异常类，但更具体。

然后，我们从程序字符串中截断匹配的部分，并将该部分与表达式的对象一起传递给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(...args) {
    if (args.length != params.length) {
      throw new TypeError("Wrong number of arguments");
    }
    let localScope = Object.create(scope);
    for (let i = 0; i < args.length; i++) {
      localScope[params[i]] = args[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 值。桥接与更原始的系统（如处理器理解的机器码）之间的差距需要更多努力 - 但其工作方式类似于我们在这里所做的。

虽然本章的玩具语言没有做任何在 JavaScript 中无法做得更好的事情，但确实存在编写小型语言有助于完成实际工作的情况。

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

或者想象一下，您正在构建一个程序，该程序可以通过提供要解析的语言的逻辑描述来快速创建解析器。您可以为此定义一个特定的符号，以及一个将其编译为解析器程序的编译器。

expr = number | string | name | application

number = digit+

name = letter+

string = '"' (! '"')* '"'

application = expr '(' (expr (',' expr)*)? ')'

这通常被称为领域特定语言，一种专门用于表达狭窄领域知识的语言。这种语言比通用语言更具表达力，因为它被设计成只描述其领域中需要描述的东西，而不会描述其他任何东西。

练习

数组

通过将以下三个函数添加到顶层范围来为 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.hasOwn` 来找出给定对象是否具有某个属性。

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