SICP 2.5 Systems with Generic Operations
2023-11-15 Wed

Exercise:

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?

Answer:

Here is z:

-->[o|o]-->[o|o]-------->[o|o]
    |       |             | |
    v       v             v v
'complex  'rectangular    3 4

Louis evaluates (magnitude z).

Louis is using the procedure defined as follows:

(define (magnitude z)
  (apply-generic 'magnitude z))

This means that when calling magnitude, the first thing we do is looking in the table for the item specified by the row 'magnitude and column 'complex (the type of z).

However, nobody has stored such a table item. (At the moment there is an element specified by row 'magnitude and column 'rectangular, and an element specified by row 'magnitude and column 'polar.) So, Louis' invocation produces an error.

Alyssa's code adds to the table four objects. Those objects are the generic procedures defined on page 84, which are themselves designed to look for and use an object in the table.

So, now, when Louis calls (magnitude z), we look for a table item which exists. It's the item which has been installed by Alyssa with this line:

(put 'magnitude '(complex) magnitude)

Given that we find an item in the table, apply-generic applies it to the contents of z. These are the contents of z:

    [o|o]------>[o|o]
     |           | |
     v           v v
'rectangular     3 4

Applying magnitude to these contents means, again, looking for an item in the table. This time we are looking for the item specified the row 'magnitude and the column 'rectangular. That item is found and applied to the contents.

Table before Alyssa's change:

Table after Alyssa's change:

When evaluating (magnitude z), after Alyssa's contribution, apply-generic is called twice. The first time it dispatches to magnitude to itself (in a sense, magnitude, through apply-generic, is dispatching to itself). The second time it dispatches to magnitude-rectangular.

(magnitude z) ;; z:  -->[o|o]-->[o|o]-------->[o|o]
              ;;         |       |             | |
              ;;         v       v             v v
              ;;     'complex  'rectangular    3 4
;;    |
;;    |
;;    V
;;  apply-generic
;;    |
;;    |
;;    V
(magnitude z') ;; z': -->[o|o]-------->[o|o]
               ;;         |             | |
               ;;         v             v v
               ;;       'rectangular    3 4
;;    |
;;    |
;;    V
;;  apply-generic
;;    |
;;    |
;;    V
(magnitude z'') ;; z'': -->[o|o]
                ;;          | |
                ;;          v v
                ;;          3 4

Basically, Alyssa's line, has the effect of making magnitude stripping off 'complex before dispatching to someone else.

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

Answer:

(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 (number? contents)
      contents
      (cons type-tag contents)))
;; alternatively
(define (attach-tag type-tag contents)
  (if (eq? type-tag 'scheme-number)
      contents
      (cons type-tag contents)))

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.

Answer:

I guess, first of all:

(define (equ? x y) apply-generic 'equ? x y)

After this, we should put the specific procedures for the types of numbers we have:

(put 'equ? '(scheme-number scheme-number)
     (lambda (x y) (= x y)))

(put 'equ? '(rational rational)
     (lambda (x y) (and (= (car x) (car y))
                        (= (cdr x) (cdr y)))))

(if equ? for rational numbers was defined within the install-rational-package procedure we could make use of number and denom)

(put 'equ? '(complex complex)
     (lambda (x y) (and (= (real-part x) (real-part y))
                        (= (imag-part x) (imag-part y)))))

(Real-part and imag-part, if I'm not wrong, here work correctly thanks to the code added by Alyssa P. Hacker in ex. 2.77.)

(Alternatively, we could have used magnitude and angle, instead of real-part and imag-part.)

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.

Answer:

(define (=zero? x)
  (apply-generic =zero? x))

(put '=zero '(scheme-number scheme-number)
     (lambda (x) (= x 0)))

(put '=zero '(rational rational)
     (lambda (x)
       (and (= (car x) 0)
            (not (= (cdr x) 0)))))
;; the numerator must be zero and the denominator must be non-zero

(put '=zero '(complex)
     (lambda (x)
       (and (= (real-part x) 0)
            (= (imag-part x) 0))))

Alternatively:

(put '=zero '(complex)
     (lambda (x)
       (= (angle x) 0)))

Exercise:

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, in addition to the scheme-number->complex coercion shown above, he would do:

(define (scheme-number->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 `expt'

What 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.

Answer:

Exercise:

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

Answer:

Authors are telling us what to try: ``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.''

So we need to ``loop'' over the arguments and, for each one of them, we get its type and then try to coerce all the others to that type. This sort of ``double loop'' operation probably lends itself to be handled in some elegant way using higher-order procedures.

In the following approach, if the first retrieval of proc fails, I'm going to loop over each argument using what I would call ``procedural iteration'' (Cf. pp. 32-33). I create the list of the functions needed from the coercion table, and create, if possible (if I've found all relevant procedures), the list of all coerced arguments. We then try to retrieve the relevant proc again. I we succeed we can call apply, otherwise we keep iterating.

(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))
          (apply-generic-coerce 0 op . args)))))

(define (apply-generic-coerce i op . args)
  (if (>= i (length args))
      (error "failed to find op")
      ;; find type of args with index i
      (let ((type (type-tag (list-ref args i))))
        ;; build a list of all the functions that are needed from the coercion table
        ;; (when the type is the same we can just use the identity function.
        (let ((coercing-funs (map (lambda (arg)
                                    (if (eq? (type-tag arg) type)
                                        identity
                                        (get-coercion (type-tag arg) type)))
                                  args)))
          (if (> (length (filter is-falsy coercing-funs) 0)
                 ;; try with next type
                 (apply-generic-coerce (+ 1 i) op . args)
                 (let ((coerced-args (map (lambda (arg)
                                            ((get-coercion (type-tag arg) type) arg)))))
                   (let ((proc (get op (map type-tags coerced-args))))
                     (if proc
                         ;; found proc!
                         (apply proc (map contents coerced-args))
                         ;; try with next type
                         (apply-generic-coerce (+ 1 i) op . args))))))))))

I suspect that the situations in which the procedure is not going to work are those situations in which, in order to find an operation in our table, we would have to coerce each argument to some type which differs from any of the types of the arguments. For example, if we have in the table an operation foo which works on triangles and we try to apply it to an isosceles triangle and a right triangle, trying to coerce the isosceles triangle to a right triangle or vice versa will not work. We will have instead to coerce both the isosceles and the right triangles to a triangle.