* Lecture 4B: Generic operators

so far we've been thinking about horizontal data abstractions

:       use
: ================
:  representation

this is a powerful technique but it's not sufficient for very complex
systems. 

the problem is that 'george' and 'martha' might both be designing
representations that are incompatible.

we would like to support multiple representations while still not
worrying about them from above the abstraction barrier.

we would like to be able to add new things with minimal changes.

we _will_ be doing the complex number system (from the book)



say we have some selectors and constructors,

: (real-part z)
: (imag-part z)
: (magnitude z)
: (angle z)

: (make-rectangular x y)
: (make-polar r a)

and we can easily implement some arithmetic:

#+BEGIN_SRC scheme
  (define (+c z1 z2)
    (make-rectangular
     (+ (real-part z1) (real-part z2))
     (+ (imag-part z1) (imag-part z2))))
  (define (*c z1 z2)
    (make-polar
     (* (magnitude z1) (magnitude z2))
     (+ (angle z1) (angle z2))))
  ;; etc...
#+END_SRC

now we can ask 'george to build a representation:

#+BEGIN_SRC scheme
  (define (make-rectangular x y)
    (cons x y))
  (define (real-part z) (car z))
  (define (imag-part z) (cdr z))

  (define (make-polar r a)
    (cons (* r (cos a)) (* r (sin a))))
  (define (magnitude z)
    (sqrt (+ (square (car z))
	     (square (cdr z)))))
  (define (angle z)
    (atan (cdr z) (car z)))
#+END_SRC

'martha' is going to take a different approach. she will define a pair
as a mag and angle, not rect form.

which is better? depends. but really: we can't decide.

what we would like is a system that has operations that add, sub, ...,
and it does not matter that there are two impls floating around.

how do we do this? harry says it's obvious. give em labels.

"designer data" comes with a tag -- gucci numbers

                  -TYPED DATA-

#+BEGIN_SRC scheme
  (define (attach-type contents)
    (cons type contents))
  (define (type datum)
    (car datum))
  (define (contents datum)
    (cdr datum))

  (define (rectangular? z)
    (eq? (type z) 'rectangular))
  (define (polar? z)
    (eq? (type z) 'polar))
#+END_SRC

here are the edits to george's rect package:

#+BEGIN_SRC scheme
  (define (make-rectangular x y)
    (attach-type 'rectangular (cons x y)))
  (define (real-part-rectangular z)
    (car z))
  (define (real-part-rectangular z)
    (cdr z))
  ;; etc...
  (define (make-polar r a)
    (attach-type 'polar (cons r a)))
  ;; etc...
#+END_SRC

generic selectors:

#+BEGIN_SRC scheme
  (define (real-part z)
    (cond ((rectangular? z)
	   (real-part-rectangular
	    (contents z)))
	  ((polar? z)
	   (real-part-polar
	    (contents z)))))
#+END_SRC

--> break

this strategy is called "dispatch on type"

the "manager" looks at the type on the data and dispatches it
accordingly.

what can we criticize?
  - we had to rename the procedures
  - what happens when u bring someone new into the system
    - manager has to add a test to each dispatch procedure
      (inflexible!)
    - the manager isn't doing anything
      - its just a "paper pusher"

abstractly in the system, there's a table

|           | polar           | rect           |
|-----------+-----------------+----------------|
| real-part | real-part-polar | real-part-rect |
| imag-part |                 |                |
| magnitude | magnitude-polar | magnitude-rect |
| angle     |                 |                |

the manager is just acting as this table, so let's get rid of it

assume we have a data structure that is a table with ways of
interacting

: (put key1 key2 value)
: (get key1 key2)

to install operations in the table:

#+BEGIN_SRC scheme
  ;; george:
  (put 'rectangular 'real-part
       real-part-rectangular)
  (put 'rectangular 'magnitude
       magnitude-rectangular)
  ;; martha:
  (put 'polar 'real-part real-part-polar)
  (put 'polar 'magnitude magnitude-polar)
#+END_SRC

manager has been automated away, replaced by the procedure operate:

#+BEGIN_SRC scheme
  (define (operate op obj)
    (let ((proc (get (type obj) op)))
      (if (not (null? proc))
	  (proc (contents obj))
	  (error "undefined operator"))))
#+END_SRC

to use it:

#+BEGIN_SRC scheme
  (define (real-part obj)
    (operate 'real-part obj))
  (define (magnitude obj)
    (operate 'magnitude obj))
#+END_SRC

if z is polar:
: (real-part z)
: (operate 'real-part z)
: ((get 'polar 'real-part) (contents z))
: (real-part-polar '(1 2))

this is called DATA DIRECTED PROGRAMMING

--> break

the power of this comes when we embed it in a more complex system

:         add  sub  mul  div
: ---------------------------------------
: rational |    complex   | ordinary nums
:  +rat    |     +c -c    |   +  -
:  *rat    |     *c /c    |   *  /
:   ...    +------+-------+
:          | rect | polar |


how do we add our old rat system to the generic arith system?

#+BEGIN_SRC scheme
  (define (make-rat x y)
    (attach-type 'rational (cons x y)))
  (put 'rational 'add +rat)
  (put 'rational 'mul *rat)
#+END_SRC

to implement the generic add that works with all our types:

#+BEGIN_SRC scheme
  (define (add x y)
    (operate-2 'add x y))
#+END_SRC

to install complex numbers:

#+BEGIN_SRC scheme
  (define (make-complex z)
    (attach-type 'complex z))
  (define (+complex z1 z2)
    (make-complex (+c z1 z2)))
  (put 'complex 'add +complex)
#+END_SRC

to install ordinary numbers:

#+BEGIN_SRC scheme
  (define (make-number n)
    (attach-type 'number n))
  (define (+number x y)
    (make-number (+ x y)))
  (put 'number 'add +number)
#+END_SRC

what if we want to add polynomials?

: x^15 + 2x^7 + 5

: (polynomial x <term-list>)

: ((15 1) (7 2) (0 5))

#+BEGIN_SRC scheme
  (define (make-poly var term-list)
    (attach-type 'poly (cons var term-list)))
  (define (+poly p1 p2)
    (if (same-var? (var p1) (var p2))
	(make-poly
	 (var p1)
	 (+terms (term-list p1)
		 (term-list p2)))
	(error "polys not in same var")))
  (put 'poly 'add +poly)
#+END_SRC

we fired the managers

we have DECENTRALIZED CONTROL
we have DECENTRALIZED CONTROL
we have DECENTRALIZED CONTROL