变量容器、运行环境、解析器、解释器都已经开发完毕,已经可以使用这些基础设施搭建一个Scheme解释器了。对于一个成熟的额解释器来说,性能式非常关键的,本文将对解释器进行简单的优化。

统计信息

在优化过程中,我们需要想办法衡量优化的效果,所有需要对解释过程中一些操作次数进行记录。statistic.hppstatistic.cpp实现了统计功能,提供了以下接口:

void createVariable();
void destroyVariable();
void copyVariable();
void traceVariable();
void finalizeVariable();
void printStatistic();
void applyStart();
void applyEnd();

这些接口需要在执行相应操作的时候调用,接口函数会根据调用次数进行统计。其中,printStatistic()用于打印统计信息。

垃圾回收

由于引用计数无法释放循环引用的对象,一种垃圾回收机制对于一个可用的解释器来说时非常重要的。这里将使用“标记-扫除”算法,基本思想就是标记程序能够访问到的内容,释放没标记的内容。很容易想到,只有保存在全局环境中的数据是可以访问的,而其他数据都是无法访问的。垃圾回收相关的代码位于garbage.hppgarbage.cpp中。

循环引用

垃圾回收主要针对循环引用,所以首先要了解循环引用发生在什么情况之下:

  • 情况1:序对循环引用

序对连接形成循环链表,只有释放掉序对中的两个元素才能沿着循环链使得序对的引用计数减为0,而只有当序对的引用计数减为0时,才能释序对,这样的矛盾导致这样的数据结构永远无法销毁。

  • 情况2:临时环境下的复合过程

有时程序需要在一个临时环境内定义一个过程,比如(let ((a 1)) (define (foo) a) (foo))。临时环境需要一个指向foo过程的指针,同时foo过程保存一个指向临时环境的指针,由于环境和过程都是采用引用计数法进行内存管理的,所以同样也形成了循环引用。

垃圾回收接口

垃圾回收需要内存保存标记信息,以及回收和标记的操作,所以可以定义一个垃圾回收对象的基类(接口),让需要进行垃圾回收的对象类(Variable和Environment)继承这个基类,并且实现finalize和scan方法。在C++中,派生类如果定义了拷贝构造函数和赋值函数,那么还需要显式地对基类进行拷贝和赋值。

class GarbageObject
{
protected:

	// Tag for GC
	std::shared_ptr<int> gcTag;

public:

	GarbageObject(): gcTag(std::make_shared<int>(0)) {}

	// Finalize value
	virtual void finalize() const {};

	// Scan and tag value in using
	virtual void scan(int tag) const {};
};
  • gcTag:标记信息

  • GarbageObject():构造函数

  • void finalize():切断对象和其他对象之间的联系后,使用引用计数技术自动回收内存

  • void scan(int tag):将值所在的内存进行标记

垃圾回收方法

首先设计一个垃圾回收器,需要包含以下变量和操作:

  • 监控列表vector<Variable> traceList:只有序对和复合过程会造成循环引用问题,所以需要把目前所有的序对和复合过程对象加入到监控列表中。

  • 添加操作void trace(const Variable& var):将一个对象加入到监控列表中。

  • 回收操作void collect(Environment& env):垃圾回收过程,从主环境开始,对所以可以访问到的对象进行标记。然后,检查监控表的对象,将未标记的对象进行finalize操作后丢弃。具体实现如下:

void collect(Environment& env)
{
	int tag = rand();
	env.scan(tag);
	vector<Variable> aliveList;
	for (const Variable& var : traceList)
		if (*var.gcTag == tag) {
			aliveList.push_back(var);
		} else {
			var.finalize();
			#ifdef STATS
			Statistic::finalizeVariable();
			#endif
		}
	std::swap(aliveList, traceList);
}

所以对于序对和复合过程这两个潜在循环引用的对象来说,在创建的时候,需要将它们添加到垃圾回收器的监控列表中。然后,在解释期间,需要不断地扫描主环境进行垃圾回收。

符号常量

