# SICP 4b Generic Operators

## 1 Complex numbers

There are two standard representations of complex numbers: rectangular representation and polar representation.

$z=x+iy=re^{iA}$

$x=r\cos A$ , $r=\sqrt{x^{2}+y^{2}}$ , $y=r\sin A$ , $A=\arctan(y,x)$ .

$\text{Re}(z_{1}+z_{2})=(\text{Re}z_{1})+(\text{Re}z_{2})$ $\text{Im}(z_{1}+z_{2})=(\text{Im}z_{1})+(\text{Im}z_{2})$ $\text{Mag}(z_{1}*z_{2})=(\text{Mag}z_{1})*(\text{Mag}z_{2})$ $\text{Angle}(z_{1}*z_{2})=(\text{Angle}z_{1})+(\text{Angle}z_{2})$

Implementation in LISP.

; selectors
(real-part z)
(imag-part z)
(magnitude z)
(angle z)

; constructors
(make-rectangular x y)
(make-polar r a)

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


Representing complex numbers as pairs (real and imaginary parts).

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


Representing complex numbers as pairs (magnitude and angle).

(define (make-polar r a) (cons r a))
(define (magnitude z) (car z))
(define (angle z) (cdr z))
(define (make-rectangular x y)
(cons (sqrt (+ (square x) (square y)))
(atan y x)))
(define (real-part z)
(* (car z) (cos (cdr z))))
(define (imag-part z)
(* (car z) (sin (cdr z))))


## 2 Types

Typed data, consisting of type and contents, enables us to distinguish between the two representations.

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


Rectangular package.

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


Polar package.

(define (make-polar r a)
(attach-type 'polar (cons r a)))
(define (real-part-polar z)
(* (car z) (cos cdr z)))
(define (imag-part-polar z)
(* (car z) (sin (cdr z))))
(define (magnitude-polar z) (car z))
(define (angle-polar z) (cdr z))


Generic selector for complex numbers.

(define (real-part z)
(cond ((rectangular? z)
(real-part-rectangular
(contents z)))
((polar? z)
(real-part-polar
(contents z)))))
(define (imag-part z)
(cond ((rectangular? z)
(imag-part-rectangular
(contents z)))
((polar? z)
(imag-part-polar
(contents z)))))
(define (magnitude z)
(cond ((rectangular? z)
(magnitude-rectangular
(contents z)))
((polar? z)
(magnitude-polar
(contents z)))))
(define (angle z)
(cond ((rectangular? z)
(angle-rectangular
(contents z)))
((polar? z)
(angle-polar
(contents z)))))


## 3 Remove bureaucracy

Each new type adds unnecessary bureaucracy. To rectify the overreach of paper shuffling, let's understand why this verbosity currently exists.

Polar Rect
real-part real-part-polar real-part-rectangular
imag-part imag-part-polar imag-part-rectangular
magnitude magnitude-polar magnitude-rectangular
angle angle-polar angle-rectangular

By creating a table, all of our paper pushing sins can be pardoned.

To add/retrieve a value to/from the table, use the following commands.

(put key1 key2 value)
(get key1 key2)


Implement rectangular and polar representations.

(put 'rectangular 'real-part
real-part-rectangular)
(put 'rectangular 'imag-part
imag-part-rectangular)
(put 'rectangular 'magnitude
magnitude-rectangular)
(put 'rectangular 'angle
angle-rectangular)
(put 'polar 'real-part
real-part-polar)
(put 'polar 'imag-part
imag-part-polar)
(put 'polar 'magnitude
magnitude-polar)
(put 'polar 'angle
angle-polar)


Now the manager is replaced by operator.

(define (operate op obj)
(let ((proc (get (type obj) op)))
(if (not (null? proc))
(proc (contents obj))
(error "undefined operator"))))


And the selectors follow.

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


Determining which procedure to use, based on data, is called data-directed programming.

## 4 Big pond

Let's broaden our horizons, and embed complex numbers into a general arithmetic system.

First, include rational numbers.

(define (make-rat x y)
(attach-type 'rational (cons x y)))
(put 'rational 'sub -rat)
(put 'rational 'mul *rat)
(put 'rational 'div /rat)

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


Include complex numbers.

(define (make-complex z)
(attach-type 'complex z))

(define (+complex z1 z2)
(make-complex (+c z1 z2)))
(define (-complex z1 z2)
(make-complex (-c z1 z2)))
(put 'complex 'sub -complex)
(define (*complex z1 z2)
(make-complex (*c z1 z2)))
(put 'complex 'mul *complex)
(define (/complex z1 z2)
(make-complex (/c z1 z2)))
(put 'complex 'div /complex)


Include ordinary garden-variety numbers.

(define (make-number n)
(attach-type 'number n))

(define (+number z1 z2)
(make-number (+ z1 z2)))
(define (-number z1 z2)
(make-number (- z1 z2)))
(put 'number 'sub -number)
(define (*number z1 z2)
(make-number (* z1 z2)))
(put 'number 'mul *number)
(define (/number z1 z2)
(make-number (/ z1 z2)))
(put 'number 'div /number)


And finally spicy polynomials. First, need to determine how to represent polynomials.

$x^{15}+2x^{7}+5$

(polynomial x <term-list>)
((15 1) (7 2) (0 5))


Where 15 is the order and 1 is the coefficient.

(define (make-polynomial var term-list)
(attach-type 'polynomial
(cons var term-list)))

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

(define (+terms l1 l2)
(cond ((empty-termlist? l1) l2)
((empty-termlist? l2) l1)
(else
(let ((t1 (first-term l1))
(t2 (first-term l2)))
(cond
((> (order t1) (order t2))
t1
(+terms (rest-terms l1) l2)))
((< (order t1) (order t2))
t2
(+terms l1 (rest-terms l2))))
(else
(make-term (order t1)
(coeff t2)))
(+terms (rest-terms l1)
(rest-terms l2)))))))))


Note that add in the fourth last line means that the coefficients can be rational, complex, ordinary, or even other polynomials.

$(x^{2}+1)y^{2}+(x^{3}-2x)y+(x^{4}-7)$

A similar generalisation can be done to rationals.

(define (+rat x y)
(make-rat
(add (mul (numer x) (denom y))
(mul (denom x) (numer y)))
(mul (denom x) (denom y))))


We have now incorporated decentralised control.