在上个月重新看了《SICP》第四章后觉得写个lisp解释器也不是很困难，甚至我发现只要理解了其中的原理整个解释器其实非常简单。我觉得书中理解原理的关键一段就在4.1节：
The metacircular evaluator is essentially a Scheme formulation of the environment model of evaluation described in section 3.2. Recall that the model has two basic parts:
To evaluate a combination (a compound expression other than a special form), evaluate the subexpressions and then apply the value of the operator subexpression to the values of the operand subexpressions.
To apply a compound procedure to a set of arguments, evaluate the body of the procedure in a new environment. To construct this environment, extend the environment part of the procedure object by a frame in which the formal parameters of the procedure are bound to the arguments to which the procedure is applied.
These two rules describe the essence of the evaluation process, a basic cycle in which expressions to be evaluated in environments are reduced to procedures to be applied to arguments, which in turn are reduced to new expressions to be evaluated in new environments, and so on, until we get down to symbols, whose values are looked up in the environment, and to primitive procedures, which are applied directly.
也就是说eval和apply是相互递归的，eval会调用apply去产生结果，而apply会调用eval解释整个程序的子句。
apply的基本作用就是在调用函数之前创造出一个环境帧，这个帧中包含解析函数子句所必需的变量绑定，而被apply调用的eval会在这个新的环境中解析函数子句。
而eval则是负责在环境中查找符号的绑定，根据表达式中的第一个符号的内容（也就是表达式的operator），来决定下一步行动，如果是普通函数则调用apply，如果是宏则调用macroexpand，宏扩展之后再调用eval去解析扩展后的表达式。这样说可能有些难以理解，具体可以看我以前写的一篇关于lisp环境帧的文章。在理解了这个原理之后再看SICP的图就好理解了。
总的来说，整个解释器也就这些东西了。而且由于lisp基本上都内置了read函数直接返回读到的表达式，而且由于表达式就是列表，所以用lisp来解释lisp简直没什么技术含量，所以我也就花了几天时间就写出了个lisp解释器。我实现的基本上是scheme的函数，并且支持call/cc，不过宏却是CL类的宏，因为scheme的宏虽然干净但是感觉还是太难用了，还是觉得defmacro用起来舒服，所以我也就只实现了defmacro宏。
关于lisp解释器
虽然lisp版的解释器已经实现了，但是完成后却发现没什么技术含量，不过由于使用高阶语言完成了一个项目，那么整体的思路也已经掌握，所以我还是想用C实现一个解释器，这样一想其实会多很多工作量：内存管理，垃圾收集，符号查找，链表的读入等这些在lisp实现中完全不需要考虑的细节全部冒出水面了。
不过即使是使用高阶语言来实现我也发现自己对难度的判断有些错误（看来别人说的“要把程序员估计的困难提高几个数量级才能得出正确值”是对的）：本来以为call/cc实现起来非常困难，但是实际上直接使用原生的call/cc就能非常轻松地把这个功能提供给使用者。就算是使用C实现起来也不会困难，只是一个setjmp和一个longjmp而已，但是实现之前想做的的干净宏却异常困难，最后不得以，只能拿CL的defmacro（由于没有支持gensym，所以一些高级宏没办法支持）的语义来充数了。
如果有人对lisp实现感兴趣以下是一些提示：
这个解释器所支持的语法虽然混合了CL的和scheme，但是只能由scheme解释器当宿主解释器。推荐使用chicken scheme，因为我用的就是这个，使用时直接用csi main.scm就能进入repl，现在支持的一些函数和基本语法见eval.scm和setup.scm，其中setup.scm中直接导入了宿主解释器的基本函数，还定义了let和cond宏，这样你也可以照着写一个由scheme来解释的CL宏（个人觉得好帅）。
关于C实现的lisp解释器
基本功能已经在lisp实现中实现了。但是我仍然想用C来解释lisp，这样更有挑战性也更有意思。准备实现的基本解释器其实应该算是个库，它提供接口让所有链接到该库的软件可以直接解释lisp，这个接口应该包括：
- 允许让用户自己加入primitive procedure：比如库本身不提供打开文件的接口，但是应该允许用户自己拿C语言实现这个函数，并能将其加入到环境中就好像库本身提供一样，这样用户可以自己扩展该库而不需要改变库。
- 提供类似eval-string的C语言接口，让用户可以eval外部提供的lisp语言。从这个意义上来说：repl本身就是该库的一个thin wrapper。
希望最终能完成这个项目，现在还有很多的困难需要克服，最大的困难就是garbage collection，实在不知道应该怎么解决这个问题，还需要调查很久，而且一旦这个地方出现bug将会非常难找到。而性能问题也将是一个头痛的问题，因为从来没写过一个性能需求很高的软件，很多次的优化最终常常被证明还不如不优化。所以，成品估计也只能当作是一个勉强能用的东西吧。