解释

一旦解析获得了S表达式,解释过程就可以实现了。表达式有以下几种:

  • 自求值:数字和字符串;
  • 符号:(quote <quoted>)
  • 变量:符号;
  • 定义:(define <var> <val>)或者(define (<var> <arg1> <arg2> ... <argn>) <exp1> <exp2> ... <expn>)
  • 赋值:(set! <var> <val>)
  • 和:(and <exp1> <exp2> ... <expn>)
  • 或:(or <exp1> <exp2> ... <expn>)
  • 序列:(begin <exp1> <exp2> ... <expn>)
  • if:(if <predication> <consequence> <alternative>)
  • lambda:(lambda (<arg1> <arg2> ... <argn>) <exp1> <exp2> ... <expn>)
  • cond:(cond (<condition> <consequence>) ... (else <consquence>))
  • let:(let ((<var1> <val1>) ... (<varn> <valn>)) <exp1> ... <expn>)
  • 过程调用:(<proc> <arg1> ... <argn>)

解释部分的代码位于evaluator.hpp以及evaluator.cpp。表达式的判断可以使用宏定义来实现。

#define TAGGED_LIST(exp, tag)	((exp).isPair() && (exp).car().toString() == (tag))
// BOOL
#define IS_TRUE(exp)		((exp) != VAR_FALSE)
#define IS_FALSE(exp)		((exp) == VAR_FALSE)
// SELF EVALUATING
#define IS_SELF_EVALUATING(exp)	((exp).isNumber() || (exp).isString())
// VARIABLE
#define IS_VARIABLE(exp)	((exp).isSymbol())
// QUOTED
#define IS_QUOTED(exp)		TAGGED_LIST(exp, "quote")
#define QUOTED(exp)		((exp).cdr().car())
// DEFINE
#define IS_DEFINE(exp)		TAGGED_LIST(exp, "define")
#define IS_DEFINE_VAR(exp)	(IS_DEFINE(exp) && exp.cdr().car().isSymbol())
#define IS_DEFINE_PROC(exp)	(IS_DEFINE(exp) && exp.cdr().car().isPair())
#define DEFINE_VAR_NAME(exp)	((exp).cdr().car())
#define DEFINE_VAR_VAL(exp)	((exp).cdr().cdr().car())
#define DEFINE_PROC_NAME(exp)	((exp).cdr().car().car())
#define DEFINE_PROC_ARGS(exp)	((exp).cdr().car().cdr())
#define DEFINE_PROC_BODY(exp)	((exp).cdr().cdr())
// ASSIGNMENT
#define IS_ASSIGNMENT(exp)	TAGGED_LIST(exp, "set!")
#define ASSIGNMENT_VAR(exp)	((exp).cdr().car())
#define ASSIGNMENT_VAL(exp)	((exp).cdr().cdr().car())
// SEQUENCE
#define IS_SEQ(exp)		TAGGED_LIST(exp, "begin")
#define SEQUENCE(exp)		((exp).cdr())
// LAMBDA
#define IS_LAMBDA(exp)		TAGGED_LIST(exp, "lambda")
#define LAMBDA_ARGS(exp)	((exp).cdr().car())
#define LAMBDA_BODY(exp)	((exp).cdr().cdr())
// AND
#define IS_AND(exp)		TAGGED_LIST(exp, "and")
#define AND_ARGS(exp)		((exp).cdr())
// OR
#define IS_OR(exp)		TAGGED_LIST(exp, "or")
#define OR_ARGS(exp)		((exp).cdr())
// IF
#define IS_IF(exp)		TAGGED_LIST(exp, "if")
#define IF_PRED(exp)		((exp).cdr().car())
#define IF_CON(exp)		((exp).cdr().cdr().car())
#define IF_ALTER(exp)		((exp).cdr().cdr().cdr().car())
#define IS_APPLICATION(exp)	((exp).isPair())
#define IS_COND(exp)		TAGGED_LIST(exp, "cond")
#define IS_ELSE(exp)		TAGGED_LIST(exp, "else")
// COND
#define COND_CLUASES(exp)	((exp).cdr())
#define COND_PRED(exp)		((exp).car())
#define COND_CONSEQUENCE(exp)	((exp).cdr())
// LET
#define IS_LET(exp)		TAGGED_LIST(exp, "let")
#define LET_BINDINGS(exp)	((exp).cdr().car())
#define BINDING_VAR(exp)	((exp).car())
#define BINDING_VAL(exp)	((exp).cdr().car())
#define LET_BODY(exp)		((exp).cdr().cdr())
// APPLICATION
#define APPLICATION_NAME(exp)	((exp).car())
#define APPLICATION_ARGS(exp)	((exp).cdr())

