Re: Class Precedence List: Rebuttal to Danny

[Danny Bobrow <Bobrow.pa@Xerox.COM>]

    Danny writes:

    ``This primacy [of the preorder] is good I claim, because in
    the simple (and usual) case it describes the result of the sort.''

    I guess Danny means that he expects most people will build a
    tree, except for the lattice requirement of the class named T being
    at the top; in this case he's right.  But, if you have almost any
    nontrivial structure to the upper part of the lattice, it is a big
    mistake for users to adopt this mental model.

There is a simple rule.  If any mixin appears more than once, and not in
last position in the local supers, then the user must apply the movement
rules.  I claim this is relatively rare, although it is easy to
construct examples.  (Dave do you have data on this?  How many flavors
have components that share mixins where the mixins are not last in the
chain?)

Thus it is both easy to construct the usual list, and easy to know when
the movement rules are to apply.

The example you give is clearly has the property I gave, and the
movement rule is easy for this case.
(defclass c1 () ())
(defclass c2 () ())
(defclass c3 () ())
(defclass e1 (c1) ())
(defclass e2 (c2) ())
(defclass e3 (c3) ())
(defclass e4 (e3 e2 e1) ())
(defclass e5 (c1 c2) ())
(defclass e6 (c2 c3) ())
(defclass e7 (e5 e6 e4) ())

 He eliminates duplicates from the front of the list:
   (E7 E5 E6 E4 E3 C3 E2 C2 E1 C1) 
Now going from the left, C3 depends directly on C2, so move it past all
of it dependendents (this means C1).  Then coming to C2, move it past
its dependents getting
   (E7 E5 E6 E4 E3 E2 E1 C1 C2 C3)
 
    Danny writes:

    ``It is primary in how people will try to simulate the
    algorithm.''

    I think we should discourage users from using preorder to
    simulate the algorithm. They will lose unless the lattice is mostly
    like a tree.  I think users knowing that the local precedence
    orders are very important and providing tools to look at the total
    orders at classes is the only good option.

I think it is foolhardy to try to discourage programmers from thinking
about algorithms.  They are not mathematicians.  Who could argue that it
is bad to provide tools to look at the total orders at classes, but for
understnadability off line, they should have an easy way to think about
construction of the list.

    Danny asks:

    ``How does the topological sort algorithm state the error
    condition about loops?''

    The sort terminates when it can not find a class that is
    preceeded by no others. If, when the sort terminates, there are
    classes left to be sorted, then there is a loop in the relations.

I don't understand.  If e3 in the above example had (c3 c2) as supers,
where would it fail?

    Danny asks:

    ``What determines the order of fruit and spice [in Moon's
    algorithm]? What determines the order in your algorithm except the
    preorder?''

    In Moon's algorithm the preorder determines it along with the
    fact that the local precedence orders never veto the preorder
    constraint.

    In my algorithm the preorder arbitrates.

Sounds like the preorder determines it.  Moons constraints don't
determine it though -- only the algorithm (except for the "hidden"
flavor rule he told us about.)

    The point of this variable is that the explicit constraints
    that the user writes - the subclass-superclass relations and the
    local precedence orders - ought to uniquely determine the total
    order, because these are the only things that he directly
    manipulates. When the class precedence list computation relies on
    the preorder, it is looking at some more global structure of the
    lattice when the direct constraints underconstrain the total order.

But you ignore the fact the the user does not want to directly constrain
the total order.  If two mixins C1 and D1 live in a hierarchy, and C1
inherits from C2 inherits from C3, and D1 from D2 and D2 from D3, then
anything that contains C and D will have many possible total orders.
Did I care?  Didn't I want a fixed one obeying Moon's hidden rule, so
that splitting a class doesn't change behavior.  So no variable either.

    I think the document requires a ``"meaningless"'' bottom
    element, which is the class named NIL.

We could merely apologize for the slight misuse of the term "lattice"
and call it one from then on.  Possbily alluding to the fact that the
user has been allowed to not be burdened with the NIL class.

    I've already explained why I think your algorithm results in
    potential confusion in readers of a description of it. Of course,
    your algorithm has been, up to now, subjected to no very strenuous
    writing onslaught.

I think I have answered you, and good writing is indeed called for. 
   
  danny