In 2.4, saw how to design systems where data can be represented in more than one way. Key idea: link code that specifies the data operations to several representations by means of generic interface procedures. Now, define operations that are generic over different kinds of arguments.
Example, arithmetic. Built-in primitive (+, -, *, /), rational-number (add-rat, sub-rat, mul-rat, div-rat), and complex. Now, use data-directed techniques to construct a package of arithmetic operations that incorporates all.
Can implement by following strategy from 2.4.3. Attach a type tag to each kind of number and cause the generic procedure to dispatch to an appropriate package.
Generic arithmetic procedures:
(define (add x y) (apply-generic 'add x y))
(define (sub x y) (apply-generic 'sub x y))
(define (mul x y) (apply-generic 'mul x y))
(define (div x y) (apply-generic 'div x y))First, install package for ordinary numbers. Tag these with the symbol scheme-number. Since they can take two arguments, they are installed in the table keyed by the list (scheme-number scheme-number):
(define (install-scheme-number-package)
(define (tag x) (attach-tag 'scheme-number x))
(put 'add '(scheme-number scheme-number)
(lambda (x y) (tag (+ x y))))
(put 'sub '(scheme-number scheme-number)
(lambda (x y) (tag (- x y))))
(put 'mul '(scheme-number scheme-number)
(lambda (x y) (tag (* x y))))
(put 'div '(scheme-number scheme-number)
(lambda (x y) (tag (/ x y))))
(put 'make 'scheme-number (lambda (x) (tag x)))
'done)Users of the package will create tagged ordinary numbers by means of:
(define (make-scheme-number n)
((get 'make 'scheme-number)) n)Here is a package that performs rational arithmetic:
(define (install-rational-package)
;; internal procedures
(define (numer x) (car x))
(define (denom x) (cdr x))
(define (make-rat n d)
(let ((g (gcd n d)))
(cons (/ n g) (/ d g))))
(define (add-rat x y)
(make-rat (+ (* (numer x) (denom y))
(* (numer y) (denom x)))
(* (denom x) (denom y))))
(define (sub-rat x y)
(make-rat (- (* (numer x) (denom y))
(* (numer y) (denom x)))
(* (denom x) (denom y))))
(define (mul-rat x y)
(make-rat (* (numer x) (numer y))
(* (denom x) (denom y))))
(define (div-rat x y)
(make-rat (* (numer x) (denom y))
(* (denom x) (numer y))))
;; interface to the rest of the system
(define (tag x) (attach-tag 'rational x))
(put 'add '(rational rational)
(lambda (x y) (tag (add-rat x y))))
(put 'sub '(rational rational)
(lambda (x y) (tag (sub-rat x y))))
(put 'mul '(rational rational)
(lambda (x y) (tag (mul-rat x y))))
(put 'div '(rational rational)
(lambda (x y) (tag (div-rat x y))))
(put 'make 'rational
(lambda (n d) (tag (make-rat n d))))
'done)
(define (make-rational n d)
((get 'make 'rational) n d))And for complex numbers:
(define (install-complex-package)
;; imported procedures from rectangular and polar packages
(define (make-from-real-imag x y)
((get 'make-from-real-imag 'rectangular) x y))
(define (make-from-mag-ang r a)
((get 'make-from-mag-ang 'polar) r a))
;; internal procedures
(define (add-complex z1 z2)
(make-from-real-imag (+ (real-part z1) (real-part z2))
(+ (imag-part z1) (imag-part z2))))
(define (sub-complex z1 z2)
(make-from-real-imag (- (real-part z1) (real-part z2))
(- (imag-part z1) (imag-part z2))))
(define (mul-complex z1 z2)
(make-from-mag-ang (* (magnitude z1) (magnitude z2))
(+ (angle z1) (angle z2))))
(define (div-complex z1 z2)
(make-from-mag-ang (/ (magnitude z1) (magnitude z2))
(- (angle z1) (angle z2))))
;; interface to the rest of the system
(define (tag z) (attach-tag 'complex z))
(put 'add '(complex complex)
(lambda (z1 z2) (tag (add-complex z1 z2))))
(put 'sub '(complex complex)
(lambda (z1 z2) (tag (sub-complex z1 z2))))
(put 'mul '(complex complex)
(lambda (z1 z2) (tag (mul-complex z1 z2))))
(put 'div '(complex complex)
(lambda (z1 z2) (tag (div-complex z1 z2))))
(put 'make-from-real-imag 'complex
(lambda (x y) (tag (make-from-real-imag x y))))
(put 'make-from-mag-ang 'complex
(lambda (r a) (tag (make-from-mag-ang r a))))
'done)(define (make-complex-from-real-imag x y)
((get 'make-from-real-imag 'complex) x y))
(define (make-complex-from-mag-ang r a)
((get 'make-from-mag-ang 'complex) r a))Louis Reasoner tries to evaluate the expression (magnitude z) where z is the object shown in Figure 2.24. To his surprise, instead of the answer 5 he gets an error message from apply-generic, saying there is no method for the operation magnitude on the types (complex). He shows this interaction to Alyssa P. Hacker, who says “The problem is that the complex-number selectors were never defined for complex numbers, just for polar and rectangular numbers. All you have to do to make this work is add the following to the complex package:”
(put 'real-part '(complex) real-part)
(put 'imag-part '(complex) imag-part)
(put 'magnitude '(complex) magnitude)
(put 'angle '(complex) angle)Describe in detail why this works. As an example, trace through all the procedures called in evaluating the expression (magnitude z) where z is the object shown in Figure 2.24. In particular, how many times is apply-generic invoked? What procedure is dispatched to in each case?
As described, the selectors for complex-numbers were not ever interfaced to the rest of the system. Once the above lines are added to the package, there are two calls to apply-generic.
The internal procedures in the scheme-number package are essentially nothing more than calls to the primitive procedures +,-, etc. It was not possible to use the primitives of the language directly because our type-tag system requires that each data object have a type attached to it. In fact, however, all Lisp implementations do have a type system, which they use internally. Primitive predicates such as symbol? and number? determine whether data objects have particular types. Modify the definitions of type-tag, contents, and attach-tag from Section 2.4.2 so that our generic system takes advantage of Scheme’s internal type system. That is to say, the system should work as before except that ordinary numbers should be represented simply as Scheme numbers rather than as pairs whose car is the symbol scheme-number.
(define (type-tag datum)
(cond ((number? datum) 'scheme-number)
((pair? datum) (car datum))
(else (error "Bad tagged datum: TYPE-TAG" datum))))
(define (contents datum)
(cond ((number? datum) datum)
((pair? datum) (cdr datum))
(else (error "Bad tagged datum: CONTENTS" datum))))
(define (attach-tag type-tag contents)
(if (= 'scheme-number type-tag)
contents
(cons type-tag contents)))Define a generic equality predicate equ? that tests the equality of two numbers, and install it in the generic arithmetic package. This operation should work for ordinary numbers, rational numbers, and complex numbers.
;; in the scheme-number package
(define (equ? a b) (= a b))
(put 'equ? '(scheme-number scheme-number)
(lambda (a b) (equ? a b)));; in the rational-number package
(define (equ? a b)
(and (= (numer a) (numer b))
(= (denom a) (denom b))))
(put 'equ? '(rational rational)
(lambda (a b) (equ? a b)));; in the complex number package
(define (equ? a b)
(and (= (magnitude a) (magnitude b))
(= (angle a) (angle b))))
(put 'equ? '(complex complex)
(lambda (a b) (equ? a b)))Define a generic predicate =zero? that tests if its argument is zero, and install it in the generic arithmetic package. This operation should work for ordinary numbers, rational numbers, and complex numbers.
;; in the scheme-number package
(define (zero? x) (= x 0))
(put 'zero? '(scheme-number) zero?);; in the rational-number package
(define (zero? x) (= (numer x) 0)
(put 'zero? '(rational) zero?);; in the complex number package
(define (zero? x) (and (= (real-part x) 0) (= (imag-part x) 0)))
(put 'zero? '(complex) zero?)Operations defined so far treat independent data types as completely independent. Have not considered that it is meaningful to define opreations across the type boundaries. Would like to be able to introduce this without violating module boundaries.
One way is to design a different procedure for each possible combination of types for the operation. e.g. extend complex-number package so that it provides a procedure for adding complex to ordinary and install it in the table:
;; to be included in the complex package
(define (add-complex-to-schemenum z x)
(make-from-real-imag (+ (real-part z) x) (imag-part z)))
(put 'add '(complex scheme-number)
(lambda (z x) (tag (add-complex-to-schemenum z x))))This works but is cumbersome. Undermines the ability to separate packages additively.
In the general case, implementing explicit cross-type operations is the best to hope for, though not ideal. Can usually do better by taking advantage of additional structure latent in the type system. Often may be a way one data type can be viewed as another. Called coercion.
In general, can imlpement by designing coercion procedures:
(define (scheme-number->complex n)
(make-complex-from-real-imag (contents n) 0))Install in a special coercion table, indexed under the names of the types:
(put-coercion 'scheme-number
'complex
scheme-number->complex)Generally, some slots will be empty, can't always coerce. Once table has been set up, can handle coercion by modifying apply-generic from Section 2.4.3. First check if the operation is defined for the types, as before. If so, dispatch the procedure. Otherwise, try coercion.
(define (apply-generic op . args)
(let ((type-tags (map type-tag args)))
(let ((proc (get op type-tags)))
(if proc
(apply proc (map contents args))
(if (= (length args) 2)
(let ((type1 (car type-tags))
(type2 (cadr type-tags))
(a1 (car args))
(a2 (cadr args)))
(let ((t1->t2 (get-coercion type1 type2))
(t2->t1 (get-coercion type2 type1)))
(cond (t1->t2
(apply-generic op (t1->t2 a1) a2))
(t2->t1
(apply-generic op a1 (t2-> t1 a2)))
(else (error "No method for these types"
(list op type-tags))))))
(error "No method for these types"
(list op type-tags)))))))This has many advantages over explicit cross-type operations. Still need to write coercion procedures to relate types (possibly n^2 for a system with n types), but only need one for each pair.
Still, might not be general enough. Maybe we can coerce each object to a third type that allows the operation. Usually its necessary to build further structure in relations among types.
Coercion scheme above relies on natural relations between pairs of types. Often there is a more global strcuture. e.g. an integer is a special kind of real number is a special kind of a complex number. We have a hierarchy of types where integers are a subtype of rational numbers and rational numbers are a supertype of integers. This simple structure is called a tower.
Can add a new type to the tower by specfying how it is embedded in the type above and how it is the supertype to the type below.
Redesign our apply-generic procedure: for each type, supply a raise procedure, which "raises" objects of that type one level. Then the system can successively raise lower types until all objects are at the same level.
Another advantage of tower: can implement that every type "inherits" all operations on supertype. Also by modifying apply-generic. If the operation is not directly defined for the type, raise the object to supertype and try again.
Another advantage: gives a simple way to "lower" data object. See Exercise 2.85.
Usually cannot naturally arrange types into a tower. e.g. relationship among geographic figures. A type may have more than one subtype (triangles and quadrilaters are subtypes of polygons). A type may have more than one supertype (isosceles right triangle can be an isosceles triangle or a right triangle). Multiple supertype issue is particularly thorny. No unique way to "raise" a type. Finding the correct supertype can involve considerable searching.
Louis Reasoner has noticed that apply-generic may try to coerce the arguments to each other’s type even if they already have the same type. Therefore, he reasons, we need to put procedures in the coercion table to coerce arguments of each type to their own type. For example, inaddition to the scheme-number->complex coercion shown above, he would do:
(define (scheme-numbe->scheme-number n) n)
(define (complex->complex z) z)
(put-coercion 'scheme-number
'scheme-number
scheme-number->scheme-number)
(put-coercion 'complex 'complex complex->complex)a. With Louis’s coercion procedures installed, what happens if apply-generic is called with two arguments of type scheme-number or two arguments of type complex for an operation that is not found in the table for those types? For example, assume that we’ve defined a generic exponentiation operation:
(define (exp x y) (apply-generic 'exp x y))and have put a procedure for exponentiation in the Scheme-number package but not in any other package:
;; following added to Scheme-number package
(put 'exp '(scheme-number 'scheme-number)
(lambda (x y) (tag (expt x y))))
; using primitive exptWhat happens if we call exp with two complex numbers as arguments?
b. Is Louis correct that something had to be done about coercion with arguments of the same type, or does apply-generic work correctly as is?
c. Modify apply-generic so that it doesn’t try coercion if the two arguments have the same type.
a. In the specific example, apply-generic will attempt to cast the complex numbers to complex numbers, and then throw the error "no method for these types". If the same-type coercicon is added, it will cause an infinite loop.
b. Adding logic to coerce the numbers to the same type won't solve the above problem, currently it correctly throws an error if called when a procedure for the types doesn't exist.
c. A modified version of apply generic:
(define (apply-generic op . args)
(let ((type-tags (map type-tag args)))
(let ((proc (get op type-tags)))
(if proc
(apply proc (map contents args))
(if (= (length args) 2)
(let ((type1 (car type-tags))
(type2 (cadr type-tags))
(a1 (car args))
(a2 (cadr args)))
(if (= type1 type2)
(let ((t1->t2 (get-coercion type1 type2))
(t2->t1 (get-coercion type2 type1)))
(cond (t1->t2
(apply-generic op (t1->t2 a1) a2))
(t2->t1
(apply-generic op a1 (t2-> t1 a2)))
(else (error "No method for these types"
(list op type-tags)))))
(error "No method for these types"
(list op type-tags))))
(error "No method for these types"
(list op type-tags)))))))Show how to generalize apply-generic to handle coercion in the general case of multiple arguments. One strategy is to attempt to coerce all the arguments to the type of the first argument, then to the type of the second argument, and so on. Give an example of a situation where this strategy (and likewise the two-argument version given above) is not sufficiently general. (Hint: Consider the case where there are some suitable mixed-type operations present in the table that will not be tried.)
Suppose you are designing a generic arithmetic system for dealing with the tower of types shown in Figure 2.25: integer, rational, real, complex. For each type (except complex), design a procedure that raises objects of that type one level in the tower. Show how to install a generic raise operation that will work for each type (except complex).