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

*To*: common-lisp-object-system@SAIL.STANFORD.EDU*Subject*: Class Precedence List: Rebuttal to Danny*From*: Dick Gabriel <RPG@SAIL.STANFORD.EDU>*Date*: 09 Jan 87 1154 PST

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-

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