1|
2| 2.4 SYSTEMS WITH GENERIC OPERATORS
3| ==================================
4|
5|
6| 2.4.1 GENERIC ARITHMETIC OPERATORS -- USING DATA DIRECTED PROGRAMMING
7| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
8|
9| We wish to construct a system with generic arithmetic operators, that
10| will work correctly on every type of numbers: On primitive numbers, such
11| as '5' will use the built in arithmetic package of Scheme, on rational
12| numbers will use the rational arithmetic we defined earlier, and on
13| complex numbers will use the complex arithmetic. The idea is to insert a
14| new level of interface between the generic operators: add, sub, mul, div,
15| and the various arithmetical operators such as +c, -c, etc. we use data-
16| directed programming approach.
17|
18| FIRST STEP: list the generic selectors/operators:
19| ******* add, sub, mul, div. *******
20| Main difference from previous table: The generic selectors take two
21| arguments (2-ary selectors). Hence, we need a new table manager--
22| operate-2 -- that knows about the 2 arity of the operators:
23|
24| Operate procedure for table activation for 2-ary selectors:
25| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
26| (define (operate-2 op arg1 arg2)
27| (let ((t1 (type arg1)))
28| (if (eq? t1 (type arg2))
29| (let ((proc (get t1 op)))
30| (if (not (null? proc))
31| (proc (contents arg1) (contents arg2))
32| (error
33| "Operator undefined on this type -- OPERATE-2"
34| (list op arg1 arg2))))
35| (error "Operands not of same type -- OPERATE-2"
36| (list op arg1 arg2)))))
37|
38| System's construction:
39| ~~~~~~~~~~~~~~~~~~~~~~
40| 1. Table construction:
41| a. For each internal type a sequence of 'put' applications, that
42| associates a type name and a generic arithmetical operator name with
43| an internal arithmetical procedure (like, 'complex and 'add with
44| +complex). This stage is needed for every new type, added to the
45| system.
46| b. Each internal type should be defined in the manifest types approach.
47| For example, for the complex number arithmetics, a manifest type
48| 'complex' has to be attached, and a new 'make-complex' and
49| '+complex', '-complex, etc., have to be defined.
50| 2. Definitions of the generic arithmetical operators in terms of table
51| activation (operate-2).
52|
53| Step 1---Types insertion and construction:
54| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
55|
56| a. New numbers type--Primitive numbers:
57| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
58|
59| Type construction:
60|
61| Constructor: make-number.
62| Operators: +number, -number, *number, /number.
63|
64| (define (+number x y)
65| (make-number (+ x y)))
66|
67| (define (-number x y)
68| (make-number (- x y)))
69|
70| (define (*number x y)
71| (make-number (* x y)))
72|
73| (define (/number x y)
74| (make-number (/ x y)))
75|
76| (define (make-number n)
77| (attach-type 'number n))
78|
79| Insertion to table:
80|
81| (put 'number 'add +number)
82| (put 'number 'sub -number)
83| (put 'number 'mul *number)
84| (put 'number 'div /number)
85|
86| b. Complex numbers--manifesting the new type 'complex':
87| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
88|
89| Type construction:
90|
91| Constructor: make-complex.
92| Selectors: real-part, imag-part, magnitude, angle.
93| Operators: +complex, -complex, *complex, /complex.
94|
95| (define (make-complex z)
96| (attach-type 'complex z))
97|
98| (define (+complex z1 z2) (make-complex (+c z1 z2)))
99| (define (-complex z1 z2) (make-complex (-c z1 z2)))
100| (define (*complex z1 z2) (make-complex (*c z1 z2)))
101| (define (/complex z1 z2) (make-complex (/c z1 z2)))
102|
103| Insertion to table :
104|
105| (put 'complex 'add +complex)
106| (put 'complex 'sub -complex)
107| (put 'complex 'mul *complex)
108| (put 'complex 'div /complex)
109|
110| (put 'complex 'real-part real-part)
111| (put 'complex 'imag-part imag-part)
112| (put 'complex 'magnitude magnitude)
113| (put 'complex 'angle angle)
114|
115| Step 2 -- Definitions of generic arithmetical operators:
116| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
117|
118| (define (add x y) (operate-2 'add x y))
119| (define (sub x y) (operate-2 'sub x y))
120| (define (mul x y) (operate-2 'mul x y))
121| (define (div x y) (operate-2 'div x y))
122|
123| Mode of work:
124| Within the complex package, only rectangular and polar types are
125| recognized. Outside: only complex type is known. A complex number, on the
126| generic arithmetical level would have the form:
127| (complex (rectangular 3 5)).
128| The table activation procedure strips off the 'complex' manifest type, and
129| passes (rectangular 3 4) and (polar 3 30) like forms to the complex
130| arithmetical operators +complex, -complex, etc. These operators apply the
131| internal complex arithmetics (+c, -c, etc.), and attaches the manifest
132| type 'complex' to the result.
133|
134| > (define z1 (make-rectangular 3 5))
135| #
136| > (define z2 (make-polar 3 30))
137| #
138| > (define z4 (make-rectangular 4 -5))
139| #
140| > z1
141| (rectangular 3 . 5)
142| > z2
143| (polar 3 . 30)
144| > z4
145| (rectangular 4 . -5)
146| > (define z11 (make-complex z1))
147| #
148| > (define z21 (make-complex z2))
149| #
150| > z11
151| (complex rectangular 3 . 5)
152| > z21
153| (complex polar 3 . 30)
154| > (define z3 (+complex z1 z2))
155| #
156| > z3
157| (complex rectangular 3.46275434966275 . 2.03590512772141)
158| > (define z5 (+complex z1 z4))
159| #
160| > z5
161| (complex rectangular 7.0 . 0.0)
162|
163|
164| 2.4.2 COMBINING OPERANDS OF DIFFERENT TYPES; TYPE HIERARCHIES
165| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
166|
167| The methods for data abstraction like manifest types, data directed
168| programming, and introducing generic operators are all based on the idea
169| of TYPE INDEPENDENCE. For example, there are separate packages for
170| ordinary number arithmetics, for complex numbers arithmetics, etc. The
171| generic operators dispatch on data types.
172|
173| The types described so far are independent of each other, and operators
174| cannot be applied to arguments of different types.
175|
176| The subject of this chapter involves relationships among types, or type
177| structures, that enable MIXING of operations, and SHARING or INHERITANCE
178| of information among related types.
179|
180| COMBINED OPERATORS: We wish to add numbers of different types, like
181| ordinary numbers and complex numbers, or rational and real numbers.
182| A straightforward technique would be to have special addition procedures
183| for all reasonable type combinations of operands, like: +number-complex,
184| +rat-real, etc. Then,
185| *** the dispatch of a generic operator will be on the TYPE COMBINATION
186| of its operands. ***
187| This will require a 3 dimensional table, that for the types of the two
188| operands, and for a generic operator, selects the appropriate mixed
189| operator. The operate-2 procedure of the data directed programming
190| approach can control such a table.
191|
192| PROBLEM with that approach: Too many operators --
193| for each generic operator,n**2 operators in worst case, for n types,
194| might be needed. For 3-ary operators, n**3 versions might be needed,
195| in worst case.
196| *** The cost of introducing a new operator--defining all combined
197| types' versions.
198| *** The cost of introducing a new type: defining its combined version
199| arithmetic, for all generic operators, and for all other types.
200|
201| *********************************************************************
202| ** If all types are, indeed, independent and completely unrelated, **
203| ** the 3 dimensional table is, probably, the best one can do. **
204| *********************************************************************
205|
206|
207| COERCION of RELATED TYPES
208| ~~~~~~~~~~~~~~~~~~~~~~~~~
209| If types are related, there might be a general,
210| ***OPERATORS' INDEPENDENT***
211| way, for turning operands of related types into a single type. The method
212| of turning an object of one type into an object of another type, is called
213| COERCION.
214| Examples of coercion are
215| "turning an integer into real",
216| "turning a character into and integer", etc.
217|
218| *********************************************************************
219| ** The main idea behind coercion is that it is OPERATOR INDEPENDENT! **
220| ** Hence, at worst case we might need n**2 coercion procedures. In **
221| ** the non-coercion approach the n**2 procedures were defined for **
222| ** EACH generic operator. **
223| *********************************************************************
224|
225| We assume the existence of COERCION PROCEDURES like:
226|
227| (define (number->complex n)
228| (make-complex (make-rectangular (contents n) 0)))
229|
230| Data directed programming with coercion:
231| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
232| The information about the coercion procedures can be organized in a
233| COERCION TABLE that for two types gives their coercion procedure, if one
234| exists:
235|
236| (put-coercion 'number 'complex number->complex)
237|
238| and its analogous get-coercion procedure.
239|
240| Data directed programming that supports mixed operations would be as
241| before; the only difference is that now if the operands of an operator are
242| of different types, the coercion table is checked instead of just giving
243| up as before. If it is found that coercion is possible, it is applied, and
244| the operator that correspond to the resulting unique type is applied:
245|
246| (define (operate-2 op obj1 obj2)
247| (let ((t1 (type obj1)) (t2 (type obj2)))
248| (if (eq? t1 t2)
249| (let ((proc (get t1 op)))
250| (if (not (null? proc))
251| (proc (contents obj1) (contents obj2))
252| (error "Operator undefined on this type -- OPERATE-2"
253| (list op obj1 obj2))))
254| (let ((t1->t2 (get-coercion t1 t2))
255| (t2->t1 (get-coercion t2 t1)))
256| (cond ((not (null? t1->t2)) (operate-2 op (t1->t2 obj1) obj2))
257| ((not (null? t2->t1)) (operate-2 op obj1 (t2->t1 obj2)))
258| (else (error "Operands not of same type -- OPERATE-2"
259| (list op obj1 obj2))))))))
260|
261| ADVANTAGES: Save in the number of different procedures.
262| Introduction of a new type: At worst, 2*n coercion procedures.
263| Introduction of a new generic operator: No extra work.
264|
265| DISADVANTAGES: Not sufficiently powerful. For example:
266| 1) if 2 types cannot be coerced to one another, but can both be coerced to
267| a common type, the coercion approach would not work.
268| 2) The types' structure can be used to save redundant coercion procedures.
269| For example, a number->rational procedure, and rational->real
270| procedure, implicitly yields a number->real coercion procedure.
271|
272|
273| HIERARCHIES OF TYPES
274| ~~~~~~~~~~~~~~~~~~~~
275| The structure of types' inter-relationships can be used to enhance the
276| power of the system. For example, the number types form the following
277| structure:
278|
279| *** integer ISA rational ISA real ISA complex ***
280|
281| TERMINOLOGY:
282| ** if "t1 ISA t2" we say that
283| "t1 is a DIRECT SUBTYPE of t2, and t2 is a DIRECT SUPERTYPE of t1".
284| ** The direct subtype/supertype relations are generalized into their
285| transitive closure as follows:
286| if t1 is a direct subtype/supertype of t1 then t1 is also a SUBTYPE/
287| SUPERTYPE of t2.
288| All subtypes/supertypes of t1 are also subtypes/supertypes of t2.
289|
290| A structure of types as above is called a **TOWER** of types:
291| Each type has at most a single direct subtype/supertype.
292| In general, the structure of types is called TYPE HIERARCHY: It can form
293| an arbitrary directed acyclic graph (dag).
294|
295| ***** Types hierarchies are an essential part of a software *****
296| ***** engineering approach, called OBJECT-ORIENTED. *****
297|
298| Properties of systems based on TYPE-HIERARCHY:
299| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
300| 1. Coercing a type UP the hierarchy:
301| The only needed coercion procedures are for the direct supertype of a
302| type. For example, for the tower of number types, just three coercion
303| procedures are needed. All other coercions can be obtained by following
304| the ISA branch.
305| The 'operate-2' procedure can be modified as follows:
306| A 'raise' procedure is added, for raising a type, one level in the
307| hierarchy.
308| The operate-2 procedure, for objects of different types can RAISE the
309| object of lower type until the two objects have the same type.
310| This is called COERCING A TYPE UP THE HIERARCHY.
311|
312| 2. INHERITANCE:
313| All operators available for a type (like complex) are AUTOMATICALLY
314| available for all of its subtypes. This feature is called INHERITANCE
315| along the hierarchy.
316| ** For example, the selector 'real-part', is automatically inherited
317| from the complex type to the integers type.
318| The technique for inheriting information is called INHERITANCE
319| MECHANISM. It can be implemented by modifying the operate and operate-2
320| procedures to 'raise' the type of their argument objects, once the
321| argument operation is not defined for the given type(s) of their
322| objects. If the top of the hierarchy is reached--that's when the
323| procedures give up and send an error message.
324| ** For example, if operate-2 gets two integer objects, it would look
325| for the appropriate integer operation. However, if that operation
326| is not found for integers, the inheritance mechanism (using
327| 'raise') can be applied.
328| Sometimes, for efficiency reasons, we might not be interested in
329| taking advantage of that property (for example, we are not interested
330| in keeping addition just of complex numbers).
331|
332| 3. ENCAPSULATING/HIDING OPERATORS:
333| All operators available for a type are HIDDEN from its supertypes.
334| For example, integer addition is hidden from the complex type.
335| Integer operations cannot be applied to complex objects.
336| The hiding mechanism is used for REWRITING operations of supertypes.
337| ** For example, if we have a natural kinds hierarchy that includes:
338|
339| *** royal-elephant ISA elephant ***
340|
341| and the elephant type has the selector 'color' with constant value
342| GRAY, we can rewrite that selector for royal-elephants:
343| color(royal-elephant) = white. The operate procedure will pick the
344| white value for all royal-elephant typed objects, as royal-elephant
345| is a subtype of elephant.
346|
347| 4. COERCING A TYPE DOWN THE HIERARCHY:
348| Usually a subtype has a more concrete/specific package of operators.
349| Hence, it is useful to identify the most specific type of an object.
350| ** For example, if a number is known to be complex with a 0 imaginary
351| part, then it is simply a real, or even an integer (depends on
352| the real part).
353| A "smart" usage of the type hierarchy should also
354| take advantage of "lowering" the type of an object.
355| ** The square power of the real number "square root of 2" is just
356| the integer 2. Similarly, the sum of the complex numbers
357| 2 + 3i and 5 - 3i is the integer 7, which is also the complex
358| 7 + 0i.
359|
360| 5. MULTIPLE INHERITANCE:
361| General type hierarchies have the structure of a directed acyclic
362| graph (DAG): No ISA cycles, but a type can have several direct
363| subtypes, and several direct supertypes. In a general hierarchical
364| structure of types, the operations of inheritance, and coercion up
365| and down the hierarchy present complex problems.
366| Coercion up might involve considerable search through the entire
367| hierarchy, until a most specific supertype of the argument objects
368| is found.
369| For coercion down, there may be several ways to coerce down an object.
370| For inheritance, a type may have supertypes with the same selector
371| (defined differently for each supertype). This problem is called:
372| MULTIPLE INHERITANCE. The question is: how to uniquely determine the
373| inheritance mechanism in case of multiple inheritance.
374| There is no single/common solution to these questions. Current system
375| employ their private solutions.
376|
377| The subject of object-oriented (OO) representation is an area of
378| much current research in AI (semantic networks, description languages),
379| databases (OODB), and programming languages (C++, Smalltalk, Actor,
380| Clos--Common Lisp Object -oriented System).
381|
382|
383| 2.4.3 CONCLUDING EXAMPLE: Polynomial arithmetic
384| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
385|
386| A polynomial is a sum of terms, each of which is:
387| 1. A coefficient, or
388| 2. A power of a variable, or
389| 3. A product of a coefficient and a power of a variable.
390| A coefficient is an algebraic expression that is not dependent on the
391| variables of the polynomial. A coefficient can be a polynomial itself, in
392| different variables, of course. For example,
393| (y**2 +4)x**3 + (2y)x + 5x + (-3)
394| is a polynomial.
395|
396| Simplifying assumptions:
397| 1) Polynomials with a single variable.
398| 2) Polynomials are considered as syntactic objects. That is:
399| mathematically equal polynomials that look different are different!
400| 3) Only addition and multiplication of polynomials.
401| 4) Two polynomials combined by an arithmetic operation must have the same
402| variable.
403|
404| Polynomials representation: as a pair of a variable and a collection of
405| terms.
406| Selectors: 'variable' and 'term-list'.
407| All arithmetics is done on the collections of terms.
408| Constructor: make-polynomial, that constructs a polynomial from a given
409| variable and collection of terms.
410|
411| Generic arithmetic operators for polynomials, in terms of the
412| make-polynomial, variable and term-list operators:
413|
414| (define (+poly p1 p2)
415| (if (same-variable? (variable p1) (variable p2))
416| (make-polynomial (variable p1)
417| (+terms (term-list p1) (term-list p2)))
418| (error "Polys not in same var -- +POLY" (list p1 p2))))
419|
420| (define (*poly p1 p2)
421| (if (same-variable? (variable p1) (variable p2))
422| (make-polynomial (variable p1)
423| (*terms (term-list p1)
424| (term-list p2)))
425| (error "Polys not in same var -- *POLY" (list p1 p2))))
426|
427| ;;; Install polynomial arithmetic in the generic-arithmetic system
428|
429| (put 'polynomial 'add +poly)
430| (put 'polynomial 'mul *poly)
431|
432| Termlists and terms as abstract data types:
433| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
434| Term-lists:
435| Constructors are:
436| the-empty-termlist: that generates an empty term list.
437| adjoin-term: that adjoins a new term to a term list.
438| Selectors are:
439| first-term: that extracts the highest order term from a term list.
440| rest-terms: that returns all but the highest order term.
441| Predicate:
442| empty=termlist?: that characterizes empty term lists.
443| Terms:
444| selectors are 'order' and 'coeff', and the constructor is 'make-term'.
445|
446| Using these data abstraction assumptions, the term lists for a sum
447| and for a product of two polynomials are constructed by the following
448| procedures:
449|
450| (define (+terms L1 L2)
451| (cond ((empty-termlist? L1) L2)
452| ((empty-termlist? L2) L1)
453| (else
454| (let ((t1 (first-term L1)) (t2 (first-term L2)))
455| (cond ((> (order t1) (order t2))
456| (adjoin-term t1
457| (+terms (rest-terms L1) L2)))
458| ((< (order t1) (order t2))
459| (adjoin-term t2
460| (+terms L1 (rest-terms L2))))
461| (else
462| (adjoin-term (make-term (order t1)
463| (add (coeff t1)
464| (coeff t2)))
465| (+terms (rest-terms L1)
466| (rest-terms L2)))))))))
467|
468| NOTE: The generic addition operator 'add' is used for the coefficients
469| addition.
470|
471|
472| (define (*terms L1 L2)
473| (if (empty-termlist? L1)
474| (the-empty-termlist)
475| (+terms (*-term-by-all-terms (first-term L1) L2)
476| (*terms (rest-terms L1) L2))))
477|
478| (define (*-term-by-all-terms t1 L)
479| (if (empty-termlist? L)
480| (the-empty-termlist)
481| (let ((t2 (first-term L)))
482| (adjoin-term (make-term (+ (order t1) (order t2))
483| (mul (coeff t1) (coeff t2)))
484| (*-term-by-all-terms t1
485| (rest-terms L))))))
486|
487|
488| NOTE: The generic multiplication operator 'mul' is used for the
489| coefficients multiplication.
490| OBSERVATION:
491| Using the generic arithmetic operators 'add' and 'mul', enables the system
492| to correctly handle polynomials with polynomial coefficients, such as
493| (y + 1)x**2 + (3y**4)x + 5.
494| The system can add and multiply such polynomials. The addition (+poly) of
495| such polynomials would invoke recursive calls of +poly for the
496| coefficients, which are, themselves, polynomials. Similarly for *poly.
497| This is possible since we'v installed the polynomial addition and
498| multiplication operators in the generic arithmetic package, as 'add' and
499| 'mul', respectively.
500| If coercion mechanism is installed, the polynomial arithmetic can be
501| applied to polynomials with different coefficient types:
502|
503| [3x**2 + (2 +3i)x + 6]*[x**3 + (y**3 + 1)x**2 + (2/3)x + (5 +3i) ]
504|
505|
506| Representation of term lists
507| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
508| Term lists are sets of coefficients, keyed by the order of their terms.
509| Hence, any of the methods for sets representation can apply.
510| Since the selector 'first-term' picks the highest order term, it is
511| reasonable to represent term lists as lists, ordered by
512| descending order of the terms.
513| We will use a list of pairs, each pair being an order of a term, and the
514| corresponding coefficient. For example:
515| x**100 + 2x**2 + 1
516| will be represented by: ( (100 1) (2 2) (0 1) ).
517| Note that if all orders are present, i.e., the polynomial is DENSE, then
518| the orders become redundant.
519|
520| The term list and term packages:
521| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
522| Term lists:
523|
524| (define (adjoin-term term term-list)
525| (if (=zero? (coeff term))
526| term-list
527| (cons term term-list)))
528|
529| (define (the-empty-termlist) '())
530| (define (first-term term-list) (car term-list))
531| (define (rest-terms term-list) (cdr term-list))
532| (define (empty-termlist? term-list) (null? term-list))
533|
534| Note: '=zero?' is a generic arithmetic predicate that tests if the
535| argument is zero. '=zero?' is defined for all number types.
536|
537| Terms:
538|
539| (define (make-term order coeff) (list order coeff))
540| (define (order term) (car term))
541| (define (coeff term) (cadr term))
542|
543| Representation of polynomials:
544| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
545| (define (make-polynomial variable term-list)
546| (attach-type 'polynomial (cons variable term-list)))
547|
548| (define (variable p) (car p))
549|
550| (define (term-list p) (cdr p))
551|
552| Note: 'same-variable?' was defined in the symbolic differentiation
553| example.
554|
555|
556| Concluding observation:
557| ~~~~~~~~~~~~~~~~~~~~~~~
558| The polynomials arithmetic examples demonstrate the processing of
559| abstract data types that are recursively composed of other types. But the
560| above package still DOES NOT provide an answer to general problems of
561| polynomial arithmetics, such as operations on polynomials of different
562| types (different variables, different coefficient types).
563| Such polynomials can be organized into a type hierarchy which IS NOT a
564| tower. There is no common, generally accepted solution to such problems.
565| Coercion and the very basic notion of an abstract data type are still,
566| just partly understood.