《计算机程序的构造与解释》的练习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

异常

无论是解释器本身还是运行的代码,总会出现错误的情况。作为解释器,不仅要知道错误内容,还需要知道错误发生的位置。代码位于exception.hpp,只有头文件。

class Exception
{
	string msg;
	vector trace;
public:
	Exception(const string& msg);
	void addTrace(const string& exp);
	void printStack();
};
  • msg:异常信息

  • trace:抛出异常信息经过的过程调用

  • Exception(const string& msg):使用异常信息初始化异常

  • void addTrace(const string& exp):向调用栈中增加一条记录

  • void printStack():输出异常信息以及调用栈到cerr

变量

值的类型

Scheme中的变量都是类型无关的,这就需要我们去定义一个类来封装类型无关。“类型无关”这是变量意义上的类型无关,变量的值还是有类型的。我们需要分析一下究竟需要用到多少的类型:

  • 特殊类型:
    • 真类型true
    • 假类型false
    • 空类型null
    • 无类型void。在Scheme中,例如define这样的表达式是不会返回任何值的,为了保持求值器求值过程的一致性,表达式返回无返回值类型;
  • 浮点类型:Scheme中的浮点的精度非常高;
  • 有理数类型:本项目使用boost库中的cpp_rational类型;
  • 符号类型:Scheme中的(quote ...)包含的内容就是符号类型,使用string表示;
  • 字符串类型:就是双引号中的字符串,同样使用string表示;
  • 序对类型:算是Scheme中数据结构的基石了,C++中有类似的pair
  • 基本过程:基本过程就是不能通过其他基本过程实现的过程,例如carcdrcons以及常见的算术运算、值类型检测等操作,使用一个string来保存名称,使用函数对象来保存过程;
  • 复合过程:复合过程又称闭包,包含参数列表、过程里的表达式和一个保存着所在作用域中所有变量的“环境”,还有一个过程名。

为了在实际使用中方便,我们可以将上面的几种类型合并到一种大类中:

  • 数值类型:浮点和有理数,都可以参与数值运算
  • 文本类型:字符串和符号,都包含字符串值
  • 过程类型:基本过程和复合过程,都可以进行“调用”

所以首先在Variable类定义值类型的枚举变量,为了方便进行复杂的类型检查操作,使用位图的方法表示:

// Type of variable
enum Type {
	TYPE_RATIONAL 	= 0x01,
	TYPE_DOUBLE 	= 0x02,
	TYPE_STRING 	= 0x04,
	TYPE_SYMBOL  	= 0x08,
	TYPE_SPEC     	= 0x10,
	TYPE_PAIR 	 	= 0x20,
	TYPE_PRIM 	 	= 0x40,
	TYPE_COMP 	 	= 0x80,
	// Type class
	TYPE_TEXT		= 0x0C,
	TYPE_NUMBER		= 0x03,
	TYPE_PROCEDURE	= 0xC0
};
​```

使用位图的好处在于,如果需要判断一种类型是否为数值类型,只需要进行位运算`type & TYPE_TEXT`。

#### 容器设计

设计了基本的值类型,我们接下来需要设计值的“容器”,通过封装来实现类型无关。首先需要考虑的就是容器应该具有怎么样的特性,是类似值特性还是类似引用特性。在Scheme中,pair对象保存的是两个“指针”,因此引用特性更佳。容器设计如下:

​```c++
class Variable
{
public:

	// Type of variable
	...
	
private:

	// Indent class
	struct Primitive;
	struct Compound;

	// Type alias
	using string = std::string;
	using ostream = std::ostream;
	using istream = std::istream;
	using ostringstream = std::ostringstream;
	using pair = std::pair<Variable, Variable>;
	using cpp_rational = boost::multiprecision::cpp_rational;
	using pool = std::map<string, Variable>;
	using function = std::function<Variable(const Variable&, Environment&)>;

	// Type of variable
	Type type;

	// Reference count
	int* refCount = nullptr;

	// Value of variable
	union {
		cpp_rational*	rationalPtr;
		double*		doublePtr;
		string*		stringPtr;
		pair*		pairPtr;
		void*		voidPtr;
		Primitive*	primPtr;
		Compound*	compPtr;
	};

public:

