[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Class Precedence List: Rebuttal to Danny
- To: RPG@SAIL.STANFORD.EDU
- Subject: Re: Class Precedence List: Rebuttal to Danny
- From: Danny Bobrow <Bobrow.pa@Xerox.COM>
- Date: 9 Jan 87 16:59 PST
- Cc: common-lisp-object-system@SAIL.STANFORD.EDU
- In-reply-to: Dick Gabriel <RPG@SAIL.STANFORD.EDU>'s message of 09 Jan 87 11:54 PST
- Sender: Bobrow.pa@Xerox.COM
``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
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)
``It is primary in how people will try to simulate the
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.
``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?
``What determines the order of fruit and spice [in Moon's
algorithm]? What determines the order in your algorithm except the
In Moon's algorithm the preorder determines it along with the
fact that the local precedence orders never veto the preorder
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
I think I have answered you, and good writing is indeed called for.