SICP - Generic Operators

This lecture was ostensibly about generic operators, though much of the lecture ACTUALLY dealt with typing.  I took a TON of notes this time around because the lecture was nearly an hour and a half long. I'm really starting to get annoyed with Mr. Stache-Mullet, he sometimes asks good questions but more often than not he gets hung up on stupid crap.



Here are my notes:

Generic Operators

Abstraction layers create barriers that separate use from representation.
Another way to think of is is that the Boss is using the object and George
is down implementing it.

Not sufficient for really complex systems. The problem is that there are lots 
of Georges (or George and Martha).  Both programmers are making representations
that are completely incompatible with each other.  Abstraction should be such that 
the boss doesn't care if George or Martha implemented something.  Should also have
vertical barriers (between George and Martha)

Generic Operators allow us to get common data from different representations of the
same type of object. Generic operators allow us to include new things by making minimal
changes.

Example will be a system that does arithmetic on complex numbers.

Imaginary numbers can be represented in a rectangular form z = x + iy or
polar form as z = re^(iA). Looking at creating add, subtract, multiply, and divide procedures.

Complex addition (rectangular form)
Re (Z1 + Z2) = (Re Z1) + (Re Z2)
Im (Z1 + Z2) = (Im Z1) + (Im Z2) 

Complex multiplication (polar form)
Mag (Z1 * Z2) = (Mag Z1) * (Mag Z2)
Angle (Z1 * Z2) = (Angle Z1) + (Angle Z2)

Like rational numbers, we assume we have some constructors and selectors
Selectors:
(REAL-PART Z)
(IMAG-PART Z)
(MAGNITUDE Z)
(ANGLE Z)

Constructors:
(MAKE-RECTANGULAR X Y)
(MAKE-POLAR R A)

(DEFINE (+C Z1 Z2)
(MAKE-RECTANGULAR
(+ (REAL-PART Z1) (REAL-PART Z2))
(+ (IMAG-PART Z1) (IMAG-PART Z2))))

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

(DEFINE (/C Z1 Z2)
(MAKE-POLAR
(/ (MAGNITUDE Z1) (MAGNITUDE Z2))
(- (ANGLE Z1) (ANGLE Z2))))

;;; Georges version:
;;; Representing complex numbers as
;;; pairs REAL-PART.IMAGINARY-PART

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

This is conceptually the same as the rational number 

;;; Marthas version:
;;; Representing complex numbers as
;;; pairs MAGNITUDE.ANGLE

