2.5 Systems with Generic Operations⁠

• In § 2.4 we saw how to create operations that work on multiple data representations.
• We can extend this further to create operations that are generic over different kinds of arguments, not just different representations of the same kind of data.
• We will develop a general arithmetic system using data-directed programming that works on several kinds of numbers.

# 2.5.1 Generic Arithmetic Operations⁠

• We want add to work for primitive, rational, and complex numbers.
• We will attach a type tag to each kind of number. Complex numbers will have two levels of tagging: a 'complex tag on top of the 'rectangular or 'polar tag.
• The tags get stripped off as the data is passed down through packages to the appropriate specific procedure.

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

• Here is the arithmetic package for Scheme numbers:

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

(define (make-scheme-number n)
  ((get 'make 'scheme-number) n))

• We can implement similar packages for rational and complex numbers.

# 2.5.2 Combining Data of Different Types⁠

• In our unified arithmetic system, we ignored an important issue: we did not consider operations that cross type boundaries, like adding a Scheme number to a rational.
• One solution would be to design a procedure for every possible combination of types. But this is cumbersome, and it violates modularity.

# Coercion

• Often the different data types are not completely independent.
• For example, any real number can be expressed as a complex number with an imaginary part of zero.
• We can make all operations work on combinations of Scheme numbers and complex numbers by first coercing the former to the latter.
• Here is a typical coercion procedure:

(define (scheme-number->complex n)
  (make-complex-from-real-imag (contents n) 0))

• The big advantage of coercion is that, although we may need to write many coercion procedures, we only need to implement each operation once per type.
• We could modify apply-generic to try coercion if there is no specific procedure available for the given types.
• But it gets complicated. What if both types can be converted to a third type? What if multiple coercions are required? We end up with a graph of relations among types.

# Hierarchies of types

• We can simplify the problem by using a type hierarchy instead of an arbitrary graph.
• In the hiearchy, each type is related to supertypes above it and subtypes below it.
• A tower is a hiearchy where each type has at most one supertype and subtype.
• Our numeric tower comprises integers, rationals, real numbers, and complex numbers.
• Coercion then simply becomes a matter of raising the argument whose type is lower in the tower to the level of the other type.
• We can write fewer procedures by allowing types to inherit their supertype’s operations.
• In some cases we can simplify results by lowering a value down the type tower.

# Inadequacies of hierarchies

• In general, a type may have more than one subtype. This is easy to deal with.
• Allowing multiple super types (known as multiple inheritance) is tricky, since the type can be raised via multiple paths to search for a procedure.
• Having large numbers of interrelated types conflicts with modularity.

# 2.5.3 Example: Symbolic Algebra⁠

• Manipulating symbolic algebraic expressions is hard.
• We can view them as trees of operators applied to operands.
• To keep things simple, we’ll stick to polynomials.

# Arithmetic on polynomials

• Polynomials are expressed in terms of variables called indeterminates.
• A univariate polynomial has the form $c_0 + c_1x + c_2x^2 + \cdots + c_nx^n\htmlClass{math-punctuation}{\text{.}}$
• To avoid thorny issues of identity and sameness, we will consider our polynomials to be syntactic forms, not representations of mathematical functions.
• We will implement addition and multiplication for polynomials in the same variable.

(define (add-poly p1 p2)
  (if (same-variable? (variable p1) (variable p2))
      (make-poly (variable p1)
                 (add-terms (term-list p1)
                            (term-list p2)))
      (error "polys not in same var" p1 p2)))

(define (mul-poly p1 p2)
  (if (same-variable? (variable p1) (variable p2))
      (make-poly (variable p1)
                 (mul-terms (term-list p1)
                            (term-list p2)))
      (error "polys not in same var" p1 p2)))

• We will install these procedures in our generic arithmetic system:

(define (install-polynomial-package)
  ;; Internal procedures
  (define (make-poly variable term-list)
    (cons variable term-list))
  (define (variable p) (car p))
  (define (term-list p) (cdr p))
  (define (add-poly p1 p2) ...)
  (define (mul-poly p1 p2) ...)

  ;; Interface to rest of the system
  (define (tag p) (attach-tag 'polynomial p))
  (put 'add '(polynomial polynomial)
       (lambda (p1 p2) (tag (add-poly p1 p2))))
  (put 'mul '(polynomial polynomial)
       (lambda (p1 p2) (tag (mul-poly p1 p2))))
  (put 'make 'polynomial
       (lambda (var terms) (tag (make-poly var terms))))
  'done)

• Here is the implementation of add-terms:

(define (add-terms L1 L2)
  (cond ((empty-termlist? L1) L2)
        ((empty-termlist? L2) L1)
        (else
         (let ((t1 (first-term L1)) (t2 (first-term L2)))
           (cond ((> (order t1) (order t2))
                  (adjoin-term
                   t1 (add-terms (rest-terms L1) L2)))
                 ((< (order t1) (order t2))
                  (adjoin-term
                   t2 (add-terms L1 (rest-terms L2))))
                 (else
                  (adjoin-term
                   (make-term (order t1)
                              (add (coeff t1) (coeff t2)))
                   (add-terms (rest-terms L1)
                              (rest-terms L2)))))))))

• Since it uses the generic add internally, the system automatically works with polynomials whose coefficients are themselves polynomials in a different variable!

# Representing term lists

• Our procedures add-terms and mul-terms always access terms sequentially from highest to lowest order, so we need some kind of ordered representation.
• For dense polynomials (mostly nonzero coefficients), a simple list is best.
  • Example: $x^5+2x^4+3x^2-2x-5$ becomes '(1 2 3 -2 -5).
• For sparse polynomials (mostly zero coefficients), an associative list is best.
  • Example: $x^{100}+2x^2+1$ becomes '((100 1) (2 2) (0 1)).
• Here is an associative list representation:

(define (adjoin-term term term-list)
  (if (=zero? (coeff term))
      term-list
      (cons term term-list)))
(define (the-empty-termlist) '())
(define (first-term term-list) (car term-list))
(define (rest-terms term-list) (cdr term-list))
(define (empty-termlist? term-list) (null? term-list))
(define (make-term order coeff) (list order coeff))
(define (order term) (car term))
(define (coeff term) (cadr term))

# Hierarchies of types in symbolic algebra

• The data types in our polynomial algebra cannot easily be arranged in a tower.
• For example, how would we coerce $(x+1)y^2$ and $(y+1)x^2$ to a common type?

It should not be surprising that controlling coercion is a serious problem in the design of large-scale algebraic-manipulation systems. Much of the complexity of such systems is concerned with relationships among diverse types. Indeed, it is fair to say that we do not yet completely understand coercion. In fact, we do not yet completely understand the concept of a data type. Nevertheless, what we know provides us with powerful structuring and modularity principles to support the design of large systems. (Section 2.5.3)

# Extended exercise: Rational functions

• Rational functions are “fractions” with polynomial numerators and denominators.
• We can use our rational package from § 2.5.1, but we need to change a few things.
• To reduce rational functions, we need to be able to compute the GCD of polynomials, which in turn requires computing the remainder after polynomial division.
• To avoid fractional coefficients, we can multiply the result by an integerizing factor.
• Here is our algorithm for reducing a rational function to lowest terms:
  1. Compute the integerized GCD of the numerator and denominator.
  2. Multiply the numerator and denominator by an integerizing factor: the leading coefficient of the GCD raised to the power $1 + \max\{O_\text{N}, O_\text{D}\} - O_\text{G}\htmlClass{math-punctuation}{\text{,}}$ where those constants refer to the order of the numerator, denominator, and GCD, respectively.
  3. Divide the results of (2) by the GCD from (1).
  4. Divide the results of (3) by the GCD of all their coefficients.
• The GCD algorithm is at the heart of every system that does operations on rational functions. Ours is very slow. Probabilistic algorithms like Zippel’s are faster.