程序中的符号主要用来表示各种变量名,变量名通常数量比较固定,并且在程序文本中会反复出现。如果使用一个常量池来保存所有的符号值,在需要构造符号值的时候从常量池中取出,这种优化将避免不必要的符号值的构造,节省了内存空间和管理内存的代价。常量池优化的代码位于variable.hpp以及variable.cpp

首先在Variable创建一个unordered_map来保存常量:

std::unordered_map<std::string, Variable> pool;

然后在Variable中添加一个方法管理常量池:

Variable Variable::createSymbol(const std::string& str)
{
	if (pool.find(str) == pool.end())
		pool[str] = Variable(str, Variable::TYPE_SYMBOL);
	return pool[str];
}

尾递归实现

Scheme标准对Scheme实现中的尾递归有着明确的要求,Scheme的解释器/编译器必须针对尾递归进行优化,否则,严重依赖递归的Scheme程序将很容易耗尽栈空间。尾调用优化的代码位于evaluator.hpp以及evaluator.cpp

尾调用

在大多数编程语言中,当一个函数调用另外的一个函数的时候,通常需要在栈中保存调用者本身的信息(函数内定义的变量、返回地址等)。当调用结束之后,调用者根据被调用函数返回值进行下一步的操作,最后返回结果,清除栈的记录。

考虑一种特殊情况:函数返回值直接来自于另一个函数的返回值。

(define (factor-iter n factor)
	(if (= n 0) factor)
				(factor-iter (- n 1) (* factor n)))

在上面的函数中,当n不等于0的时候,函数的返回值来自于(factor-iter n-1 factor*n)。在这个时候,我们不需要再次调用apply过程,而是直接在当前的apply过程中将过程对象、参数列表、求值环境进行更新后对(factor-iter n-1 factor*n)进行应用,然后最后只需要返回(factor-iter n-1 factor*n)的结果。

寻找尾调用

实现尾调用优化的前提就是首先找到过程体中的尾调用,对于不属于尾调用的表达式,直接进行求值,如果找到了尾调用,那么返回Tail对象。

参数结构体

首先定义一个结构体来传递尾调用的参数。

struct Tail {

	// Is application?
	bool app;

	// Arguments for apply
	Variable proc;
	Variable args;
	Environment env;

	// Constructor for value
	Tail(const Variable& val): app(false), args(val) {}

	// Constructor for application
	Tail(const Variable& proc, const Variable& args, const Environment& env):
		app(true), proc(proc), args(args), env(env) {}
};

如果过程体中不存在尾调用,那么直接返回返回值。

寻找尾调用的分派

对于自求值、赋值、定义、短路求值这些表达式来说,直接返回求值结果。如果是if、cond、let这些语句来说,分派到对应的处理函数中。如果表达式刚好是过程调用,那么将过程对象、参数列表、求值环境构造Tail对象返回。

Tail tail(const Variable &expr, Environment &env)
{
	#ifdef LOG
	VERBOSE("tail",expr);
	#endif
	if (IS_SELF_EVALUATING(expr)
		|| IS_VARIABLE(expr)
		|| IS_QUOTED(expr)
		|| IS_DEFINE_VAR(expr)
		|| IS_DEFINE_PROC(expr)
		|| IS_ASSIGNMENT(expr)
		|| IS_AND(expr)
		|| IS_OR(expr)
		|| IS_LAMBDA(expr))
		return Tail(eval(expr, env));
	if (IS_SEQ(expr))
		return tailSeq(SEQUENCE(expr), env);
	if (IS_IF(expr))	
		return IS_TRUE(eval(IF_PRED(expr), env)) ? tail(IF_CON(expr), env) : tail(IF_ALTER(expr), env);
	if (IS_COND(expr))
		return tailCond(expr, env);
	if (IS_LET(expr))
		return tailLet(expr, env);
	if (IS_APPLICATION(expr))	
		return Tail(eval(APPLICATION_NAME(expr), env), evalArgs(APPLICATION_ARGS(expr), env), env);
	throw Exception(string("tail: can't evaluate ") + expr.toString());
}
在表达式串寻找尾调用

在表达式串中,只需要在最后一个表达式中寻找尾调用。如果不存在表达式的话,返回VOID。

