数据表示
不同类型语言的实现使用了截然不同的数据表示方式。
对于Scheme这样的动态类型语言的实现，数据在运行时需要标志以区分不同类型，所有类型的数据通常需要适配某一种通用的格式，通常是一个字的指针，指向一个block，block里存储具体的数据，这种存储方式称为boxed，记录类型、数组等都是boxed类型。对于双精度浮点数，因为占64位，而机器字长不足以同时表示指针和所有可能的浮点数，因此浮点数也必须采用boxed类型。
因为整数使用的普遍性及性能考虑，整数通常不存储在block中并用指针标识，而是用左移一位且最低位置1的方式表示。因为指针通常要满足一定的对齐条件，最低位为0，这种表示方法不会引起歧义。
对于C、Pascal这样的monomorphic静态类型语言的实现，因为无需进行运行时类型测试，各数据类型不必有统一的格式，因此往往可以有不同的大小。单精度、双精度浮点数可以采取格子的unboxed表示，可以有各种大小的整数类型，比如int8_t、int64_t等。不同类型的函数也可以采取不同的调用约定，比如参数为浮点数或整数时，很多架构下在调用函数时会把参数放在不同的寄存器中。
引入parametric polymorphism后，问题变得复杂，有三类解决方案：
限制polymorphism的形式，比如Modula中规定抽象类型必须是指针类型，Java中不允许unboxed类型如
int转换为Object。这种方式的缺点是不够直观，并且对语言表现力有较大的牺牲。为不同类型生成多份代码。C++模板通常采取这种方式，为不同类型生成不同的代码。缺点是代码大小膨胀，链接复杂性增加，可能需要链接代码生成等。
采用Scheme式样的处理方式。普遍采用boxed类型。缺点是性能损失。
这方面有一些研究成果，比如采取C和Scheme结合的方法、在polymorphic代码中引入类型大小信息等。
Block和整数的区分
我们采取boxed类型的方式，多数类型如元组、数组、float等，它们的实际内容都用堆上分配的一块内存表示，使用指针来标识它们，参数传递和变量存储时都使用表示它们的指针。整数则用低位为1的值表示。
整数
一个整数\(i\)表示为\(2i+1\)，在一个字长为32位的机器上(下面都假定采用32位机)，能表示的int范围不再是\([-2^{31},2^{31})\)，丢失了一位变为\([-2^{30},2^{30})\)。相应地，整数运算需要做一些修改，比如取反实现为\(2-x\)、加法实现为\(x+y-1\)等。
Block
一个block由记录元数据的首部和实际存储的数据两部分组成。字符串、数组和闭包的格式有些特殊，其他block采用统一的格式，元数据占两个字，第一个字记录tag、block的大小和用于垃圾收集的字段color。第二个字是一个XOR链表指针，堆上所有分配的block都串在一个XOR链表里。
bits 31 20 19 8 7 0 31 0
+------+-------+-----+ +--------------------+
| size | color | tag | | xor of prev & next |
+------+-------+-----+ +--------------------+Tag占据一个字节，标识了该block的类型，可用于区分内置类型float(表示为一个双精度浮点数)、string、array和sum类型采用了哪一个构造器。注意经过类型检查后，我们不需要区分不同代数数据类型，只需要标识特定代数数据类型采用了哪一个构造器。
若tag值大于或等于No_scan_tag(251)，就表示这个block存储的数据都是不透明的字节信息，不应该把它们解释为指向其他block的指针。一个代数数据类型的各个构造器，分别用tag值0、1、2等表示。unit类型的构造器()的tag值为1，bool类型的构造器false的tag值为0，true的tag值为1。
size域代表block的指针域数目，对于true这类不包含子域的值，其size为0。
color域用于垃圾收集，对于我们采用的Schorr-Waite graph marking算法，color域需要\(\max\lceil\log_2{n+1}\rceil\)个bit，其中\(n\)是该节点的指针域数目。如果color域和size域使用相同的长度，如我们的实现中所选取的，size域最大可以为\(2^{12}-1=4095\)。元组很难有超过4095项，一个类型的构造器数目也很难超过4095，因此这种方式对于这些类型都是合适的。但是对于字符串长度和数组大小，4095还是相对较小，因此这两个类型要采取特殊的表示方式，把color域的bit也作为size使用，但这样就需要其他地方存储color域，我们选择了在XOR指针域后再加一个字编码color。
下表整理了一些常见类型值的表示方式：
|l|l| 值 & 表示
3 & 3*2+1=7
’a’ & 97*2+1=195
true & 指向一个tag为1，size为0的块的指针
false & 指向一个tag为0，size为0的块的指针
[] & 指向一个tag为0，size为0的块的指针
3::[] &
指向一个tag为1，size为2的块的指针，该块的两个域分别为2*3+1=7和一个表示[]的块
字符串的表示
字符串的block的tag大于No_scan_tag，但元数据存储格式略有区别。因为字符串不包含指向其他节点的指针域，采用Schorr-Waite
graph
marking算法垃圾收集时只需要区分是否被标记过，color域被缩短为只有一个bit，其余bit都被size域占用，size域共23个bit，最多可以表示长度为\(2^{23}-1\)的字符串。
bits 31 9 8 8 7 0 31 0
+------+-----+-+-----+ +--------------------+
| size | color | tag | | xor of prev & next |
+------+-------+-----+ +--------------------+数组的表示
数组的block的tag大于No_scan_tag。原来第一个字的color域全部都被size域占用，因此最大长度是\(2^{24}-1\)，color域被移动到XOR链表指针域的下一个字。
bits 31 8 7 0 31 0 31 0
+--------------+-----+ +--------------------+ +--------------------+
| size | tag | | xor of prev & next | | color |
+--------------+-----+ +--------------------+ +--------------------+闭包的表示
闭包的block的tag小于No_scan_tag，size域固定为2，两个域分别为代码指针和表示环境的闭包。
环境的表示
为了一致性，环境也用block表示，但因为它不会作为值传递，tag值无关紧要，size域的值就是环境中存储的变量数。
Block中的XOR指针域
使用mark-sweep方式的垃圾收集器需要能追踪分配过的堆对象，我们在首部的XOR指针域中维护了所有分配对象的双链表。对于简单的收集所有对象并标记扫除的垃圾收集器，单链表足矣。但考虑到拓展性，我们采用了双链表，以方便未来可能需要支持的操作。因为两个指针域空间开销有点大，我们使用了XOR链表，即每个节点的指针域为其前驱和后继节点地址的XOR。根据XOR链表头或尾节点的地址即可遍历整个链表。