实现微型Lisp编译器的小心得

by

at 2013-04-05 13:03:11

original http://liutos.github.com/posts/GitHub%E9%A1%B9%E7%9B%AE/%E5%AE%9E%E7%8E%B0%E5%BE%AE%E5%9E%8BLisp%E7%BC%96%E8%AF%91%E5%99%A8%E7%9A%84%E5%B0%8F%E5%BF%83%E5%BE%97.html

实现微型Lisp编译器的小小心得

黑历史

大二的时候开始上数据结构的课程，所用的教材里面有一个章节讲的是广义表的概念及其实现。当时恰好和Lisp邂逅中，而且因为觉得自己学习的Lisp相关的知识也不少了，因此想试着按照书上的广义表的实现方式来自己写一个可以分析Lisp的S表达式的程序。尽管花了比较长的时间，不过终究也是写出来了。后来就顺水推舟，在这个S表达式分析器的基础上开始折腾Lisp的实现了。那时候确实是无知者无畏，居然妄想着可以写出Common Lisp的解释器，果然还是太天真了。不过那时候的另外一个重要的想法，就是要把实现一个Lisp的解释器作为自己的毕业设计。而现在，这个当初的梦想，还真的就实现了。而且尽管论文的初稿可能差强人意，但是我对自己目前的实现还是感到满意的，因为，它现在不再是解释器——它是一个编译器加虚拟机了XD

写不腻的解释器

说来蛋疼，我写了好几个解释器。光是在GitHub上和解释器相关的项目，就有过LiutCL、LiutScm以及Camel-Lisp。LiutCL已经是个死掉的项目了，毕竟已经没有那个兴趣去更新它；LiutScm已经被我直接删掉了，因为我另外开了一个几乎同名的项目，所以不想留着这个死剩种；Camel-Lisp是一个用OCaml写的Lisp实现，和用C进行开发的感受确实有很大的不同，而且这个是在看了一轮Scheme From Scratch系列的文章之后开始动手写的，用的几乎都是其中的思路。其实我从头开始写的解释器的数量绝对不止这么多，因为我在写LiutCL的过程中貌似也推翻过一两次了，所以很可能我已经试着从头开始写的解释器已经有五个了，尽管它们的代码的差别可能不大。那个把LiutScm换掉的新项目，叫做liutscm（变成全小写了XD），就是新的Lisp实现。不过它不是单纯的解释器，还加上了编译器和虚拟机的功能。

编译器代码来源

尽管我也试着去看和编译原理，或者编译器的构造有关的书或者论文，不过我到目前为止所懂得的东西，也就只有编译器一般分为多少个步骤而已。至于怎么实现诸如词法分析或者语法分析这样的功能，则是完全没有概念的，尽管可能一些诸如LL(k)这样的名词我会认识。所以说，我写的编译器的代码，也是有来源的，正如liutscm的解释器部分一开始的代码来自于Scheme From Scratch一样。编译器的代码，来自于《Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp》，它的作者是Google的搜索质量负责人Peter Norvig。在书中的第22和第23章，PN大神先后讲解了如何用CL来实现一个简单的Scheme子集的解释器和编译器，最后还有虚拟机的实现。

不同于解释器的感受

不同的感受是必然会存在的，毕竟是两个完全不同的东西，代码的风格和思路看起来也是截然不同。不过因为可以说的东西比较多，讲太多了我也很容易陷入写文章的烦躁之中，所以我就挑一个今天扫墓的时候想到的内容好了——原语函数的实现。

