CPL etc

[Dick Gabriel <RPG@SAIL.STANFORD.EDU>]

After a day of meetings I was finally able to get back to our favorite
topic. Moon's tiebreaker variant admits a linear implementation, which is
pretty good. I have some questions about whether we think it is intuitive:

(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass d1 (c1 c2) ())
(defclass d2 (c1 c3) ())
(defclass e1 (d1 d2) ())

At some point Danny mentioned that the ``right'' order for this is
(E1 D1 D2 C1 C2 C3 TOP) 

The new algorithm (and New Flavors, I think) produces
(E1 D1 D2 C1 C3 C2 TOP) 

Is this less intuitive? More later.

Some people might have been confused by Moon's description. It read:

``When topological sort finds multiple candidates to go in next, choose the
candidate that has a direct subclass rightmost in the class precedence list
computed so far.  ***If that subclass has more than one direct superclass
among the candidates, take the superclass that is most specific according
to the subclass's local precedence order.***''

The condition described in the sentence between the asterisks cannot
happen, so you shouldn't try to understand it. A candidate for
entering the final CPL has no predecessors, which means that all of its
siblings to the left have already been placed in the CPL, and so none of
them can be candidates to go next.

I think that in worrying about the CPL we have to keep in mind that most
people will operate under the following model: The direct superclasses
mentioned in the DEFCLASS form and their relative order are important. The
system will then provide some arbitrary total order, and the program will
have to be massaged until it works - simply because no one can understand
the algorithm. This is the model that KDO will have; KDO is no wimp.
Many people will wish they can simply supply their own ordering algorithm.

Here is a simple example, which many of you have seen before. There are 4
classes, perhaps poorly chosen:

		     Animate-things
		       blush-method  = turn-pink
		       noseup-method = become-haughty
			 |
			 |
                     /        \
                   /            \
                 /                \
    Turtles                         Green-animals
      noseup-method = pick-up-pen     blush-method = turn-purple
               \                    /
                 \                /
                   \            /
                         |
                         |
                    Green-turtles


Animate-things has two methods, blush-method and noseup-method. The effect of
the blush-method is to change colors and the effect of the noseup-method is
to change the attitude of the object to haughtiness. The first subclass is
Turtles, like LOGO turtles. The noseup-method shadows the animate-things method,
and the effect of it is to pick up the pen; the blush-method is ok. The second
subclass is Green-animals, and the blush-method is different, because when
a green thing turns pink, it really turns purple.

The final class is Green-turtles. This might be a dumb thing to do, but
the user's intuition might be reasonable. He sees that the Turtle noseup-method
is good, and that the Green-animals blush method is good, so he inherits from
both. But he has to mention Turtles and Green-animals in some order. If he
mentions them in the above order, he gets the wrong blush-method; if he reverses
them he gets the wrong noseup-method.

The solution is to reformulate the classes into more parts with hairy
relationships.  A similar problem can happen when a user wants to inherit
slots.  One can imagine an asymptotic situation where each DEFCLASS has
exactly one slot and you build your classes by the shopping cart method.

The user of the above class lattice believes that the CPL will reflect a
breadth-first CPL. The depth-first nature of all CPL computations so far
reflects a desire for ``transparency'' of subclass-superclass inheritance.
Perhaps we need to have a notation for inheriting from a set of
superclasses in no partocular order, which would signal the CPL
computation to go breadth-first. Maybe another partial solution is some
means of having generic functions be able to distinguish instances of
``this very class'' rather than instances of this very class or of its
subclasses.

In any event, what we are doing by defining the CPL computation as we 
are is to provide a mechanism for people to curse the standard. Perhaps
it is necessary to have such a well-defined default, but maybe we should think
about a variety of alternatives from which the user can select as well
as an alternative to roll your own.

			-rpg-