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

*To*: common-lisp-object-system@SAIL.STANFORD.EDU*Subject*: Elaboration on the Non-intuitiveness of New Flavors Algorithm...*From*: Dick Gabriel <RPG@SAIL.STANFORD.EDU>*Date*: 27 Jan 87 1801 PST

...and other related issues. Remember the funny little configuration of classes mentioned in an earlier message (defclass Ai (Bi Ci) ()) (defclass Bi (Di Ai+1) ()) (defclass Ci (Di) ()) (defclass Di () ()) for 0 <= i < n. Here's what it looks like: A1 D0 / | \ / | \/ | /\ | / \ B0 C0 \ / \ / \/ A0 Suppose we are following the New Flavors description of how to compute the CPL for A0. We start walking through this in depth-first manner starting at A0. We visit/output A0, visit/output B0, visit D0, visit A1, visit/output C0, and then visit/output D0. There is no path in depth-first order with which to get to A1 again, so the first depth-first pass is over. We notice A1 has not been output and walk it again, outputting A1 last. If A1 is the root of another copy of this, we cannot visit up through it on the first pass. If there are classes to the right of A0, they wil be visited and probably output during the first pass. When the second pass is made, A1 will be output. Let's call this configuration the ``MeLast.'' Now consider the following configuration: T1 T2 T3 | | | D E F \ | / \ | / \ | / \|/ C where C is a class and T1, T2, T3 are independent lattices, except for a common top. What does intuition say? It says that all of T1 should be together, all of T2 should be together, and all of T3 should be together, each group in in some order relative to one another, and the order within each group unknown. One could argue T1 should precede T2 should precede T3, but I won't. Suppose that T1 has a MeLast in it, and neither T2 nor T3 does. Then some part of T1 - namely A0, B0, C0, and D0 - will come early on, then parts of T2 and T3, and finally A1 will be last. Similar situations hold for T2 and T3, but in all cases, A1 will be last, assuming there are no other MeLast-like configurations in the T groups. The intuition is gone. Here is an example: MeLast | X Y Z \ | / \|/ W The New Flavors order is: W,X,Y,A0,B0,C0,D0,Z,A1 The gabriel order is: W,X,Y,A0,B0,C0,D0,A1,Z Notice that in the gabriel order, the Y/MeLast guys are together between Y and Z. The existence of a MeLast configuration is purely an artifact of the multiple passes that the New Flavors CPL computation does. If it had a way to remember to redo A1 as soon as its predecessor, D0, was cleared up, it would not need to make another pass through the lattice. The MeLast configuration also proves that no algorithm based on topological sort with a tiebreaker that is like a single-pass, single-stack treewalk is equivalent to the New Flavors computation. I haven't thought through the exact constraints, but preorder, reversed reversed postorder, and things like that as the tiebreaker in conjunction with topological sort cannot be the same as New Flavors, because they will put classes in the groups T1, T2, and T3 together. This increases the strength of my belief that the New Flavors algorithm is not suitable for the CLOS standard. -rpg-

- Prev by Date:
**Re: CPL Update** - Next by Date:
**Re: ---** - Previous by thread:
**CPL Computation** - Next by thread:
**Re: Elaboration on the Non-intuitiveness of New Flavors Algorithm...** - Index(es):