Exercise 3.19 · 习题

Exercise 3.19: Redo Exercise 3.18 using an
algorithm that takes only a constant amount of space. (This requires a very
clever idea.)

Mutation is just assignment

When we introduced compound data, we observed in 2.1.3 that pairs
can be represented purely in terms of procedures:

(define (cons x y)
(define (dispatch m)
(cond ((eq? m 'car) x)
((eq? m 'cdr) y)
(else (error "Undefined
operation: CONS" m))))
dispatch)

(define (car z) (z 'car))
(define (cdr z) (z 'cdr))

The same observation is true for mutable data. We can implement mutable data
objects as procedures using assignment and local state. For instance, we can
extend the above pair implementation to handle set-car! and
set-cdr! in a manner analogous to the way we implemented bank accounts
using make-account in 3.1.1:

(define (cons x y)
(define (set-x! v) (set! x v))
(define (set-y! v) (set! y v))
(define (dispatch m)
(cond ((eq? m 'car) x)
((eq? m 'cdr) y)
((eq? m 'set-car!) set-x!)
((eq? m 'set-cdr!) set-y!)
(else (error "Undefined
operation: CONS" m))))
dispatch)

(define (car z) (z 'car))
(define (cdr z) (z 'cdr))

(define (set-car! z new-value)
((z 'set-car!) new-value)
z)

(define (set-cdr! z new-value)
((z 'set-cdr!) new-value)
z)

Assignment is all that is needed, theoretically, to account for the behavior of

mutable data. As soon as we admit set! to our language, we raise all

the issues, not only of assignment, but of mutable data in general.

练习 3.19：用只需常数空间的算法重做练习 3.18。（这需要一个非常巧妙的想法。）

赋值即是变动

在介绍复合数据时，我们在 2.1.3 节中观察到，序对可以纯粹用过程来表示：

(define (cons x y)
(define (dispatch m)
(cond ((eq? m 'car) x)
((eq? m 'cdr) y)
(else (error “Undefined\noperation: CONS” m))))
dispatch)

(define (car z) (z 'car))
(define (cdr z) (z 'cdr))

同样的观察对可变数据也成立。我们可以用赋值和局部状态将可变数据对象实现为过程。例如，可以将上述序对的实现加以扩展，以处理 set-car! 和 set-cdr!，其方式类似于我们在 3.1.1 节中用 make-account 实现银行账户的做法：

(define (cons x y)
(define (set-x! v) (set! x v))
(define (set-y! v) (set! y v))
(define (dispatch m)
(cond ((eq? m 'car) x)
((eq? m 'cdr) y)
((eq? m 'set-car!) set-x!)
((eq? m 'set-cdr!) set-y!)
(else (error “Undefined\noperation: CONS” m))))
dispatch)

(define (car z) (z 'car))
(define (cdr z) (z 'cdr))

(define (set-car! z new-value)
((z 'set-car!) new-value)
z)

(define (set-cdr! z new-value)
((z 'set-cdr!) new-value)
z)

从理论上说，仅凭赋值就足以解释可变数据的全部行为。一旦我们在语言中引入 set!，便同时引入了所有关于赋值的问题，以及可变数据的一般性问题。