零基础构建语言解释器
在编写Interpreter之前，我们需要先了解Lexer（词法分析器），Parser（语法解析器），AST（抽象语法树）。
一般情况下，Interpreter在解释执行程序时，一般会经过如下步骤。
- Lexer读入程序代码，把代码转换token序列。
- Parser把读到的token序列转换为AST（大部分情况下，Lexer内嵌为Parser的一部分）。
- 对AST进行Lowering（化简AST）或者desugar（把语法糖的AST节点转换为标准等价AST节点）处理。
- Interpreter递归执行AST，AST决定了代码的执行顺序。
介绍完了基本的一些概念，我们现在开始来实现语言解释器。
首先，我们需要先定制文法规则，一般情况下，我们只要制定好了文法规则，就可以找一些工具来帮我们生成AST，对于复杂的文法规则，手写Parser是非常麻烦并且乏味的。 这里，为了简单，我们选用S-Expression来作为我们的文法规则来实现Lambda Calculus（Lambda演算）的解释器。 通过该Interpreter的实现，大家可以很容易就搞明白程序设计语言中耳熟能详却又未必深刻了解的一些概念，比如：类型，Lexical Scope（词法作用域），Dynamic Scope（动态作用域），闭包等概念。
Lambda Calculus
虽然规则简单，Lambda演算却是一门强大的语言。它的三个元素分别是是：变量，函数，调用。用传统的表达法，它们看起来就是：
变量：x
函数：λx.t
调用：t1 t2
每个程序语言里面都有这三个元素，只不过具体的语法不同，所以你其实每天都在使用 lambda calculus。换成S-Expression就是：
变量：x
函数：(lambda (x) e)
调用：(e1 e2)
Parser的实现
在parse处理token序列之前，我们先对tokens序列做一下预处理，其转换规则如下例所示，详细源码可以在此查看。
"(((lambda (x) (lambda (y) (+ x y))) 2) 3)" => [[[lambda [x] [lambda [y] [+ x y]]] 2] 3]
function doParse(node) {
var head;
if (isArray(node)) {
if (node.length == 0) {
throw new SyntaxError("syntax error: " + node);
} else {
head = node[0];
switch(head) {
case 'def':
return parseDef(node);
case 'lambda':
return parseLambda(node);
default:
return parseApply(node);
}
}
} else {
return node;
}
}
为了演示方便，除了变量，函数，调用Node之外，我这里还额外实现了一个节点def，它的主要功能是方便给变量及函数定制别名。
解析Lambda节点
function parseLambda(node) {
var params, paramNames;
if (node.length !== 3) {
throw new SyntaxError("syntax error in function definition" + node);
}
params = node[1];
if (!isArray(params)) {
throw new SyntaxError("incorrect format of parameters: " + params);
}
paramNames = params.map(function(param, _){
if (isArray(param)) {
throw new SyntaxError("illegal argument name : " + param);
}
return param;
});
return {type: 'lambda', params: paramNames, body: doParse(node[2])};
}
解析Apply节点
function parseApply(node) {
return {type: 'apply', func: doParse(node[0]), args: doParseList(aps.call(node, 1))};
}
解析Def节点
function parseDef(node) {
if (node.length != 3) {
throw new SyntaxError("incorrect format of definition " + node);
}
return {type: 'def', pattern: doParse(node[1]), value: doParse(node[2])}
}
(def if (lambda (p) (lambda (x) (lambda (y) ((p x) y))))) 转化的AST如下：
Interpreter的实现
function interpret(node, scope) {
switch (node.type) {
case 'def':
return scope.define(node.pattern, interpret(node.value, scope));
case 'apply':
var closure = interpret(node.func, scope),
args = node.args.map(function(arg) { return interpret(arg, scope); }),
newScope;
if (closure.type === 'closure') { // Lambda Closure
newScope = closure.fn.params.reduce(function(ctx, param, i) {
ctx.define(param, args[i]);
return ctx;
}, closure.env.copy()); // scope.copy() static scope vs. dynamic scope
return interpret(closure.fn.body, newScope);
} else { // BuiltIn Function
return closure.apply(scope, args);
}
case 'lambda':
return {type: 'closure', fn: node, env: scope};
default:
if (scope.defined(node)) {
return scope.lookup(node);
} else {
throw new EvalError("Unknown variable " + JSON.stringify(node));
}
}
}
如果你想支持原生的数据类型，比如字符串和数字，default部分可以改为：
default:
if (node[0] === '"' && node.slice(-1) === '"') {
return node.slice(1, -1);
} else if (!isNaN(parseFloat(node))) {
return parseFloat(node);
} else {
if (scope.defined(node)) {
return scope.lookup(node);
} else {
throw new EvalError("Unknown variable " + node);
}
}
程序设计语言中的一些概念
Closure(闭包)
在计算机科学中，闭包（Closure）是词法闭包（Lexical Closure）的简称，是引用了自由变量的表达式（通常是函数）。这些被引用的自由变量将和这个函数一同存在，即使已经离开了创造它的环境也不例外。 词法作用域(lexical scope)等同于静态作用域(static scope)。所谓的词法作用域其实是指作用域在词法解析阶段既确定了，不会改变。
在这里很容易看出，闭包的数据结构可以定义为，包含一个函数定义 f 和它定义时所在的环境 (struct Closure (f env))
(def add (lambda (x) (lambda (y) (+ x y)))) ;; add是一个全局函数，它是没有绑定任何自由变量的闭包，它的env就是全局的scope。
(def add5 (add 5)) ;; add5是一个全局函数，它是有捕获自由变量的闭包。
(add5 10) ;; Output: 15
动态作用域 vs. 词法作用域
本例中，以下代码决定语言程序语言使用的是词法作用域还是动态作用域。
newScope = closure.fn.params.reduce(function(ctx, param, i) {
ctx.define(param, args[i]);
return ctx;
}, closure.env.copy());
return interpret(closure.fn.body, newScope);
把closure.env.copy()替换为scope.copy()就可以把当前的词法作用域替换为动态作用域。词法作用域总是关联定义该Closure的Scope环境，动态作用域则是使用执行该Closure的Scope环境。
####
类型
类型的本质在于它所定义的操作以及操作之间的关系和不变式。类型的实现关键在于满足类型规范的要求，而具体实现是可以变化的，使用者和测试用例都应该只依赖于类型规范而不依赖于具体实现。函数式的类型实现往往和类型规范是直接对应的，简单通用，但可能有性能问题，而命令式的类型实现往往会引入复杂的内部数据结构，但是其优点是高效。这两种实现并不是完全互斥的，有时候可以将二者相结合达到简单与高效的结合。下面我们就使用函数式的方式来实现数据类型。
自然数
下面的代码定义了0~9几个自然数（这种方式定义的自然数也称为Church数），并定义了+，*，**(幂)三种操作。
(def 0 (lambda (f) (lambda (x) x)))
(def succ (lambda (n) (lambda (f) (lambda (x) (f ((n f) x))))))
(def 1 (succ 0))
(def 2 (succ 1))
(def 3 (succ 2))
(def 4 (succ 3))
(def 5 (succ 4))
(def 6 (succ 5))
(def 7 (succ 6))
(def 8 (succ 7))
(def 9 (succ 8))
(def + (lambda (m) (lambda (n) (lambda (f) (lambda (x) ((m f) ((n f) x)))))))
(def * (lambda (m) (lambda (n) (lambda (f) (n (m f))))))
(def ** (lambda (a) (lambda (n) (n a)))) // exp
为了方便直观演示，我们这里还定义了几个辅助的内建函数。
env.define('inc', function(v){
return v ? v + 1 : 1;
});
env.define('println', function(){
console.log.apply(this, arguments);
});
env.define('nil', null);
我们再定义一个方法，用于把Church数转为普通的数字。
(def church->int (lambda (n) ((n (lambda (x) (inc x))) nil)))
((3 (lambda (x) (println (church->int 5))))
;; output:
;; 5
;; 5
;; 5
(church->int 0) ;; => undefined
(church->int 6) ;; => 6
(church->int ((+ 1) 2)) ;; => 3
(church->int ((* 2) 3)) ;; => 6
(church->int ((** 2) 3)) ;; => 8
布尔类型
布尔值及其操作定义
(def true (lambda (x) (lambda (y) x)))');
(def false (lambda (x) (lambda (y) y)))');
(def and (lambda (p) (lambda (q) ((p q) false))))');
(def or (lambda (p) (lambda (q) ((p true) q))))');
(def not (lambda (p) ((p false) true)))))');
(def if (lambda (p) (lambda (x) (lambda (y) ((p x) y)))))');
为了方便测试并查看效果，我们新增一个内建函数。
env.define('assert-equals', function(n1, n2){
if (n1 !== n2) {
throw new EvalError(n1 + " must equals " + n2);
} else {
return true;
}
});
测试布尔类型上的操作。
(assert-equals ((and true) true) true)
(assert-equals ((and true) false) false)
(assert-equals ((and false) true) false)
(assert-equals ((and false) false) false)
(assert-equals ((or true) true) true)
(assert-equals ((or true) false) true)
(assert-equals ((or false) true) true)
(assert-equals ((or false) false) false)
(assert-equals (not false) true)
(assert-equals (not true) false)
(assert-equals (((if true) 3) 5) 3)
(assert-equals (((if false) 3) 5) 5)
LISP中常用的数据类型cons（有序对）
(def cons (lambda (x y) (lambda (p) (((if p) x) y)))))
(def car (lambda (cons) (cons true)))
(def cdr (lambda (cons) (cons false)))
验证cons类型及其操作。
(def c (cons 1 (cons 2 (cons 3 (cons 4 (cons 5 0))))))
(assert-equals (car c) 1)
(assert-equals (car (cdr c)) 2)
(assert-equals (car (cdr (cdr c))) 3)