Class Precedence List: Rebuttal to Danny

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

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.

Here is a possibly too large and too ugly example:

(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) ())

If a user does a preorder treewalk to guess how the total order will
look, he will get the following. 

1. If he eliminates duplicates from the front of the list:
   (E7 E5 E6 E4 E3 C3 E2 C2 E1 C1) 

2. If he eliminates duplicates from the rear of the list:
   (E7 E5 C1 C2 E6 C3 E4 E3 E2 E1) 

Meanwhile, the total order looks like:
   (E7 E5 E6 E4 E3 E2 E1 C1 C2 C3)

Well, option 1 is correct to the halfway point, so I suppose half right is
better than nothing. On the other hand, option 2 gets the critical
and curious relatives order of (E3,E2,E1) and (C1,C2,C3) right. Hard to
know which a user would be better off with.

I should mention, as a curiosity, that my algorithm makes no appeal to the
preorder when computing the class precedence list for E7: The user would
be, therefore, encouraged to use the very thing that is irrelevant to the
total order to intuit that total order.

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.

Danny writes:

``There is no question about whether the algorithm terminates....''

I agreed it is clear to me that the algorithm terminates. I stated that
a reader might be puzzled by this question.

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.

Danny writes:

``    	EXAMPLE 2 (not repeated here)

    admits a single possibility by his rules, which is

    (pie apple fruit cinnamon spice food)

Not by my interpretation of his rules....''

This is the example Moon uses in the document ``Common Lisp Classes:
A Draft Object-oriented Standard'' on page 30 under the heading ``Example
of a Tree Walk.'' I claim it admits a single possibility by Moon's
interpretation of Moon's rules.

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.

Danny writes:

``  [quote: rpg]
    I also propose that implementations be encouraged to offer a
    means of warning or signalling an error every time that appeal is
    made to the preorder.
    [unquote: rpg]

Again this is the usual case where one has independent mixins with
superclasses.  So no warning please.''

I suppose I should be more precise with my language.

I propose that implementations be encouraged to provide a special variable
called *warn-on-nondeterminism-in-topological-sort*, for example, whose
default value is NIL and such that when its value is non-null the
algorithm that computes the class precedence list warns the user (or
signals an error) when it encounters a situation in which the topological
sort cannot uniquely determine a total order from the partial orders.

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.

``So no warning please'' translates into (setq *warn...* nil).

Well, I won't press on this issue too much. I think, however, that without
tools to display the class precedence list programmers will be stumped
a lot of the time.

Danny writes:

``By the way, this DAG is not a lattice in that there is no "meaningful"
lower bound for any two classes.  But I believe we have agreed on a top of
T in any event.''

I think the document requires a ``"meaningless"'' bottom element, which is
the class named NIL. If we decide we don't like that, then we can describe
it as a set of lattices rooted at the class named T, or as a directed
acyclic graph with a distinguished element that is the class named T.  I
think it's nicer to say we have a lattice than a set of lattices or a
directed acyclic graph, but this, I believe, is a matter of taste. Except
for being able to state that one aspect of the partial order on the
structure is the lattce order, there is no reason for it - we can always
explain that when you compute the class precedence list for a class, you
have a lattice with top the class named T and bottom that given class.

The meaningless bottom element can have a local precedence order that reflects
the order in which the classes directly above it were created.

Danny concludes:

``So my conclusion is that your description is a good mathematical one,
and should be included.  Mine is a good operational one, and should be
included.  And both agree with Moon's algorithm with the other Flavors
rule, so we are all right.''

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.

			-rpg-