让我们把翻译(“将存储看作向量”)丢到一边吧,它不好理解。
这一节我们需要想想如何在我们知道的 memory 里面表示 scheme 的 list 结构。
内存模型就是一个超大的连续数组(课本上把这个东西叫 Vector)。在这个 连续 数组中,我们怎么表示一个 list(或者 pair) 的 car 和 cdr?
书中的模型是这样的。我们需要两个 vector, the-cars 存 car 的结果, the-cdrs 存 cdr 的结果。结果可以是另外一个 pointer,指向另外一个 vector 中的位置;可以是数字;也可以是空。
index 0 1 2 3 4 5 6 7
the-cars p5 n3 n4 n1 n2
the-cdrs p2 p4 e0 p7 e0
对于示例 ((1 2) 3 4) 而言,它实际就是 (p5 p2) 组成的,p5 是 pair 的前半部分;p2 是 pair 的后半部分。p5 具体是什么呢?我们再看 index 是 5 的时候–(n1 p7),即数字 1 和位置 7。
如果使用 C 来表示,我们可以这么看(当然,int 的存法可以再次抽象,注意看书本的注解 9)。
typedef union T {
Pair * p;
int n;
} T;
typedef struct Pair {
T the-car, the-cdr; // group the-cars and the-cdrs
} Pair;
Pair e0;
Pair pairs[N];
pairs[1].the-car.p = &pairs[5];
pairs[1].the-cdr.p = &pairs[2];
pairs[5].the-car.n = 1;
pairs[5].the-cdr.p = &pairs[7];
以上仅仅模拟了 pair 的模型,在这之后,我们还要考虑如何表示大数字,如何表示 symbol,等等。