第十二课 - 数据修改 （Mutation）
之前的课程中，我们已经讨论数据抽象的几个重要组成部分：构造器 (constructors)、选择器 (selectors)、操作 (operations) 以及契约 (contract)。只要按照数据的契约来使用、操作数据，程序就会向着我们预想中的方向运行。为了达到目的，我们需要反复从旧数据中构造新数据。要是我们能够直接修改旧数据，情况又会发生什么样的变化？本节课将引入数据修改 (Data Mutation) ，丰富我们的数据抽象思路。
替代模型 (substitution model) 假设我们使用函数式编程 (functional programming)，没有数据变动和副作用，每段程序都像一个数学函数，无论在什么时候，都准确地将确定的输入映射到确定的输出上。但如果我们引入数据修改，每段程序的输出结果就不仅仅只依赖于输入，还依赖于程序被执行时的环境。举例如下：
(define x 10)
(+ x 5)
> 15
(set! x 94)
(+ x 5)
> 99
我们将看到
引入数据修改使得许多事情变得容易，但会提高犯错的可能性。
Pair/List Mutation
除了构造器、选择器、操作外，数据抽象可能还包含修改器 (mutators)。将数据变动引入到 Scheme 的 pair/list 中，可以得到如下的 pair/list 数据抽象：
；constructor
(cons x y) ; creates a new pair p
; selectors
(car p) ; returns car part of pair
(cdr p) ; returns cdr part of pair
; mutators
(set-car! p new-x) ; changes car pointer in pair
(set-cdr! p new-y) ; changes cdr pointer in pair
; Pair, anytype -> undef ; side-effect only
其中，set-car! 和 set-cdr! 分别修改 pair 的 car 部分和 cdr 部分指针指向的数据，而且这两种方法只有副作用，没有返回值，因此其返回值是不确定的 (unspecified)。
例1：
mutation 给我们编程带来方便的同时引入问题，需要我们格外注意：
(define a (list 1 2))
(define b a)
; a ==> (1 2)
; b ==> (1 2)
(set-car! a 10)
; a ==> (10 2)
; b ==> (10 2)
由于 a 和 b 指向同一块内存，修改 a 的同时，也会修改 b，如下图所示：
因此我们需要在充分了解 mutation 的基础上加以使用。
例2：
如下图所示修改 x 对应的 list：
可以这样实现：
(define x (list 'a 'b))
(set-car! (cdr x) (list 1 2))
Equivalence and Identity
在表示相等关系时，我们常常有这样两个问题：
- a 和 b 是否很像？
- a 和 b 是否是同一个？
如果 a 和 b 很像，那么二者至少表面看起来给人相似的感觉，这就是 equivalence。
如果 a 和 b 是同一个，那么二者实际上指代同一个物体，这就是 identity。
; equivalence
; a、b 是否是同一个
(eq? a b)
; identity
; a、b 是否长得像
(equal? a b)
例1：Stack Data Abstraction
Stack 数据抽象的几个组成部分如下所示：
; constructor
(make-stack) ; returns an empty stack
; selectors
(top stack) ; returns current top element from a stack
; operations
(insert stack elt) ; returns a new stack with the element added to the top of the stack
(delete stack) ; returns a new stack with the top element removed from the stack
(empty-stack? stack) ; returns #t if no elements, #f otherwise
; contract
; if s is a stack, created by (make-stack) and subsequent stack procedures, where i is the
; number of insertions and j is the number of deletions, then
; 1. if j > i : then it is an error
; 2. if j = i : then (empty-stack? s) is true, and (top s) and (delete s) are errors
; 3. if j < i : then (empty-stack? s) is false and (top (delete (insert s val))) = (top s)
; 4. if j <= i: then (top (insert s val)) = val for any val.
实现1：利用 list
; constructor
(define (make-stack) nil)
; predicator
(define (empty-stack? stack) (null? stack))
; operations
(define (insert stack elt) (cons elt stack))
(define (delete stack)
(if (empty-stack? stack)
(error "stack underflow - delete")
(cdr stack)))
; selectors
(define (top stack)
(if (empty-stack? stack)
(error "stack underflow - top")
(car stack)))
利用 list 直接实现，符合上文中的数据抽象的各个部分。但是我们每次 insert、delete 之后都会生成新的 stack，而并非原来的那个 stack。因此用 eq? 来判断两个 insert 或者 delete 操作前后的 stack 会得到 false。但我们在使用 stack 的过程中，更希望 stack 自始至终是同一个 stack，既符合直觉也能使得操作更加方便。这一切将在引入 mutation 之后得以解决……
实现2：利用 mutators
首先我们需要引入 tag，它有两个好处：
- defensive programming
- 提供 identity --- 试想如果没有 tag，我们将无法做到每次都返回同一个 stack，因为 insert 将改变 list 的 identity，除非我们自己利用 set! 重新将新的 stack 绑定到原来的 name 上。
; constructor
(define (make-stack) (cons 'stack nil))
; predicators
(define (stack? stack)
(and (pair? stack) (eq? 'stack (car stack))))
(define (empty-stack? stack)
(if (not (stack? stack))
(error "object not a stack: " stack)
(null? (cdr stack))))
; mutators
(define (insert! stack elt)
(cond ((not (stack? stack))
(error "object not a stack: " stack))
(else
(set-cdr! stack (cons elt (cdr stack)))
stack)))
(define (delete! stack)
(if (empty-stack? stack)
(error "stack underflow - delete")
(set-cdr! stack (cddr stack)))
stack)
; selector
(define (top stack)
(if (empty-stack? stack)
(error "stack underflow - top")
(cadr stack)))
例2：Queue Data Abstraction
queue 数据抽象的几个组成部分如下：
; constructor
(make-queue) returns an empty queue
; selectors
(front-queue q) returns the object at the front of the queue. If queue is empty signals error
; mutators
(insert-queue q elt) returns a queue with elt at the rear of the queue
(delete-queue q) returns a queue with the item at the front of the queue removed
; operations/predicators
(empty-queue? q) tests if the queue is empty
; (queue? q) tests if the object is a queue
; contracts
; if q is a queue, created by (make-queue) and subsequent queue procedures, where i is the number
; of insertions, j is the number of deletions, and x_i is the i-th item inserted into q, then
; 1. if j > i: then it is an error
; 2. if j = i: then (empty-queue? q) is true, and (front-queue q) and (delete-queue q) are errors
; 3. if j < i: then (front-queue q) = x_(j+1)
实现1：没有 mutation
; constructor
(define (make-queue) nil)
; predicator
(define (empty-queue? q) (null? q))
; selector
(define (front-queue) q)
(if (empty-queue? q)
(error "front of empty queue: " q)
(car q)))
; mutators
(define (delete-queue q)
(if (empty-queue? q)
(error "delete of empty queue: " q)
(cdr q)))
(define (insert-queue q elt)
(if (empty-queue? q)
(cons elt nil)
(cons (car q) (insert-queue (cdr q) elt))))
其中 insert-queue 的时间、空间复杂度皆为 O(n)
实现2：mutation
为了减少 insert-queue 的复杂度，我们在引入 tag 的同时，在 queue 中加上队首 (front )和队尾 (rear) 指针:
; helpers, hidden inside abstraction
(define (front-ptr q) (cadr q))
(define (rear-ptr q) (cddr q))
(define (set-front-ptr! q item)
(set-car! (cdr q) item))
(define (set-rear-ptr! q item)
(set-cdr! (cdr q) item))
; constructor
(define (make-queue)
(cons 'queue (cons nil nil)))
; predicator
(define (queue? q)
(and (pair? q) (eq? 'queue (car q))))
(define (empty-queue? q)
(if (not (queue? q))
(error "object not a queue: " q)
(null? (front-ptr q))))
; selector
(define (front-queue) q)
(if (empty-queue? q)
(error "front of empty queue: " q)
(car (front-ptr q))))
; mutators
(define (delete-queue q)
(cond ((empty-queue? q)
(error "delete of empty queue: " q))
(else
(set-front-ptr! q
(cdr (front-ptr q)))
q)))
(define (insert-queue q elt)
(let ((new-pair (cons elt nil)))
(cond ((empty-queue? q)
(set-front-ptr! q new-pair)
(set-rear-ptr! q new-pair)
q)
(else
(set-cdr! (rear-ptr q) new-pair)
(set-rear-ptr! q new-pair)
q))))
这时候，在获得 identity 的同时，insert-queue 的复杂度降到了 O(1)