2.5.1 Generic Arithmetic Operations - SICP Comparison Edition

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 function add that acts like ordinary primitive addition + on ordinary numbers, like add-rat add_rat on rational numbers, and like add-complex add_complex on complex numbers. We can implement add, and the other generic arithmetic operations, by following the same strategy we used in section 2.4.3 to implement the generic selectors for complex numbers. We will attach a type tag to each kind of number and cause the generic procedure function to dispatch to an appropriate package according to the data type of its arguments.

The generic arithmetic procedures functions are defined as follows:

Original	Python
`(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))`	`def add(x, y): return apply_generic("add", llist(x, y)) def sub(x, y): return apply_generic("sub", llist(x, y)) def mul(x, y): return apply_generic("mul", llist(x, y)) def div(x, y): return apply_generic("div", llist(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. string "python_number". The arithmetic operations in this package are the primitive arithmetic procedures functions (so there is no need to define extra procedures functions to handle the untagged numbers). Since these operations each take two arguments, they are installed in the table keyed by the listlinked list (scheme-number scheme-number): llist("python_number", "python_number"):

Original

Python

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

def install_python_number_package(): def tag(x): return attach_tag("python_number", x) put("add", llist("python_number", "python_number"), lambda x, y: tag(x + y)) put("sub", llist("python_number", "python_number"), lambda x, y: tag(x - y)) put("mul", llist("python_number", "python_number"), lambda x, y: tag(x * y)) put("div", llist("python_number", "python_number"), lambda x, y: tag(x / y)) put("make", "python_number", lambda x: tag(x)) return "done"

Users of the Scheme-number package Python-number package will create (tagged) ordinary numbers by means of the procedure: function:

Original	Python
`(define (make-scheme-number n) ((get 'make 'scheme-number) n))`	`def make_python_number(n): return get("make", "python_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 2.1.1 as the internal procedures functions in the package:

Original

Python

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

def install_rational_package(): # internal functions def numer(x): return head(x) def denom(x): return tail(x) def make_rat(n, d): g = gcd(n, d) return pair(n // g, d // g) def add_rat(x, y): return make_rat(numer(x) * denom(y) + numer(y) * denom(x), denom(x) * denom(y)) def sub_rat(x, y): return make_rat(numer(x) * denom(y) - numer(y) * denom(x), denom(x) * denom(y)) def mul_rat(x, y): return make_rat(numer(x) * numer(y), denom(x) * denom(y)) def div_rat(x, y): return make_rat(numer(x) * denom(y), denom(x) * numer(y)) # interface to rest of the system def tag(x): return attach_tag("rational", x) put("add", llist("rational", "rational"), lambda x, y: tag(add_rat(x, y))) put("sub", llist("rational", "rational"), lambda x, y: tag(sub_rat(x, y))) put("mul", llist("rational", "rational"), lambda x, y: tag(mul_rat(x, y))) put("div", llist("rational", "rational"), lambda x, y: tag(div_rat(x, y))) put("make", "rational", lambda n, d: tag(make_rat(n, d))) return "done" def make_rational(n, d): return get("make", "rational")(n, d)

We can install a similar package to handle complex numbers, using the tag complex. "complex". In creating the package, we extract from the table the operations make-from-real-imag make_from_real_imag and make-from-mag-ang 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, add_complex, sub-complex, sub_complex, mul-complex, mul_complex, and div-complex div_complex procedures functions from section 2.4.1.

Original

Python

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

def install_complex_package(): # imported functions from rectangular and polar packages def make_from_real_imag(x, y): return get("make_from_real_imag", "rectangular")(x, y) def make_from_mag_ang(r, a): return get("make_from_mag_ang", "polar")(r, a) # internal functions def add_complex(z1, z2): return make_from_real_imag(real_part(z1) + real_part(z2), imag_part(z1) + imag_part(z2)) def sub_complex(z1, z2): return make_from_real_imag(real_part(z1) - real_part(z2), imag_part(z1) - imag_part(z2)) def mul_complex(z1, z2): return make_from_mag_ang(magnitude(z1) * magnitude(z2), angle(z1) + angle(z2)) def div_complex(z1, z2): return make_from_mag_ang(magnitude(z1) / magnitude(z2), angle(z1) - angle(z2)) # interface to rest of the system def tag(z): return attach_tag("complex", z) put("add", llist("complex", "complex"), lambda z1, z2: tag(add_complex(z1, z2))) put("sub", llist("complex", "complex"), lambda z1, z2: tag(sub_complex(z1, z2))) put("mul", llist("complex", "complex"), lambda z1, z2: tag(mul_complex(z1, z2))) put("div", llist("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))) return "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, functions, originally defined in the rectangular and polar packages, are exported to the complex package, and exported from there to the outside world.

Original	Python
`(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))`	`def make_complex_from_real_imag(x, y): return get("make_from_real_imag", "complex")(x, y) def make_complex_from_mag_ang(r, a): return 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+4i$ in rectangular form, would be represented as shown in figure 2.37. figure 2.38. The outer tag (complex) ("complex") is used to direct the number to the complex package. Once within the complex package, the next tag (rectangular) ("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.

Original		Python
Figure 2.37 Representation of $3+4i$ in rectangular form.		Figure 2.38 Representation of $3+4i$ in rectangular form.

In the above packages, we used add-rat, add_rat, add-complex, add_complex, and the other arithmetic procedures functions exactly as originally written. Once these declarations are internal to different installation procedures, functions, 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 2.77 Louis Reasoner tries to evaluate the expression (magnitude z) magnitude(z) where z is the object shown in figure 2.37. figure 2.38. To his surprise, instead of the answer $5$ he gets an error message from apply-generic, apply_generic, saying there is no method for the operation magnitude on the types (complex). llist("complex"). He shows this interaction to Alyssa P. Hacker, who says The problem is that the complex-number selectors were never defined for complex "complex" numbers, just for polar "polar" and rectangular "rectangular" numbers. All you have to do to make this work is add the following to the complex package:

Original	Python
`(put 'real-part '(complex) real-part) (put 'imag-part '(complex) imag-part) (put 'magnitude '(complex) magnitude) (put 'angle '(complex) angle)`	`put("real_part", llist("complex"), real_part) put("imag_part", llist("complex"), imag_part) put("magnitude", llist("complex"), magnitude) print(put("angle", llist("complex"), angle))`

Describe in detail why this works. As an example, trace through all the procedures functions called in evaluating the expression (magnitude z) magnitude(z) where z is the object shown in figure 2.37. figure 2.38. In particular, how many times is apply-generic apply_generic invoked? What procedure function is dispatched to in each case?

Putting the above lines to the package will open up z, and those lines act as a pass-through. apply-generic apply_generic will be invoked twice. We shall trace with substitution model how the program evaluates.

Original

Python

;;*** Use substitution rule: (magnitude z) ;;** First apply-generic: (apply-generic 'magnitude z) ;; where z is the whole object including symbol 'complex. ;;recall (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)) (error "No method for these types -- APPLY-GENERIC" (list op type-tags)))))) ;; substitution (let ((type-tags '(complex)) ... )) (let ((proc (get op '(complex))) ... )) (let ((proc magnitude) ... )) (if proc... ;; true (apply magnitude (contents z)) (magnitude z-prime) ;; where z-prime is the contents (the cdr) of the original ;; object, that is, with the 'complex stripped off. ;;** Second apply-generic: (let ((type-tags '(rectangular)) ... )) (let ((proc (get op '(rectangular))) ... )) (let ((proc (get 'magnitude '(rectangular))) ... )) (let ((proc (lambda (z) (sqrt (+ (square (real-part z)) (square (imag-part z)))))) ... ))) (if proc... ;; true (apply (lambda (z) (sqrt (+ (square (real-part z)) (square (imag-part z))))) (contents z-prime)) (sqrt (+ (square 3) (square 4))) 5

magnitude(z) apply_generic("magnitude", llist(z)) # In this case: # type_tags = map(type_tag, llist(z)) # Which evaluates to: # type_tags = llist("complex") # and # fun = get("magnitude", llist("complex")) # which, due to the addition of # put("magnitude", llist("complex"), magnitude) # fun = magnitude apply(magnitude, map(contents, llist(z))) apply(magnitude, pair("rectangular", pair(3, 4))) magnitude(pair("rectangular"), pair(3, 4)) apply_generic("magnitude", llist(pair("rectangular"), pair(3, 4))) # type_tags = map(type_tag, llist(z)) evaluates to llist("rectangular") # fun = get("magnitude", llist("rectangular")) which evaluates to # lambda z: math_sqrt(square(real_part(z)) + square(imag_part(z))) # lambda z: math_sqrt(square(head(z)) + square(tail(z))) apply(fun, map(contents, llist(pair("rectangular"), pair(3, 4)))) apply(fun, pair(3, 4)) (lambda z: math_sqrt(square(head(z)) + square(tail(z))))(pair(3, 4)) math_sqrt(square(head(pair(3, 4))) + square(tail(pair(3, 4)))) ... math_sqrt(square(3) + square(4)) ... math_sqrt(9 + 16) math_sqrt(25) 5

Exercise 2.78 The internal procedures functions in the scheme-number python_number package are essentially nothing more than calls to the primitive procedures functions +, -, 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 Python implementations do have a type system, which they use internally. Primitive predicates such as symbol? is_string and number? is_number determine whether data objects have particular types. Modify the definitions of type-tag, type_tag, contents, and attach-tag attach_tag from section 2.4.2 so that our generic system takes advantage of Scheme's Python's internal type system. That is to say, the system should work as before except that ordinary numbers should be represented simply as Scheme Python numbers rather than as pairs whose car head is the symbol scheme-number. string "python_number".

The following modifications will take advantage of the Python number implementation:

Original

Python

(define (attach-tag type-tag contents) (if (number? contents) contents (cons type-tag contents))) (define (type-tag datum) (cond ((number? datum) 'scheme-number) ((pair? datum) (car datum)) (else (error "Wrong datum -- TYPE-TAG" datum)))) (define (contents datum) (cond ((number? datum) datum) ((pair? datum) (cdr datum)) (else (error "Wrong datum -- CONTENTS" datum))))

def attach_tag(type_tag, contents): return (pair("python_number", contents) if is_number(contents) else pair(type_tag, contents)) def type_tag(datum): return ("python_number" if is_number(datum) else head(datum) if is_pair(datum) else error("bad tagged datum -- type_tag", datum)) def contents(datum): return (datum if is_number(datum) else tail(datum) if is_pair(datum) else error("bad tagged datum -- contents", datum))

Exercise 2.79 Define a generic equality predicate equ? is_equal 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.

# provided by GitHub user clean99 def is_equal(x, y): return apply_generic("is_equal", llist(x, y)) def install_python_number_package(): # ... put("is_equal", llist("python_number", "python_number"), lambda x, y: x == y) # ... def install_rational_package(): # ... def is_equal(x, y): return numer(x) * denom(y) == numer(y) * denom(x) put("is_equal", llist("rational", "rational"), is_equal) # ... def install_complex_package(): # ... def is_equal(z1, z2): return (imag_part(z1) == imag_part(z2) if real_part(z1) == real_part(z2) else False) put("is_equal", llist("complex", "complex"), is_equal) #...

Exercise 2.80 Define a generic predicate =zero? is_equal_to_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.

# provided by GitHub user clean99 def is_equal_to_zero(x): return apply_generic("is_equal_to_zero", llist(x)) def install_python_number_package(): # ... put("is_equal_to_zero", "python_number", lambda x: x == 0) # ... def install_rational_package(): # ... def is_equal_to_zero(x): return numer(x) == 0 put("is_equal_to_zero", "rational", is_equal_to_zero) # ... def install_complex_package(): # ... def is_equal_to_zero(z): return (imag_part(z) == 0 if real_part(z) == 0 else False) put("is_equal_to_zero", "complex", is_equal_to_zero) #...