项目：一门编程语言
求值器是确定编程语言中表达式含义的程序，它本身也只是另一个程序。
——哈尔·阿贝尔森与杰拉尔德·萨斯曼，《计算机程序的构造和解释》
（插图：一个带孔的鸡蛋，内部可见更小的鸡蛋，而这些小鸡蛋内部又有甚至更小的鸡蛋，以此类推）
构建属于自己的编程语言出奇地简单（只要目标不设得太高），而且极具启发性。
本章我想展示的核心观点是：构建编程语言并不存在魔法。我常常觉得某些人类发明极其巧妙复杂，以至于自认为永远无法理解。但经过少量阅读和实践后会发现，它们往往非常平常。
我们将构建一门名为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}
]
}
这种数据结构被称为语法树。如果将对象视为节点、对象间的关联视为节点间的连线（如下图所示），该结构会呈现树状形态。表达式中包含其他表达式（而后者可能再包含更多表达式）的特性，类似于树枝不断分叉的形态。
（https://eloquentjavascript.net/img/syntax_tree.svg示意图：示例程序的语法树结构。根节点标记为'do'，有两个子节点分别标记为'define'和'if'，这些子节点又进一步包含描述其内容的子节点）
这与我们在第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(
`未定义的绑定: ${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("应用非函数值");
}
}
}
}
求值器为每种表达式类型都提供了处理逻辑：
-
字面值表达式直接返回其值（例如表达式
100求值为数字100） - 绑定名称需检查是否在作用域中定义，存在则获取对应值
- 应用表达式处理逻辑更复杂：若是特殊形式（如if），则直接将参数表达式和作用域传给处理函数；若是普通调用，先求值运算符得到函数，再用求值后的参数调用该函数
我们用纯JavaScript函数值表示Egg的函数值，这一点会在定义fun特殊形式时详细说明。
evaluate的递归结构与解析器结构相呼应，两者都镜像了语言本身的结构。也可以将解析器和求值器合并为一个函数，在解析时直接求值，但拆分实现会让程序更清晰灵活。
这就是解释Egg所需的全部核心逻辑，就是这么简单！但如果不定义一些特殊形式并向环境添加有用值，这门语言目前还做不了太多事。
特殊形式
specialForms对象用于定义Egg的特殊语法，将名称与求值这些形式的函数关联，目前它还是空的。先添加if形式：
specialForms.if = (args, scope) => {
if (args.length != 3) {
throw new SyntaxError("if参数数量错误");
} else if (evaluate(args[0], scope) !== false) {
return evaluate(args[1], scope);
} else {
return evaluate(args[2], scope);
}
};
Egg的if结构严格要求3个参数：先求值第一个参数，若结果不是false则求值第二个参数，否则求值第三个参数。这种if形式更像JavaScript的三元运算符?:——它是表达式而非语句，会产生一个值（第二个或第三个参数的求值结果）。
Egg与JavaScript的另一个区别是条件值处理：只有false会被视为假值，0或空字符串等不会被当作假值。
必须将if表示为特殊形式而非普通函数的原因在于：函数的所有参数都会在调用前求值，而if应根据第一个参数的值仅求值第二个或第三个参数。
while形式类似：
specialForms.while = (args, scope) => {
if (args.length != 2) {
throw new SyntaxError("while参数数量错误");
}
while (evaluate(args[0], scope) !== false) {
evaluate(args[1], scope);
}
// 因Egg中不存在undefined，返回false作为无意义结果
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("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));
}
我们将用对象原型链表示嵌套作用域，使程序能在局部作用域添加绑定而不修改顶层作用域。例如计算1到10之和的程序：
run(`
do(define(total, 0),
define(count, 1),
while(<(count, 11),
do(define(total, +(total, count)),
define(count, +(count, 1)))),
print(total))
`);
// → 55
虽然比等价的JavaScript程序更繁琐，但对于用不到150行代码实现的语言来说已经不错了。
函数
没有函数的编程语言是残缺的。好在添加fun结构并不难：它将最后一个参数作为函数体，前面的参数作为函数参数名：
specialForms.fun = (args, scope) => {
if (!args.length) {
throw new SyntaxError("函数需要函数体");
}
let body = args[args.length - 1];
let params = args.slice(0, args.length - 1).map(expr => {
if (expr.type != "word") {
throw new SyntaxError("参数名必须是标识符");
}
return expr.name;
});
return function(...args) {
if (args.length != params.length) {
throw new TypeError("参数数量错误");
}
let localScope = Object.create(scope);
for (let i = 0; i < args.length; i++) {
localScope[params[i]] = args[i];
}
return evaluate(body, localScope);
};
};
Egg的函数有自己的局部作用域：fun生成的函数创建局部作用域并添加参数绑定，然后在该作用域中求值函数体并返回结果。
示例1：定义加1函数并调用：
run(`
do(define(plusOne, fun(a, +(a, 1))),
print(plusOne(10)))
`);
// → 11
示例2：递归定义幂函数：
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对应结构的简单包装，Egg的值也直接使用JavaScript值。要对接更底层的系统（如处理器理解的机器码）需要更多工作，但原理与当前实现类似。
尽管本章的玩具语言在功能上不如JavaScript，但在某些场景下，编写小型语言能更高效地完成实际工作。
这种语言不一定要像传统编程语言。例如若JavaScript没有正则表达式，可自行编写正则表达式的解析器和求值器。
再比如构建一个程序，允许通过提供语言的逻辑描述来快速创建解析器，就可以为该场景定义特定表示法和编译器。例如：
expr = 数字 | 字符串 | 名称 | 应用
数字 = 数字+
名称 = 字母+
字符串 = '"' (! '"')* '"'
应用 = expr '(' (expr (',' expr)*)? ')'
这就是所谓的领域特定语言（DSL），专为表达特定领域知识设计。由于只描述该领域需要的内容，DSL比通用语言更具表达力。
练习
数组
通过向topScope添加以下三个函数为Egg增加数组支持：
-
array(...values)：构造包含参数值的数组 -
length(array)：获取数组长度 -
element(array, n)：获取数组第n个元素
topScope.array = Function("...values", "return values;");
topScope.length = Function("arr", "return arr.length;");
topScope.element = Function("arr, n", "return arr[n];");
测试程序：
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
闭包
Egg的fun定义方式允许函数引用外围作用域，使函数体能使用定义时可见的局部值，这与JavaScript函数的闭包行为一致。
以下程序中，函数f返回的函数将自身参数与f的参数相加，这需要访问f作用域内的绑定a：
run(`
do(define(f, fun(a, fun(b, +(a, b)))),
print(f(4)(5)))
`);
// → 9
原理在于：fun生成的函数通过localScope = Object.create(scope)继承了定义时的作用域（scope参数是定义函数时的作用域）。当内部函数执行时，scope指向f调用时创建的局部作用域，因此能访问a的值。
注释
为Egg添加注释支持：遇到#时将该行剩余部分视为注释忽略，类似JavaScript的//。修改skipSpace函数使其跳过注释（将注释视为空白）：
function skipSpace(string) {
let first = string.search(/\S/);
if (first == -1) return "";
if (string[first] == "#") {
// 跳过#直到行尾
let end = string.indexOf("\n", first);
if (end == -1) end = string.length;
return skipSpace(string.slice(end));
}
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特殊形式，用于更新绑定值：若当前作用域不存在该绑定，则在外层作用域查找；若完全未定义则抛出ReferenceError。
specialForms.set = (args, scope) => {
if (args.length != 2 || args[0].type != "word") {
throw new SyntaxError("set使用错误");
}
let name = args[0].name;
let value = evaluate(args[1], scope);
let currentScope = scope;
// 查找绑定所在的作用域
while (currentScope) {
if (Object.hasOwn(currentScope, name)) {
currentScope[name] = value;
return value;
}
currentScope = Object.getPrototypeOf(currentScope);
}
throw new ReferenceError(`未定义的绑定: ${name}`);
};
测试用例：
run(`
do(define(x, 4),
define(setx, fun(val, set(x, val))),
setx(50),
print(x))
`);
// → 50
run(`set(quux, true)`);
// → ReferenceError: 未定义的绑定: quux
