SICP Exercise 2.77: Tracing magnitude

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?

A couple of things first:

1. It's not explicitly stated in the book (at least in my reading of it), but you not only need to install the rectangular and polar packages for the generic arithmetic operations system - you need to include the generic complex-number selectors real-part, imag-part, magnitude and angle defined in section 2.4.3.
2. In exercise 2.73 I listed the code from section 3.3.3 that provides the put and get procedures we need for implementing data-directed systems in the style presented. I also noted that, under DrRacket, I'd had to include a couple of packages to get this to work. One of them, rnrs/base-6, includes its own complex-number support, which clashes with the generic complex-number selectors we need to include. I got around this by simply prefixing these selectors with complex-.

Anyway.

The important parts of install-rectangular-package and install-polar-package are as follows:

(define (install-rectangular-package)
  ;; internal procedures
  …
  (define (magnitude z)
    (sqrt (+ (square (real-part z))
             (square (imag-part z)))))
  …
  ;; interface to the rest of the system
  …
  (put 'magnitude '(rectangular) magnitude)
  …
  'done)

(define (install-polar-package)
  ;; internal procedures
  (define (magnitude z) (car z))
  …
  ;; interface to the rest of the system
  …
  (put 'magnitude '(polar) magnitude)
  …
  'done)

You'll note from the highlighted portion that both packages install procedures under the operation key 'magnitude, but for the type lists '(rectangular) and '(polar).

Let's also refresh our minds on how the generic magnitude operation is implemented:

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

Simple, really.

Prior to following Alyssa's suggestion there is no procedure installed under the operation key 'magnitude for the type list '(complex). So when Louis tries to evaluate (magnitude z) the call to apply-generic fails to get a 'magnitude operation for the complex number and so it raises an error.

When Louis extends the complex package as Alyssa suggests this is no longer the case. Now apply-generic does get a 'magnitude operation for the complex number. It's the one we've just installed for the complex package. And this is the generic magnitude operation itself!

So how does this work then?

Well, remember that when apply-generic invokes the procedure it has retrieved using get, it strips the outer-most type tag of the data before passing it to the procedure. When we evaluate (magnitude z) it gets the procedure magnitude from the table and then effectively evaluates (magnitude (contents z)). Now z has an outer tag of 'complex with an inner tag of 'rectangular on the pair (3 4), so the second (recursive) invocation of magnitude is now dealing with a different type, 'rectangular. This time around it gets the inner procedure, magnitude, defined in the rectangular package that handles the rectangular representation appropriately.

So there are two invocations of apply-generic. The first invocation dispatches to the generic magnitude operation, while the second dispatches to the inner procedure magnitude defined in the rectangular package.

Let's trace this through. First let's define z:

(define z (make-complex-from-real-imag 3 4))

And now let's evaluate (magnitude z)... For brevity's sake I've not expanded out map or get, and to make it clear which magnitude procedure is which, I've referred to the inner procedure magnitude from the rectangular package as rectangular->magnitude below.

  (magnitude z)
= (apply-generic 'magnitude z)
= (let ((type-tags (map type-tag (z))))
    (let ((proc (get 'magnitude type-tags)))
      (if proc
          (apply proc (map contents (z)))
          (error
            "No method for these types -- APPLY-GENERIC"
            (list 'magnitude type-tags))))))
= (let ((type-tags '(complex)))
    (let ((proc (get 'magnitude type-tags)))
      (if proc
          (apply proc (map contents (z)))
          (error
            "No method for these types -- APPLY-GENERIC"
            (list 'magnitude type-tags))))))
= (let ((proc (get 'magnitude '(complex))))
    (if proc
        (apply proc (map contents (z)))
        (error
          "No method for these types -- APPLY-GENERIC"
          (list 'magnitude '(complex)))))))
= (let ((proc magnitude))
    (if proc
        (apply proc (map contents (z)))
        (error
          "No method for these types -- APPLY-GENERIC"
          (list 'magnitude '(complex)))))))
= (if magnitude
      (apply magnitude (map contents (z)))
      (error
        "No method for these types -- APPLY-GENERIC"
        (list 'magnitude '(complex)))))))
= (apply magnitude (map contents (z)))
= (apply magnitude (('rectangular (3 4))))
≡ (magnitude ('rectangular (3 4)))
= (apply-generic 'magnitude ('rectangular (3 4)))
= (let ((type-tags (map type-tag (('rectangular (3 4))))))
    (let ((proc (get 'magnitude type-tags)))
      (if proc
          (apply proc (map contents (('rectangular (3 4)))))
          (error
            "No method for these types -- APPLY-GENERIC"
            (list 'magnitude type-tags))))))
= (let ((type-tags '(rectangular)))
    (let ((proc (get 'magnitude type-tags)))
      (if proc
          (apply proc (map contents (('rectangular (3 4)))))
          (error
            "No method for these types -- APPLY-GENERIC"
            (list 'magnitude type-tags))))))
= (let ((proc (get 'magnitude '(rectangular))))
    (if proc
        (apply proc (map contents (('rectangular (3 4)))))
        (error
          "No method for these types -- APPLY-GENERIC"
          (list 'magnitude '(rectangular)))))))
= (let ((proc rectangular->magnitude))
    (if proc
        (apply proc (map contents (('rectangular (3 4)))))
        (error
          "No method for these types -- APPLY-GENERIC"
          (list 'magnitude '(rectangular)))))))
= (if rectangular->magnitude
      (apply rectangular->magnitude (map contents (('rectangular (3 4)))))
      (error
        "No method for these types -- APPLY-GENERIC"
        (list 'magnitude '(rectangular)))))))
= (apply rectangular->magnitude (map contents (('rectangular (3 4)))))
= (apply rectangular->magnitude ((3 4)))
≡ (rectangular->magnitude (3 4))
= (sqrt (+ (square (real-part (3 4)))
           (square (imag-part (3 4))))))
= (sqrt (+ (square (car (3 4))) (square (cdr (3 4))))))
= (sqrt (+ (square 3) (square 4)))
= (sqrt (+ (* 3 3) (* 4 4)))
= (sqrt (+ 9 16))
= (sqrt 25)
= 5