1| 2| 2. BUILDING ABSTRACTIONS WITH DATA 3| =================================== 4| 5| We already saw that abstractions can be formed by compound procedures 6| and higher order procedures that model processes and general methods of 7| computation. The ability to combine data objects into compound objects, 8| that can be further combined adds additional power of abstraction: The 9| objects that participate in the modeled process are no longer just atomic, 10| unrelated objects, but are organized into some relevant structures. The 11| modeled world is not just an un-ordered collection of elements, but have 12| some internal structure. 13| Compound data increases the CONCEPTUAL LEVEL of the design. Adds 14| MODULARITY and improves the EXPRESSIVE POWER. 15| Modularity: The IMPLEMENTATION can be separated from the USAGE of the 16| data--a method called DATA ABSTRACTION. 17| Expressivity: General combinations can be expressed, such as: 18| Linear combination: ax+by, where x and y can be matrices, 19| polynomials, complex numbers, etc. 20| Algebraic rules, such as commutativity, associativity, etc can be 21| expressed, independently from the data identity--numbers, 22| regular expressions, etc. 23| 24| 25| 2.1 INTRODUCTION TO DATA ABSTRACTION 26| ===================================== 27| 28| The idea is the separation between USAGE to IMPLEMENTATION, or CONCRETE 29| REPRESENTATION. 30| 31| *** The parts of the program that USE the data objects refer to them via 32| CONCEPTUAL OPERATIONS, such as set union, intersection, selection. They 33| make no assumption about how the data objects are implemented. 34| 35| *** The parts of the program that IMPLEMENT the data objects provide 36| procedures for referring to the implemented data objects. These are called 37| SELECTORS (like take the head of a list) and CONSTRUCTORS (like set 38| union). Constructors are the "glue" for constructing compound objects, and 39| selectors are the means for splitting compound objects into their 40| components. The connection between the abstract level of USAGE to the 41| concrete level of IMPLEMENTATION is done by implementing the conceptual 42| operations in terms of the constructors and selectors. 43| 44| The principle of data abstraction is the SEPARATION between two main 45| levels: 46| 47| 1. CONCEPTUAL LEVEL 48| || 49| || 50| \||/ 51| \/ 52| Data operators--constructors, selectors 53| /\ 54| /||\ 55| || 56| || 57| 2. IMPLEMENTATION LEVEL 58| 59| 60| Concrete implementation of data objects are verified (tested to be 61| TRUE) by RULES OF CORRECTNESS that the constructors and selectors should 62| satisfy. In principle, every implementation that satisfies the correctness 63| rules is correct. For example, every implementation of arrays that 64| satisfies: Assign(A[i], select(A[i])) = A, for an array A, and reference 65| index i, is correct. Correct implementations can, still, differ in other 66| criteria, like space and time efficiency. 67| 68| 2.1.1 EXAMPLE: ARITHMETIC OPERATORS FOR RATIONAL NUMBERS 69| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 70| 71| We assume that rational numbers are represented "somehow" by compound 72| objects constructed from a numerator and a denominator. The **glue** and 73| the **selection** are given by the procedures: 74| 75| DATA OPERATORS: 76| ~~~~~~~~~~~~~~~ 77| CONSTRUCTOR: 78| (make-rat ): returns a rational number whose numerator is the 79| integer , and whose denominator is the integer . 80| 81| SELECTORS: 82| (numer ) : returns the numerator of the rational number . 83| (denom ) : returns the denominator of the rational number . 84| 85| The **conceptual operations** for using rationals are: Addition, 86| subtraction, multiplication, division, and test for equality. They can be 87| **implemented** in terms of the constructor and selectors as follows: 88| 89| CONCEPTUAL LEVEL: Rational-number operations 90| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 91| 92| (define (+rat x y) 93| (make-rat (+ (* (numer x) (denom y)) 94| (* (denom x) (numer y))) 95| (* (denom x) (denom y)))) 96| 97| (define (-rat x y) 98| (make-rat (- (* (numer x) (denom y)) 99| (* (denom x) (numer y))) 100| (* (denom x) (denom y)))) 101| 102| (define (*rat x y) 103| (make-rat (* (numer x) (numer y)) 104| (* (denom x) (denom y)))) 105| 106| (define (/rat x y) 107| (make-rat (* (numer x) (denom y)) 108| (* (denom x) (numer y)))) 109| 110| (define (=rat x y) 111| (= (* (numer x) (denom y)) 112| (* (numer y) (denom x)))) 113| 114| 115| IMPLEMENTATION LEVEL: 116| ~~~~~~~~~~~~~~~~~~~~~ 117| In this level we define PROCEDURES for the data operators. These 118| procedures will act as INTERFACE PROCEDURES between the conceptual level 119| to the implementation level: They will **hide** the details of 120| implementation from the conceptual level. 121| We have to agree in what terms we implement the data operators. This 122| will be called the REPRESENTATION of the data operators. For the rational 123| numbers, it seems natural to represent a rational number, that is, the 124| result of a 'make-rat' operation as a PAIR, and let 'numer' and 'denom' 125| pick the first and second elements of the pair, respectively. 126| 127| *** Implementation is preceded by REPRESENTATION decision *** 128| 129| 130| PAIRS in Scheme/LISP: 131| ~~~~~~~~~~~~~~~~~~~~~ 132| Pairs are the basic compound data object in Scheme/LISP. The 133| Scheme/LISP primitive procedure for forming pairs is "cons", and the 134| primitives procedures for selecting the first and second elements of a 135| pair are "car" and "cdr", respectively. 136| The correctness rules for 'cons', 'car', and 'cdr' are: 137| (car (cons x y)) = x 138| (cdr (cons x y)) = y 139| 140| For example: 141| > (define x (cons 1 2)) 142| # 143| > (car x) 144| 1 145| > (cdr x) 146| 2 147| > x 148| (1 . 2) 149| 150| ;;; This is an example of the DOTTED NOTATION for pairs: This the way 151| ;;; Scheme prints out pairs. 152| 153| > (define y (cons x 2)) 154| # 155| > (car y) 156| (1 . 2) 157| > (cdr y) 158| 2 159| > y 160| ((1 . 2) . 2) 161| > (define z (cons x y)) 162| # 163| > (car z) 164| (1 . 2) 165| > (cdr z) 166| ((1 . 2) . 2) 167| > (car (car z)) 168| 1 169| > (car (cdr z)) 170| (1 . 2) 171| > z 172| ((1 . 2) (1 . 2) . 2) 173| 174| ;;; This is the way Scheme prints out pairs whose 'cdr' is a pair. It 175| ;;; results from the way Scheme prints out LISTS--data objects that will 176| ;;; be discussed later. 177| 178| > (cdr (cdr z)) 179| 2 180| > (car (car y)) 181| 1 182| > (car (cdr y)) 183| 184| ERROR: car: Wrong type in arg1 2 185| 186| ;;; Note the (1 . 2) is NOT a Scheme combination/form. It is just the 187| ;;; printed representation of pairs: It cannot be evaluated by the 188| ;;; interpreter. 189| ;;; For example: (define x (1 . 2)) will cause an error. 190| 191| REPRESENTATION: 192| The rational numbers data operators can be implemented by representing a 193| rational number by a pair of the numerator and denominator. 194| This representation can be IMPLEMENTED by implementing the constructor and 195| selectors using cons, car and cdr: 196| 197| ;;; Rational-number implementation of the PAIRS representation-- unreduced 198| 199| (define (make-rat n d) (cons n d)) 200| 201| (define (numer x) (car x)) 202| 203| (define (denom x) (cdr x)) 204| 205| > make-rat 206| # 207| 208| ;;; Printing rational numbers 209| 210| > (define (print-rat x) 211| (princ (numer x)) 212| (princ "/") 213| (princ (denom x)) 214| (newline)) 215| # 216| > (define one-half (make-rat 1 2)) 217| # 218| > (define two-sixth (make-rat 2 6)) 219| # 220| > (print-rat (+rat one-half two-sixth)) 221| 10/12 222| # 223| > (print-rat (*rat one-half two-sixth)) 224| 2/12 225| # 226| > (print-rat (/rat two-sixth one-half)) 227| 4/6 228| > (/rat two-sixth one-half) 229| (4 . 6) 230| > (define x (print-rat (/rat two-sixth one-half))) 231| 4/6 232| # 233| > x 234| # 235| > 236| 237| A different implementation for the same representation: 238| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 239| 240| > (define make-rat cons) 241| # 242| > (define numer car) 243| # 244| > (define denom cdr) 245| # 246| > (print-rat (+rat one-half two-sixth)) 247| 10/12 248| # 249| > make-rat 250| # 251| > (/rat two-sixth one-half) 252| (4 . 6) 253| > 254| 255| THE DIFFERENCE between the two implementations: 256| In the first-- make-rat USES cons. 'make-rat' is a compound procedure. 257| In the second-- make-rat is another name for the primitive procedure 258| which is the value of cons. In this case there is a 259| SINGLE procedure with two names. 260| The second option is more efficient in terms of both 261| time and space. 262| 263| 264| A different REPRESENTATION: 265| ~~~~~~~~~~~~~~~~~~~~~~~~~~~ 266| ;;; Rational-number representation -- reduced at construction time 267| > (define (make-rat n d) 268| (let ((g (gcd n d))) 269| (cons (/ n g) (/ d g)))) 270| # 271| > (define (numer x) (car x)) 272| # 273| > (define (denom x) (cdr x)) 274| # 275| > (print-rat (/rat two-sixth one-half)) 276| 2/3 277| # 278| > (define one-half (make-rat 5 10)) 279| # 280| > one-half 281| (1 . 2) 282| > 283| 284| 285| Rules of correctness for the rational numbers' implementation: 286| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 287| First suggestion: (numer (make-rat n d)) = n 288| (denom (make-rat n d)) = d 289| Are these rules satisfied by the two implementations above? 290| 291| Second suggestion: 292| [ (numer (make-rat n d)) / (denom (make-rat n d)) ] = n/d 293| Is that rule satisfied by the two implementations above? 294| 295| Yet another representation of rational numbers: 296| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 297| ;;; Rational-number representation -- reduced at selection time 298| 299| > (define make-rat cons) 300| # 301| (define (numer x) 302| (let ((g (gcd (car x) (cdr x)))) 303| (/ (car x) g))) 304| # 305| > (define (denom x) 306| (let ((g (gcd (car x) (cdr x)))) 307| (/ (cdr x) g))) 308| 309| Is that representation correct? 310| 311| 312| 2.1.2 ABSTRACTION BARRIERS 313| ~~~~~~~~~~~~~~~~~~~~~~~~~~ 314| 315| Levels in Data Abstraction: 316| ~~~~~~~~~~~~~~~~~~~~~~~~~~~ 317| 1. Programs that USE the data objects: expressed in terms of conceptual 318| operators -- +rat, -rat, etc. 319| 2. Conceptual operators--expressed in terms of constructors and selectors 320| that provide the FULL ACCOUNT for the data objects. 321| 3. Constructors and selectors--represented and implemented in terms of 322| primitives of some implemented computer language. 323| 4. Implemented language primitives--like the cons, car and cdr of LISP. 324| 325| Programs: On data objects 326| | 327| \|/ 328| V 329| Conceptual operators: User's view 330| | 331| \|/ 332| V 333| Constructors & selectors 334| | 335| \|/ 336| V 337| Implemented language primitives. 338| 339| 340| **** Data abstraction provides **** : 341| 1. ** Modularity of design **: Upper levels can be designed independently 342| of representation and implementation decisions. 343| 2. ** Flexibility **: Change of implementation language's primitives does 344| not affect the 2 upper levels. 345| 3. ** Increased chances for correct programs **: Constructors and 346| selectors are verified with respect to rules of correctness. 347| Conceptual operators are, usually, easy to verify, when expressed in 348| terms of the abstract data structure--constructors & selectors. 349| Programs are expressed using conceptually meaningful operators. 350| 351| The result is: 352| Possible to have MULTIPLE REPRESENTATIONS and IMPLEMENTATIONS for the 353| same data objects. 354| Possible to have MULTIPLE sets of INTERFACE (data) OPERATORS. All can, 355| possibly be represented and implemented in the same way. 356| Possible to have MULTIPLE sets of CONCEPTUAL OPERATORS. 357| 358| 359| 2.1.3 WHAT IS MEANT BY DATA? 360| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 361| 362| We said that this chapter handles "abstractions built with data", while 363| the previous chapter dealt with abstractions formed by procedures. 364| We never bothered to define exactly 365| WHAT IS DATA????? 366| This question is especially hard to answer in the environment of Scheme, 367| where "procedures" and "data" are uniformly handled. 368| 369| We tend to say that: 370| **************************************************************** 371| ** Data is just anything defined by constructors and selectors, ** 372| ** that should satisfy given rules of correctness. ** 373| ** Such "data" is called an ABSTRACT DATA TYPE (ADT). ** 374| **************************************************************** 375| 376| Example of data abstraction for PAIRS: 377| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 378| 379| Assume that the language does not support the compound data PAIR, with 380| the cons constructor, and the car and cdr selectors. 381| Pair can be implemented in Scheme using compound procedures alone. 382| 383| The constructor is 'cons'. The selectors are 'car' and 'cdr'. 384| The rules of correctness for "pair" are: 385| (car (cons x y)) = x 386| (cdr (cons x y)) = y 387| 388| ;;; Procedural representation of pairs 389| 390| (define (cons x y) 391| (define (dispatch m) 392| (cond ((= m 0) x) 393| ((= m 1) y) 394| (else (error "Argument not 0 or 1 -- CONS" m)))) 395| dispatch) 396| 397| (define (car z) (z 0)) 398| 399| (define (cdr z) (z 1)) 400| 401| 'cons' returns a procedure named dispatch! car takes a procedure as 402| argument, and applies it to 0, and cdr is similar, but applies its 403| argument procedure to 1. Dispatch, when applied to 0, returns the binding, 404| in the environment (given by the enclosing cons), of the first parameter 405| of cons. Hence, (car (cons x y)), evaluates to x. The rule for cdr holds 406| for similar arguments. 407| 408| This definition of 'cons' is confusing since: 409| It returns the internal procedure itself as its value (it does not APPLY 410| the internal procedure, just defines it and returns it). 411| This definition of 'cons' can be REWRITTEN as follows: 412| (define (cons x y) 413| (lambda (m) 414| (cond ((= m 0) x) 415| ((= m 1) y) 416| (else (error "Argument not 0 or 1 -- CONS" m) ))) ) 417| 418| Using the substitution model, the evaluation of 419| (cons 1 2) 420| yields: 421| (lambda (m) 422| (cond ((= m 0) 1) 423| ((= m 1) 2) 424| (else (error "Argument not 0 or 1 -- CONS" m) ))) 425| 426| Now, the evaluation of 427| (car (cons 1 2 )) 428| yields, by substituting the value of (cons 1 2) for the formal parameter z 429| in the body of 'car': 430| ( (lambda (m) 431| (cond ((= m 0) 1) 432| ((= m 1) 2) 433| (else (error "Argument not 0 or 1 -- CONS" m) ))) 434| 0 ) 435| The evaluation of the last form yields: 436| (cond ((= 0 0) 1) 437| ((= 0 1) 2) 438| (else (error "Argument not 0 or 1 -- CONS" m) ))) 439| 440| which evaluates to 1. 441| 442| > (define x (cons 1 2)) 443| # 444| > x 445| # (define y (car x)) 447| # 448| > y 449| 1 450| > (define z (cdr x)) 451| # 452| > z 453| 2 454| > (define w (cons y z)) 455| # 456| > (car w) 457| 1 458| > (cdr w) 459| 2 460| > cons 461| # car 463| # 464| > 465| 466| SUMMARY: The PAIR data object was represented as a procedure that is 467| capable of receiving "messages". It was implemented using scheme 468| capability to define procedures that return procedures as values. Each 469| pair (new application of the 'cons' procedure generates a NEW procedure, 470| for the defined pair. So, x, and w above are DIFFERENT pair objects, that 471| is, different procedures. Each can receive just two messages and return 472| the right car or cdr. 473| 474| 475| 2.1.4 EXAMPLE: Interval Arithmetic 476| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 477| 478| Data objects are "intervals", i.e., compound objects that represent a 479| range of values. Each interval has 2 end points: a lower bound and an 480| upper bound. An interval can be constructed from its 2 end points. 481| Constructor: make-interval. 482| Selectors: lower-bound, upper-bound. 483| Constructor and the selectors are not implemented yet. 484| Rules of correctness for their implementations: 485| (lower-bound (make-interval l u)) = l 486| (upper-bound (make-interval l u)) = u 487| 488| Conceptual operations: 489| 490| (define (intadd x y) 491| (make-interval (+ (lower-bound x) (lower-bound y)) 492| (+ (upper-bound x) (upper-bound y)))) 493| 494| (define (intmul x y) 495| (let ((p1 (* (lower-bound x) (lower-bound y))) 496| (p2 (* (lower-bound x) (upper-bound y))) 497| (p3 (* (upper-bound x) (lower-bound y))) 498| (p4 (* (upper-bound x) (upper-bound y)))) 499| (make-interval (min p1 p2 p3 p4) 500| (max p1 p2 p3 p4)))) 501| 502| (define (intdiv x y) 503| (intmul x 504| (make-interval (/ 1 (upper-bound y)) 505| (/ 1 (lower-bound y)))))