New traits system

[Lee Salzman]

To put this more succinctly, our old system of inheritance did not work
with multiple inheritance in many common use cases. As an example, if you 
had the following inheritance hierarchy:

            ReadWriteStream
                 /\
                /  \
               /    \
     ReadStream      WriteStream
               \    /
                \  /
                 \/
               Stream

It is important to note the primitive delegation mechanism traverses
this hierarchy DEPTH-FIRST. So it would visit ReadWriteStream,
ReadStream, Stream, WriteStream in that order. If this seems
counter-intuitive, again, remember, the old system was depth-first.

But if WriteStream overrides methods on Stream, then searching Stream
before WriteStream will cause Stream to override WriteStream! Ideally,
we want to scan WriteStream before Stream, and we want the overall
visitation order to be: ReadWriteStream, ReadStream, WriteStream,
Stream. 

This "ideal" visitation order is "topological". In other words, it
ensures that an object is not visited until all things that are
delegating to it have been visited first. i.e. Since both ReadStream and
WriteStream delegate to Stream, they must both be visited first before
visiting Stream.

We achieved this by sticking a new kind of "traits" on our objects,
called a "traits window". This window contains a flat list of all the
traits an object has, in the exact order they need to be visited, so
that this decision is not left entirely up to the unreliable primitive
depth-first order. i.e. "ReadWriteStream traitsWindow" is an object that
looks as follows:

   (traits: ReadWriteStream traits. traits1: ReadStream traits. 
    traits2: WriteStream traits. traits3: Stream traits).
               
Since the traits of all the things it inherits are laid out flat and in
order like this, it ensures they get visited in the exact order desired.

On Mon, Nov 15, 2004 at 10:57:12PM -0800, Brian Rice wrote:
> So, I'll present the new system of inheritance, how it differs from our 
> prior system, and explain part of the decision-making process that was 
> involved in choosing this new direction.
> 
> First, the object-traits direct slot relationship has been mediated by 
> an object-traitsWindow relationship, which I will explain shortly.
> 
> Previously, object inheritance was performed solely through creating 
> and setting delegation slots, and traits slots were not special in any 
> way. Traits slots were also traversed in depth-first order with the 
> slot-ordering performed from most-recently-added to 
> least-recently-added. Since this order was not explicitly visible or 
> easily controllable, performing addDelegate: on your newly derived type 
> of object would make delegate behavior the /primary/ behavior when 
> defining methods, i.e. @(Foo traits) would go to the delegated object's 
> traits object and not what was in Foo's #traits object (Note: this is 
> BAD). We have modified #slotNames and #delegateNames primitives to 
> answer slots in an array which reflects their ordering. We have also 
> added addDelegate:after: and addDelegate:before: (which position 
> relative to other slot names).
> 
> But this is not enough. Even with the ability to easily deal with 
> delegation order, there is still some complexity or confusion of levels 
> in the way that traits objects work. Basically each object's traits 
> object is delegating to its parent traits as well as Traits traits, its 
> own traits object, on the same level. It doesn't matter what the 
> delegation order is, because often one meaning of a selector will be 
> needed and then another on the same object. We hypothetically worked 
> with a few different delegation orders (breadth-first, topological), 
> and /all/ of them lead to problems with ambiguity of meaning.
> 
> So instead we talked about a "traits window": essentially each object 
> delegates to one of these which holds all of the /various/ traits 
> objects in order of precedence in slots, and these just delegate right 
> to Traits traits instead of each other. So we're talking about 
> composition now, not a multiple inheritance graph. And each object can 
> take its traits window and re-arrange the ordering to suit its behavior 
> better. So if you have a "diamond inheritance" shape, instead of having 
> to perform resends through local method overrides in order to get the 
> desired combination of behaviors and exclusion of others, you simply 
> (re-)order the visitation at the bottom of the diamond.
> 
> To make this work properly, a flag was added to maps to restrict 
> delegation: if dispatch sees an object with the flag set, it will not 
> traverse any subsequent objects it finds with the flag set. This flag 
> may be set in userland, and in fact the normal derivation routines will 
> set this flag for a traitsWindow's map. So within a single lookup, an 
> object-traitsWindow relation be traversed at most once. This avoids 
> issues where Traits traits definitions are reachable from any object 
> (e.g. accessing #clone method definitions from Oddballs), but it's 
> userland controlled so it may be used anywhere where such a tower needs 
> to be avoided.
> 
> And what does this mean to all of you? Not a whole lot, thankfully. :-) 
> The protocols for addPrototype:derivedFrom: and derive itself are the 
> same, but create more sensibly-behaving results. You have the added 
> control that each prototype (via its traitsWindow) can go about 
> re-ordering its delegation order regardless of its parents.
> 
> When you define a method on "Foo traits", it still goes to the right 
> object, but that is reached via the traitsWindow, and basically 
> represents "how I'm overriding my ancestors". From a broader 
> perspective, all of the behavior can be put into re-usable parts, and 
> then the "Foo traits" of the world be used just where compositions of 
> these parts don't line up correctly. This is analogous to the Squeak 
> research on traits as a way to safely add composable multiple 
> inheritance to single-inheritance class-based OOP.
> 
> *** The Bottom Line ***
> 
> Everything is the same as it used to be in terms of inheritance 
> capabilities and the regular grammar, but in order to determine lookup 
> patterns, you don't have to mentally traverse the inheritance graph; 
> instead you can just look at the traitsWindow and re-order it if you 
> don't like it, on a case-by-case basis.
> 
> I'll spend some more time refining this for the manual with some 
> examples, and I'm sure we'll find convenient ways to manage this as we 
> go.
> 
> --
> Brian T. Rice
> LOGOS Research and Development
> http://tunes.org/~water/
>