// Find the tail of sequence
Tail tailSeq(const Variable &expr, Environment &env)
{
	Variable tl = VAR_NULL;
	for (Variable it = expr; it != VAR_NULL; it = it.cdr()) {
		if (tl != VAR_NULL)
			eval(tl, env);
		tl = it.car();
	}
	return tl == VAR_NULL ? Tail(VAR_VOID) : tail(tl, env);
}
在if语句寻找尾调用

首先对判断条件进行求值,根据求值的结果在真操作或者假操作寻找尾调用。

在cond语句寻找尾调用

逐个测试cond语句中的条件,在相应的操作中寻找尾调用。

// Find the tail of cond
Tail tailCond(const Variable &expr, Environment &env)
{
	for (Variable clauses = COND_CLUASES(expr); clauses != VAR_NULL; clauses = clauses.cdr()) {
		const Variable& clause = clauses.car();
		if (IS_ELSE(clause) || IS_TRUE(eval(COND_PRED(clause), env)))
			return tailSeq(COND_CONSEQUENCE(clause), env);
	}
	return Tail(VAR_VOID);
}
在let语句寻找尾调用

根据let语句中需要绑定的变量和值创建一个新的环境,然后在新的环境中寻找尾调用。

// Find the tail of let
Tail tailLet(const Variable &expr, Environment &env)
{
	Environment extendEnv = Environment(VAR_NULL, VAR_NULL, env);
	for (Variable bindings = LET_BINDINGS(expr); bindings != VAR_NULL; bindings = bindings.cdr()) {
		const Variable& binding = bindings.car();
		extendEnv.defineVariable(BINDING_VAR(binding), eval(BINDING_VAL(binding), env));
	}
	return tailSeq(LET_BODY(expr), extendEnv);
}

尾调用优化

修改apply函数,如果过程是原生过程,那么直接返回返回值,如果是复合过程,需要在函数体中一边求值一边寻找尾调用。

如果成功找到了尾调用,那么更新过程对象、参数列表、求值环境,继续求值。否则,tailSeq将返回一个求值结果,函数直接返回这个求值结果。

// Apply procedure
Variable apply(const Variable &proc, const Variable &vals, Environment &env)
{
	try {
		Tail tl = Tail(proc, vals, env);
		while (tl.app) {
			const Variable& proc = tl.proc;
			const Variable& vals = tl.args;
			Environment& env = tl.env;
			if (proc.isPrim()) {		// Apply primitives
				return proc(vals, env);
			} else if (proc.isComp()) {	// Apply compound
				const Variable& body = proc.getProcedureBody();
				const Variable& args = proc.getProcedureArgs();
				Environment extendEnv = Environment(args, vals, proc.getProcedureEnv());
				tl = tailSeq(body, extendEnv);
			} else {					// Exception
				throw Exception(string("apply: can't apply ") + proc.toString());
			}
		}
		return tl.args;
	} catch (Exception e) {
		e.addTrace(proc.toString());
		throw e;
	}
}

总结

首先我在大二暑假,花了大概半个月的时间,初步完成了这个Scheme解释器。在大三上学习了编译原理之后,决定对代码进行重构,将手写的解析器改成Flex+Bison。重构之后的代码在可读性和可维护性上都好了不少,也添加了高精度计算的支持。

这个解释器已经可以运行《计算机程序的构造与解释》书中大部分的代码了,当然Scheme的特性要比这个解释器所实现的特性要多得多。例如:宏支持、向量、复数、丰富的内置过程等特性,有了良好的程序框架,这些特性还是容易实现的。

项目代码量1500+,不及一个随便写写的Java项目。写代码是最轻松的部分,最难的部分就是想办法不断设计好的结构,在编写过程中,总会发现一些自己当初不曾想到的情况,然后又要回去修改一些已经完成的代码。如果不是《计算机程序的构造与解释》和《C++ Primer》这两本书,我大概是不会写这个项目的。

参考文献

  1. Structure and Interpretation of Computer Programs 2/E
  2. The Scheme Programming Language 4/E