lisp解释器实现总结

考完研后玩了一个多星期，总之闲了后就想着得干点东西，不能一直玩了。之前写的c语言编译器前端也卡在了{}初始化器的解析上，写不动了。所以在其他大佬的推荐下开始实现一个自己的lisp解释器，跟随的教程是https://github.com/Robert-van-Engelen/tinylisp。

相较于教程的调整

使用parser和lexer生成器。由于lisp语言完全基于列表，而列表实现起来较为简单（复杂的什么定义我也不太清楚），因此其lexer和parser的实现起来也相对简单，简化后可能几十行就能实现。所以手写LL(1)的parser应该是较为合适的。但是因为我之前实现的parser都是手写的LL(1)类型，为了能尝试点新东西或者说成熟的业界工具，我打算使用Flex/Bison来处理lexer/parser过程，生成对应代码。

由于计算过程只有浮点数，为了能省一点内存，对任意数值，创建数值对象时会根据数值实际的大小和内容来自动推导并创建足够存储数值的对象类型。

// 实现片段
if (number > FLT_MAX || number < -FLT_MAX) {
    !double_eq(number, (float)number)) {
  e = create_hdr(NUM, EXTAG_NUM_DOUBLE);
  e->value.number._double = number;
} else {
  e = create_hdr(NUM, EXTAG_NUM_FLOAT);
  e->value.number._float = number;
}

实现了一个名为autotype的模块，原本用于fp的类型推导和计算，但是阉割后作用并不重要了，目前主要作用是计算过程中的类型提升：例如当出现float+double类型的情况时，强制将float提升为double类型。

其实之前写的很复杂：想要能处理在float+float的情况下，判断计算过程是否需要提升为double再重新计算这个情况，同时又要避免double类型的直接计算。但是实现下来发现情景比较复杂：
1. 考虑计算结果溢出。
2. 考虑极大值加极小值导致精度丢失。
  
  采用的解决方案是判断结果是否和原值几乎相等，这又引出一个新的问题：四则运算中有合法运算计算结果会与参与运算的数相等的情况。例如0+x=x或者1*x=x，他们都符合这一判断条件，但是同时也是合法的float类型可保存的运算。这样的情况可能并不少，全部写出条件判断或许并不明智，因此最终移除这一方案，采用更简单的计算时转换为double，创建result对象时再判断计算结果是否能用float存储来进行的方案。
3. 太坏了浮点数。
允许重新定义值为原语的符号，并支持以\开头的符号在绑定时优先匹配原语而不是从全局环境中寻找值。
1. 主要用于重定义原语，以提供更强的灵活性（虽然以后可能根本不会用它干什么，但是我还是要这么提供）。
2. 可以实现这么一个神奇操作
  1
  (define if (macro (cond body) (\if (not cond) body)))
  其中if和cond都是原语，macro是此教程的宏实现的原语，经过特别设计后cond可以在这个作用语作为一般符号使用，而if也可以被覆盖掉，实现类似重载原语的神奇功能。定义后再调用它时，实现了一个类似于not-if的功能，当条件为#f时，就对body求值，否则不求值，和一般if相反。如果不使用\if，则会由于在模板展开时优先匹配此值，从而导致递归调用然后崩溃。
使用tagged address来标记可以进行尾调用优化的原语。
1. 源于kernel的rbtree实现，通过声明struct rb_node对齐，实现指向它的指针的最低数位恒为0，从而可用于存储颜色。是一个很棒的想法，所以我应用在这里了。
2. 实践中，原语函数应该都在.data段，而且他们的地址应该是默认不对齐到8的，所以保险起见，我在原语函数声明上添加了__attribute__((2))让他们对齐到2，以保留最低位可用于标记，但是我也不知道这么做是否会出现什么意外情况。
3. 当然，tagged address这是我起的名称，我也不知道这个东西的正式名称是什么。
使用标记清除算法实现的GC。
修改了macro的实现，教程为了简化操作，macro实现时通过eval来对模板展开时的符号进行绑定，定义模板时不得不使用list和'来避免模板被求值，因此自行实现了一个函数用于遍历并替代所有模板参数符号。

GC设计

采用引用计数算法发现问题颇多

