实现自己的Lisp解释器（一）

注意：这个程序完全没有优化，执行效率在某些情况下可能会低的惊人，如果你有兴趣，对于这个问题我们可以进一步探讨。

如果你是一个软件工程派，喜欢合理的结构，规范的代码和详尽的文档，你一定不会喜欢我写的程序；如果你是一个Design Pattern Zealot，你一定会发现我的程序里很多地方没有规范的使用GoF Pattern。考虑到这是一个Quick and Dirty Solution，我建议你把有关规范性的合理化建议放到你所在的公司/学校/组织机构的开发例会上提出，这样会更有效。

如果这些可能被你视为垃圾的代码严重的伤害了你的感情，触犯了你的审美观和道德观，你可以选择：1、提出改进意见；2、在其它地方痛斥我和程序；3、去看别的网页。如果你在我的地盘上用不适当的词语斥责我，结果只能是删贴，这样做浪费的不光是我的时间和精力，还有你的。

请不要在这里发表对排版格式/命名规范的观点和看法，这里不是火葬场，不是Flame War应该出现的地方。而且我绝对不会采纳这样的意见。因为就我的个人经验，我采用的命名规范往往比你按照教科书提出的规范更好用。

Lisp的语法很简单，而且程序和数据结构相同，这就为我们编写解释器提供了很大的便利，而且为了简单起见，我们在这里不考虑Lexical Scope，而是按照McCarthy创造Lisp时所采用的Dynamic Scope方式进行名字解析，这样我们只需要在运行过程中保留一个Context。总而言之，现代Lisp中的一切会导致实现复杂化的因素在这里都不存在。

在Lisp中，函数、程序都是表，表是由原子和表组成的一个嵌套递归结构，所以我们首先从一个抽象的数据结构MetaObject说起。

在本程序中，MetaObject有如下形式的定义：

class MetaObject
{
public:
	virtual ~MetaObject(){} // 确保RTTI和dynamic_cast可以使用

	// Overloads
	virtual MetaPtr Clone() const=0;

	virtual MetaPtr atom() const=0;
	virtual MetaPtr null() const=0;
	virtual MetaPtr eq(MetaPtr m) const=0;
	virtual MetaPtr equal(MetaPtr m) const=0;

protected:
	// Convenient functions
	virtual std::string ToString() const=0;
	virtual void Parse(std::string s)=0;

public:
	// Properties
	void Text(std::string s)
	{
		Parse(s);
	}

	std::string Text() const
	{
		return ToString();
	}
};

这里有几点需要注意：

1. Clone函数的作用顾名思义，把它放在这里的一个最主要的目的在于：在“古代”Lisp中，表达式没有副作用，所有的表和原子都是不可变的（对照Python中的不可变类型），修改一个表唯一的办法就是生成一个新表，既然如此，那么Clone接口就是很重要的，我们将会看到，Clone在整个程序中大量使用（这恐怕也是效率低下的一个主要原因）。
2. eq和equal，在Common Lisp中，eq测试两个表的“同一性”而不是值是否相等，也就是说(eq '(a b) '(a b))在CL中返回nil，测试是否相等要使用equal，(equal '(a b) '(a b))在CL中返回T；但是在“古代”的Lisp中，没有同一性测试，只有等值测试，使用eq操作符，(eq '(a b) '(a b))在其中返回T。
   我在这里准备了两个操作符，但是由于我们要实现的是“古代”Lisp，所以eq在程序中并没有使用，只是放在这里而已。
3. 一个空表是一个原子，所以atom和null对于空表同时等于T。
4. ToString/Parse/Text用来处理文本输入输出，这里只是一个接口，具体实现在后面讨论。
5. 关于垃圾收集，我没精神去自制一个GC，也没精神去研究bohemGC等流行的库，所以我采用了一种“穷人的垃圾收集”，也就是引用计数，这种方式在我目前的这个实现中是有好处的，因为在这里不存在循环引用的问题（除非是我程序的Bug），每一个新表都是通过Clone制做的Deep copy或者凭空new出来的。实际上我连引用计数都没兴趣自己做，所以我用了Boost.SharedPtr，这个比较省事。