[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: common-lisp-object-system@SAIL.STANFORD.EDU*Subject*: Class Precedence List*From*: Dick Gabriel <RPG@SAIL.STANFORD.EDU>*Date*: 02 Jan 87 2231 PST

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

- Next by Date:
**STANDARD-TYPE-CLASS** - Next by thread:
**Re: Class Precedence List** - Index(es):