前两天和mayadong说到lisp，想起很久以前看过的一篇文章《Lisp之根源》(http://daiyuwen./gb/rol/roots_of_lisp.html)。当时看得似懂非懂，于是想找来再看看。
搜到文章以后，从头到尾看了一遍，基本上算是看懂了。文章中的lisp只有lambda, label以及7个原始操作符。而这种lisp的有趣之处是它可以实现一个函数作为解释自己的解释器。不过这个解释器并不是解释字符形式的源码，而是解释表示lisp程序的表。看完文章后，我突然想，如果用C++实现一个这样的解释器如何呢？
分析了一下，觉得应该不是很困难。在这几天找了些时间，做了这么一个东西。这个解释器相当简陋，甚至没有出错的处理，如果lisp程序有错，要么就没有任何反应，要么解释器本身就会挂掉。而且只能解释在《Lisp之根源》中说的那种lisp语言。所以冠之“迷你”以解嘲。
其实用C++写解释器程序到没费太大的劲，只是用lisp测试时把我累坏了。lisp这语言真不是盖的，括号稀里哗啦一大堆，看得我眼花缭乱。
为了输出结果，增加了一个print函数。
用法：
可以把lisp源程序作为参数传递给程序minilisp。如果没有参数，minilisp将试图执行test.lsp。
比如，有一个subst.lsp文件：
(defun subst (x y s) ; 函数subst用x替换s中所有的y
(cond
((atom s) (cond
((eq s y) x)
('t s)))
('t (cons (subst x y (car s))
(subst x y (cdr s))))))
(label s '(Hello this (no any Hello) word))
(print (subst 'Hi 'Hello s))
F:\Projects\minilisp>minilisp subst.lsp
(Hi this (no any Hi) word)
源程序，可执行文件，及测试lisp程序，可以在这儿下载
http://code.google.com/p/scriptdraw/downloads/detail?name=minilisp.zip&can=2&q=#makechanges
备用地址 http:///file/aq5fib2x#
不想下载的，可以直接看下面的源程序：
#include <iostream>
#include <fstream>
#include <string>
#include <map>
using namespace std;
#include <assert.h>
typedef string* Atom;
// Cell为链表的节点，Cell*对应lisp中的表
struct Cell {
void* first; // 节点的第一个元素，是一个原子(Atom)或一个链表(Cell*)
Cell* rest;
};
// 解析结果
struct Result {
const char* tail; // 没有解析的源码位置
void* parsed; // 解析出的内容
Result(const char* r, void* p) : tail(r), parsed(p) {}
};
typedef map<Atom, void*> Environment; // 包含各种变量的环境
// ------ Atom ------
const int MAX_ATOMS = 4096; // 最大原子数
string* atomTable; // 所有原子存放在一个统一的表中
string* lastAtom; // 最后一个原子的位置
map<string, Atom> atomDict; // 原子字典，根据字符串查找对应的原子
Atom atomTrue, atomLambda, atomQuote; // 解释器中用到的原子
bool isCell(void* p); // 指针p是否指向一个Cell
void gc(Environment& env); // 进行垃圾收集
void* gcAlloc(size_t size); // GC方式分配内存
// 创建一个原子
Atom createAtom(const string& sym) {
if(atomDict.find(sym) == atomDict.end()) { // 如果在字典中没有这个原子
if(lastAtom < atomTable + MAX_ATOMS) { // 原子表中还有空位
*lastAtom = sym; // 加入原子表中
atomDict[sym] = lastAtom; // 放入原子字典
++ lastAtom;
return lastAtom - 1;
} else {
return 0; // 原子溢出，简单起见，不处理
}
}
return atomDict[sym]; // 在原子表中已存在该原子，直接返回
}
// p 是否是一个原子
bool isAtom(void* p) {
return atomTable <= p && p <= atomTable + MAX_ATOMS;
}
// 创建一个lisp中的表
Cell* cons(void* fst, Cell* rst) {
Cell* c = (Cell*)gcAlloc(sizeof(Cell));
c->first = fst;
c->rest = rst;
return c;
}
// ------ Parser ------
Result parseList(const char* p);
Result parseAtom(const char* p);
bool isAtomChar(char ch);
bool isBlank(char ch);
const char* skipBlanks(const char* p);
// 解析源码p
Result parse(const char* p) {
p = skipBlanks(p); // 跳过空白
if(*p == '(') { // 如果是(，解析表
return parseList(p+1);
} else if(*p == '\'') { // '表示quote
Result r = parse(p+1);
return Result(r.tail, cons(atomQuote, cons(r.parsed, 0)));
} else if(isAtomChar(*p)) { // 如果是组成原子的字符
return parseAtom(p);
}
return Result(p, 0);
}
// 解析原子
Result parseAtom(const char* p) {
const char* q = p;
while(isAtomChar(*q)) {
++q;
}
return Result(q, createAtom(string(p, q)));
}
// 解析表
Result parseList(const char* p) {
p = skipBlanks(p);
if(*p == ')') { // 表结束了，返回一个空表()
return Result(p+1, 0);
}
Result rfirst = parse(p); // 解析表中的第一个元素
Result rrest = parseList(rfirst.tail); // 解析其它元素
return Result(rrest.tail, cons(rfirst.parsed, (Cell*)rrest.parsed)); // 将两者构造成一个表
}
// 除'(' ')'和空白外都是原子字符
bool isAtomChar(char ch) {
return ch != '\0' && ch != '(' && ch != ')' && !isBlank(ch);
}
// 空格、制表符、换行符等都是空白字符
bool isBlank(char ch) {
return ch == ' ' || ch == '\t' || ch == '\v' || ch == '\r' || ch == '\n';
}
// 跳过空白，返回值为p的非空白的开始位置
const char* skipBlanks(const char* p) {
while(isBlank(*p))
p++;
return p;
}
// ------ evaluate -------
typedef void* (*PrimeFunc)(Environment* env, Cell* args);
const int MAX_LAMBDAS = 2048;
void* evalExpression(Environment* env, Cell* expr);
void* evalValue(Environment* env, void* v);
// 输出原子和表
void print(void* x) {
if(x == 0) {
cout << "()"; // 空表
} else if(isAtom(x)) { // 原子
Atom atom =(Atom)x;
cout << *atom;
} else { // 表
cout << "(";
Cell* cell = (Cell*)x;
while(cell) {
print(cell->first);
cell = cell->rest;
if(cell) {
cout << " ";
}
}
cout << ")";
}
}
// 参数为表达式的函数
// 表达式直接传递给函数，不进行求值
// quote, lambda, label, cond, defun对应的C++函数
void* primeQuote(Environment* env, Cell* args) {
return args->first;
}
void* primeLambda(Environment* env, Cell* args) {
return cons(atomLambda, args);
}
void* primeLabel(Environment* env, Cell* args) {
if(isAtom(args->first)) {
Atom nameAtom = Atom(args->first);
(*env)[nameAtom] = evalValue(env, args->rest->first);
}
return 0;
}
void* primeCond(Environment* env, Cell* args) {
Cell* c = args;
while (c != 0) {
if(isAtom(c->first)) break; // error!
Cell* pair = (Cell*)(c->first);
if(evalValue(env, pair->first) != 0) {
return evalValue(env, pair->rest->first);
}
c = c->rest;
}
return 0;
}
void* primeDefun(Environment* env, Cell* args) {
Cell* lam = cons(atomLambda, args->rest);
void* name = args->first;
return primeLabel(env, cons(name, cons(lam, 0)));
}
// 参数为值的函数
// 表达式求值后，将值传递给函数
// print, car, cdr, cons...对应的函数
void* primePrint(Environment* env, Cell* args) {
print(args->first);
if(args->rest) {
cout << " ";
primePrint(env, args->rest);
}
cout << endl;
return 0;
}
void* primeFirst(Environment* env, Cell* args) {
if(args->first && !isAtom(args->first)) {
Cell* arg1 = (Cell*)(args->first);
return arg1->first;
}
return 0;
}
void* primeRest(Environment* env, Cell* args) {
if(args->first && !isAtom(args->first)) {
Cell* arg1 = (Cell*)(args->first);
return arg1->rest;
}
return 0;
}
void* primeCons(Environment* env, Cell* args) {
return cons(args->first, (Cell*)(args->rest->first));
}
void* primeAtom(Environment* env, Cell* args) {
if(args->first == 0 || isAtom(args->first)) { //
return atomTrue;
}
return 0;
}
void* primeEq(Environment* env, Cell* args) {
void* fst = args->first;
void* snd = args->rest->first;
if(fst == 0 && snd == 0 ||
isAtom(fst) && isAtom(snd) && fst == snd) {
return atomTrue;
}
return 0;
}
void* primeList(Environment* env, Cell* args) {
return args;
}
// 函数和名称对应的表，用于注册函数
PrimeFunc exprArgFuncTable[] = {
primeQuote,
primeLambda,
primeLabel,
primeCond,
primeDefun
};
const char* exprArgFuncNames[] = {
"quote",
"lambda",
"label",
"cond",
"defun"
};
PrimeFunc valArgFuncTable[] = {
primePrint,
primeFirst,
primeRest,
primeCons,
primeAtom,
primeEq,
primeList
};
const char* valArgFuncNames[] = {
"print",
"car",
"cdr",
"cons",
"atom",
"eq",
"list"
};
// 注册函数到lisp
#define REGISTER_FUNCTIONS(env, type) registerFunctions(env, type##Names, type##Table, sizeof(type##Names)/sizeof(const char*))
void registerFunctions(Environment& env, const char** names, PrimeFunc* funcs, size_t n) {
for (unsigned i=0; i<n; i++) {
Atom nameAtom = createAtom(names[i]);
env[nameAtom] = funcs + i;
}
}
bool isExprArgFunc(void* p) {
const char* tab = (const char*)exprArgFuncTable;
return tab <= p && p < tab + sizeof(exprArgFuncTable);
}
bool isValArgFunc(void* p) {
const char* tab = (const char*)valArgFuncTable;
return tab <= p && p < tab + sizeof(valArgFuncTable);
}
void* getValue(Environment* env, Atom name) {
Environment::iterator it = env->find(name);
if(it != env->end())
return it->second;
return 0;
}
void* evalValue(Environment* env, void* v) {
if(isAtom(v)) {
return getValue(env, Atom(v));
} else {
return evalExpression(env, (Cell*)v);
}
}
Cell* evalArguments(Environment* env, Cell* args) {
if(args == 0)
return 0;
return cons(evalValue(env, args->first), evalArguments(env, args->rest));
}
// 对一个表达式(也是一个表)求值
void* evalExpression(Environment* env, Cell* expr) {
if(expr == 0) // 空表
return 0;
void* v = evalValue(env, expr->first); // 对表的第一个元素求值
if(v != 0) {
if(isExprArgFunc(v)) { // 如果是传表达式的函数
PrimeFunc fn = *(PrimeFunc*)v; // 转换成函数指针
return fn(env, expr->rest); // 将表达式直接传递给函数
} else if(isValArgFunc(v)) { // 如果是传值的函数
PrimeFunc fn = *(PrimeFunc*)v;
return fn(env,
evalArguments(env, expr->rest)); // 对参数的表达式求值，再传递给函数
} else {
if(isCell(v)) { // 如果是Cell
Cell* c = (Cell*)v;
Atom fst = Atom(c->first);
if(Atom(c->first) == atomLambda) { // 如果是lambda表达式
Cell* rest = c->rest;
Cell* params = (Cell*)(rest->first);
void* body = rest->rest->first;
Environment e = *env;
Cell* argus = evalArguments(env, expr->rest); // 对参数求值
while (params) { // 将参数的值绑定到形参上
Atom name = Atom(params->first);
e[name] = argus->first;
params = params->rest;
if(argus)
argus = argus->rest;
}
return evalValue(&e, body); // 对lambda表达式体求值
}
}
}
}
return 0;
}
void evalStatement( Environment& env, Cell* stmt ) {
evalExpression(&env, stmt);
gc(env);
}
// ------ GC -------
// 简单的垃圾回收
void* gcmem;
char* gcptr;
void* tomem;
char* toptr;
const int MAX_MEM = 64*1024;
bool isCell(void* p) {
return gcmem <= p && p < gcptr;
}
void gcInit() {
gcptr = (char*)(gcmem = malloc(MAX_MEM));
}
void gcEnd() {
free(gcmem);
}
// 4字节对齐
inline void* align(char* val) {
return (void*)(((unsigned)val + 3) & ~3);
}
// gcmem指向大块内存，每次分配直接从中划出来
void* gcAlloc(size_t size) {
assert(gcptr < (char*)gcmem + MAX_MEM);
void* p = 0;
if(gcptr + size < (char*)gcmem + MAX_MEM) {
p = gcptr;
gcptr = (char*)align(gcptr + size);
}
return p;
}
// 回收
// 遍历内存进行复制
void* gcVisit(Cell* c) {
void* p = c->first;
if(tomem <= p && p < toptr) {
return p;
}
Cell* toc = (Cell*)toptr; // 将访问到Cell复制到新分配的内存中
*toc = *c;
c->first = toptr;
toptr += sizeof(Cell);
if(isCell(toc->first)) { // 如果第一个元素是一个Cell
toc->first = gcVisit((Cell*)(toc->first)); // 访问之
}
if(toc->rest) {
toc->rest = (Cell*)gcVisit(toc->rest); // 访问其它的元素
}
return toc;
}
// 在执行完一个语句后，进行一次回收
void gc(Environment& env) {
toptr = (char*)(tomem = malloc(MAX_MEM)); // 先分配同样大的内存
for(Environment::iterator it=env.begin(); it != env.end(); ++it) { // 从环境中变量使用的Cell出发
if(isCell(it->second)) {
it->second = gcVisit((Cell*)(it->second)); // 访问每个用到的Cell
}
}
free(gcmem);
gcmem = tomem;
gcptr = toptr;
}
// 判断括号是否匹配
bool parenMatched(const string& stmt) {
int counter = 0;
for(unsigned i=0; i<stmt.length(); i++) {
if(stmt[i] == '(')
++ counter;
else if(stmt[i] == ')')
-- counter;
if(counter < 0)
return false;
}
return counter == 0;
}
void run(Environment& env, char* filename) {
ifstream istrm(filename);
if(!istrm.is_open()) {
cerr << "open file fail!" << endl;
return;
}
string statement = "";
while (!istrm.eof()) {
char line[512];
istrm.getline(line, 512);
char* comStart = strchr(line, ';');
if(comStart) { // 如果是注释，跳过
*comStart = '\0';
}
if(statement == "") {
statement = line;
} else {
statement += string(" ")+line;
}
if(!parenMatched(statement)) { // 如果括号不匹配，说明这一行还没有结束
continue;
}
Result r = parse(statement.c_str());
if(r.parsed == 0)
continue;
evalStatement(env, (Cell*)r.parsed);
statement = "";
}
}
int main(int argc, char** argv) {
atomTable = new string[MAX_ATOMS];
lastAtom = atomTable;
gcInit();
Environment env;
atomTrue = createAtom("t");
atomLambda = createAtom("lambda");
atomQuote = createAtom("quote");
REGISTER_FUNCTIONS(env, exprArgFunc);
REGISTER_FUNCTIONS(env, valArgFunc);
env[createAtom("p")] = env[createAtom("print")];
char* filename = "test.lsp";
if(argc > 1) {
filename = argv[1];
}
run(env, filename);
gcEnd();
delete[] atomTable;
return 0;
}
