Elaboration on the Non-intuitiveness of New Flavors Algorithm...

[Dick Gabriel <RPG@SAIL.STANFORD.EDU>]

...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-