	// Constructor for special
	Variable();

	// Constructor for rational
	Variable(const cpp_rational& rational);

	// Constructor for double
	Variable(double value);

	// Constructor for rational, double, string and symbol
	Variable(const string &str, Type type);

	// Constructor for pairs
	Variable(const Variable& lhs, const Variable& rhs);

	// Constructor for primitive procedure
	Variable(const string& name, const function& func);

	// Constructor for compound procedure
	Variable(const string& name, const Variable& args, const Variable& body, const Environment& env);

	// Copy constructor
	Variable(const Variable& var);

	// Destructor
	~Variable();

	// Swap two variables
	friend void swap(Variable& lhs, Variable& rhs);

	// Assignment
	Variable& operator=(Variable var);

	// Standard I/O
	...
};
​```

Variable值的内存管理采用引用计数,给每一个值绑定一个计数器记录使用这个值的对象数量,当计数器的值变为0后,自动释放内存。

- `struct Primitive;`

基本过程结构体,定义如下:

​```c++
// Primitive procedure

struct Variable::Primitive
{
	string name;	// Name of procedure
	function func;	// Function object
	Primitive(const string& name, const function& func): name(name), func(func) {}
};
​```

- `struct Compound;`

复合过程结构体,定义如下:

​```c++
// Compound procedure

struct Variable::Compound
{
	string name;		// Name of procedure
	Variable args, body;// Argument and body
	Environment env;	// Closure
	Compound(const string& name, const Variable& args, const Variable& body, const Environment& env):
		name(name), args(args), body(body), env(env) {}
};

​```

- `Type type;`

值的类型。

- `int* refCount;`

引用计数。

- `union {...};`

保存变量的值指针。

- `Variable();`

默认的构造函数,默认类型为SPEC,无需保存任何值,但是为了一致性,同样需要引用计数。

- `Variable(const cpp_rational& rational);`

使用cpp_rational构造Variable,类型自然就是RATIONAL了。

- `Variable(double value);`

使用double构造Variable,类型自然就是DOUBLE了。

- `Variable(const string &str, Type type);`

string构造SYMBOLSTRINGDOUBLERATIONAL,如果类型错误或者有理数被零除将抛出异常。

- `Variable(const Variable& lhs, const Variable& rhs);`

使用两个Variable构造一个PAIR

- `Variable(const string& name, const function& func);`

使用一个过程名字和一个函数对象构造一个基本过程。

- `Variable(const string& name, const Variable& args, const Variable& body, const Environment& env);`

使用过程名称、参数列表、过程体和环境构造一个复合过程。

- `Variable(const Variable& var);`

拷贝构造函数,拷贝类型、计数器指针、值指针,并且将指针的值加一。

- `~Variable();`

析构函数,将计数器的值减一,如果计数器变为零,那么说明值不再被使用,释放计数器和值。

- `friend void swap(Variable& lhs, Variable& rhs);`

交换函数,交换两个对象的类型、计数器指针、值指针即可。

- `Variable& operator=(Variable var);`

赋值函数,采用拷贝交换的方式。

#### I/O

输入输出,其中输入操作需要调用解析器。

​```c++
// Standard I/O
friend ostream& operator<<(ostream& out, const Variable& var);
friend istream& operator>>(istream& in, Variable& var);
​```

#### 类型约束

有些操作只限于某些类型,因此需要一个函数来检查值类型,如果类型不符合,那么抛出异常。getTypeName用来获取类型的名称。

​```c++
// Require type, throw exception if type is wrong
void requireType(const string &caller, int type) const;

