4B Generic Operators⁠

# Part 1

# Limits of data abstraction

• So far, we’ve talked a lot about data abstraction. We’ve had these horizontal abstraction barriers that separate use from representation.
• This is powerful, but not sufficient for really complex systems.
• The problem is that sometimes we to use need multiple, incompatible representations.
• We want some kind of vertical barrier in addition to the horizontal barriers.
• We want generic operators that work on multiple data representations.
• It should be easy to add new data types to the system, so that the generic operators work on them too with minimal changes.

# Complex number arithmetic

• We can represent a complex number rectangular form or in polar form.
• The rectangular form $x + yi$ and the polar form $re^{iθ}$ are related:

$$\begin{aligned} x &= r\cos θ, & r &= \sqrt{x^2+y^2}, \\ y &= r\sin θ, & θ &= \arctan(y, x). \end{aligned}$$

• Adding is easy in rectangular form: just add up the real and imaginary parts.
• Multiplying is easy in polar form: just multiply the magnitudes and add the angles.

# Incompatible representations

• We could expose rectangular and polar selectors but still use one particular representation under the hood. This is nothing new.
• What if we want both representations? Data abstraction allows us to postpone the representation decision, but we don’t want to make a decision at all!
• We need a vertical barrier between rectangular and polar forms.
• The selectors real-part, imag-part, magnitude, and angle must be generic procedures that work with either representation.
• For this to work, we need typed data. We need to tag our data objects with labels telling us the type of their contents.
• We can simply cons the symbol 'rectangular or 'polar to the complex number data.
• The generic procedures check the type of their argument, strip off the type information, and dispatch the contents to the appropriate specific procedure.

# Part 2

# Problems with the manager

• The strategy we just looked at is called type dispatch.
• One annoyance is that we had to rename specific procedures to avoid naming conflicts.
• We’ll talk about namespaces to fix that problem later.
• What happens when you add a new type to the system?
  • The other types don’t care. They can remain the same.
  • But the manager needs to add a new clause to every generic procedure that should be able to work with the new type.
  • This is annoying because generic procedure case analyses are very repetitive.

# Data-directed programming

• Our system has a table with types (horizontal axis) and operators (vertical axis).
• Instead of writing these generic procedures manually, we should just use a table.
• We introduce two new procedures: (put key1 key2 value) and (get key1 key2).
• Now we just need to insert our specific procedures into the table using put, and the rest will be automated.
• It’s the procedures that go in the table, not their names, so we could even pass a lambda expression and not give it a name.
• The key procedure in this whole system is operate:

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

• This uses the table to look up the correct procedure, and applies it to the given object.
• Here’s what happens when we extract the real part of a complex number in polar form:

(real-part z)
(operate 'real-part z)
((get 'polar 'real-part) (contents z))
(real-part-polar '(1 . 2))
(* 1 (cos 2))
-0.4161468365

• This style of programming called data-directed programming.
• The data objects themselves carry information about how you should operate on them.

# Part 3

# Generic arithmetic system

• We just looked at data-directed programming for complex numbers.
• The power of the methodology only becomes apparent when you embed this in a more complex system.
• Let’s consider a generic arithmetic system with operations add, sub, mul, and div.
• This should sit on top of ordinary Lisp numbers, rationals, and complex numbers.
• We already made a rational number package. We just need to change the constructor make-rat so that it attaches the tag 'rational to the data.
• We can’t use operate anymore because it was designed for a single argument. The apply-generic procedure from § 2.4.3 works for multiple arguments.
• Now, our complex numbers will have two levels of type tags: 'complex on top and either 'rectangular or 'polar underneath.
• At each level, we strip off a type tag and pass the data down to the level beneath. The chain of types leads you down.

# Polynomials

• We can also add polynomials to the generic arithmetic system.
• Our polynomials will have a variable (symbol) and a term list (list of ordered pairs).
• We can add polynomials in the same variable by combining their term lists.
• By using the generic add when we add term lists, we can use any kind of number as a coefficient, for free! Including polynomials themselves!
• In other words, all because we wrote add instead of +, we have this recursive tower of types: the coefficients can be polynomials all the way down, or as far as we’d like.
• If we use the generic arithmetic procedures in the rational number package, we can get rational functions (polynomials over polynomials) for free as well.

# Conclusion

• We built a system that has decentralized control.
• We don’t have to worry about how operations are actually performed.
• This lets us build this complex hierarchy where all the operations sort of do the right thing automatically.
• The true complexity comes in with coercion: when you add a complex number and a rational, who worries about converting what?