Generic Arithmetic Operations

The task of designing generic arithmetic operations is analogous to
that of designing the generic complex-number operations. We would
like, for instance, to have a generic addition procedure `add` that
acts like ordinary primitive addition `+` on ordinary numbers,
like `add-rat` on rational numbers, and like `add-complex` on
complex numbers. We can implement `add`, and the other generic
arithmetic operations, by following the same strategy we used in
section to implement the generic selectors for
complex numbers. We will attach a type tag to each kind of
number and cause the generic procedure to dispatch to an appropriate
package according to the data type of its arguments.

The generic arithmetic procedures are defined as follows:

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

We begin by installing a package for handling *ordinary* numbers,
that is, the primitive numbers of our language. We will tag these
with the symbol `scheme-number`. The arithmetic operations in this
package are the primitive arithmetic procedures (so there is no need to
define extra procedures to handle the untagged numbers). Since
these operations each 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 Scheme-number package will create (tagged) ordinary numbers by means of the procedure:

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

Now that the framework of the generic arithmetic system is in place, we can readily include new kinds of numbers. Here is a package that performs rational arithmetic. Notice that, as a benefit of additivity, we can use without modification the rational-number code from section as the internal procedures in the package:

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

We can install a similar package to handle complex numbers, using the
tag `complex`. In creating the package, we extract from the table
the operations `make-from-real-imag` and `make-from-mag-ang`
that were defined by the rectangular and polar packages.
Additivity
permits us to use, as the internal operations, the same `
add-complex`, `sub-complex`, `mul-complex`, and `
div-complex` procedures from
section .

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

Programs outside the complex-number package can construct complex numbers either from real and imaginary parts or from magnitudes and angles. Notice how the underlying procedures, originally defined in the rectangular and polar packages, are exported to the complex package, and exported from there to the outside world.

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

What we have here is a two-level tag system. A typical complex number,
such as 3+4*i* in rectangular form, would be
represented as shown in figure .
The outer tag (`complex`) is used to direct the number to the
complex package. Once within the complex package, the next tag (`
rectangular`) is used to direct the number to the rectangular package.
In a large and complicated system there might be many levels, each
interfaced with the next by means of generic operations. As a data
object is passed ``downward,'' the outer tag that is used to direct
it to the appropriate package is stripped off (by applying `
contents`) and the next level of tag (if any) becomes visible to be used for
further dispatching.

In the above packages, we used `add-rat`, `add-complex`, and
the other arithmetic procedures exactly as originally written.
Once these definitions are internal to different installation procedures,
however, they no longer need names that are distinct from each other:
we could simply name them `add`, `sub`, `mul`, and `div`
in both packages.

**Exercise.**
Louis Reasoner tries to evaluate the
expression `(magnitude z)` where `z` is the object
shown in figure . 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

**Exercise.**
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 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`.

**Exercise.**
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.

**Exercise.**
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.