Class Precedence List

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

I am not necessarily trying to devise a new algorithm, but to duplicate
the current one in such a way that explaining how it works is easier. I
also have the goal of structuring the explanation so that the parts of the
algorithm that are important correspond to easily identifiable portions of
the explanation.

Here are the important parts of the algorithm, presented in increasing
order of importance:

1. We are embedding a partial order in a total order.

2. The important relations in the partial order are the lattice
order and the local precedence orders.

3. In case the lattice and local precedence orders underspecify the
total order, we use preorder treewalk order to specify it.

How does Dave's and Danny's explanations match up to these strictures?

Everyone's explanation states that a partial order is being embedded
in a total order.

Moon first:

Moon's first two rules state number 2 pretty well, but they leave
open the consideration of whether direct superclasses or superclasses
are meant by ``a class always precedes its own superclasses.'' This
doesn't matter, except that some reader might be slightly confused.
We, of course, can state the meaning exactly in the document.

Moon's rule 3 states:

``Duplicate classes are eliminated from the ordering; if a class
appears more than once, it is placed as close to the beginning of the
ordering as possible, while still obeying the other rules.''

What duplicates? Does this mean the user did

(defclass foo ...)
....
(defclass foo ...)

That's silly. But it is an interpretation that some reader might
pursue first.

There are two interpretations. One is that the rule that states that a
class always precedes its superclasses can introduce duplicates. Does this
mean that this rule is inconsistent? The other possibility is that a treewalk
is done from the class in question, call it C, to the top of the lattice, and
the resulting list contains duplicates. The rest of the explanation, which
is a description of a treewalk with insertions at the end of a list, seems
to hint at the second possibility.

The reader, puzzled, goes on to read the description of the treewalk process.
He thinks that the treewalk is the primary means of establishing the order, and
that the contraints in Moon's rules 1 and 2 sometimes change that order. Then
he has to understand that the treewalk might have to be repeated to add classes
left out. Why are they left out? Will this algorithm terminate? 
Many intelligent readers will not believe that the predicate that tells
whether a class can be added at the end of the list being constructed can
be tested efficiently (one of Knuth's students wasn't sure; he believed the
algorithm did something reasonable after 15 minutes of study but could not
convince himself it could run efficiently.)

The impression that the treewalk is primay violates my third statement
that the lattice order and local precedence orders are the primary
determiners of the total order and the preorder is secondary.

Danny next.

Danny has three rules also. Rule 1 is:

C-1) A class appears only once on the list.

Hm. It couldn't be a total order is this weren't true. But extra
information is always ok, and we can make this part read well in
the document.

His rules 2 and 3 are simply the local precedence order and lattice
order rules, and well-stated.

Here is his explanation of what the class precedence list is. I
don't care about wording, but about what wrong impressions or 
incomprehensibilities will rise in the reader's mind.

``The class precedence list is a left to right, depth first linearization
of the transitive closure of inheritance from the local super classes of
a class.  It satisfies three constraints: <the three rules>''

The first sentence states that the class precedence list is a
linearization (total order) constructed by doing a preorder treewalk
and then making sure some constraints are followed. 

Then he goes on to give an algorithm that does the preorder treewalk, putting
classes that appear several times as far to the right as possible. This
list is then edited using his rules 1, 2, and 3.

This algorithm gives primacy to the preorder treewalk, and there is a
question about whether the algorithm terminates - though it's actually
easy to prove if the algorithm is stated clearly - and about how the
error condition is computed.

In my formulation, Moon's rules 1 and 2 and Danny's rules 2 and 3
are explicit and refer to direct superclasses. Topological sort
is used because many people know it already, if they don't it's
easy to explain and to prove correct, and it emphasizes that the
local precedence order and lattice order are primary.

The topological sort algorithm clearly highlights where the two
problematic situations arise (loops and multiple orders), and it
is easy to see how the loop (inconsistency) error is noticed. When
multiple orders are possible, it shows up as a choice among a set of
classes. The condition can be noted and the preorder treewalk information
is appropriately applied here. The reader can see where this secondary
constraint enters the picture. 

An explanation that depends on the mathematically known topological
sort lends some credibility that the concept of the class precedence
list and the algorithm for computing it are not ad hoc nightmares by
a group of crazed hackers.

Now, there is an interesting problem with the algorithm and explanation
that I gave, which is the situation with the example:

(defclass pie (apple cinnamon) ())
(defclass apple (fruit) ())
(defclass cinnamon (spice) ())
(defclass fruit () ())
(defclass spice () ())

 	EXAMPLE 1

This is one of Moon's examples. He states that his algorithm applied
to it produces an order, but that several other orders are possible.

The order his algorithm produces is:

	(pie apple fruit cinnamon spice)

and the other two orders are:

	(pie apple cinnamon fruit spice)
	(pie apple cinnamon spice fruit)

On the other hand, the example

(defclass pie (apple cinnamon) ())
(defclass apple (fruit) ())
(defclass cinnamon (spice) ())
(defclass fruit (food) ())
(defclass spice (food) ())
(defclass food () ())

	EXAMPLE 2

admits a single possibility by his rules, which is

(pie apple fruit cinnamon spice food)

Notice that the only difference between the two examples is that
the first is a true tree while the second is a lattice with a join
of FOOD. 

If we insist that the class directed acyclic graph be a lattice, there
there is a least upper bound for every pair of classes, and the first
example has an implicit top element. In this case the first example
would admit the same result as the second. Here are pictures of
the situations:

EXAMPLE 1:

fruit	spice
  |	  |
  |	  |
apple  cinnamon
  \       /
   \   	 /
    \   /
     pie

Notice that fruit and spice have no join.

EXAMPLE 2:

    food
    /   \
   /     \
fruit	spice
  |	  |
  |	  |
apple  cinnamon
  \       /
   \   	 /
    \   /
     pie

Here there is a join.

EXAMPLE 1':

      T 
    /   \
   /     \
fruit	spice
  |	  |
  |	  |
apple  cinnamon
  \       /
   \   	 /
    \   /
     pie

If there was a top element, call it the class named T, the first situation
would be this, which is the same as the original second situation (T is at
the top where FOOD would be). The original second situation would become

EXAMPLE 2':

      T
      |
    food
    /   \
   /     \
fruit	spice
  |	  |
  |	  |
apple  cinnamon
  \       /
   \   	 /
    \   /
     pie

Without requiring that the class DAG be a lattice, my algorithm
always produces a total order when there is one, while Moon's
will produce the same one, but will admit several other possibilities.
When the class DAG is further restricted to being a lattice, Moon's
algorithm and mine agree (I think). 

So, I propose that the class DAG should be required to be a lattice,
and because of that, I think, Moon's algorithm, Danny's, and mine are all
the same, and I think mine is the easiest to understand. I don't claim
superior skill at designing algorithms, because all I did was try to break
Moon's and Danny's algorithms down into the simplist terms.

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.

			-rpg-