3.3.1 Mutable List Structure

The basic operations on pairs—cons, car, and cdr—can

be used to construct list structure and to select parts from list structure,

but they are incapable of modifying list structure. The same is true of the

list operations we have used so far, such as append and list,

since these can be defined in terms of cons, car, and cdr.

To modify list structures we need new operations.

序对上的基本操作——cons、car 和 cdr——可以用来构造表结构，以及从表结构中选取各部分，但它们无法修改表结构。我们迄今使用的各种表操作，如 append 和 list，同样如此，因为这些操作都可以用 cons、car 和 cdr 来定义。要修改表结构，我们需要新的操作。

The primitive mutators for pairs are set-car! and

set-cdr!. Set-car! takes two arguments, the first of which must

be a pair. It modifies this pair, replacing the car pointer by a

pointer to the second argument of set-car!.

序对的基本变动器 (mutators) 是 set-car! 和 set-cdr!。set-car! 接受两个参数，其中第一个必须是序对。它修改这个序对，用指向 set-car! 第二个参数的指针替换原来的 car 指针。

As an example, suppose that x is bound to the list ((a b) c d)

and y to the list (e f) as illustrated in Figure 3.12.

Evaluating the expression (set-car! x y) modifies the pair to which

x is bound, replacing its car by the value of y. The

result of the operation is shown in Figure 3.13. The structure x

has been modified and would now be printed as ((e f) c d). The pairs

representing the list (a b), identified by the pointer that was

replaced, are now detached from the original structure.

Figure 3.12: Lists x: ((a b) c d) and y: (e f).

Figure 3.13: Effect of (set-car! x y) on the lists in Figure 3.12.

举个例子，假设 x 被绑定到表 ((a b) c d)，y 被绑定到表 (e f)，如图 3.12 所示。对表达式 (set-car! x y) 求值，会修改 x 所绑定的序对，用 y 的值替换它的 car。操作结果如图 3.13 所示。结构 x 已被修改，现在打印出来将是 ((e f) c d)。表示表 (a b) 的那些序对——由被替换的指针所指向——现在已从原始结构中脱离。图 3.12：表 x: ((a b) c d) 与 y: (e f)。图 3.13：(set-car! x y) 对图 3.12 中各表的影响。

Compare Figure 3.13 with Figure 3.14, which illustrates the result

of executing (define z (cons y (cdr x))) with x and y

bound to the original lists of Figure 3.12. The variable z is now

bound to a new pair created by the cons operation; the list to which

x is bound is unchanged.

Figure 3.14: Effect of (define z (cons y (cdr x))) on the lists in Figure 3.12.

将图 3.13 与图 3.14 相比较，图 3.14 展示了在 x 和 y 仍绑定到图 3.12 中原始各表的情况下，执行 (define z (cons y (cdr x))) 的结果。变量 z 现在被绑定到由 cons 操作新创建的序对；x 所绑定的表则保持不变。图 3.14：(define z (cons y (cdr x))) 对图 3.12 中各表的影响。

The set-cdr! operation is similar to set-car!. The only

difference is that the cdr pointer of the pair, rather than the

car pointer, is replaced. The effect of executing (set-cdr! x y)

on the lists of Figure 3.12 is shown in Figure 3.15. Here the

cdr pointer of x has been replaced by the pointer to (e

f). Also, the list (c d), which used to be the cdr of x,

is now detached from the structure.

Figure 3.15: Effect of (set-cdr! x y) on the lists in Figure 3.12.

set-cdr! 操作与 set-car! 类似，唯一的区别在于被替换的是序对的 cdr 指针而非 car 指针。在图 3.12 的各表上执行 (set-cdr! x y) 的效果如图 3.15 所示。这里，x 的 cdr 指针被替换为指向 (e f) 的指针。此外，原先作为 x 的 cdr 的表 (c d) 现在已从结构中脱离。图 3.15：(set-cdr! x y) 对图 3.12 中各表的影响。

Cons builds new list structure by creating new pairs, while

set-car! and set-cdr! modify existing pairs. Indeed, we could

implement cons in terms of the two mutators, together with a procedure

get-new-pair, which returns a new pair that is not part of any existing

list structure. We obtain the new pair, set its car and cdr

pointers to the designated objects, and return the new pair as the result of

the cons.

cons 通过创建新的序对来构造新的表结构，而 set-car! 和 set-cdr! 则修改已有的序对。事实上，我们可以用这两个变动器加上一个过程 get-new-pair 来实现 cons，其中 get-new-pair 返回一个不属于任何现有表结构的新序对。我们获取这个新序对，将其 car 和 cdr 指针设置为指定的对象，然后将这个新序对作为 cons 的结果返回。