SICP 2.4 Multiple Representations for Abstract Data
2023-09-27 Wed

We want a complex number arithmetic system. Basically we want four operations that work with complex numbers: addition, subtraction, multiplication, and division.

Using a data-abstraction strategy — exactly what we did with rational number) —, we can just assume that we have the following selectors and constructors:

• Selectors:
  • real-part;
  • imag-part;
  • magnitude;
  • angle.
• Constructors:
  • make-from-real-imag;
  • make-from-mag-ang.

The selectors and constructors above are our abstract data. We can specify operations on complex numbers in terms of that abstract data:

• add-complex:

  (define (add-complex z1 z2)
    (make-from-real-imag (+ (real-part z1) (real-part z2))
                         (+ (imag-part z1) (imag-part z2))))
  

• sub-complex:

  (define (sub-complex z1 z2)
    (make-from-real-imag (- (real-part z1) (real-part z2))
                         (- (imag-part z1) (imag-part z2))))
  

• mul-complex:

  (define (mul-complex z1 z2)
    (make-from-mag-ang (* (magnitude z1) (magnitude z2))
                       (+ (angle z1) (angle z2))))
  

• div-complex:

  (define (div-complex z1 z2)
    (make-from-mag-ang (/ (magnitude z1) (magnitude z2))
                       (- (angle z1) (angle z2))))
  

Now that we have the complex number arithmetic operations, we need somebody to implement a complex number representation. Both Ben and Alyssa want to do it and, for some reason — pick your favorite reason —, we are forced to use both representations in our system.

Here is what Ben does:

;; Ben's representation
(define (real-part z) (car z))

(define (imag-part z) (cdr z))

(define (magnitude z)
  (sqrt (+ (square (real-part z)) (square (imag-part z)))))

(define (angle z)
  (atan (imag-part z) (real-part z)))

(define (make-from-real-imag x y) (cons x y))

(define (make-from-mag-ang r a)
  (cons (* r (cos a)) (* r (sin a))))

And here is what Alyssa does:

;; Alyssa's representation
(define (real-part z)
  (* (magnitude z) (cos (angle z))))

(define (imag-part z)
  (* (magnitude z) (sin (angle z))))

(define (magnitude z) (car z))

(define (angle z) (cdr z))

(define (make-from-real-imag x y)
  (cons (sqrt (+ (square x) (square y)))
        (atan y x)))

(define (make-from-mag-ang r a) (cons r a))

Ben has implemented what can be called a ``rectangular'' representation (in which a complex number is represented as a pair of a real-part and an imaginary part), whereas Alyssa has implemented what can be called a ``polar'' representation (in which a complex number is represented as a pair of a magnitude and an angle). The selectors and the constructors they have created have the same name, operate differently underneath the hood.

Given that the operations add-complex, sub-complex, mul-complex, and div-complex are implemented in terms of abstract data, choosing Ben's representation over Alyssa's, or vice versa, would make no difference: those operations would work in both cases.

Now, what if don't want to choose one representation over the other? What if we want to keep both representations? What if we want a system that looks like that figure 2.19?

If our system has to include multiple representations for the same object type, then we need some way to distinguish objects with representation foo from objects with representation bar. A simple way to do that is tagging the objects. To tag and check the tags we can do something like this:

(define (attach-tag type-tag contents)
  (cons type-tag contents))

(define (type-tag datum)
  (if (pair? datum)
      (car datum)
      (error "Bad tagged datum -- TYPE-TAG" datum)))

(define (contents datum)
  (if (pair? datum)
      (cdr datum)
      (error "Bad tagged datum -- CONTENTS" datum)))

