1| 2| 3.3 MODELING WITH MUTABLE DATA 3| =============================== 4| 5| ADTs with constructors, selectors and predicates model VALUES, not 6| OBJECTS: They cannot have CHANGING STATE. 7| Constructors build NEW DATA objects from old, and selectors split data 8| values. They do not provide means for CHANGING a given data object. 9| 10| In order to model compound OBJECTS with changing states, we turn ADT 11| values into ADT objects. We do it by adding new kind of operators, called 12| MUTATORS, which modify data objects. 13| ************************************************************************ 14| ** ADTs for which mutators are defined are called MUTABLE data objects. ** 15| ************************************************************************ 16| 17| An example of a possible mutator for a bank account data object: 18| (set-balance! ) 19| 20| 21| 3.3.1 MUTABLE LIST STRUCTURE 22| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 23| The pairs constructor 'cons', and the lists constructors 'list' and 24| 'append' generate new values. They do not MODIFY their arguments. 25| The LIST and PAIR ADT values turn into LIST and PAIR MUTABLE ADTs by 26| adding mutators. The primitive mutators for list and pair structures are: 27| 'set-car!' and 'set-cdr!'. 28| 29| *** 'set-car!' takes two arguments: and . The first argument 30| must be a pair. The evaluation of set-car! modifies the car pointer 31| of to point to . 32| For example: 33| > (define x (list '(a b) 'c 'd) ) 34| # 35| > (define y (list 'e 'f)) 36| # 37| > (set-car! x y) 38| # 39| > x 40| ((e f) c d) 41| 42| The value of x has been changed by set-car!. This is different from: 43| > (define z (cons y (cdr x)) ) 44| # 45| > z 46| ((e f) c d) 47| > x 48| ((e f) c d) 49| > (eq? x z) 50| #f 51| 52| The variable z is bound to a NEW pair, created by the cons operation. 53| It does not affect any existing value. 54| 55| *** set-cdr! is similar to set-car!: It replaces the cdr pointer of the 56| first argument (which must be a pair), to its second argument: 57| > (set-cdr! x y) 58| # 59| > x 60| ((e f) e f) 61| > z 62| ((e f) c d) 63| > (set-cdr! y (cdr z)) 64| # 65| > z 66| ((e c d) c d) 67| > x 68| ((e c d) e c d) 69| > y 70| (e c d) 71| > (set-cdr! y z) 72| # 73| > z 74| ((e (e (e (e (e (e (e (e (e (e (e (e (e (e (e (e (e (e (e (e (e (e (e (... 75| > y 76| (e (e (e (e (e (e (e (e (e (e (e (e (e (e (e (e (e (e (e (e (e (e (e (e... 77| > x 78| ((e (e (e (e (e (e (e (e (e (e (e (e (e (e (e (e (e (e (e (e (e (e (e (... 79| > (set-cdr! y y) 80| # 81| > y 82| (e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e ... 83| 84| Implementing 'cons' in terms of set-car! and set-cdr!: 85| (define (cons x y) 86| (let ((new (get-new-pair))) 87| (set-car! new x) 88| (set-cdr! new y) 89| new)) 90| 91| 92| SHARING AND IDENTITY: 93| ~~~~~~~~~~~~~~~~~~~~~ 94| > (define x (list 'a 'b)) 95| # 96| > (define z1 (cons x x)) 97| # 98| > (define z2 (cons (list 'a 'b) (list 'a 'b)) ) 99| # 100| > z1 101| ((a b) a b) 102| > z2 103| ((a b) a b) 104| > (eq? z1 z2) 105| #f 106| > (equal? z1 z2) 107| #t 108| > (eq? (car z1) (cdr z1)) 109| #t 110| > (eq? (car z2) (cdr z2)) 111| #f 112| 113| ********************************************************************* 114| ** 'eq?' is Scheme's test for SHARING --- for being the same object. ** 115| ** 'eq?' represent the "identical is sharing" view. ** 116| ** If expressions pass the eq? test they will be the same also under ** 117| ** changes (can be substituted for one another) ** 118| ** 'equal?' tests for VALUES equality. ** 119| ** 'eq?' tests for OBJECT's IDENTITY sharing. ** 120| ********************************************************************* 121| 122| We can see that z1 and z2 are not identical by applying mutators: 123| > (define (set-to-wow! x) 124| (set-car! (car x) 'wow) 125| x) 126| # 127| > (set-to-wow! z1) 128| ((wow b) wow b) 129| > z1 130| ((wow b) wow b) 131| > z2 132| ((a b) a b) 133| > (set-to-wow! z2) 134| ((wow b) a b) 135| > (eq? (car z1) (cdr z1)) 136| #t 137| > (equal? z1 z2) 138| #f 139| 140| Another example: 141| ~~~~~~~~~~~~~~~~ 142| > (define (memq x list) 143| (cond ((null? list) nil) 144| ((eq? x (car list)) list) 145| (else (memq x (cdr list))))) 146| 147| WARNING: redefining built-in memq 148| # 149| > (define x (list 'a 'b)) 150| # 151| > (define y (cons x x)) 152| # 153| > (memq? x y) 154| ((a b) a b) 155| > (memq? (list 'a 'b) y) 156| #f 157| > (define numer car) 158| # 159| > (eq? numer car) 160| #t 161| > (define (numer x) (car x)) 162| # 163| > (eq? numer car) 164| #f 165| 166| 167| MUTATION IS JUST ASSIGNMENT: 168| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 169| Mutable data objects can be implemented as procedures using assignment 170| and local state: 171| 172| (define (cons x y) 173| (define (set-x! v) (set! x v)) 174| (define (set-y! v) (set! y v)) 175| (define (dispatch m) 176| (cond ((eq? m 'car) x) 177| ((eq? m 'cdr) y) 178| ((eq? m 'set-car!) set-x!) 179| ((eq? m 'set-cdr!) set-y!) 180| (else (error "Undefined operation -- CONS" m)))) 181| dispatch) 182| (define (car z) (z 'car)) 183| (define (cdr z) (z 'cdr)) 184| (define (set-car! z new-value) 185| ((z 'set-car!) new-value) 186| z) 187| (define (set-cdr! z new-value) 188| ((z 'set-cdr!) new-value) 189| z) 190| 191| 192| 3.2.3 REPRESENTING QUEUES: 193| ~~~~~~~~~~~~~~~~~~~~~~~~~~ 194| A queue is a sequence in which items are inserted at one end (rear), 195| and deleted from the other end (front). A queue is also called a FIFO 196| buffer (First In First Out). 197| As an ADT, a queue is defined by the following operations: 198| 199| *** A CONSTRUCTOR: make-queue() that returns an empty queue. 200| *** A PREDICATE: empty-queue?(). 201| *** A SELECTOR: front(), that selects the item at the front, 202| and signals an error if the queue is empty. 203| *** Two MUTATORS: insert-queue!(, ): inserts at the 204| rear end, and returns the modified queue as its value. 205| delete-queue!(): Removes the item at the front, 206| and returns the modified queue as its value. 207| 208| A queue can be represented as a list, with the front being the car of 209| the list, and the rear being the end of the list. The problem with this 210| representation is that insertion requires scanning of the entire list, 211| i.e., O(n) operation, for a queue of n items. 212| A representation that requires O(1) time for deletion and insertion: 213| A queue is represented as a list, together with two pointers to the front 214| and to the rear of the queue. The two pointers provide direct access to 215| the front and to the rear. In this representation a queue is a pair 216| (created by cons), whose car is 'front-ptr, and its cdr is 'rear-ptr'. 217| Front ptr points to the queue's front, and rear-ptr points to the queue's 218| rear. If the queue is empty, both pointers are null. If the queue consists 219| of a single element, both pointers point to it. 220| 221| Utilities for selection and modification of the queue's rear and front: 222| 223| (define (front-ptr queue) (car queue)) 224| 225| (define (rear-ptr queue) (cdr queue)) 226| 227| (define (set-front-ptr! queue item) (set-car! queue item)) 228| 229| (define (set-rear-ptr! queue item) (set-cdr! queue item)) 230| 231| ;;; Operations on queues 232| 233| (define (empty-queue? queue) (null? (front-ptr queue))) 234| 235| (define (make-queue) (cons '() '())) 236| 237| (define (front queue) 238| (if (empty-queue? queue) 239| (error "FRONT called with an empty queue" queue) 240| (car (front-ptr queue)))) 241| 242| (define (insert-queue! queue item) 243| (let ((new-pair (cons item nil))) 244| (cond ((empty-queue? queue) 245| (set-front-ptr! queue new-pair) 246| (set-rear-ptr! queue new-pair) 247| queue) 248| (else 249| (set-cdr! (rear-ptr queue) new-pair) 250| (set-rear-ptr! queue new-pair) 251| queue)))) 252| 253| (define (delete-queue! queue) 254| (cond ((empty-queue? queue) 255| (error "Delete called with an empty queue" queue)) 256| (else 257| (set-front-ptr! queue (cdr (front-ptr queue))) 258| queue))) 259| 260| 261| 3.3.3 REPRESENTING TABLES 262| ~~~~~~~~~~~~~~~~~~~~~~~~~ 263| A table is a set of records, indexed by identifying keys. In a one 264| dimensional table there is a single key per record; in a two dimensional 265| table there are two keys per record. 266| 267| ONE-DIMENSIONAL TABLES 268| ~~~~~~~~~~~~~~~~~~~~~~ 269| A one dimensional table can be represented as a list of records, each 270| being a pair of a key and a value. The records are "glued" together by a 271| list of pairs whose cars point to successive records, and their cdrs 272| point to the next pair in the list. This list is called the BACKBONE of 273| the table. 274| 275| In order to prepair a fixed location for new records the first pair in the 276| BACKBONE of the table is kept as a HEADER that points to a dummy value 277| (the symbol *table*). New records will be inserted right after the header. 278| This way the table is identified by the first pair in the backbone list--- 279| the header. Mutators of the table do not change it. Such lists, that have 280| a fixed header are called HEADED lists. 281| 282| Table operators: 283| ~~~~~~~~~~~~~~~~ 284| *** make-table(): Creats an empty table--- a header only. 285| *** lookup(, ): selects the record associated with in 286|
. If there isn't such a record it returns nil. 287| *** insert!(, ,
): If
already has a record 288| identified by it changes its value to . 289| Otherwise, it inserts a new record, identified by , 290| right after the header record. 291| 292| Utility procedure: 293| ~~~~~~~~~~~~~~~~~~ 294| assq(, ): Returns the record identified by . The header 295| is not included in . 296| 297| Implementation of one-dimensional tables as headed lists: 298| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 299| (define (lookup key table) 300| (let ((record (assq key (cdr table)))) 301| (if (not record) 302| nil 303| (cdr record)))) 304| 305| (define (assq key records) 306| (cond ((null? records) nil) 307| ((eq? key (caar records)) (car records)) 308| (else (assq key (cdr records))))) 309| 310| (define (insert! key value table) 311| (let ((record (assq key (cdr table)))) 312| (if (not record) 313| (set-cdr! table (cons (cons key value) (cdr table))) 314| (set-cdr! record value))) 315| 'ok) 316| 317| (define (make-table) 318| (list '*table*)) 319| 320| TWO-DIMENSIONAL TABLES 321| ~~~~~~~~~~~~~~~~~~~~~~ 322| A two dimensional table can be represented as a one dimensional table, 323| in which each key identifies a one dimensional table. The embedded 324| subtable does not need a special header symbol, as the first key serves 325| this purpose. 326| 327| The lookup selector: 328| First looks for a record identified by the first key, and then looks 329| for a record identified by the second key. 330| The insert! mutator: 331| First looks for a record identified by the first key. If there isn't, 332| it inserts a new subtable, containing a single record (key-2, value) 333| right after the header of the table. If there is a record identified 334| by key-1, it inserts a record identified by key-2, at the one- 335| dimensional subtable identified by key-1 (using the same method as the 336| one-dimensional insert!). 337| 338| Implementation: 339| ~~~~~~~~~~~~~~~ 340| 341| (define (lookup key-1 key-2 table) 342| (let ((subtable (assq key-1 (cdr table)))) 343| (if (not subtable) 344| nil 345| (let ((record (assq key-2 (cdr subtable)))) 346| (if (not record) 347| nil 348| (cdr record)))))) 349| 350| (define (insert! key-1 key-2 value table) 351| (let ((subtable (assq key-1 (cdr table)))) 352| (if (not subtable) 353| (set-cdr! table 354| (cons (list key-1 (cons key-2 value)) (cdr table))) 355| (let ((record (assq key-2 (cdr subtable)))) 356| (if (not record) 357| (set-cdr! subtable 358| (cons (cons key-2 value) (cdr subtable))) 359| (set-cdr! record value))))) 360| 'ok) 361| 362| 363| CREATING LOCAL TABLES: 364| ~~~~~~~~~~~~~~~~~~~~~~ 365| Table as a PROCEDURAL OBJECT that maintains an INTERNAL STATE as its 366| local state, and private lookup and insert! for each table. In this 367| approach, lookup and insert! do not need the extra 'table' argument. 368| The 'let' environment provides the local state variable: 369| 370| (define (make-table) 371| (let ((local-table (list '*table*))) 372| 373| (define (lookup key-1 key-2) 374| (let ((subtable (assq key-1 (cdr local-table)))) 375| (if (not subtable) 376| nil 377| (let ((record (assq key-2 (cdr subtable)))) 378| (if (not record) nil (cdr record)))))) 379| 380| (define (insert! key-1 key-2 value) 381| (let ((subtable (assq key-1 (cdr local-table)))) 382| (if (not subtable) 383| (set-cdr! local-table 384| (cons (list key-1 (cons key-2 value)) 385| (cdr local-table))) 386| (let ((record (assq key-2 (cdr subtable)))) 387| (if (not record) 388| (set-cdr! subtable 389| (cons (cons key-2 value) (cdr subtable))) 390| (set-cdr! record value))))) 391| `ok) 392| 393| (define (dispatch m) 394| (cond ((eq? m 'lookup-proc) lookup) 395| ((eq? m 'insert-proc!) insert!) 396| (else (error "Unknown operation -- TABLE" m)))) 397| 398| dispatch)) 399| 400| An application of 'make-table' does the following: 401| 1. Creats an environment with an already initialized local-table. 402| 2. Creats procedures 'lookup, 'insert!', and 'dispatch' that have that 403| environment in their environment part. 404| 405| The returned value is the dispatch procedure created in step 2. 406| 407| ** An application of that procedure to a message 'lookup-proc returns the 408| lookup procedure created by this same application of make-table. 409| ** An application of that dispatch procedure to a message 'insert-proc 410| returns the insert! procedure created by that application of 411| make-table. 412| 413| This way we get, in the global environment, procedures 'lookup' and 414| 'insert!' that apply only to the LOCAL TABLE for which they were created. 415| These are the 'put' and 'get' operations we used in implementing the data- 416| directed programming approach: 417| 418| (define operation-table (make-table)) 419| (define get (operation-table 'lookup-proc)) 420| (define put (operation-table 'insert-proc!))