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

SICP Exercise 2.76: Compare and Contrast Data Representation Strategies

As a large system with generic operations evolves, new types of data objects or new operations may be needed. For each of the three strategies -- generic operations with explicit dispatch, data-directed style, and message-passing-style -- describe the changes that must be made to a system in order to add new types or new operations. Which organization would be most appropriate for a system in which new types must often be added? Which would be most appropriate for a system in which new operations must often be added?

Let's examine each of the strategies in turn and outline the changes required for adding types and operations before discussing the appropriateness of different strategies for different systems.

Generic Operations with Explicit Dispatch

When using generic operations with explicit dispatch each generic operation must be able to identify the type of passed data and invoke an appropriate type-specific procedure to perform the operation. As a result each generic operation contains type-specific code and so the changes required for additions to the system are as follows:

• Adding a New Type: Once the representation for the type has been decided upon, procedures must be implemented that perform each of the existing generic operations for that type, along with appropriate constructors for the type, and then each generic operation must be updated so that it tests for the new type and invokes the appropriate procedure when the new type is identified.
• Adding a New Operation: First a procedure must be implemented for each existing type that performs the new operation for that type. Once these are in place the generic operation itself can be implemented. This will follow the pattern of existing generic operations, testing for each of the existing types in turn and delegating to the appropriate type-specific procedure when the matching type is found.

Both cases expose this strategy's lack of modularization. The developer of a new type must have access to all of the generic procedures, while the developer adding the new operation must write code to test for each type and delegate to the appropriate type-specific procedure.

Data-Directed Style

Under the data-directed style each procedure that performs a particular operation for a specific type is stored in a table keyed under tags for the operation and type. The generic operations simply extract the type tag from the passed data, look up the appropriate procedure in the table and, if it's present, invoke it. Under this style we make changes to the system as follows:

• Adding a New Type: Once the representation for the type has been decided upon, procedures must be implemented that perform each of the existing generic operations for that type, along with appropriate constructors for the type, and then those procedures must be registered in the table under the appropriate tags.
• Adding a New Operation: First a procedure must be implemented for each existing type that performs the new operation for that type. Once these are in place the generic operation itself can be implemented. This simply invokes a utility procedure to perform the procedure look-up (such as the apply-generic procedure defined in section 2.4.3) and then delegates the execution of the operation to the returned procedure.

Note that in the first case there is no need to update the existing generic operations to support the type, while in the second case there is no need to add type-specific support into the new generic operation. However, this doesn't quite tell the full story...

In section 2.4.3 we are shown how to group together the set of procedures that implement all of the the operations for a specific type into a package that both defines the procedures and installs them in the table. In part (d) of exercise 2.73 we also explored inverting this packaging so that we group together the procedures that implement a specific operation for all of the types.

So depending upon how the system is factored we may find that, in order to make the changes for adding a type or operation and leave system tidy, we may need to either add a new package or modify all of the packages. For example, if in a particular system a package groups together all of the operations for a specific type then adding a new type will involve adding a new package, while adding a new operation will involve updating all of the packages, adding a procedure and its installation to each package.

Message-Passing Style

The message-passing style produces data objects that can receive and respond to messages indicating the type of operation to perform. We can still have generic operations under such a system - they simply invoke the apply-generic procedure defined in the Message Passing section appropriately. Under the message-passing system we make changes to the system as follows:

• Adding a New Type: This involves implementing a new constructor procedure for the type that returns a procedure that can dispatch messages appropriately. We've actually just done this in exercise 2.75.
• Adding a New Operation: First each type's dispatching procedure must be updated so that it can handle a message corresponding to the new operation appropriately. Once these are in place a generic operation can be implemented that simply invokes a utility procedure to perform the message passing (such as the apply-generic procedure defined in the Message Passing section).

Under this strategy the handling of messages (i.e. the operations) is performed by the dispatch procedure associated with each type. As a result the message handling is tightly bound to the data objects, meaning that new types are far more straightforward to add than operations.

Note that the author's indicated in a footnote that message-passing, as implemented in the book, restricts you to generic operations of one argument. This isn't strictly true. A generic operation could be implemented with multiple parameters that then gathered those parameters together into a single list, which could then be passed to the message.

What Strategy When?

We've seen that the approach of generic operations with explicit dispatch suffers from a lack of modularization, meaning that adding either a type or an operation requires large changes to the system.

We've also seen that, under the data-directed system, to add either a type or an operation we only have to register appropriate procedures in a table and then the generic operations can access the appropriate procedures without having to know about all types. However, we further noted that the cleanliness of additions for a particular system under this style may depend upon how said system is factored.

Finally, we saw how message-passing produces data objects that tightly bind the operations to the type, which can produce well-contained types, but does not necessarily make adding operations easy.

Based upon this I would suggest using the message-passing style for a system in which new types are frequently added, and the data-directed style (with appropriate factoring) for a system in which new operations are frequently added.

SICP Exercise 2.75: Message-Passing make-from-mag-ang

Implement the constructor make-from-mag-ang in message-passing style. This procedure should be analogous to the make-from-real-imag procedure given above.

Here's the make-from-real-imag procedure that's "given above":

(define (make-from-real-imag x y)
  (define (dispatch op)
    (cond ((eq? op 'real-part) x)
          ((eq? op 'imag-part) y)
          ((eq? op 'magnitude)
           (sqrt (+ (square x) (square y))))
          ((eq? op 'angle) (atan y x))
          (else
           (error "Unknown op -- MAKE-FROM-REAL-IMAG" op))))
  dispatch)

Now back in section 2.4.1, where the real/imaginary and magnitude/angle representations were introduced, the authors showed how, given a complex number represented as a magnitude, r, and an angle, A, we could calculate the real, x, and imaginary, y, parts as follows:

x = r cos A
y = r sin A

Given this, the message-passing style implementation of make-from-mag-ang is straightforward. It simply returns r in response to the 'magnitude operation, A in response to the 'angle operation, and performs the respective calculations for 'real-part and 'imag-part operations:

(define (make-from-mag-ang r a)
  (define (dispatch op)
    (cond ((eq? op 'real-part) (* r (cos a)))
          ((eq? op 'imag-part) (* r (sin a)))
          ((eq? op 'magnitude) r)
          ((eq? op 'angle) a)
          (else
           (error "Unknown op -- MAKE-FROM-MAG-ANG" op))))
  dispatch)

Let's give this a spin... First, to make things easy on us we'll define π (to 15 decimal places) and a procedure to convert degrees to radians:

(define pi 3.141592653589793)
(define (degrees->radians d) (/ (* d pi) 180))

First, we can test the selectors:

> (define a (make-from-mag-ang 2 (degrees->radians 45)))
> (define b (make-from-mag-ang 3 0))
> (define c (make-from-mag-ang 2 (degrees->radians 135)))
> (magnitude a)
2
> (angle a)
0.7853981633974483
> (real-part a)
1.4142135623730951
> (imag-part a)
1.414213562373095
> (real-part b)
3.0
> (imag-part b)
0.0
> (real-part c)
-1.414213562373095
> (imag-part c)
1.4142135623730951

Then we can try a few arithmetic operations:

> (define d (add-complex a a))
> (real-part d)
2.8284271247461903
> (imag-part d)
2.82842712474619
> (define e (add-complex a b))
> (real-part e)
4.414213562373095
> (imag-part e)
1.414213562373095
> (define f (sub-complex b a))
> (real-part f)
1.5857864376269049
> (imag-part f)
-1.414213562373095
> (define g (mul-complex a b))
> (real-part g)
4.242640687119286
> (imag-part g)
4.242640687119285