话说在解释器里头，以Scheme From Scratch中用C语言实现的解释器为例子，其中的原语函数的实现代码，即它们对应的C代码，它们的函数声明都是统一的。这是为什么呢？是因为在解释器的核心部分，一个实现了eval功能的C函数中，对于所有的函数调用，都是通过递归地调用eval本身来实现的。一个函数调用的表达式中，函数的参数部分在递归调用了eval来进行求值后，是以列表的形式存储其求值过后的结果的。之后，这个列表会直接被传递给原语函数实现对应的C函数作为参数，进行函数指针引导的函数调用。对于其中的函数的处理，都是通过函数在C代码中进行存取操作来实现的。例如对于原语函数cons，在C代码中，它要自己从参数列表中取出第一个参数o1和第二个参数o2，然后在调用函数拼接为一个CONS类型的对象返回。相当于每个原语函数都是以&rest参数的形式实现的。

在解释器里头，原语函数的代码的声明和Lisp级别用起来的样子几乎完全不一样，而且每个函数要自己存取参数列表，再进行函数体的实际操作。

那么在编译器里头会怎么样呢？首先，编译器值对代码进行分析和产生后端的虚拟机所支持的指令集合，并不会对产生的代码进行执行——那是虚拟机干的事情！在编译器中，对于函数调用而言，一般最后会产生一条例如叫做CALL或者APPLY这样的指令，而这个指令会带有一个参数，表示现在所进行的函数调用，在原来的表达式中到底有多少个参数被传递进去了。显然，如果是原语函数，那么我们可以按照数据驱动的思路，在初始化时为每一个函数定义指明参数个数，那么在编译器产生指令的时候，完全可以产生含有参数个数信息的代码，例如叫做CALL0、CALL1这样的。这样的指令不需要参数，它们的名字本身就含有数量信息——当然了，名字对于C语言一般是没用的，你要手动给每一个指令实现具体的代码。

那么在CALL0和CALL1这类指令的实现中，我们就不需要让参数以列表的形式进行传递了，而是直接传入固定数量的参数——只要位置没有搞错就可以了。例如我们有一个宏fn，它可以取出原语函数型的Lisp对象中含有的C函数指针，那么要调用一个含有单个参数的函数，假设Lisp对象叫o，参数为arg1，那么调用形式就是

(fn(o))(arg1) 

以此类推，CALL2这样的指令中，就会含有

(fn(o))(arg1, arg2) 

这样的代码了。当然了，这些都是hard-code的例子，可以认为是因为C语言对表达式的处理能力太弱才会导致我们手写的——假如C的宏的功能再强大一点，有个循环或者什么的，就可能有机会把这样的代码用一段含有参数的宏给代替了，不过那样C就变成了Lisp了。或许，没有那么多方便的高级功能，才是用C语言实现高级编程语言的乐趣所在吧=。=

好处是？

这样的好处显而易见。以定义原语函数cons为例，我不再是像下面这样定义cons的

lisp_object_t pair_cons_proc(lisp_object_t args) {  
  lisp_object_t o1 = pair_car(args);  
  lisp_object_t o2 = pair_cadr(args);  
  return make_pair(o1, o2);  
} 

而是像下面这样定义的

sexp pair_cons_proc(sexp o1, sexp o2) {  
  return make_pair(o1, o2);  
} 

显然，第二种方式更加地自然，它才和我们想象中的cons函数的实现方法一致吧XD而且这样子的定义方式，可以让虚拟机的原语函数库的实现人员以更加有Lisp感觉的方法来定义这些函数，并且还有另外一个好处，就是增加了原语函数的可重用性。如果是第一个原语函数的定义，那么在C代码中要使用就困难重重了，因为我要把原来好好的两个参数先给拼接成参数列表，好让pair_cons_proc把它给拆开——这真是自找苦吃啊！因此，为了保证每一个原语函数的实现层面的函数声明是一致的，就需要对一些可以在C语言中直接使用的，实现了类似于原语函数功能的一些C函数，给重新包装一遍。例如，在我的C代码中，make_pair函数是真正负责构造PAIR类型的对象的函数。在解释器的版本中，pair_cons_proc实际上是一个对make_pair的包装器；如果是在编译器+虚拟机的版本中，pair_cons_proc完全可以去掉——不过为了减少代码修改量，我只是改了它的实现罢了:-P

总结

全剧终……