SICP 全笔记

让我们把翻译(“将存储看作向量”)丢到一边吧,它不好理解。

这一节我们需要想想如何在我们知道的 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,等等。