十二、项目：编程语言

十二、项目：编程语言

确定编程语言中的表达式含义的求值器只是另一个程序。

Hal Abelson 和 Gerald Sussman，《计算机程序的构造和解释》

构建你自己的编程语言不仅简单（只要你的要求不要太高就好），而且对人富有启发。

希望通过本章的介绍，你能发现构建自己的编程语言其实并不是什么难事。我经常感到某些人的想法聪明无比，而且十分复杂，以至于我都不能完全理解。不过经过一段时间的阅读和实验，我就发现它们其实也并没有想象中那么复杂。

我们将创造一门名为 Egg 的编程语言。这是一门小巧而简单的语言，但是足够强大到能描述你所能想到的任何计算。它允许基于函数的简单抽象。

解析

程序设计语言中最直观的部分就是语法（syntax）或符号。解析器是一种程序，负责读入文本片段（包含程序的文本），并产生一系列与程序结构对应的数据结构。若文本不是一个合法程序，解析器应该指出错误。

我们的语言语法简单，而且具有一致性。Egg 中一切都是表达式。表达式可以是绑定名称、数字，或应用（application）。不仅函数调用属于应用，而且if和while之类的语言构造也属于应用。

为了确保解析器的简单性，Egg 中的字符串不支持反斜杠转义符之类的元素。字符串只是简单的字符序列（不包括双引号），并使用双引号包围起来。数值是数字序列。绑定名由任何非空白字符组成，并且在语法中不具有特殊含义。

应用的书写方式与 JavaScript 中一样，也是在一个表达式后添加一对括号，括号中可以包含任意数量的参数，参数之间使用逗号分隔。

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

Egg 语言的一致性体现在：JavaScript 中的所有运算符（比如>）在 Egg 中都是绑定，但是可以像其他函数一样调用。由于语法中没有语句块的概念，因此我们需要使用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 章中编写的配置文件格式解析器进行对比，第 9 章中的解析器结构很简单：将输入文件划分成行，并逐行处理。而且每一行只有几种简单的语法形式。

我们必须使用不同方法来解决这里的问题。Egg 中并没有表达式按行分隔，而且表达式之间还有递归结构。应用表达式包含其他表达式。

所幸我们可以使用递归的方式编写一个解析器函数，并优雅地解决该问题，这反映了语言自身就是递归的。

我们定义了一个函数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函数来包装parseExpression，在解析完表达式之后验证输入是否到达结尾（一个 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}]}

程序可以正常工作了！当表达式解析失败时，解析函数不会输出任何有用的信息，也不会存储出错的行号与列号，而这些信息都有助于之后的错误报告。但考虑到我们的目的，这门语言目前已经足够优秀了。

求值器（evaluator）

在有了一个程序的语法树之后，我们该做什么呢？当然是执行程序了！而这就是求值器的功能。我们将语法树和作用域对象传递给求值器，执行器就会求解语法树中的表达式，然后返回整个过程的结果。

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语句需要三个参数。Egg 会求解第一个参数，若结果不是false，则求解第二个参数，否则求解第三个参数。相较于 JavaScript 中的if语句，Egg 的if形式更类似于 JavaScript 中的?:运算符。这是一条表达式，而非语句，它会产生一个值，即第二个或第三个参数的结果。

Egg 和 JavaScript 在处理条件值时也有些差异。Egg 不会将 0 或空字符串作为假，只有当值确实为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，会自顶向下执行其所有参数。整个do表达式的值是最后一个参数的值。

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

我们还需要创建名为define的形式，来创建绑定对绑定赋值。define的第一个参数是一个单词，第二个参数是一个会产生值的表达式，并将第二个参数的计算结果赋值给第一个参数。由于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语言构造，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 编写一个可供选择的求值策略，首先使用Function，调用 JavaScript 编译器编译代码，将 Egg 程序转换成 JavaScript 程序，接着执行编译结果。若能正确实现该功能，可以使得 Egg 运行的非常快，而且实现这种编译器确实非常简单。

如果读者对该话题感兴趣，愿意花费一些时间在这上面，建议你尝试实现一个编译器作为练习。

站在别人的肩膀上

我们定义if和while的时候，你可能注意到他们封装得或多或少和 JavaScript 自身的if、while有点像。同样的，Egg 中的值也就是 JavaScript 中的值。

如果读者比较一下两种 Egg 的实现方式，一种是基于 JavaScrip t之上，另一种是直接使用机器提供的功能构建程序设计语言，会发现第二种方案需要大量工作才能完成，而且非常复杂。不管怎么说，本章的内容就是想让读者对编程语言的运行方式有一个基本的了解。

当需要完成一些任务时，相比于自己完成所有工作，借助于别人提供的功能是一种更高效的方式。虽然在本章中我们编写的语言就像玩具一样，十分简单，而且无论在什么情况下这门语言都无法与 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

这通常被称为领域特定语言（Domain-specific Language），一种为表达极为有限的知识领域而量身定制的语言。它可以准确描述其领域中需要表达的事物，而没有多余元素。这种语言比通用语言更具表现力。

习题

数组

在 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的方式允许函数引用其周围环境，就像 JavaScript 函数一样，函数体可以使用在定义该函数时可以访问的所有局部绑定。

下面的程序展示了该特性：函数f返回一个函数，该函数将其参数和f的参数相加，这意味着为了使用绑定a，该函数需要能够访问f中的局部作用域。

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