解释分派

根据语句类型,进行对应的操作,返回求值结果。

Variable eval(const Variable &expr, Environment &env)
{
	if (IS_SELF_EVALUATING(expr))
		return expr;
	if (IS_VARIABLE(expr))
		return env.lookupVariable(expr);
	if (IS_QUOTED(expr))
		return QUOTED(expr);
	if (IS_DEFINE_VAR(expr))
		return env.defineVariable(DEFINE_VAR_NAME(expr), eval(DEFINE_VAR_VAL(expr), env));
	if (IS_DEFINE_PROC(expr))
		return env.defineVariable(DEFINE_PROC_NAME(expr), 
				Variable(DEFINE_PROC_NAME(expr).toString(),
					DEFINE_PROC_ARGS(expr),
					DEFINE_PROC_BODY(expr), env));
	if (IS_ASSIGNMENT(expr))
		return env.assignVariable(ASSIGNMENT_VAR(expr), eval(ASSIGNMENT_VAL(expr), env));
	if (IS_SEQ(expr))
		return evalSeq(SEQUENCE(expr), env);
	if (IS_AND(expr))
		return evalAnd(expr, env);
	if (IS_OR(expr))
		return evalOr(expr, env);
	if (IS_IF(expr))
		return IS_TRUE(eval(IF_PRED(expr), env)) ? eval(IF_CON(expr), env) : eval(IF_ALTER(expr), env);
	if (IS_COND(expr))
		return evalCond(expr, env);
	if (IS_LAMBDA(expr))
		return Variable("lambda expression", LAMBDA_ARGS(expr), LAMBDA_BODY(expr), env);
	if (IS_LET(expr))
		return evalLet(expr, env);
	if (IS_APPLICATION(expr))
		return apply(eval(APPLICATION_NAME(expr), env), evalArgs(APPLICATION_ARGS(expr), env), env);
	throw Exception(string("eval: can't evaluate ") + expr.toString());
}

和求值

和需要短路求值,遇到false结束求值,返回false,只有全部的求值结果为true时返回true。

Variable evalAnd(const Variable &expr, Environment &env)
{
	for (Variable it = AND_ARGS(expr); it != VAR_NULL; it = it.cdr())
		if (IS_FALSE(eval(it.car(), env)))
			return VAR_FALSE;
	return VAR_TRUE;
}

或求值

或也一样需要短路求值,遇到true结束求值,返回true,只有全部的求值结果为false时返回false。

Variable evalOr(const Variable &expr, Environment &env)
{
	for (Variable it = OR_ARGS(expr); it != VAR_NULL; it = it.cdr())
		if (IS_TRUE(eval(it.car(), env)))
			return VAR_TRUE;
	return VAR_FALSE;
}

表达式序列求值

从头到尾依次求值,返回最后一个表达式的求值结果。

Variable evalSeq(const Variable &expr, Environment &env)
{
	Variable val = VAR_VOID;
	for (Variable it = expr; it != VAR_NULL; it = it.cdr())
		val = eval(it.car(), env);
	return val;
}

cond表达式求值

逐个尝试每个条件,如果条件成立,则执行条件后面的表达式,如果条件是else则无条件执行对应的表达式。

Variable evalCond(const Variable &expr, Environment &env)
{
	for (Variable clauses = COND_CLUASES(expr); clauses != VAR_NULL; clauses = clauses.cdr()) {
		Variable clause = clauses.car();
		if (IS_ELSE(clause) || IS_TRUE(eval(COND_PRED(clause), env)))
			return evalSeq(COND_CONSEQUENCE(clause), env);
	}
	return VAR_VOID;
}

let表达式求值

let表达式的求值过程:创建一个新的环境,以当前环境为外层环境,将let表达式中需要绑定的变量和值加入新的环境中,接着在新的环境中对表达式进行求值。

