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.