Exercise 3.14 · 习题

Exercise 3.14: The following procedure is quite
useful, although obscure:

(define (mystery x)
(define (loop x y)
(if (null? x)
y
(let ((temp (cdr x)))
(set-cdr! x y)
(loop temp x))))
(loop x '()))

Loop uses the “temporary” variable temp to hold the old value
of the cdr of x, since the set-cdr! on the next line
destroys the cdr. Explain what mystery does in general. Suppose
v is defined by (define v (list 'a 'b 'c 'd)). Draw the
box-and-pointer diagram that represents the list to which v is bound.
Suppose that we now evaluate (define w (mystery v)). Draw
box-and-pointer diagrams that show the structures v and w after
evaluating this expression. What would be printed as the values of v
and w?

Sharing and identity

We mentioned in 3.1.3 the theoretical issues of “sameness” and
“change” raised by the introduction of assignment. These issues arise in
practice when individual pairs are
shared among different data
objects. For example, consider the structure formed by

(define x (list 'a 'b))
(define z1 (cons x x))

As shown in Figure 3.16, z1 is a pair whose car and
cdr both point to the same pair x. This sharing of x by
the car and cdr of z1 is a consequence of the
straightforward way in which cons is implemented. In general, using
cons to construct lists will result in an interlinked structure of pairs
in which many individual pairs are shared by many different structures.

SVG

Figure 3.16: The list z1 formed by (cons x x).

In contrast to Figure 3.16, Figure 3.17 shows the structure created
by

(define z2
(cons (list 'a 'b) (list 'a 'b)))

SVG

Figure 3.17: The list z2 formed by (cons (list 'a 'b) (list 'a 'b)).

In this structure, the pairs in the two (a b) lists are distinct,
although the actual symbols are shared.

When thought of as a list, z1 and z2 both represent “the same”
list, ((a b) a b). In general, sharing is completely undetectable if we
operate on lists using only cons, car, and cdr. However,
if we allow mutators on list structure, sharing becomes significant. As an
example of the difference that sharing can make, consider the following
procedure, which modifies the car of the structure to which it is
applied:

(define (set-to-wow! x)
(set-car! (car x) 'wow)
x)

Even though z1 and z2 are “the same” structure, applying
set-to-wow! to them yields different results. With z1, altering
the car also changes the cdr, because in z1 the car
and the cdr are the same pair. With z2, the car and
cdr are distinct, so set-to-wow! modifies only the car:

z1
((a b) a b)

(set-to-wow! z1)
((wow b) wow b)

z2
((a b) a b)

(set-to-wow! z2)
((wow b) a b)

One way to detect sharing in list structures is to use the predicate
eq?, which we introduced in 2.3.1 as a way to test whether
two symbols are equal. More generally, (eq? x y) tests whether
x and y are the same object (that is, whether x and
y are equal as pointers). Thus, with z1 and z2 as defined
in Figure 3.16 and Figure 3.17, (eq? (car z1) (cdr
z1)) is true and (eq? (car z2) (cdr z2)) is false.

As will be seen in the following sections, we can exploit sharing to greatly

extend the repertoire of data structures that can be represented by pairs. On

the other hand, sharing can also be dangerous, since modifications made to

structures will also affect other structures that happen to share the modified

parts. The mutation operations set-car! and set-cdr! should be

used with care; unless we have a good understanding of how our data objects are

shared, mutation can have unanticipated results.

练习 3.14：以下过程相当有用，尽管有些难以理解：

(define (mystery x)
(define (loop x y)
(if (null? x)
y
(let ((temp (cdr x)))
(set-cdr! x y)
(loop temp x))))
(loop x '()))

loop 使用"临时"变量 temp 保存 x 的 cdr 的旧值，因为下一行的 set-cdr! 会破坏该 cdr。请解释 mystery 在一般情形下的作用。假设 v 由 (define v (list 'a 'b 'c 'd)) 定义。画出表示 v 所绑定的表的序对指针图。假设现在求值 (define w (mystery v))。画出求值该表达式后 v 和 w 所对应结构的序对指针图。v 和 w 的值分别会打印出什么？

共享与同一性

在 3.1.3 节中，我们提到了引入赋值所引发的关于"同一性"与"变化"的理论问题。当各个序对被多个不同数据对象共享时，这些问题就会在实践中显现。例如，考虑由以下代码构成的结构：

(define x (list 'a 'b))
(define z1 (cons x x))

如图 3.16 所示，z1 是一个 car 和 cdr 都指向同一序对 x 的序对。z1 的 car 和 cdr 共享 x，这是 cons 的直接实现方式所导致的结果。一般来说，用 cons 构造表会产生一个相互链接的序对结构，其中许多单独的序对被许多不同的结构所共享。

SVG

图 3.16：由 (cons x x) 构成的表 z1。

与图 3.16 不同，图 3.17 显示了由以下代码创建的结构：

(define z2
(cons (list 'a 'b) (list 'a 'b)))

SVG

图 3.17：由 (cons (list 'a 'b) (list 'a 'b)) 构成的表 z2。

在这一结构中，两个 (a b) 表中的序对是不同的，尽管实际的符号是共享的。

若视为表，z1 和 z2 都表示"相同的"表 ((a b) a b)。一般来说，如果只使用 cons、car 和 cdr 来操作表，共享是完全无法察觉的。然而，如果允许对表结构进行变异操作，共享就变得非常重要了。以下过程展示了共享可能造成的差异，它修改所操作结构的 car：

(define (set-to-wow! x)
(set-car! (car x) 'wow)
x)

尽管 z1 和 z2 是"相同"的结构，对它们分别应用 set-to-wow! 会产生不同的结果。对 z1 而言，修改 car 同时也修改了 cdr，因为在 z1 中 car 和 cdr 是同一个序对。对 z2 而言，car 和 cdr 是不同的序对，因此 set-to-wow! 只修改 car：

z1
((a b) a b)

(set-to-wow! z1)
((wow b) wow b)

z2
((a b) a b)

(set-to-wow! z2)
((wow b) a b)

检测表结构中共享的一种方法是使用谓词 eq?，我们在 2.3.1 节将其作为检验两个符号是否相等的方法引入。更一般地，(eq? x y) 检验 x 和 y 是否是同一个对象（即 x 和 y 作为指针是否相等）。因此，对于图 3.16 和图 3.17 中定义的 z1 和 z2，(eq? (car z1) (cdr z1)) 为真，而 (eq? (car z2) (cdr z2)) 为假。

正如后面几节将看到的，我们可以利用共享来大大扩展可用序对表示的数据结构种类。另一方面，共享也可能带来危险，因为对某一结构所做的修改也会影响到恰好共享了被修改部分的其他结构。变异操作 set-car! 和 set-cdr! 应当谨慎使用；除非我们对数据对象的共享情况有充分的了解，否则变异可能产生意想不到的结果。