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

*To*: common-lisp-object-system@SAIL.STANFORD.EDU*Subject*: CPL Computation*From*: Dick Gabriel <RPG@SAIL.STANFORD.EDU>*Date*: 27 Jan 87 1207 PST

As I've mentioned earlier, I wasn't interested in proposing a new definition of the CPL computation different from what Flavors presents but in proposing a clear way of describing it. I took Moon's suggestion and looked for a different ``tiebreaker'' from preorder treewalk. I have a simple way to describe it, but the naive implementation has bad running behavior. The fast version is describable, but the description is horrendous. I think we want to consider what this all means once the algorithms are presented. The algorithm is precisely as before, but when the topological sort would nondeterministically select one class from among a set of equally good ones, you choose based on a last-visited preorder treewalk. A last-visited preorder treewalk is defined in terms of the order in which classes are visited while performing a process called ``walking from a class.'' The following is a recursive definition of walking from a class. Let C be a class and let {C1...Cn} be its direct superclasses in the local precedence order. To walk from C, first C is visited, then we walk from C1, then we walk from C2, and so on until we finally walk from Cn. If a class has been visited before, you ignore that visit. That is, the order is the order in which the last visits to a node are made. Normally, one computes the preorder treewalk order as a number attached to the class. Again normally, this number is computed by performing the preorder treewalk and INCFing a counter. In a preorder treewalk, when a class already has a preorder number, you do not re-visit that class; the modification to normal preorder treewalk to obtain last-visited preorder treewalk is to eliminate this last pruning. The tiebreaker simply looks at these preorder numbers, choosing the class with the smallest preorder number. Notice that a lot of pruning might have been done by the original preorder walk and that the last-visited preorder walk eliminates all of the pruning. Here is some crufty code to compute the normal preorder number into a slot of the class called the PREORDER: (defun preorder-walk (class) (cond ((< 0 (preorder class))) ;already visited (t (setf (preorder class) (incf *preorder-counter*)) (dolist (superclass (direct-superclasses class)) (preorder-walk superclass))))) Here is the modified code: (defun lv-preorder-walk (class) (setf (preorder class) (incf *preorder-counter*)) (dolist (superclass (direct-superclasses class)) (lv-preorder-walk superclass))) This is, of course, less efficient than the previous code, though it looks simpler. One can get a fast algorithm by doing what could be called a reversed reversed postorder treewalk (``moonwalk,'' for short). We define reversed postorder treewalk and then modify that to be reversed reversed postorder treewalk. A reversed postorder treewalk is defined in terms of the order in which classes are visited while performing a process called ``walking from a class.'' The following is a recursive definition of walking from a class. Let C be a class and let {C1...Cn} be its direct superclasses in the local precedence order. Classes are visited unless they have already been visited. To walk from C, first we walk from Cn, then we walk from Cn-1, and so on until we finally walk from C1. Finally we visit C. A reversed reversed postorder treewalk visits classes in precisely the reverse order that they are visited in a reversed postorder treewalk. Implementationally, moonwalk isn't too bad. You place reversed postorder numbers on each class at or above the class of interest, and ties are broken by selecting the class with the largest reversed postorder number (note that we chose the smallest number in the preorder tiebreaker). Selecting the largest effects the second reversing. Here is the code to do this: (defun walk (class) (cond ((< 0 (rpostorder class))) (t (dolist (superclass (reverse (direct-superclasses class))) (walk superclass)) (setf (rpostorder class) (incf *counter*))))) This algorithm works on all of the examples I sent before plus the two killers Moon sent Sunday. The question now becomes: Is this what we really want? I claim that it doesn't matter too much what the tiebreaker is, because it is always possible to reformulate the lattice and use direct superclasses to achieve the desired effect. The fact the there are millions of flavors that use the moonwalk tiebreaker doesn't support the claim that the moonwalk tiebreaker is right: Perhaps the flavors have been carefully crafted to inherit properly. The explicit local precedence orders are the means by which programmers specify the ordering they want. The tiebreaker simply makes the total order well-defined. The tiebreaker is not intended to be a ``model'' of the class precedence list. If the topological sort produces a unique order, that order is intuitive; the cases where tiebreaking happens is ad hoc and is no intuitive. In the spirit of trying to figure out the New Flavors algorithm in order to be able to present it well, my algorithms wizard and I have tried come up with a more easily explainable algorithm that mimics the New Flavors and does not have topological sort as an explicit part of it. We failed, though we have not yet written down an example for which it fails. [I only mention this because I promised to show this algorithm in my last message.] Finally, I'm not sure that the first of Moon's killers has a very intuitive Flavors order. Here it is again: (DEFCLASS PTEST1 (PTEST2 PTEST3 PTEST5) ()) (DEFCLASS PTEST2 (PTEST5) ()) (DEFCLASS PTEST3 (PTEST4) ()) (DEFCLASS PTEST4 () ()) (DEFCLASS PTEST5 () ()) The Flavors order is (ptest1 ptest2 ptest3 ptest4 ptest5). Why is ptest4 before ptest5? Here's what the thing looks like: top------ | | pt4 | | | |-----------pt5 | | / pt2 pt3 / \ | / \ | / pt1 pt5 is a direct superclass of pt1 and pt4 isn't. One could argue that pt5 is the last of the direct superclasses, so it should come after the earlier direct superclasses and all of their superclasses; in this case you get to pt4 first because it is above pt3, which precedes pt5. But, does being mentioned first in a defclass count for anything? If so, you get to pt5 by passing through the first of the direct superclasses of pt1 (pt1 to pt2 to pt5) whereas you get to pt4 by passing through the second of the direct supeclasses of pt1 (pt1 to pt3 to pt4), and there are exactly the same number of intermediate classes. Everything says pt5 should precede pt4, but Flavors doesn't. I believe this to be a serious problem. Finally, my algorithms wizard and I studied the New Flavors CPL computation description and think there is a performance problem with the algorithm it describes. Consider the following graph of 4n+1 classes: (defclass Ai (Bi Ci) ()) (defclass Bi (Di Ai+1) ()) (defclass Ci (Di) ()) (defclass Di () ()) for 0 <= i < n. Here are the classes for n=2. (defclass a0 (b0 c0) ()) (defclass b0 (d0 a1) ()) (defclass c0 (d0) ()) (defclass d0 () ()) (defclass a1 (b1 c1) ()) (defclass b1 (d1 a2) ()) (defclass c1 (d1) ()) (defclass d1 () ()) The New Flavors algorithm, as described, seems to take n+1 passes, though there is exactly one total order possible. Given that reversed reversed postorder treewalk (or last-visited preorder) is the tiebreaker, that there is at least one suspicious Flavors-order example, that people can formulate their lattices as they want to get the right inheritance, that there is no intuition to any order beyond what the topological sort gives you, and there is a possible performance problem with the algorithm described in the New Flavors document, I have now flipped my bit on this issue from wanting to mimic the Flavors order to insisting on preorder tiebreaker with topological sort. -rpg-

- Prev by Date:
**Re: ---** - Next by Date:
**Re: CPL Computation** - Previous by thread:
**Re: CPL Update** - Next by thread:
**Re: CPL Computation** - Index(es):