Lisp解释器终于写完了

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

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

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

Step 0

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

Step 1

在实现 read_form 和 read_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用到实际项目中了。

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

那么这个坑填差不多了，下一个坑挖点啥？