// Get type name
static string getTypeName(int type);
​```

#### 转换操作

在进行错误报告的时候,需要将值转换成string。在进行计算的时候,可能需要将RATIONAL转换成DOUBLE

​```c++
// Convert operations
string toString() const;
double toDouble() const;
​```

#### 检查操作

检查操作用用来判断类型。

​```c++
// Check operations
bool isNull() const;
bool isVoid() const;
bool isPair() const;
bool isNumber() const;
bool isSymbol() const;
bool isString() const;
bool isPrim() const;
bool isComp() const;
bool isProcedure() const;
​```

#### 算术操作

只有数值类型的值能参与算术运算,否则抛出类型约束异常。如果DOUBLERATIONAL进行运算,那么RATIONAL会被转换成DOUBLE。其中,如果除法操作的除数为零,那么也将抛出异常。

​```c++
// Arithmetic operations
friend Variable operator+(const Variable& lhs, const Variable& rhs);
friend Variable operator-(const Variable& lhs, const Variable& rhs);
friend Variable operator*(const Variable& lhs, const Variable& rhs);
friend Variable operator/(const Variable& lhs, const Variable& rhs);
friend Variable operator-(const Variable& var);
​```

#### 比较操作

只有数值类型能够进行大小比较,其他类型只能进行相等/不等比较。如果DOUBLERATIONAL进行比较,那么RATIONAL会被转换成DOUBLE。其中,数值、字符串、符号类型对值进行比较,序对类型将进行递归比较,其他类型比较值的指针,

​```c++
// Compare operations
friend bool operator<(const Variable& lhs, const Variable& rhs);
friend bool operator>(const Variable& lhs, const Variable& rhs);
friend bool operator<=(const Variable& lhs, const Variable& rhs);
friend bool operator>=(const Variable& lhs, const Variable& rhs);
friend bool operator==(const Variable& lhs, const Variable& rhs);
friend bool operator!=(const Variable& lhs, const Variable& rhs);
​```

#### 序对操作

序对的操作只限于序对。

​```c++
// Pair operations
Variable car() const;
Variable cdr() const;
Variable setCar(const Variable& var) const;
Variable setCdr(const Variable& var) const;
​```

#### 过程操作

其中,函数调用运算符只限于基本过程,获取环境、参数列表、过程体只限于复合过程。

​```c++
// Procedure operations
Variable operator()(const Variable& arg, Environment& env) const;
Variable getProcedureArgs() const;
Variable getProcedureBody() const;
string getProcedureName() const;
Environment getProcedureEnv() const;
​```

不难发现,其中没有逻辑操作。当然了,这不是我漏了什么,因为在Scheme中,andor操作具有短路求值的特性,因此需要交给解释器来操作。

## 环境

运行环境用于保存当前作用域内的所有变量,是实现闭包的基础,借助于C++map,可以实现高效的变量查找与创建。运行环境需要包含当前作用域内的变量-值映射关系,以及一个外层的环境,当然顶层环境就没有外层环境了。运行环境需要在求值器中传递,拷贝后的环境和原对象应该是一致的,需要具有引用特性,

​```c++
class Environment
{
	// Type alias
	using string = std::string;
	using frame = std::map<string, Variable>;
	template <typename T> using shared_ptr = std::shared_ptr<T>;

	// Data member
	shared_ptr<Environment> encloseEnvPtr;
	shared_ptr<frame> framePtr;

	// Add variables
	void addVars(const Variable& vars, const Variable& vals);

	// Find variable
	frame::iterator findVar(const string& var);

public:
	
	// Constructor for top-environment
	Environment(const Variable& vars = VAR_NULL, const Variable& vals = VAR_NULL);

	// Constructor for sub-environment
	Environment(const Variable& vars, const Variable& vals, const Environment& encloseEnv);

	// Assign variable
	Variable assignVariable(const Variable& var, const Variable& val);

	// Define variable
	Variable defineVariable(const Variable& var, const Variable& val);
	Variable defineVariable(const string& var, const Variable& val);

	// Lookup variable
	Variable lookupVariable(const Variable& var);
};
​```

- `shared_ptr<Environment> encloseEnvPtr;`

外层环境。

- `shared_ptr<frame> framePtr;`

当前环境中的所有变量-值。

- `Environment(const Variable& vars = VAR_NULL, const Variable& vals = VAR_NULL);`

构造一个顶层环境。

- `Environment(const Variable& vars, const Variable& vals, const Environment& encloseEnv);`

构造一个子环境。

- `Variable assignVariable(const Variable& var, const Variable& val);`

变量赋值。

- `Variable defineVariable(const Variable& var, const Variable& val);`

在本环境中定义一个变量。

- `Variable lookupVariable(const Variable& var);`

变量查找。

- `void addVars(const Variable& vars, const Variable& vals);`

将一组变量和值加入环境中。

- `frame::iterator findVar(const string& var);`

从内向外查找某个变量。