《计算机程序的构造与解释》的练习5.51要求我们用“低级语言”实现一个Scheme的求值器,同时我最近重新阅读了《C++ Primer》,重新学习了一下C++,所以计划使用C++来实现一个Scheme求值器。Scheme是一种“高级语言”,曾经先进的类型无关、垃圾回收、闭包调用、S表达式…,而我较为熟悉的C/C++/Java相比较而言就显得低级了。实现一个Scheme解释器的需要以下方面的考虑:

  • 弱类型:实现弱类型的基本方法就是设计一个特殊的类来模拟。如果使用弱类型的语言(如Python)来编写的话,这个问题自然可以无视了,
  • 实现垃圾回收:如果采用Java语言编写的话,垃圾回收就不需要考虑了,交给JVM来做就好。对于C++来说,最常用的技术就是RAII,采用引用计数来实现内存的管理。引用计数效率非常高,但是遇到循环引用的时候就很难解决。
  • 实现闭包:实现闭包的思路《计算机程序的构造与解释》文中已经有现成的,就是引入求值环境的概念。
  • 实现S表达式:S表达式相比其他语言来说非常简单,由于手写还是有些麻烦,所以使用Flex+Bison来解析S表达式。
  • 尾递归:利用尾调用无需保存调用者状态的特点来优化尾递归,将尾递归过程优化为迭代过程。

当然还需要考虑很多其他的东西,但是它们并不决定整个解释器结构。本篇文章主要讨论变量和运行环境的实现,对应于源代码中的variable.hppvariable.cppenvironment.hppenvironment.cpp

Continue reading