某学校编译原理讲课重点集中在编译器的前端，也就是文法分析、语义分析什么的上面，讲得实在繁琐，感觉自己更想去接受语法纯粹一点的Lisp。

同时也是非常好奇，Lisp的编译过程是怎么实现的呢，于是就决定读一下Lisp的源代码。

为什么是chibi-scheme

答案很简单，因为它足够小。首先我找到的是scheme，但是Scheme的MIT的实现(GNU那个)好像挺长的，于是找到了一个相对较小的版本，也就是chibi-scheme，这是由C来实现的Scheme语言。而且它的代码并不多，我觉得就这种规模的代码读起来才好读一些。

可以从这里获得Chibi-scheme的源代码。

代码中最主要的部分就在include/chibi/sexp.h中，里面包含了Lisp的S表达式和基本数据结构的具体实现。

类型

在Lisp的思想中包括动态类型的想法，也就是对于所有变量，我们操作的都只是它的指针，指针指向的对象有类型的区别，但是指针没有。

但是在具体实用的时候，我们会给进去别的东西，比如一个数字、字符或者别的东西，那就是立即值。立即值与上面说的动态类型的指针存在于同一个东西里面。在解析的时候需要判断是一个立即值还是一个指针，然后在进行具体的操作。

区分两者的方式很简单粗暴，因为指针的最后两位一定都是00^1，所以如果最后两位是00，那么它是指针，其他情况编址为其他位数，为了保证更好地利用每一位，这里使用的是霍夫曼编码：在include/chibi/目录里有其他带有huff的都是实现这个编码的。

编码之后最后这几位的意义在exp.h的注释中也列出来了：

1
2
3
4
5
6
7
8
9
10
/* tagging system
 *   bits end in     1:  fixnum
 *                  00:  pointer
 *                 010:  string cursor (optional)
 *                0110:  immediate symbol (optional)
 *            00001110:  immediate flonum (optional)
 *            00011110:  char
 *            00101110:  reader label (optional)
 *            00111110:  unique immediate (NULL, TRUE, FALSE)
 */

而比较一个这样长度的对象是指针还是立即值的方法就可以通过对特定值取与的方式来得到。

SEXP

sexp类型是一个指针，但是它并不是直接指向所有特定的类型的值的，而是指向了一个统一的结构体：

1
typedef struct sexp_struct *sexp;

sexp_struct数据结构的定义也在sexp.h中给了出来(379行附近)。它里面主要包含了一个sexp_tag_t用以表示这个结构体里面的内容；一个char类型和一些按位给的变量用于垃圾回收和表示这个结构体的状态；在这些之后是一个Union用以表示sexp所指向的真正内容。

在chibi-scheme中，sexp可以包括几乎所有的数据类型，甚至于运行时的类型如堆、上下文等。

当然我们看到的只是sexp这个结构体的一些优化而已，在实际使用中，并不会使用这个结构体，因为这个结构体是Union，Union的大小取决于最大的成员的大小。

对于这个的解决方案是手动计算出每种类型的大小，然后在分配的时候按需分配。

1
2
3
4
5
// 这两个代码都在sexp.h中可以找到
#define sexp_alloc_type(ctx, type, tag) sexp_alloc_tagged(ctx, sexp_sizeof(type), tag)

#define sexp_sizeof(x) (offsetof(struct sexp_struct, value) \
                        + sizeof(((sexp)0)->value.x))

接下来来看这个结构体中的Union都有些什么。

Union

在Union结构体中，需要注意的结构中包括以下这些：

一个Scheme中的类型也是一个sexp_struct的结构体。

1
struct sexp_type_struct type;

sexp_type_struct的定义也可以在sexp.h中找到。留到之后再说。

Pair类型（也就是S表达式的基本类型）。

1
2
3
4
struct {
    sexp car, cdr;
    sexp source;
} pair;

在Union中，很多结构体都包含一个指示长度的int类型变量和一个长度不定的数组，比如vector类型和bytes类型：

1
2
3
4
struct {
    sexp_uint_t length;
    sexp data SEXP_FLEXIBLE_ARRAY;
} vector;

SEXP_FLEXIBLE_ARRAY在前面是这样定义的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#ifdef __cplusplus
extern "C" {
#define SEXP_FLEXIBLE_ARRAY [1]
#else
#define SEXP_FLEXIBLE_ARRAY []
#endif
​```c

那是就表示一个数组，如果是C++环境的时候，默认分配一个长度为1的数组，以保证存在这个东西。

在Union中还包含一个env的结构体，也就是我们之前博客写解释器的时候提到的"环境"。

​```c
    struct {
        sexp parent, lambda, bindings;
#if SEXP_USE_RENAME_BINDINGS
        sexp renames;
#endif
    } env;

通过parent构成了一个链表，由当前的环境指向它的父环境，当有一个变量在当前环境中找不到的时候，则在其父环境中查找。

lambda和bindings中分别存储了在这个环境中出现的函数和变量。最后如果有一定的编译选项的话，可以使用变量的重命名机制。

在下面还有宏类型。宏类型里面包括宏的名字，宏本身，以及宏当时的环境。

1
2
3
struct {
    sexp proc, env, source;
} macro;

再向下，就是AST树的内容了。里面包括了lambda, cnd…等

之后有编译时期的东西存在，后面有stack，context等东西存在的。

现在我们已经基本分析完了关于lisp的s表达式的结构体。下一次我们来看看这个东西的解释器的实现吧。