(define (rectangular? z)
  (eq? (type-tag z) 'rectangular))

(define (polar? z)
  (eq? (type-tag z) 'polar))

If Ben and Alyssa have a designed their representation packages separately, what would they have to do to exist compatibly in the system? Here is what they can do. Ben can write his representation in this way:

(define (real-part-rectangular z) (car z))

(define (imag-part-rectangular z) (cdr z))

(define (magnitude-rectangular z)
  (sqrt (+ (square (real-part-rectangular z))
           (square (imag-part-rectangular z)))))

(define (angle-rectangular z)
  (atan (imag-part-rectangular z)
        (real-part-rectangular z)))

(define (make-from-real-imag-rectangular x y)
  (attach-tag 'rectangular (cons x y)))

(define (make-from-mag-ang-rectangular r a)
  (attach-tag 'rectangular
              (cons (* r (cos a)) (* r (sin a)))))

And Alyssa can write her representation in this way:

(define (real-part-polar z)
  (* (magnitude-polar z) (cos (angle-polar z))))

(define (imag-part-polar z)
  (* (magnitude-polar z) (sin (angle-polar z))))

(define (magnitude-polar z) (car z))

(define (angle-polar z) (cdr z))

(define (make-from-real-imag-polar x y)
  (attach-tag 'polar
              (cons (sqrt (+ (square x) (square y)))
                    (atan y x))))

(define (make-from-mag-ang-polar r a)
  (attach-tag 'polar (cons r a)))

These ``packages'' differ from the original packages in two respects:

1. the constructor is now tagging the objects it creates;
2. the function names have been modified in order to avoid name conflicts (for example, in Ben's representation, real-part has become real-part-rectangular).

Now that we have been given typed data, we need somebody, say a ``manager'' (see lecture), that looks at those types and make things work. The manager can now write generic selectors:

(define (real-part z)
  (cond ((rectangular? z)
         (real-part-rectangular (contents z)))
        ((polar? z)
         (real-part-polar (contents z)))
        (else (error "Unknown type -- REAL-PART" z))))

(define (imag-part z)
  (cond ((rectangular? z)
         (imag-part-rectangular (contents z)))
        ((polar? z)
         (imag-part-polar (contents z)))
        (else (error "Unknown type -- IMAG-PART" z))))

(define (magnitude z)
  (cond ((rectangular? z)
         (magnitude-rectangular (contents z)))
        ((polar? z)
         (magnitude-polar (contents z)))
        (else (error "Unknown type -- MAGNITUDE" z))))

(define (angle z)
  (cond ((rectangular? z)
         (angle-rectangular (contents z)))
        ((polar? z)
         (angle-polar (contents z)))
        (else (error "Unknown type -- ANGLE" z))))

This strategy is called dispatch on type. We can think of the system as having three parts: Ben, Alyssa, and the manager. The idea is that you break your system into a bunch of pieces. There is Ben and Alyssa, who are making representations, and then there is the manager, who looks at the types on the data and dispatches tasks to the right person.

How can we criticize the system described above? First, Ben and Alyssa had to change the names of their procedures. Second, when somebody wants to add a representation into the system, even if Ben and Alyssa don't care, whoever is in charge of the generic selectors — the manager, in our narrative —, has to change all of them!

(Roughly, from the lecture:) ``The inflexibility in the system, the place where work has to be done to accommodate is in the manager. That's quite annoying. It's even more annoying when you think that the manager isn't really doing anything… the bottleneck in the system is in the bureaucracy…''

Now, abstractly, in the system, there is a table:

In the table we have the right procedures for the given types (columns) and operators (rows). ``That's really what's going on. In some sense, all the manager is doing is acting as this table''.

How do we fix our system? We get rid of the manager. We let our system use the table directly. How do we do that? Let's assume — again, data abstraction! — that we have some sort of table data structure in which we can put things:

`(put <OP> <TYPE> <ITEM>)' installs the `<ITEM>' in the table,
indexed by the `<OP>' and the `<TYPE>'.

`(get <OP> <TYPE>)' looks up the `<OP>', `<TYPE>' entry in the
table and returns the item found there.  If no item is found,
`get' returns false.

Given that we have this table, now Ben and Alyssa, when they build their systems, can fill the table appropriately:

Ben:

(define (install-rectangular-package)
  ;; internal procedures
  (define (real-part z) (car z))
  (define (imag-part z) (cdr z))
  (define (make-from-real-imag x y) (cons x y))
  (define (magnitude z)
    (sqrt (+ (square (real-part z))
             (square (imag-part z)))))
  (define (angle z)
    (atan (imag-part z) (real-part z)))
  (define (make-from-mag-ang r a)
    (cons (* r (cos a)) (* r (sin a))))

  ;; interface to the rest of the system
  (define (tag x) (attach-tag 'rectangular x))
  (put 'real-part '(rectangular) real-part)
  (put 'imag-part '(rectangular) imag-part)
  (put 'magnitude '(rectangular) magnitude)
  (put 'angle '(rectangular) angle)
  (put 'make-from-real-imag 'rectangular
       (lambda (x y) (tag (make-from-real-imag x y))))
  (put 'make-from-mag-ang 'rectangular
       (lambda (r a) (tag (make-from-mag-ang r a))))
  'done)

Alyssa:

(define (install-polar-package)
  ;; internal procedures
  (define (magnitude z) (car z))
  (define (angle z) (cdr z))
  (define (make-from-mag-ang r a) (cons r a))
  (define (real-part z)
    (* (magnitude z) (cos (angle z))))
  (define (imag-part z)
    (* (magnitude z) (sin (angle z))))
  (define (make-from-real-imag x y)
    (cons (sqrt (+ (square x) (square y)))
          (atan y x)))

  ;; interface to the rest of the system
  (define (tag x) (attach-tag 'polar x))
  (put 'real-part '(polar) real-part)
  (put 'imag-part '(polar) imag-part)
  (put 'magnitude '(polar) magnitude)
  (put 'angle '(polar) angle)
  (put 'make-from-real-imag 'polar
       (lambda (x y) (tag (make-from-real-imag x y))))
  (put 'make-from-mag-ang 'polar
       (lambda (r a) (tag (make-from-mag-ang r a))))
  'done)

Who makes a representation has the responsibility of setting up a column in the table. The manager has been ``automated out of existence''. The manager is replaced by a procedure. This procedure is called apply-generic and is the key procedure in the whole system (see also its simpler version operate shown in the lecture).

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

We use apply-generic to define the generic selectors:

(define (real-part z) (apply-generic 'real-part z))
(define (imag-part z) (apply-generic 'imag-part z))
(define (magnitude z) (apply-generic 'magnitude z))
(define (angle z) (apply-generic 'angle z))

This strategy is called ``data-directed programming'', because, ``in some sense the data objects themselves are carrying with them the information about how you should operate on them''.