搜索
怎样写一个解释器这是一篇解释器的入门教程。虽然我试图从最基本的原理讲起，尽量让这篇文章不依赖于其它知识，但是这篇教程并不是针对编程的入门知识，所以我假设你已经学会了最基本的Scheme和函数式编程。我不是很推崇函数式编程，但它里面确实包含了很重要的一些方法。如果你完全不了解这些，可以读一下SICP的第一，二章（或者接下去读TheLittleSchemer)。当然你也可以继续读这篇文章，有不懂的地方再去查资料。我在这里也会讲递归和模式匹配的原理。如果你已经了解这些东西，这里的内容也许可以加深你的理解。解释器是一种简单却又深奥的东西，以至于好多人都不会写，或者自认为会写却又不真正的会写。在这个领域里有一些历史遗留下来的误解，以至于很少有人真正的知道如何写出正确的解释器。很多“语言专家”或者“逻辑学家”的解释器代码里面有各种各样的错误，却又以谬传谬，搞得无比复杂。这误解的渊源之深，真是一言难尽。你必须从最简单的语言开始，逐步增加语言的复杂度，才能构造出正确的解释器。这篇文章就是告诉你如何写出一个最简单的语言(lambdacalculus)的解释器，并且带有基本的的算术功能，可以作为一个高级计算器来使用。一般的程序语言课程往往从语法分析(parsing)开始，折腾lex和yacc等麻烦却不中用的工具，解决一些根本不需要存在的问题。Parsing的作用其实只是把字符串解码成程序的语法树（AST）结构。麻烦好久得到了AST之后，真正的困难才开始！而很多人在写完parser之后就已经倒下了。鉴于这个原因，这里我用所谓的“S-expression”来表示程序的语法树（AST）结构。S-expression（加上Lisp对它发自“本能”的处理能力）让我们可以直接跳过parse的步骤，进入关键的主题：语义(semantics)。这里用的Scheme实现是Racket。为了让程序简洁，我使用了Racket的模式匹配（patternmatching）。我对Racket没有特别的好感。但它安装比较方便，而且是免费的。如果你用其它的Scheme实现的话，恐怕要自己做一些调整。解释器是什么首先我们来谈一下解释器是什么。说白了解释器跟计算器差不多。它们都接受一个“表达式”，输出一个“结果”。比如，得到'(+12)之后就输出3。不过解释器的表达式要比计算器的表达式复杂一些。解释器接受的表达式叫做“程序”，而不只是简单的算术表达式。从本质上讲，每个程序都是一台机器的“描述”，而解释器就是在“模拟”这台机器的运转，也就是在进行“计算”。所以从某种意义上讲，解释器就是计算的本质。当然，不同的解释器就会带来不同的计算。需要注意的是，我们的解释器接受的参数是一个表达式的“数据结构”，而不是一个字符串。这里我们用一种叫“S-expression”的数据结构来表示表达式。比如表达式'(+12)里面的内容是三个符号：'+,'1和'2，而不是字符串“(+12)”。从结构化的数据里面提取信息很方便，而从字符串里提取信息很麻烦，而且容易出错。从广义上讲，解释器是一个通用的概念。计算器实际上是解释器的一种形式，只不过它处理的语言比程序的解释器简单很多。也许你会发现，CPU和人脑，从本质上来讲也是解释器，因为解释器的本质实际上是“任何用于处理语言的机器”。递归定义(recursivedefinition)解释器一般都是“递归程序”。之所以是递归的原因，在于它处理的数据结构（程序）本身是“递归定义”的结构。算术表达式就是一个这样的结构，比如：'(*(+12)(*(-96)4))。每一个表达式里面可以含有子表达式，子表达式里面还可以有子表达式，如此无穷无尽的嵌套。看似很复杂，其实它的定义不过是：“算术表达式”有两种形式：1.一个数2.一个'(ope1e2)这样的结构（其中e1和e2是两个“算术表达式”）看出来哪里在“递归”了吗？我们本来在定义“算术表达式”这个概念，而它的定义里面用到了“算术表达式”这个概念本身！这就构造了一个“回路”，让我们可以生成任意深度的表达式。很多其它的数据，包括自然数，都是可以用递归来定义的。比如常见的对自然数的定义是：“自然数”有两种形式：1.零2.某个“自然数”的后继看到了吗？“自然数”的定义里面出现了它自己！这就是为什么我们有无穷多个自然数。所以可以说递归是无所不在的，甚至有人说递归就是自然界的终极原理。递归的数据总是需要递归的程序来处理。虽然递归有时候表现为另外的形式，比如循环(loop)，但是“递归”这个概念比“循环”更广泛一些。有很多递归程序不能用循环来表达，比如我们今天要写的解释器就是一个递归程序，它就不能用循环来表达。所以写出正确的递归程序，对于设计任何系统都是至关重要的。其实递归的概念不限于程序设计。在数学证明里面有个概念叫“归纳法”(induction)，比如“数学归纳法”(mathematicalinduction)。其实归纳法跟递归完全是一回事。我们今天的解释器就是一个递归程序。它接受一个表达式，递归的调用它自己来处理各个子表达式，然后把各个递归的结果组合在一起，形成最后的结果。这有点像二叉树遍历，只不过我们的数据结构（程序）比二叉树复杂一些。模式匹配和递归：一个简单的计算器既然计算器是一种最简单的解释器，那么我们为何不从计算器开始写？下面就是一个计算器，它可以计算四则运算的表达式。这些表达式可以任意的嵌套，比如'(*(+12)(+34))。我想从这个简单的例子来讲一下模式匹配(patternmatching)和递归(recursion)的原理。下面就是这个计算器的代码。它接受一个表达式，输出一个数字作为结果，正如上一节所示。(definecalc(lambda(exp)(matchexp;匹配表达式的两种情况[(?number?x)x];是数字，直接返回[`(,op,e1,e2);匹配并且提取出操作符op和两个操作数e1,e2(let([v1(calce1)];递归调用calc自己，得到e1的值[v2(calce2)]);递归调用calc自己，得到e2的值(matchop;分支：处理操作符op的4种情况['+(+v1v2)];如果是加号，输出结果为(+v1v2)['-(-v1v2)];如果是减号，乘号，除号，相似的处理['*(*v1v2)]['/(/v1v2)]))])))这里的match语句是一个模式匹配。它的形式是这样：(matchexp[模式结果][模式结果]......)它根据表达式exp的“结构”来进行“分支”操作。每一个分支由两部分组成，左边的是一个“模式”，右边的是一个结果。左边的模式在匹配之后可能会绑定一些变量，它们可以在右边的表达式里面使用。一般说来，数据的“定义”有多少种情况，用来处理它的“模式”就有多少情况。比如算术表达式有两种情况，数字或者(ope1e2)。所以用来处理它的match语句就有两种模式。“你所有的情况，我都能处理”，这就是“穷举法”。穷举的思想非常重要，你漏掉的任何一种情况，都非常有可能带来麻烦。所谓的“数学归纳法”，就是这种穷举法在自然数的递归定义上面的表现。因为你穷举了所有的自然数可能被构造的两种形式，所以你能确保定理对“任意自然数”成立。那么模式是如何工作的呢？比如'(,op,e1,e2)就是一个模式（pattern），它被用来匹配输入的exp。模式匹配基本的原理就是匹配与它“结构相同”的数据。比如，如果exp是'(+12)，那么'(,op,e1,e2)就会把op绑定到'+，把e1绑定到'1，把e2绑定到'2。这是因为它们结构相同：'(,op,e1,e2)'(+12)说白了，模式就是一个可以含有“名字”（像op,e1和e2）的“数据结构”，像'(,op,e1,e2)。我们拿这个带有名字的结构去“匹配”实际的数据（像'(+12))。当它们一一对应之后，这些名字就自动被绑定到实际数据里相应位置的值。模式里面不但可以含有名字，也可以含有具体的数据。比如你可以构造一个模式'(,op,e142)，用来匹配第二个操作数固定为42的那些表达式。看见左边的模式，你就像直接“看见”了输入数据的形态，然后对里面的元素进行操作。它可以让我们一次性的“拆散”(destruct)数据结构，把各个部件（域）的值绑定到多个变量，而不需要使用多个访问函数。所以模式匹配是非常直观的编程方式，值得每种语言借鉴。很多函数式语言里都有类似的功能，比如ML和Haskell。注意这里e1和e2里面的操作数还不是值，它们是表达式。我们递归的调用interp1自己，分别得到e1和e2的值v1和v2。它们应该是数字。你注意到我们在什么地方使用了递归吗？如果你再看一下“算术表达式”的定义：“算术表达式”有两种形式：1.一个数2.一个'(ope1e2)这样的结构（其中e1和e2是两个“算术表达式”）你就会发现这个定义里面“递归”的地方就是e1和e2，所以calc在e1和e2上面递归的调用自己。如果你在数据定义的每个递归处都进行递归，那么你的递归程序就会穷举所有的情况。之后，我们根据操作符op的不同，对这两个值v1和v2分别进行操作。如果op是加号'+，我们就调用Scheme的加法操作，作用于v1和v2，并且返回运算所得的值。如果是减号，乘号，除号，我们也进行相应的操作，返回它们的值。所以你就可以得到如下的测试结果：(calc'(+12));;=3(calc'(*23));;=6(calc'(*(+12)(+34)));;=21一个计算器就是这么简单。你可以试试这些例子，然后自己再做一些新的例子。什么是lambdacalculus？现在让我们过渡到一种更强大的语言：lambdacalculus。它虽然名字看起来很吓人，但是其实非常简单。它的三个元素分别是是：变量，函数，调用。用传统的表达法，它们看起来就是：变量：x函数：λx.t调用：t1t2每个程序语言里面都有这三个元素，只不过具体的语法不同，所以你其实每天都在使用lambdacalculus。用Scheme作为例子，这三个元素看起来就像：变量：x函数：(lambda(x)e)调用：(e1e2)一般的程序语言还有很多其它的结构，可是这三个元素却是缺一不可的。所以构建解释器的最关键步骤就是把这三个东西搞清楚。构造任何一个语言的解释器一般都是从这三个元素开始，在确保它们完全正确之后才慢慢加入其它的元素。有一个很简单的思维方式可以让你直接看到这三元素的本质。记得我说过，每个程序都是一个“机器的描述”吗？所以每个lambdacalculus的表达式也是一个机器的描述。这种机器跟电子线路非常相似。lambdacalculus的程序和机器有这样的一一对应关系：一个变量就是一根导线。一个函数就是某种电子器件的“样板”，有它自己的输入和输出端子，自己的逻辑。一个调用都是在设计中插入一个电子器件的“实例”，把它的输入端子连接到某些已有的导线，这些导线被叫做“参数”。所以一个lambdacalculus的解释器实际上就是一个电子线路的模拟器。所以如果你听说有些芯片公司开始用类似Haskell的语言（比如BluespecSystemVerilog）来设计硬件，也就不奇怪了。需要注意的是，跟一般语言不同，lambdacalculus的函数只有一个参数。这其实不是一个严重的限制，因为lambdacalculus的函数可以被作为值传递(这叫first-classfunction)，所以你可以用嵌套的函数定义来表示两个以上参数的函数。比如，(lambda(x)(lambda(y)y))就可以表示一个两个参数的函数，它返回第二个参数。不过当它被调用的时候，你需要两层调用，就像这样：(((lambda(x)(lambda(y)y))1)2);;=2虽然看起来丑一点，但是它让我们的解释器达到终极的简单。简单对于设计程序语言的人是至关重要的。一开头就追求复杂的设计，往往导致一堆纠缠不清的问题。lambdacalculus不同于普通语言的另外一个特点就是它没有数字等基本的数据类型，所以你不能直接用la