💾 Archived View for gemini.lostleonardo.xyz › sicp › lecture-4B.gmi captured on 2021-12-04 at 18:04:22. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2021-11-30)
-=-=-=-=-=-=-
So far in this course we've been talking a lot about data abstraction and the idea is that we build systems that have these horizontal abstraction barriers which seperate use (the way in which you might use some data object) and representation.
Seperating use from representation so that you can think about these two problems seperately is a very powerful programming methodology, but it is not really sufficient for really complex systems, and the probelm with this is George and Martha.
In designing a system, you not only want horizontal barriers, you also want vertical barriers to keep George and Martha seperate.
The way of introducing these vertical barriers is to have generic operators; data objects that know how to operate on themselves.
"Generic operator means that precisely what the object does depends on the type of data that it's looking at. We want to be able to introduce new things by making minimal changes".
Start with the constuctors
- make-rectangular x y
- make-polar
and selectors
- real-part z
- imag-part z
- magnitude z
- angle z
The system has two constructors and four selectors, then we can implement complex number operations based on that abstract data.
How we do that is that every piece of compound data needs another piece of information that tells us its type. Then, when we looked at the object, we could see how to operate on it.
Typed data means that there is some kind of cloud and what it has in it are ordinary data objects, as well as a type. In effect the object is signed, so that we know where it comes from.
Typed data - a cloud and what it has in it are ordinary data objects, as well as a type; it is signed.
Typed data allows us to do some powerful things.
"When we are given a piece of data we will test what type it is. To see what type a piece of data is we need some predicates".
Once we can test the kind of data we are looking at we can dispatch on that type.
So now when George and Martha make their concrete representations, they sign them by attaching a type to the content. In this case the type is either 'rectangular or 'polar.
Now that we have these concrete implementations, we need a kind of manager (I think we might be able to say runtime) to look at these types.
The manager is comprised of a group of generic selectors for real-part, imaginary-part, magnitude and angle, and what those do is to look up the type of the arguments that are passed into them (using the predicate expressions) and to perform the operation (method) that is appropriate for the given representation. That is, the system performs a dispatch based on the type.
The system has three parts: George, Martha and the manager. "That is how you get generic operators implemented".
Data is 'signed' with a type before it is passed to the manager, and likewise the manager strips off the type before it passes it to the concrete operators, so there is no confusion about what the abstract data represents.
"We just looked at a strategy for implementing generic operators and that strategy has a name. It is called dispatch on type".
Dispatch on type requires a system comprised of multiple parts:
- George and Martha, who are making concrete implementations
- and the manager, who looks that types on the data and then dispatches them to the right person
"The inflexibility in this system - the place where work has to happen to accommodate change - is in the manager. That's pretty annoying. It's even more annoying, when you realise that the manager is not doing anything it's just being a paper pusher".
Abstractly, what is happening in this system is that somewhere there is a table:
Polar Rect
Real-part Real-part-polar Real-part-rect
Imag-part
Mag Mag-polar Mag-rect
Angle
There are types - polar and rect
There are operators - real-part, imag-part, mag, angle
"That is really what is going on".
In some sense, all the manager is doing is acting as this table. So, how do we fix our system?
Instead of having the manager who consults this table, we will have our system use the table directly.
(put key1 key2 value)
(get key1 key2)
Now when George and Martha build their systems, they have a responsibility to put the operations that they define into the table, using the name of the type and the name of the operation as keys.
(put 'rectangular 'real-part real-part-rectangular)
(put 'rectangular 'imag-part imag-part-rectangular)
(put 'rectangular 'magnitude magnitude-rectangular)
(put 'rectangular 'angle angle-rectangular)
Everybody involved in the system has a responsibility for setting up their column in the table.
This is describing how you implement a v-table in an object-oriented language, so that you can dispatch on a type. Really interesting stuff!
The manager has been automated out of existence and replaced with a procedure called operate which is the key procedure in the entire system.
The manager has been automated out of existence and replaced with a procedure called operate.
op = operation
obj = object
(DEFINE (operate op obj
(LET ((proc (get (type obj) op))))
(if (not (null? proc))
(proc (contents object))
(error "message not found"))))
That procedure replaces the manager... then you can define your generic selectors using operate.
Defining 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 is really neat, and I definitely need to come back to it and try to describe it in more detail.
Back to add a bit more detail!
Operate looks up the name of the method for that type in the table and applies the procedure to the contents of the object.
(real-part z) -> (operate 'real-part z) -> ((get 'polar 'real-part) (contents z))
Operate does uniformly what the manager used to do all over the system - it finds the right thing, looks in the table, strips off the type, and passes it down to the person who handles it.
This is another, more flexible way of implementing generic operators, and it is called data-directed programming.
"The idea of that is that the data objects themselves are carrying with them the information about how you should operate on them".
Another way of organising this system is for the operators to reside, not in the table, but inside the data objects themselves. "That is another way of organising this kind of system called message passing".
---
Data-directed programming
"This is another, more flexible (for the most part) way of implementing generic operators, and the idea of that is that the data objects themselves are carrying with them the information about how you should operate on them"
That (to me) sounds like a concise description of objects in the object-oriented sense. The operations themselves are sitting in the table, and the rows and columns of the table are labelled by symbols. The key might be the symbol polar and the symbol magnitude. The value is the procedure associated with that named pair (e.g. (LAMBDA (etc.))
Okay, maybe that is not entirely correct, he just mentioned message-passing as something different.
---
But that doesn't show you the full power of this kind of design. That comes from embedding... we might imagine this complex number system sitting in a more complicated generic operator structure at the next level up.
---
A system with decentralised control.
There is some amazing stuff in here.