GC算法是在实现完不含GC的解释器后才进行添加的，添加时面对复杂写法，我无法分辨何时增加了引用，何时减少了引用。在添加GC后测试时，经常出现明明一个expr已经求值完毕并将结果输出，但是很多对象仍然无法被释放或者引用次数变为负数的情况。随后痛定思痛，放弃了引用计数，转而采用会stop-the-world但是总损耗较低且相对简单的标记清除算法。

标记清除算法实现过程中值得注意的关键点

组成部分

对于我实现的lisp解释器，root set应该为以下三个部分组成：

全局环境，储存使用define或者macro原语等行为所创建的全局符号：rt.genv
parser生成的AST结果：rt.ast
parser运行过程中尚未变成AST的对象：rt.workspace

为什么？

我实现的标记清除算法，实际上是抵达一个时间计数上限后触发标记-清除过程的算法，而所谓的时间，我将其设置为内存操作的次数。具体来说是指是创建对象的次数，这样简化了模型。

全局环境和parser生成的AST毫无疑问，但是在parser尚未完整生成AST的过程中就会产生问题，因为刚刚创建完成的对象除了GC模块会保存对它的引用外（用于清除时遍历所有对象），lisp解释器是不可达到它的，此时如果增加时间计数并触发标记清除过程，经过标记后发现新创建的对象不可达，从而立刻清除，这就产生了预料之外的结果。所以我们需要在lisp解释器运行时中添加一个名为workspace的动态数组保存对新创建而尚未成功构成AST的对象。当parse完成后，将生成的AST添加进解释器运行后，再清空workspace。

// IPE函数将会调用readline，读取完整的输入，随后调用parser，最终将parser的结果写入rt.ast
if (IPE(&rt.repl.line_buffer, LISP_PROMPT, LISP_PROMPT_CONTINUE,
        &rt.ast)) {
  fprintf(stderr, "Bye!\n");
  break;
}
//从写入rt.ast到清空workspace的过程中没有会增加引用计数的内存操作。
//清空workspace
dynarray_clear(&rt.workspace);

在创建对象时对象的指针会被添加到workspace。

1 2	`GC_obj_trace(&e->gc);//让GC追踪新创建的对象 dynarray_append(&rt.workspace, &e);//将对象添加到workspace`

这样，无论在AST创建过程中、AST创建完成并对AST进行求值过程都能追踪到所需对象。

标记

为了能够处理循环引用以及重复标记对象，我需要实现一个set，所以我实现了一个hashtable，对象是否完全相同只需要看地址是否一样就可以了，所以实现起来并不复杂。

然而，我实现hashtable时明明实现了对相同对象插入时会将其重新插入，当开发时产生了神奇的问题，我甚至描述不出来是什么情况，所以只能在插入前判断是否已存在来避免问题了。

parser设计失误

由于是第一次用成熟工具链，只能一边摸索一边实现，开始设计时是在bison每解析完一个s-expr后就执行一个函数parse_done的函数来对其进行求值，原本非常愉快地码代码，直到需要实现原语read。

read原语需要对输入的一个s-expr进行求值，也就是说需要将获得的输入传递给bison，让其进行parse和求值。但是目前我的设计是在bison未parse完成时进行解析的，官方文档中有提到bison对嵌套调用的支持并不好，实测下来调用完read原语后就直接段错误了，因此需要修改。

究其原因，原本flex/bison生成的lexer/parser是有全局状态的，需要维护一组全局状态，好处是使用起来十分方便。但是在parse过程中如果指定新的输入并进行parse则会产生意料之外的结果，因此经过查找后我找到了两个解决方案。

解决方案1. parser状态保存与恢复

第一个解决方案是保存YY_CURRENT_BUFFER，创建新的BUFFER，使用完成后再恢复已保存的BUFFER。

大概的执行流程类似于

保存YY_CURRENT_BUFFER
使用yy_scan_string和yy_parse重新parse
parse完成后取得parse结果，并进行yy_flush_buffer(YY_CURRENT_BUFFER)来清空已完成的parser的状态
yy_switch_to_buffer(已保存的buffer)来恢复原本环境

由于flex只能在flex源码文件中访问YY_CURRENT_BUFFER宏，因此需要在.l文件中实现lexer状态YY_CURRENT_BUFFER的获取以及buffer的切换。