Variable evalLet(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()) {
		Variable binding = bindings.car();
		extendEnv.defineVariable(BINDING_VAR(binding), eval(BINDING_VAL(binding), env));
	}
	return evalSeq(LET_BODY(expr), extendEnv);
}

参数列表求值

对过程参数列表求值,将求值结果组成新的链表。

Variable evalArgs(const Variable &args, Environment &env)
{
	Variable head = Variable(VAR_NULL, VAR_NULL);
	Variable tail = head;
	for (Variable it = args; it != VAR_NULL; it = it.cdr()) {
		Variable ntail = Variable(eval(it.car(), env), VAR_NULL);
		tail.setCdr(ntail);
		tail = ntail;
	}
	return head.cdr();
}

应用过程

首先对过程表达式求值,获取过程。当遇到基本过程时,直接使用参数值列表调用基本过程即可。如果遇到的是符合过程,根据参数变量列表和值列表构造一个新的环境,新的环境的外层环境为过程体绑定的环境,然后在新的环境中对过程体内的表达式进行求值。

如果在应用过程中抛出了异常,那么需要将过程信息添加到异常中后再次抛出异常。

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

内置过程和常量

和内置过程和常量管理相关的代码位于primitive.hppprimitive.cpp中。Scheme求值器需要提供一些内置的过程和常量,在解释器启动的时候,需要将所有的内置过程和内置常量加入到初始环境中,因此需要定义一个函数Environment setupEnvironment()来创建初始环境。

其中,所有的内置过程定义在std::vector<Variable> prims向量中,需要加入出事环境的内置常量只有VAR_TRUE、VAR_FALSE和VAR_NULL。

Environment setupEnvironment()
{
	Environment env;
	// add constant 
	env.defineVariable("true", VAR_TRUE);
	env.defineVariable("false", VAR_FALSE);
	env.defineVariable("null", VAR_NULL);
	// add primitive procedure
	for (const Variable &prim : prims)
		env.defineVariable(prim.getProcedureName(), prim);
	return env;
}

内置的过程一般包括以下几种:

  • 数值:数据计算就是加减乘除取余数等操作。其中,乘法操作和加法操作可以由无限数量的参数。

  • 逻辑:包括值类型的判断、数值比较、逻辑运算。由于and和or的短路求值特性,不行用基本过程实现,所以not也就成为了唯一的逻辑运算基本过程。

  • 链表:

    • cons、car、cdr、set-car!和set-cdr!这五个过程是Scheme数据结构操作的基础。

    • list过程用于创建一个链表。

    • length计算链表长度。

    • append过程能够合并无数个链表。

    • map算是最复杂的基本过程,从参数列表中获取proc过程的参数,然后将每次的求值结果组成链表返回。

  • 接口

    • newline和display都用于输出。newline输出一个换行,而display输出参数。

    • read从标准输入流读取值。

    • error用于抛出程序自定义的异常。

    • eval过程和apply过程对应着求值器的eval函数和apply函数。

求值循环

终于可以来实现求值入口了。首先创建一个全局环境,然后开始求值循环。在求值循环中,每次读取一个Variable对象,如果遇到EOF就结束循环。接着对表达式进行求值,如果返回空,则不输出,否则输出结果。如果在解析或求值过程中出现异常,那么捕获异常,输出异常信息和异常调用栈。为了处理运行中产生的垃圾,需要定期执行垃圾回收过程。

#include <iostream>
#include "variable.hpp"
#include "primitive.hpp"
#include "evaluator.hpp"
#include "exception.hpp"
#include "statistic.hpp"

using namespace std;

int main(int argc, char const *argv[])
{
	Variable var;
	// Setup initial environment
	Environment env = Primitive::setupEnvironment();
	while (cout << '>' && cin >> var) {
		try {
			Variable ret = Evaluator::eval(var, env);
			if (ret != VAR_VOID)
				cout << ret << endl;
		} catch (Exception e) {
			e.printStack();
		}
		// Collect garbage
		GarbageCollector::collect(env);
		// Print statistic information
		#ifdef STATS
		Statistic::printStatistic();
		#endif
	}
	return 0;
}

解释器入口对应源代码中的main.cpp。当然,真正的解释器入口还需要支持一些复杂的参数,加载一些内置的代码片段等等。