(DEFINE (MAKE-POLAR R A)
(CONS X Y)

(DEFINE (MAGNITUDE Z) (CAR Z))
(DEFINE (ANGLE Z) (CDR Z))

(DEFINE (MAKE-RECTANGULAR X Y)
(CONS (SQRT (+ (SQUARE X) (SQUARE Y)))
 (ATAN X Y)))

(DEFINE (REAL-PART Z)
(* (CAR Z) (COS (CDR Z))))
 
(DEFINE (IMAG-PART Z)
(* (CAR Z) (SIN (CDR Z))))

If you are mostly doing addition, Georges might be better. Lots of multiplication Marthas might be better. But ultimately maybe you can't decide. We want operations that can add, subtract, multiply, and divide that don't care which representation they get. We need a vertical barrier that allows both representations to exist in harmony.

Introduce the concept of typed data - a label saying what the data is.  We have the contents and the type.
;;; Support mechanism for manifest types
(DEFINE (ATTACH-TYPE TYPE CONTENTS)
(CONS TYPE CONTENTS))

(DEFINE (TYPE DATUM)
(CAR DATUM))

(DEFINE (CONTENTS DATUM)
(CDR DATUM))

;;; type predicates
(DEFINE (RECTANGULAR? Z)
(EQ? (TYPE Z) 'RECTANGULAR))

(DEFINE (POLAR? Z)
(EQ? (TYPE Z) 'POLAR))

Only changes that have to be made to George's and Martha's respective packages is that they need to sign 
them and make his procedures specific to his type.

;;; Georges version:
;;; Representing complex numbers as
;;; pairs REAL-PART.IMAGINARY-PART
;;; now with TYPE

(DEFINE (MAKE-RECTANGULAR X Y)
(ATTACH-TYPE 'RECTANGULAR(CONS X Y)))

(DEFINE (REAL-PART-RECTANGULAR Z) (CAR Z))
(DEFINE (IMAG-PART-RECTANGULAR Z) (CDR Z))

(DEFINE (MAGNITUDE-RECTANGULAR Z)
(SQRT (+ (SQUARE (CAR Z))
(SQUARE (CDR Z)))))
 
(DEFINE (ANGLE-RECTANGULAR Z)
(ATAN (CDR Z) (CAR Z)))

Martha's are analogous, I'm not going to repeat them.

Generic Selectors:
(DEFINE (REAL-PART Z)
(COND ((RECTANGULAR? Z)
(REAL-PART-RECTANGULAR
(CONTENTS Z)))
((POLAR? Z)
(REAL-PART-POLAR
(CONTENTS Z)))))

IMAG-PART, ANGLE, and MAGNITUDE selectors are pretty much exactly the same.
To the user of the generic selectors, it doesn't matter which representation of 
imaginary numbers is being used, because the type data ensures that the appropriate
procedures are being used.

This strategy for generic operators is called "Dispatch on type"

Criticism:
George and Martha had to change the names of their procedures. There are ways to package namespaces so 
that they don't interfere with each other.
Problem of what happens when you bring someone new into the system.  What does the manager have to do?
If Harry comes in with a new type of complex number, the manager has to change all the generic procedures
to accommodate new type.  Lack of flexibility.

Abstractly, there is a table of operators who work on each type.
           POLAR    RECTANGULAR
REAL-PART |_______|_____________|      
IMAG-PART |_______|_____________|  
MAGNITUDE |_______|_____________|  
ANGLE     |_______|_____________|  

Lets take the manager out of the equation and just have the computer use the table directly
(PUT KEY1 KEY2 VALUE)
(GET KEY1 KEY2)

;;; Installing the rectangular
;;; operations in the table

(PUT 'RECTANGULAR 'REAL-PART
REAL-PART-RECTANGULAR)

(PUT 'RECTANGULAR 'IMAG-PART
IMAG-PART-RECTANGULAR)

(PUT 'RECTANGULAR 'MAGNITUDE
MAGNITUDE-RECTANGULAR)

(PUT 'RECTANGULAR 'ANGLE
ANGLE-RECTANGULAR)

Manager is replaced by a procedure called OPERATE

(DEFINE (OPERATE OP OBJ)
(LET ((PROC (GET (TYPE OBJ) OP)))
(IF (NOT (NULL? PROC))
(PROC (CONTENTS OBJ))
(ERROR "Undefined Operator"))))

Defining the selectors using operate

(DEFINE (REAL-PART OBJ)
(OPERATE 'REAL-PART OBJ))

(DEFINE (IMAG-PART OBJ)
(OPERATE 'IMAG-PART OBJ))

(DEFINE (MAGNITUDE OBJ)
(OPERATE 'MAGNITUDE OBJ))

(DEFINE (ANGLE OBJ)
(OPERATE 'ANGLE OBJ))

This use of a table is called "Data directed programming"
The data objects themselves carry around with them the information about how you should operate on them.
Bring up the possibility of storing the procedures in the object itself, a method called "Message passing"

Assume we are embedding this in a more complex system, like say a general arithmetic system. Under this general arithmetic system, we may have multiple systems like complex, rational, and ordinary numbers.
I'm not retyping the definitions of the rational number arithmetic, but we're looking at them and they don't have to be changed at all. How do we install it into generic system? We have to add type data to the MAKE-RAT constructor.

(DEFINE (MAKE-RAT X Y)
(ATTACH-TYPE 'RATIONAL (CONS X Y)))

(PUT 'RATIONAL 'ADD +RAT)
(PUT 'RATIONAL 'SUB -RAT)
(PUT 'RATIONAL 'MUL *RAT)
(PUT 'RATIONAL 'DIV /RAT)

(DEFINE (ADD X Y)
(OPERATE-2 'ADD X Y))

(DEFINE (OPERATE-2 OP ARG1 ARG2)
(IF
(EQ? (TYPE ARG1) (TYPE ARG2))
(LET ((PROC (GET (TYPE ARG1) OP)))
IF (NOT (NULL? PROC))
(PROC (CONTENTS ARG1)
 (CONTENTS ARG2))
(ERROR "Op undefined on type")))
(ERROR "Args not same type")))

;;; installing complex numbers

(DEFINE (MAKE-COMPLEX Z)
(ATTACH-TYPE 'COMPLEX Z))

(DEFINE (+COMPLEX Z1 Z2)
(MAKE-COMPLEX (+C Z1 Z2)))

(PUT 'COMPLEX 'ADD +COMPLEX)

Pretty much the same definition for the other operators. Took me a second why we even need the +COMPLEX, 
basically it is an abstraction thing so we can add typing information to the result of +C

We install ordinary numbers the same way

;;; Installing ordinary numbers
(DEFINE (MAKE-NUMBER N)
(ATTACH-TYPE 'NUMBER N)

(DEFINE (+NUMBER X Y)
(MAKE-NUMBER (+ X Y)))

(PUT 'NUMBER 'ADD +NUMBER)

From the top most layer (general arithmetic) a complex number (say 3 + 4i) might look like this:
   [ | ] ---- [ | ] ---------- [ | ]
    |          |               /   \
   'COMPLEX   'RECTANGULAR    3     4
   
Abelson is going to make it more complex... sadist lol
Now we are looking at polynomials

(POLYNOMIAL X <TERM-LIST>)
Represent the term list as a list of pairs of order and coefficient.
x^15 + 2x^7 + 5 would be represented as such: ((15 1) (7 2) (0 5))

(DEFINE (MAKE-POLYNOMIAL VAR TERM-LIST)
(ATTACH-TYPE 'POLYNOMIAL
(CONS VAR TERMLIST)))
 
(DEFINE (+POLY P1 P2)
(IF (SAME-VAR? (VAR P1) (VAR P2))
(MAKE-POLYNOMIAL
(VAR P1)
(+TERMS (TERM-LIST P1)
(TERM-LIST P2)))
(ERROR "Polys not in same var")))

(PUT 'POLYNOMIAL 'ADD +POLY)

(DEFINE (+TERMS L1 L2)
(COND ((EMPTY-TERMLISTS? L1) L2)
((EMPTY-TERMLISTS? L2) L1)
(ELSE
(LET ((T1 (FIRST-TERM L1))
 (T2 (FIRST-TERM L2)))
(COND
((> (ORDER T1) (ORDER T2))
(ADJOIN-TERM
T1
(+TERMS (REST-TERMS L1) L2)))
((< (ORDER T1) (ORDER T2))
(ADJOIN-TERM
T2
(+TERMS L1 (REST-TERMS L2))))
(ELSE 
(ADJOIN-TERMS
(MAKE-TERM (ORDER T1)
(ADD (COEFF T1)
    (COEFF T2)))
(+TERMS (REST-TERMS L1)
(REST-TERMS L2)))))))))

Alrighty, so apparently ADD is the only interesting term. We reduced adding polynomials down to using the generic ADD. Because we can use the generic ADD, we can do polynomials of any type (complex, rational, ordinary)

So it can automatically handle rationals: (2/3)x^2 + (5/17)x + (11/4) 
or complex: (3 + 2i)x^5 + (4 + 7i)

And NOW it's even better than that... Polynomials themselves can be added.
polynomial in y whose coefficients are polynomials in x:
(x^2 + 1)y^2 + (x^3 - 2x)y + (x^4 - 7) 

Another way to think of it is that polynomials are a constructor for types.
If we change the operators in our rational number arithmatic procedures with the generics, then we are 
able to generalize these to rational objects whose numerator and denominator can be rational, complex, ordinary, or polynomial.

(DEFINE (+RAT X Y)
(MAKE-RAT
(ADD (MUL (NUMER X)(DENOM Y))
(MUL (DENOM X)(DENOM Y)))
(MUL (DENOM X)(DENOM Y))))

Could further expand the system with matrix math and by using the generic operators.
We have decentralized control. Question... pete sake the stache-mullet guy is way overthinking this...
He mentions a little about a problem called "coercion" where you can view types in terms of other types... like so you could add an ordinary number and a rational. These types of problems create a huge amount of complexity. Oh god mullet again...... talking about changing higher levels of abstraction and how that trickles down... adding a generic "equality" operator would require everyone below to decide how they want to implement it...