void* lisp_lexer_save_state() {
    return YY_CURRENT_BUFFER;
}

void lisp_lexer_restore_state(void* state) {
    yy_flush_buffer(YY_CURRENT_BUFFER);
    yy_switch_to_buffer(state);
}

返回void*而不是具体定义的原因是：我图省事将函数声明在一个公用的头文件lisp.h，所有源码都会include此头文件，但是由于flex的设计，当它的头文件被include在flex源码内时，一部分宏之类的会被undef导致无法正常编译flex生成的lexer源码。换句话说声明在公用头文件时，如果要返回具体的类型定义则需要include flex生成的头文件，但是flex源码需要include头文件lisp.h，然后就会导致我先前说的问题。

这样在实现read原语时我可以使用一种比较扭曲的方式来避免错误

1
2
3

void *state = lisp_lexer_save_state();
IPE(&read_buf, prompt, "");
lisp_lexer_restore_state(state);

好处是相较于下边这个解决方案修改代码比较少，所以先完成了。

解决方案2. parser可重入设置，修改语法解析方式

接下来这种方法是我正在采用的，个人认为比较好的解决方法，也适合于应用于lisp这种十分灵活，功能中需要对输入进行parse成ast的语言。

在原本的设计中，lisp运行时一类的相关的东西更像是挂靠在parser中的一个子模块，是在parser运行的过程中对生成的ast进行eval时调用的。

修改后，parser只生成ast，而lisp运行时会对parser生成的ast结果进行eval。这样两者地位互换了。而且减少了flex/bison代码量，我的环境没有配置对flex/bison的源码的提示，只能在纯文本模式下编辑，降低了错误发生的可能。

在lisp.l中插入

1	`%option reentrant bison-bridge noyywrap`

在lisp.y中插入

1
2
3

%define api.pure full
%lex-param {void *scanner}
%parse-param {void *scanner} {Expr* ast}

从而设置flex/bison的可重入，并且允许传入一个类型为Expr*的ast来传递parse结果。

接下来需要修改parser过程，由于先前是在parse完一个s-expr时就进行解析，现在则将输入完整parse后再让lisp运行时进行求值，所以在parser内部对所有expr只是简单地构建一个lisp list。

exprs:
    expr exprs { 
            $$ = cons($1, $2);
        }
    | expr TOK_DOT expr { 
            $$ = cons($1, $3);
        }
    | /* empty */ { 
            $$ = nil;
        }
    ;

最后将结果赋值给ast指向的内存，

top: 
    exprs {
        *ast = $1;
    }
    ;

使用方法（此例子不是REPL而是从文件读取）：

yylex_init(&sc);
yyset_in(file, sc);
yyparse(sc, &rt.ast);// 传入rt.ast的指针，当parse完成时则可以修改rt.ast的内容为parse的ast结果。
yylex_destroy(sc);
Expr t = rt.ast;
// 现在的ast结构为lisp list，我们需要遍历lisp list，对每个expr进行求值。
while (exist(t)) {
  assert(t->tag == CONS);
  Expr result = eval(car(t), rt.genv);
  t = cdr(t);
}
rt.ast = nil;

看了代码就会发现，在完成parse并删除sc（即yyscan_t）后，不存在和flex/parser相关的数据，这意味着我们可以在lisp运行时内无数次肆无忌惮地进行parse。

此时修改IPE函数，将其封装生成scan_t，parse，然后释放scan_t的过程，这样在实现native_read读取并parse输入时就没有什么难度了。

sds read_buf = sdsempty();
Expr tmp_ast = nil;
IPE(&read_buf, prompt, "", &tmp_ast);
sdsfree(read_buf);

总结

历经这三个星期左右时间，我大概理解了基础的lisp概念，也写出了第一个解释器、标记清除式GC、采用kernel的rbtree那种在地址上进行标记的方式和尝试自动地对浮点数根据结果进行不同类型的存储和转换等的很有意思的东西。收获很多。但是仍然有很多我想要做的事情没有完成：例如在这个完整的解释器项目上实现类似java和cpython那样的字节码编译和加载支持，模块系统，卫生宏，面向对象等。希望继续努力。