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)))))