[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*: 08 Jan 87 2001 PST

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-

- Prev by Date:
**What's left to do** - Next by Date:
**Issues for the CLOS committee to start focussing on** - Previous by thread:
**Re: Class Precedence List** - Next by thread:
**Re: Class Precedence List** - Index(es):