这一次打算介绍chibi-scheme中出现其他语义分析函数,以及简单提一下chibi-scheme中的GC技术。

define语句 语法分析

符号定义的函数就是analyze_define。这种define是不生成中间代码的。它所要做的只是在编译器的环境中添加一个引用。简单的例子如下:

1
2
3
> (define x 3)
> x
3

所以首先它需要获得当前上下文的环境env,然后解析得到变量名name。

判断当前环境env是否在一个lambda中,如果是在一个lambda中,给lambda结构的defs和locals属性赋上相应的值。

如果没在lambda中,会用一个函数sexp_cell_define找出所有的name原有的定义,并把它们的值全部清空。然后将所有的位置信息同name放在一起,成为一个ref数据结构。绑定这个define语句的value,放到一个set的ast类型的结构中存起来。

在define语句解析的下面有一个非常类似的函数:analyze_define_syntax,这其实是定义宏的函数。关于Scheme的宏,说实话我确实没有多少了解,粗浅看了看之后发现确实十分复杂,我打算后面花一段时间专门研究一下这个。此处就先行跳过好了。

调用语句 语法分析

这对应的函数是analyze_app。它是语法解析之前所有情况都不成立时候的默认选项,也就是把现在的第一个元素当成一个函数,然后尝试去调用他。

首先使用analyze_list解析列表中的每个元素,然后将第一个元素(如果它是函数)的params属性读取出来,那里面记录了函数的参数个数。然后根据这个params属性去遍历后面的元素(把他们作为调用的参数),放到lambda的name里。

堆对象

chibi-scheme中,所有的对象都是在一个sexp_heap_t的对象中存储的。这就是程序中的堆。里面包括一个标记的符号链、通过next指向的下一个堆指针。对于一大片连续的空间的实现方式是char数组。这是因为sexp对象具有内存对齐,所以我们可以使用字符串的方式来表示chibi-scheme中的内存。

1
2
3
4
5
6
7
8
9
typedef struct sexp_heap_t *sexp_heap;
struct sexp_heap_t {
sexp_uint_t size, max_size, chunk_size;
sexp_free_list free_list;
sexp_heap next;
/* note this must be aligned on a proper heap boundary, */
/* so we can't just use char data[] */
char *data;
};

其中

在内存中创建一个堆的函数为 sexp_make_heap,里面也是如同其他类型的构造一样,给每一个属性都赋上初值。

但是经常会出现这种状况,也就是堆的容量不足了的时候,就会需要扩展这个堆的大小。sexp_grow_heap会分配一个新的堆,并且接在原本堆的next变量里。新增堆的大小是原堆的两倍。

垃圾回收

在chibi-scheme中,使用标记-清除法进行垃圾回收,也即扫描一遍堆中的内容添加,然后再对标记的内容进行清除。在chibi-scheme中,GC发生在下面几个场合:

1
2
3
4
打开一个输入/输出文件的时候
为一个数据变量分配存储空间的时候
需要获取堆的状态的时候
压缩堆空间的时候

GC调用的函数为sexp_gc,其中sexp_mark_one(被sexp_mark调用)是用于标记一个Context下所有不可回收的变量的。

sexp_mark_one首先会遍历Context中的save链并标记他们。之后函数会开始遍历Context下的所有元素(这个函数通过tag属性确定自己的类型,通过预先设定好的基础长度得以跳过基础的属性直接遍历后面独有的属性,最终能遍历整个Context里所有的对象)。

sexp_gc下面还有一个sexp_conservative_mark函数,这是用于遍历所遇到的整个堆,并且给出进行垃圾回收之后多出来的自由空间的新位置。其中free_list属性是一个空闲空间的链表,指向堆中剩余的空闲空间。

weak_reference函数是用来标记堆中的弱引用。sexp_finalize是用于表示一些函数的析构函数。这里将它们略过。

清除阶段对应的函数在sexp_sweep函数中。在此函数中,遍历堆里面的的所有对象。然后将没有marked标签的内存部分,添加到free_list的相应位置,以达成最终垃圾回收的目的。其中会有merge的部分,也就是当两个相邻的内存空间需要回收的时候、会把它们的空间合成一个,然后只添加一个free_list元素。

一些问题

chibi-scheme中的垃圾回收是准确的进行回收的。这意味着在C中进行计算的时候、需要明确说明保留哪些值。否则在分配变量的时候首先尝试分配一定的内存空间,如果堆中的内存不足的时候,就会进行gc,如果gc不成的时候,才会分配一个新的堆空间。尤其是临时值的计算,如果在申请后面临时值的时候,就把第一个临时值给回收了,就会造成错误。因此在使用的时候,我们需要显式地声明保留变量,通过下面这种方式:

1
2
sexp_gc_varn(obj1, obj2, ..., objn) // 声明下面使用这些临时变量
sexp_gc_preserven(ctx, obj1, obj2, ..., objn) // 声明保护这些临时变量

gc_var会依次给里面的临时变量分配一个临时的空壳(空壳里面包括gc所需要的信息),等待后文分配空间。而sexp_gc_preserve函数内部会将临时变量的指针添加到ctx上下文的saves链中,进而保护它们避免被回收。

在Chibi-scheme中内部的函数经常会使用像这样的两个函数,而在最后又会使用一个sexp_gc_release函数。这个函数用以将所用的变量从saves中移除,从而可以被回收。

总结

到这里为止,对chibi-scheme的源码阅读也就基本告一段落。终于算完成了这个系列的工作了。从阅读中我看到了一些语法分析和GC的实现,这在我之前都是没有见过的。我觉得非常新奇,而且也收益匪浅。

(但是总算结束了,呼,填坑真累)