背景
平时我们写代码的时候，字符串通常会被当做 “数据” 或 “配置” 来使用，几乎不会被用来表示一段 “业务逻辑”。
比如，当我们实现阶乘 n! 的时候，下意识中我们会这样实现，
const fact = n => n == 0 ? 1 : n * fact(n - 1);
fact(5); // 120
却一般不会想到用算术表达式来写，
calc('5!');
calc('1 + 2 * 3');
calc('√2');
而当我们在浏览器页面中寻找所有 script 元素的时候，会这样做，
document.querySelectorAll('script');
而不是去遍历整个 DOM 树来实现。
有时用字符串来处理问题会非常简洁，但我们自己却很少这样做，为了打开脑洞，本文来分享一个简单的字符串处理程序应该怎样编写。
极简主义
日常所用的那些编程语言，包含了很多不得不处理的边界场景，所以让它跑起来是挺麻烦的。
但是我们并不需要如此，为了说明问题，可以秉持极简主义，看看让字符串跑起来，最少需要多少工作。
例如，我们打算在 JS 中这样运行它，
const code = ???;
const ast = parse(code);
eval(ast);
我将实现过程分成了两个部分， 解析（parse）和求值（eval）。
- 解析（parse）负责分析字符串的结构，返回一个容易被后续程序处理的对象（即 AST）。
- 求值（eval）负责执行，得到字符串跑完之后的最终结果。
解析（parse）
在解析之前，我们要先设计语法。尽量使得它容易被解析，我是这样设计的，
# Atom
abc
# List
(abc def)
(abc (def))
它只包含两种语法元素，原子（Atom） 和 列表（List）。一个没有括号，一个有括号，括号里还可以包含括号。
语法简单解析起来也会变得容易，我们只需要分情况判断下一个字符就行了。
parse 函数的代码结构如下，完整代码总共也才 100 多行，github: tiny-language/parse/index.ts
export function letParse() {
let sourceCode: string;
let length: number;
let pos: number;
let token: Token;
return parse;
// ---- ---- ---- ---- ---- ---- ---- ----
/**
* syntax
*
* Expr = Atom | List
* Atom = Identifier
* List = '(' Exprs ')'
* Exprs = Expr Exprs
*/
function parse(code): Node { }
/**
* Expr = Atom | List
*/
function parseExpr() { }
function parseAtom() { }
/**
* List = '(' Exprs ')'
*/
function parseList() { }
/**
* Exprs = Expr Exprs
*/
function parseExprs(): Node[] { }
// ---- ---- ---- ---- ---- ---- ---- ----
/**
* 向后扫描下一个 token，并修改当前 `token` 变量
*/
function nextToken() {
}
};
它分为两个部分，一个是 nextToken 用来返回下一个单词（一个或多个字符构成的串），
另一个部分，是由一堆互相递归调用的 parseXXX 函数构成，每个 parseXXX 函数针对一种场景进行解析。
(abc (def)) 对应的 AST 结构如下，
{
"nodeKind": "List",
"value": [
{
"nodeKind": "Atom",
"value": {
"tokenKind": "Identifier",
"start": 1,
"end": 4,
"text": "abc"
}
},
{
"nodeKind": "List",
"value": [
{
"nodeKind": "Atom",
"value": {
"tokenKind": "Identifier",
"start": 6,
"end": 9,
"text": "def"
}
}
]
}
]
}
求值（eval）
为了拿到程序的执行结果，我们需要以一种特定的方式对 AST 进行处理，常用的办法是对它进行归纳求值，
即，每棵树的含义，完全由它的子节点来决定，例如，
(display (add 1 2))
我们只需要定义 (display ...) 和 (add ... ) 两种表达式的含义就行了，进一步的说明如下。
（1）列表用来表示 “调用”：列表的第一个元素表示调用者，其余元素表示调用参数
(display 1)
display 是调用者，表示打印一些内容，1 表示参数，会传给 display。
（2）求值当前表达式之前，先求值它的子表达式（strict evaluation）
(display (add 1 2))
以上 display 表达式求值之前，要先求值 (add 1 2)，得到结果 3 之后，再求值 (display 3)。
求值（eval）函数的代码结构如下，
在增加了 begin lambda display define if equal add mul sub 这些功能之后，
完整代码也才 200 多行，github: tiny-language/eval/index.ts。
export function letEval() {
const env = [{}];
return function (ast) {
return theEval(ast, env);
};
// ---- ---- ---- ---- ---- ---- ---- ----
function theEval(ast, env) { }
function evalAtom(value, env) { }
function evalList(value, env) { }
function evalSpecial(operatorName, value, env) { }
function evalBegin(value, env) { }
function evalLambda(value, env) { }
function evalDisplay(value, env) { }
function evalDefine(value, env) { }
function evalIf(value, env) { }
function evalEqual(value, env) { }
function evalAdd(value, env) { }
function evalMul(value, env) { }
function evalSub(value, env) { }
function evalFuncApply(func, funcArgs, env) { }
};
函数
函数是一个很常见的语言特性，我们来看一下函数应该如何实现。
在求值各子表达式的时候，我们会遇到 (lambda ...) 表达式，它表示了函数的定义，我们来看看怎么处理它，
function evalLambda(value, env) {
const [, paramList, body] = value;
return createFunc(paramList, body);
}
export function createFunc(paramList, body, env?) {
return {
paramList,
body,
env,
};
}
办法是直接把 paramList 和 body 这两个 AST 节点存起来，包装成了一个对象 func，供以后调用的时候使用。
再来看看函数调用，
function evalList(value, env) {
const [operator] = value;
const operatorName = operator.value.text;
// 优先处理语言内置的算符
if (isSpecialOperator(operatorName)) {
return evalSpecial(operator.value.text, value, env);
}
// 第一个元素如果是一个列表，就先求值
if (operator.nodeKind === NodeKind.List) {
const [, ...funcArgs] = value;
const func = theEval(operator, env);
return evalFuncApply(func, funcArgs, env);
}
// 否则直接根据函数名查出
const [funcName, ...funcArgs] = value;
const func = lookup(funcName.value.text, env);
return evalFuncApply(func, funcArgs, env);
}
function evalFuncApply(func, funcArgs, env) {
const { paramList, body, env: funcDefEnv } = func;
const afterEvalFuncArgs = funcArgs.map(expr => theEval(expr, env));
const frame = {};
paramList.value.forEach((param, index) => {
frame[param.value.text] = afterEvalFuncArgs[index];
});
env.push(frame);
const funcReturn = evalList(body.value, env);
env.pop(frame);
return funcReturn;
}
当遇到一个列表（List）的时候，我们要根据列表的第一个元素分情况处理，
- 语言内置的算符，例如
beginlambdaif等会优先处理。 - 第一个元素是一个列表时，会先求值它，例如
((lambda (x) x) 123) - 剩下的情况看做是函数调用，例如
(f 123)，此时会先从环境中查出当时(lambda ...)定义时保存的func对象，执行函数调用。
真正调用的时候，会先从 func 对象中，拿到 paramList 和 body 这两个 AST 节点，然后对实参进行求值，将形参和实参的映射关系压入 env 中，函数返回之后，再把 env 复原。
这样实现就已经可以执行函数调用了，以下执行结果为 3。
(begin
(define f (lambda (x) (add x 1)))
(display (f 2)))
作用域
上述那样实现的函数有一个问题，下面的代码执行结果居然为 102。
(begin
(define f (lambda (x) (lambda (y) (add x y))))
(define g (f 1))
(define x 100)
(display (g 2)))
翻译成 JS 代码也许更容易看明白一些，
const f = x => {
return y => {
return x + y;
}
};
const g = f(1);
const x = 100;
console.log(g(2)); // 102 ???
x 的值当 f 返回之后并没有被保留，在 g 调用之前我们全局赋值了 x 为 100，结果 g 中拿到的 x 值也是 100 了。
这样的程序调试起来非常的麻烦，x 的是多少，取决于（时间上）最近的那次赋值。
我们能不能像 JS 那样实现闭包呢？我想让 g 把 x 的值存下来，这样 x 的值就总是 g 被定义时的那个值 1 了。
是可以的，而且也并不复杂，只需要对函数定义和调用做一点点修改就行了。
function evalLambda(value, env) {
const [, paramList, body] = value;
// 将 lambda 定义时的环境保存下来
const funcDefEnv = JSON.stringify(env);
return createFunc(paramList, body, funcDefEnv);
}
在处理函数定义的时候，我们将 “函数定义时” 的环境做了一个快照保存下来了，称为 funcDefEnv，
然后在函数调用的时候用这个环境去求值。
function evalFuncApply(func, funcArgs, env) {
const { paramList, body, env: funcDefEnv } = func;
const afterEvalFuncArgs = funcArgs.map(expr => theEval(expr, env));
const frame = {};
paramList.value.forEach((param, index) => {
frame[param.value.text] = afterEvalFuncArgs[index];
});
// 确定函数调用时的求值环境：函数定义时的环境
const funcEvalEnv = JSON.parse(funcDefEnv);
funcEvalEnv.push(frame);
const funcReturn = evalList(body.value, funcEvalEnv);
funcEvalEnv.pop(frame);
return funcReturn;
}
这样我们写的代码就跟 JS 一样了，最终结果为 3。
(begin
(define f (lambda (x) (lambda (y) (add x y))))
(define g (f 1))
(define x 100)
(display (g 2)))
像这样函数体中的自由变量，总是可以从函数的定义环境中找值的规则，称为词法作用域。
之前那种总是从（时间上）最近的 env 中取值的规则，称为动态作用域。
复杂一点的示例
有了词法作用域（或 闭包）之后，我们就可以写复杂一些的代码了。
还是回到篇首那个计算阶乘的函数，我们发现它是一个递归函数，即在函数体内又调用了自身。
const fact = n => n == 0 ? 1 : n * fact(n - 1);
fact(5); // 120
这是不是需要我们对递归特性进行额外的支持呢？例如，在函数定义执行完之后，在环境中增加一个映射关系。
其实不用再修改实现了，我们现在的实现就可以编写递归程序。
不过得借用一个称为 Y 组合子的神奇函数，它可以用来对匿名函数实现递归。
在 JS 中，Y 组合子是这样写的，
const yCombinator = function (k) {
const f = function (g) {
return g(g);
};
const p = function (r) {
return function (n) {
return k(r(r))(n);
};
};
return f(p);
};
然后我们对原始的 fact 做一些整改，用一个函数将它包起来，内部 fact 的递归调用改成对这个函数形参 h 的调用，
const factProto = function (h) {
return function (x) {
return x == 0 ? 1 : x * h(x - 1);
};
};
console.log(yCombinator(factProto)(5)); // 120
结果就可以进行递归计算了。
改成我们极简的编程语言之后，代码如下，
(begin
(define y-combinator (lambda (k) (begin
(define f (lambda (g)
(g g)))
(define p (lambda (r)
(lambda (n)
((k (r r)) n))))
(f p))))
(define fact-proto (lambda (h)
(lambda (x)
(if (equal x 0) 1 (mul x (h (sub x 1)))))))
(display ((y-combinator fact-proto) 5)))
这就是一个简单的字符串处理程序了。
参考
github: tiny-language
