记录完成mal项目实现Lisp解释器的踩坑过程,主要参照之前翻译的mal指南,边做边修改之前翻译得不清楚的地方。

我的实现https://github.com/Windfarer/lisp-interpreter

虽然在写代码的过程中不断出现如下状况但很幸运最终还是完成了(

why

Step 0

毫无难点,轻松飘过。修改配置项需要注意一下,配错了后面就没法正确运行测试。

Step 1

在实现read_formread_list之间相互调用时花了一些时间,这里要注意在恰当的时候调整reader的position,不能弄出死循环。

本步骤中我的类型判断做得比较粗糙,勉强通过测试,待后续完善。

Step 2

按照文档的说明实现,这一步坑比较少,发现我上一步的异常处理写得太垃圾,重新用Exception进行了实现。另外就是关键字类型、数字类型和字符串类型判断有问题,进行了修改。

另外这一步骤比较让人困惑的是要求修改EVAL,在ast为列表时使用eval_ast对它进行求值,并将结果列表中第一个作为函数,对列表的后续进行求值。在测试用例中发现有第一个是字符串的,字符串无法作为函数对后续进行求值。这里可以判断一下第一个元素是不是callable的,如果不是就把ast原样返回。

拜python的可变长参数所赐,本步骤轻松愉快的过了,使用其他不支持可变长参数的语言可能要多花些时间。

另外在修改代码时,要时不时跑跑前面步骤的测试,以免破坏了已经实现的特性。

Step 3

这一步改动其实比较小,主要变化是环境改为使用Env对象实现,以及对EVAL函数中apply步骤的修改。难点在于后者,需要花一些时间整理在处理完special form之后返回的东西是什么。

本步我的困惑是,在环境中的符号是用Symbol的值还是用Symbol对象本身?我在实现中的做法是使用了Symbol的值,不知道是不是在挖坑。

另外到了这里我发现,之前恶劣的类型实现,debug开始变得困难了,下一步中大概需要对这一部分进行重构

Step 4

本步骤测试用例极多。这一步修改了很多东西。在对do的处理这一块卡了很久,文档里要求使用eval_ast对列表元素逐个处理,尝试了半天,发现eval_ast并不能正确返回,反而使用EVAL来对元素进行处理才会有正确的求值逻辑,本步骤先这样通过了。

Step 5

实现TCO尾调用优化,这一步测试比较少,改动也比较少,文档上没有什么坑,照着做就可以顺利通过。

Step 6

这一步花费很多时间,因为之前实现的字符串读取部分的代码实现比较粗糙,大部分时间在修补Step 1和2写的那些代码。

Step 7

这一步实现quoting,处理的AST结构比较复杂需要仔细一些。另外本步骤有一些列表的连接之类的操作,我在这步除了与AST结构搏斗以外,还折腾了很久python的列表类型以及mal里列表类型的区分和转换。

Step 8

本步骤增加了macro(宏)这个特性。貌似坑不是很多,按照文档仔细实现即可,传参数稍有些复杂,要看清应该传什么别传错了。

Step 9

这一步实现try catch和hash-map数据结构,是为最后一步做准备。主要时间花在实现hash-map上,简单点的话实际上这个hash-map可以使用列表实现,就是查找起来比较慢,用dict实现的话要注意key的顺序,在插入修改和迭代时要保持一致。

Step A

最后一步,在你的解释器上运行mal实现的解释器,并让它通过全部测试。这步卡了一年(误 由于之前手贱在实现Step 5的代码里某个地方多加了一个continue,导致在跑解释器的时候一直循环求值导致爆炸,直接让我的这个坑变成了跨年坑。

debug的过程异常艰辛,以至怀疑人生,因为实际上你在做的是调试一个跑在你的解释器上的lisp实现的解释器,但bug存在于宿主语言的实现中,而这个lisp实现的解释器代码也很复杂,导致很难定位问题实际所在。我最后采取的办法是逐个步骤运行测试用例,直到找到某个最早的mal实现,在上面跑语句可以重现bug。然后拆解这个mal实现的代码,逐层手工运行,直到定位到问题的真正位置。

这步只遇到了这一个自己挖的深坑,目测不同的人写会遇到不同的坑吧。

总结

之后看了一下官方的python实现,它基本上直接使用了python内置的类型来实现,最终效果比我的要简单很多。由于我采用了自己定义一套类型容器,把python内置的类型包在里面,但在写的时候又想使用python的一些语法糖,比如切片之类的,这就导致需要把这些方法port到实际的数据上;再有一点是因为python是一门动态类型语言,所以如果使用自己实现的类型容器,就极易掉入到我是谁,我在哪的疑惑当中,常常不知道自己在操作的是mal的类型还是python本身的类型,如果是使用静态类型语言,或者加上type hints的应该会好很多。(现在你知道什么叫“动态一时爽,重构火葬场了吧”,我先去哭一会)开始认真考虑把type hints用到实际项目中了。

实际实现完这个东西会发现,虽然它已经强大到能够运行一个解释器了,但里面其实还有很多情况没有处理,输入一些不合规范的脚本就会爆炸,仍有很大的改进空间。

那么这个坑填差不多了,下一个坑挖点啥?