Class Precedence List

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

This message is long because there are a lot of examples of code running
at the end.

I've been searching for a way to explain the class precedence list
computation that is simpler than the existing explanations.  I think we
can explain it fairly well if we relax, a bit, the requirements of
implementations, though we can certainly recommend that implementations go
the extra distance. What I'm proposing is a subset of the behavior that
the Moon algorithm has, but it is simple to explain and understand.

Here it is. We represent a partial order as a set of pairs, (x,y), such
that (x,y) indicates that x<y.  Here are the assumed rules of the relation
<.

If x<y and y<z then x<z (transitivity)
If x<y then it is not the case that y<x  (asymmetry)
It is not the case that x<x (irreflexivity)

If x<y we'll say that ``x precedes y.'' We then define a partial order on
the components of a class, C1, as follows. Let CL be the components of C1.
If D is a direct superclass of C, where C is in CL, then (C,D) is in the
partial order. If D1 and D2 are direct superclasses of C, where C is in
CL, such that D1 precedes D2 in the local precedence order, then
(D1,D2) is in the partial order. (Note, these correspond to Moon's rules 1
and 2, but we explicitly list the pairs of relations, and we deal with
direct superclasses only.)

Now we topologically sort the elements of CL. This is done as follows.
Select a class C that is not preceded by any other. Put it first in the order.
Remove C from CL and remove all pairs that mention it. This new CL is again
partially ordered by the new pairs. Select a C that is not preceded by
any other and put it next in the order. Continue until CL is empty.

The only way that the algorithm could fail, if there really was a partial
order to start with, would be if there were elements in CL at some point
and every C in CL was preceded by another. If this were true, we could
construct an arbitrary sequence, C1, C2, ... such that Cj+1<Cj.  By
transitivity, for all j,k s.t. j<k, Ck<Cj, which implies that Cj is not
equal to Ck.  But CL is finite, so some Cj=Ck for some j,k s.t. j<k. This
is a contradiction.

So, if the algorithm fails, we did not have a partial order, which means that
the local precedence order and the lattice order are inconsistent. The algorithm
does signal an error when this happens.

Topological sort runs in C1*M+C2*N time where M is the number of ordered pairs
and N is the number of objects in CL, C1 and C2 some constants.

I hacked this together, and it is 27 lines of code once the data structure
is built. Building the data structure incrementally from a series of
DEFCLASS1's as Moon uses in his examples is another 25 lines of so of code.
The total file is 84 lines long, including the DEFSTRUCT and the code to
make MacLisp think it's Common Lisp enough to run the rest (blush, I
have no Common Lisp to use on SAIL).

The code is an approximate translation of Knuth's algorithm on page 262 of
vol 1 (first edition). It takes the precise DEFCLASS's that define the 
sublattice, but it's intended to only illustrate the algorithm at work.

If there are several total orders, the result of the topological sort depends
on the order that the algorithm selects classes that are not preceded by
any others. This depends, generally, on the order that the DEFCLASS's were
evaluated.

I propose that we require implementations to select a total order using an
implementation of topological sort, and that we encourage implementations
to signal an error when several total orders are possible. They can do
this using Moon's algorithm, for example, or by using the topological sort
and having the program notice when there are several classes not preceded
by others from which to select. It could backtrack and determine all of
them, I suppose.

I think this is simpler because many people know topological sort already,
they can understand the partial order in terms of these simple pairs, and
the topological sort algorithm can be explained in a paragraph. People can
also easily see where the non-determinism comes in if there are several
total orders. (Note that most people would know the algorithm after 
reading the specification of the partial order as those pairs and seeing
the phrase ``now topologically sort.'')

Here it is running on some examples Moon, Danny, Gregor, and who knows who
else sent out (notice I changed the name of DEFCLASS1 to DEFCLASS). TOP
means the top of the lattice.

(defclass c1 (c2 c6 c5) ())
(defclass c2 (c3 c4) ())
(defclass c3 (c5) ())
(defclass c4 (c6) ())
(defclass c5 (top) ())
(defclass c6 (top) ())
(topologically-sort) = (C1 C2 C3 C4 C6 C5 TOP) 

;;; Here are the partial order defining pairs for the above example:
;;; (c1,c2)(c1,c6)(c1,c5)(c2,c6)(c6,c5)(c2,c3)(c2,c4)(c3,c4)
;;; (c3,c5)(c4,c6)(c5,top)(c6,top)

(defclass c2 (c3 c4) ())
(defclass c3 (c5) ())
(defclass c4 (c6) ())
(defclass c5 (top) ())
(defclass c6 (top) ())
(topologically-sort) = (C2 C3 C5 C4 C6 TOP) 

(defclass c1 (c3 c2) ())
(defclass c2 (c3) ())
(defclass c3 (top) ())
(topologically-sort) = Inconsistent Lattice

(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass c4 (c1 c2) ())
(defclass c5 (c3 c2) ())
(defclass c6 (c4 c5) ())
(topologically-sort) = (C6 C4 C5 C1 C3 C2 TOP) 

(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass d4 (c3 c2) ())
(defclass d5 (c2) ())
(defclass d6 (c3 c2 d5 d4) ())
(topologically-sort) = Inconsistent Lattice

(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(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) ())
(topologically-sort) = (E7 E5 E6 E4 E3 E2 E1 C1 C2 C3)

(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass d1 (c1) ())
(defclass d2 (c2) ())
(defclass e1 (d1 d2) ())
(topologically-sort) = (E1 D1 D2 C1 C2 TOP)

(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass d1 (c1 c2) ())
(defclass d2 (c1 c3) ())
(defclass e1 (d1 d2) ())
(topologically-sort) = (E1 D1 D2 C1 C3 C2 TOP) 

(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass d4 (c3 c2) ())
(defclass d5 (c2) ())
(defclass d6 (c3 c2 d5 d4) ())
(topologically-sort) = Inconsistent Lattice

(defclass o (top) ())
(defclass b1 (o) ())
(defclass b2 (o) ())
(defclass b3 (o) ())
(defclass b4 (o) ())
(defclass ex1-1 (b1 b3 b4) ())
(defclass ex1-2 (b2 b3) ())
(defclass example-1 (ex1-1 ex1-2) ())
(topologically-sort) = (EXAMPLE-1 EX1-1 EX1-2 B1 B2 B3 B4 O TOP) 
ÿ