【感谢@李欲纯 的热心翻译。如果其他朋友也有不错的原创或译文,可以尝试推荐给伯乐在线。】
Little Lisp是一个解释器,支持函数调用、lambda表达式、 变量绑定(let)、数字、字符串、几个库函数和列表(list)。我写这个是为了在Hacker School(一所位于纽约的程序员培训学校)的一个闪电秀中展示写一个解释器不是很难。一共只有116行的JavaScript代码,下文我会解释它是如何运行的。
首先,让我们学习一些Lisp。
Lisp基础
这是一个原子,最简单的Lisp形式:
这是另一个原子,一个字符串:
这是一个空列表:
()
这是一个包含了一个原子的列表:
这是一个包含了两个原子的列表:
这是一个包含了一个原子和另一个列表的列表:
这是一个函数调用。函数调用由一个列表组成,列表的第一个元素是要调用的函数,其余的元素是函数的参数。函数first 接受一个参数(1 2) ,返回1 。
这是一个lambda表达式,即一个函数定义。这个函数接受一个参数x ,然后原样返回它。
这是一个lambda调用。lambda调用由一个列表组成,列表的第一个元素是一个lambda表达式,其余的元素是由lambda表达式所定义的函数的参数。这个lambda表达式接受一个参数"lisp" 并返回它。
1 2 3 4 5 | ((lambda (x)
x)
"Lisp")
=> "Lisp"
|
Little Lisp是如何运行的
写一个Lisp解释器真的很容易。
Little Lisp的代码包括两部分:分析器和解释器
分析器
分析分两个阶段:分词(tokenizing)和加括号(parenthesizing)。
tokenize() 接受一个Lisp字符串,在每个括号周围加上空格,然后用空格作为分隔符拆分整个字符串。举个例子,它接受((lambda (x) x) "Lisp") ,将它变换为( ( lambda ( x ) x ) "Lisp" ) ,然后进一步变换为['(', '(', 'lambda', '(', 'x', ')', 'x', ')', '"Lisp"', ')'] 。
1 2 3 4 5 6 | var tokenize = function (input) {
return replace(/\(/g, ' ( ' )
.replace(/\)/g, ' ) ' )
.trim()
.split(/\s+/);
};
|
parenthesize() 接受由tokenize() 产生的词元列表,生成一个嵌套的数组来模拟出Lisp代码的结构。在这个嵌套的数组中的每个原子会被标记为标识符或文字表达式。例如,['(', '(', 'lambda', '(', 'x', ')', 'x', ')', '"Lisp"', ')'] 被变换为:
1 2 3 | [[{ type: 'identifier', value: 'lambda' }, [{ type: 'identifier', value: 'x' }],
{ type: 'identifier', value: 'x' }],
{ type: 'literal', value: 'Lisp' }]
|
parenthesize() 一个挨一个地遍历词元。如果当前词元是左括号,就开始构建一个新的数组。如果当前词元是原子,就标记其类型并将其添加到当前数组中。如果当前词元是右括号,就停止当前数组的构建,继续构建外层的数组。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | var parenthesize = function (input, list) {
if (list === undefined) {
return parenthesize(input, []);
} else {
var token = input.shift();
if (token === undefined) {
return list.pop();
} else if (token === "(" ) {
list.push(parenthesize(input, []));
return parenthesize(input, list);
} else if (token === ")" ) {
return list;
} else {
return parenthesize(input, list.concat(categorize(token)));
}
}
};
|
当parenthesize() 第一次被调用时,input 参数包含由tokenize() 返回的词元列表数组。例如:
1 | ['(', '(', 'lambda', '(', 'x', ')', 'x', ')', '"Lisp"', ')']
|
第一次调用parenthesize() 时,参数list 是undefined ,第2-3行运行,递归调用parenthesize() ,list 被设置为空数组。
在递归中,第5行运行,input 的第一个左括号被移除。第9行中,传一个新的空数组给递归调用,开始一个新的空列表。
在新的递归中,第5行运行,从input 中移除了另一个左括号。与前面类似,第9行中,传另一个新的空数组给递归调用,开始另一个新的空列表。
继续进入递归,现在input 是['lambda', '(', 'x', ')', 'x', ')', '"Lisp"', ')'] 。第14行运行,token 被设置为lambda ,调用categorize() 函数并传递lambda 作为参数。categorize() 的第7行运行,返回一个对象,其type 属性被设置为identifier ,value 属性被设置为lambda 。
1 2 3 4 5 6 7 8 9 | var categorize = function (input) {
if (! isNaN ( parseFloat (input))) {
return { type: 'literal' , value: parseFloat (input) };
} else if (input[ 0 ] === '"' && input.slice(- 1 ) === '"' ) {
return { type: 'literal' , value: input.slice( 1 , - 1 ) };
} else {
return { type: 'identifier' , value: input };
}
};
|
parenthesize() 的第14行向list 中加入由categorize() 返回的对象,然后用input 的剩余元素和list 进一步递归。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | var parenthesize = function (input, list) {
if (list === undefined ) {
return parenthesize(input, []);
} else {
var token = input.shift();
if (token === undefined ) {
return list.pop();
} else if (token === "(" ) {
list.push(parenthesize(input, []));
return parenthesize(input, list);
} else if (token === ")" ) {
return list;
} else {
return parenthesize(input, list.concat(categorize(token)));
}
}
};
|
在递归中,下一个词元是括号。parenthesize() 的第9行用一个新的空数组递归创建一个新的空列表,进入新的递归,这时input 是['x', ')', 'x', ')', '"Lisp"', ')'] 。第14行运行,token 被设置成x ,这样创建了一个新的对象,其值为x ,类型为identifier ,然后将这个对象加入到list 中,然后接着递归。
在递归中,下一个词元是右括号,第12行运行,返回完成了的list :[{ type: 'identifier', value: 'x' }] 。
parenthesize() 继续递归直到它处理完全部的输入词元,最后返回由包含了类型信息的原子所组成的嵌套数组。
parse() 是tokenize() 和parenthesize() 的组合调用:
1 2 3 | var parse = function (input) {
return parenthesize(tokenize(input));
};
|
如果原始的输入给的是((lambda (x) x) "Lisp") ,则分析器给出的最后输出是:
1 2 3 | [[{ type: 'identifier', value: 'lambda' }, [{ type: 'identifier', value: 'x' }],
{ type: 'identifier', value: 'x' }],
{ type: 'literal', value: 'Lisp' }]
|
解释器
在分析结束后,解释就开始了。
interpret() 接收parse() 的输出并执行它。提供上例中的输出,interpret() 会构造一个lambda表达式,然后用"Lisp" 作为参数调用它。lambda调用会返回"Lisp" ,这就是整个程序的输出。
除了要执行的输入外,interpret() 还接收一个执行上下文。执行上下文是变量和变量对应的值所存储的地方。当一段Lisp代码被interpret() 执行时,执行上下文包含着这段代码可访问的变量。
这些变量是分层存储的。当前作用域的的变量处在最底层,在包含域中的变量处在上一层,包含域的上一层包含域中的变量处于更上层,依次类推。例如,在下面的代码中:
1 2 3 4 5 | ((lambda (a)
((lambda (b)
(b a))
"b"))
"a")
|
第3行,执行上下文有两个活动的作用域。内层的lambda形成了当前作用域。外层的lambda形成了包含作用域。当前作用域中b 被绑定到"b" ,包含作用域中a 被绑定到"a" 。当第3行运行时,解释器尝试在作用域中去查找b ,它检查当前作用域,发现了b 并返回它的值。还是在第3行上,解释器尝试去查找a ,它检查当前作用域,结果没找到a ,所以它尝试去包含域找,在那里它找到了a 并返回它的值。
在Little Lisp中,执行上下文用一个对象来表示,这个对象通过调用Context 构造函数来生成。这个函数接受scope 参数,即一个由在当前作用域中的变量和值组成的对象;还接受parent 参数,如果parent 是undefined ,作用域即位于顶层,或者说是全局的。
1 2 3 4 5 6 7 8 9 10 11 12 | var Context = function (scope, parent) {
this .scope = scope;
this .parent = parent;
this . get = function (identifier) {
if (identifier in this .scope) {
return this .scope[identifier];
} else if ( this .parent !== undefined ) {
return this .parent. get (identifier);
}
};
};
|
我们已看到((lambda (x) x) "Lisp") 是如何被分析的,现在让我们看看分析过后的代码是如何被执行的。
1 2 3 4 5 6 7 8 9 10 11 | var interpret = function(input, context) {
if (context === undefined) {
return interpret(input, new Context(library));
} else if (input instanceof Array) {
return interpretList(input, context);
} else if (input.type === "identifier") {
return context.get(input.value);
} else {
return input.value;
}
};
|
interpret() 第一次被调用时,context 是undefined ,第2-3行运行,创建一个执行上下文。
当初始上下文被实例化时,构造函数接受了一个叫library 的对象。这个对象包含了内建在语言中的函数:first , rest 和print 。这些函数是用JavaScript写的。
interpret() 用原始的输入和新的上下文进行递归。
input 包含了上节中例子产生的输出:
1 2 3 | [[{ type: 'identifier', value: 'lambda' }, [{ type: 'identifier', value: 'x' }],
{ type: 'identifier', value: 'x' }],
{ type: 'literal', value: 'Lisp' }]
|
因为input 是数组而且context 已定义,第4-5行运行,interpretList() 被调用。
1 2 3 4 5 6 7 8 9 10 11 12 | var interpretList = function (input, context) {
if (input[0].value in special) {
return special[input[0].value](input, context);
} else {
var list = input.map( function (x) { return interpret(x, context); });
if (list[0] instanceof Function) {
return list[0].apply(undefined, list.slice(1));
} else {
return list;
}
}
};
|
在interpretList() 中,第5行遍历input 数组,对每个元素调用interpret() 。当interpret() 在lambda定义上调用时,interpretList() 再一次被调用。这次,interpretList() 的input 参数为:
1 2 | [{ type: 'identifier', value: 'lambda' }, [{ type: 'identifier', value: 'x' }],
{ type: 'identifier', value: 'x' }]
|
interpretList() 的第3行被调用,因为数组的第一个元素lambda 是特殊形式。lambda() 被调用来创建lambda函数。
1 2 3 4 5 6 7 8 9 10 11 12 13 | var special = {
lambda: function (input, context) {
return function () {
var lambdaArguments = arguments;
var lambdaScope = input[1].reduce( function (acc, x, i) {
acc[x.value] = lambdaArguments[i];
return acc;
}, {});
return interpret(input[2], new Context(lambdaScope, context));
};
}
};
|
special.lambda() 接受input 中定义lambda的部分,返回一个函数,当这个函数被调用时,会对一些参数调用这个lambda函数。
第3行开始lambda调用函数的定义。第4行保存了传递给lambda调用的参数。第5行开始为lambda调用创建一个新的作用域,收集input 中定义lambda的参数的部分: [{ type: 'identifier', value: 'x' }] ,针对input 中的每一个lambda形参和传递给lambda的对应实参,往lambda作用域中添加一个键值对。第10行对lambda的主体调用interpret() :{ type: 'identifier', value: 'x' } 。它传递给的lambda上下文包含lambda的作用域和父上下文。
lambda现在就变成了被special.lambda() 返回的函数。
interpretList() 继续遍历input 数组,对列表的第二个元素调用interpret() :字符串"Lisp" 。
1 2 3 4 5 6 7 8 9 10 11 | var interpret = function (input, context) {
if (context === undefined) {
return interpret(input, new Context(library));
} else if (input instanceof Array) {
return interpretList(input, context);
} else if (input.type === "identifier" ) {
return context.get(input.value);
} else {
return input.value;
}
};
|
interpret() 的第9行运行,这行做的事情仅仅是返回字面量对象的value 属性'Lisp' 。interpretList() 的第5行的map操作至此完成。list 成为:
1 2 | [function(args) { /* code to invoke lambda */ },
'Lisp']
|
interpretList() 的第6行运行,发现List 的第一个元素是一个Javascript函数,这意味着list 是一个函数调用。第7行运行,调用lambda函数,并将list 的剩余部分作为参数传递。
1 2 3 4 5 6 7 8 9 10 11 12 | var interpretList = function (input, context) {
if (input[0].value in special) {
return special[input[0].value](input, context);
} else {
var list = input.map( function (x) { return interpret(x, context); });
if (list[0] instanceof Function) {
return list[0].apply(undefined, list.slice(1));
} else {
return list;
}
}
};
|
在lambda调用函数中,第8行对lambda主体调用interpret() ,{ type: 'identifier', value: 'x' } 。
1 2 3 4 5 6 7 8 9 | function() {
var lambdaArguments = arguments;
var lambdaScope = input[1].reduce(function(acc, x, i) {
acc[x.value] = lambdaArguments[i];
return acc;
}, {});
return interpret(input[2], new Context(lambdaScope, context));
};
|
interpret() 的第6行发现input 是一个标识符类型的原子,第7行去上下文里查找标识符x ,返回'Lisp' 。
1 2 3 4 5 6 7 8 9 10 11 | var interpret = function (input, context) {
if (context === undefined) {
return interpret(input, new Context(library));
} else if (input instanceof Array) {
return interpretList(input, context);
} else if (input.type === "identifier" ) {
return context.get(input.value);
} else {
return input.value;
}
};
|
'Lisp' 被lambda调用函数返回,接着被interpretList() 返回,接着被interpret() 返回,就是这样。
全部的代码见GitHub repository。还可以看看lis.py,一个优秀而简单的Scheme解释器,由Peter Norvig用Python编写。
|