Class-precedence-list computation

[David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>]

Dick, your algorithm does not produce the same results as the Flavors
algorithm, assuming that I didn't make any mistakes in coding it
based on the description in the current document.

The topological sort is the same, but the resolution of cases where the
topological sort has several choices is not the same.  The simplest test
case I could construct to demonstrate this is:

(DEFCLASS PTEST1 (PTEST2 PTEST3 PTEST5) ())
(DEFCLASS PTEST2 (PTEST5) ())
(DEFCLASS PTEST3 (PTEST4) ())
(DEFCLASS PTEST4 () ())
(DEFCLASS PTEST5 () ())

(PREORDER 'PTEST1) is (PTEST1 PTEST2 PTEST5 PTEST3 PTEST4)

Flavors order is (PTEST1 PTEST2 PTEST3 PTEST4 PTEST5 T)
Gabriel order is (PTEST1 PTEST2 PTEST3 PTEST5 PTEST4 T)

I couldn't find a test case with fewer than five classes.

I wrote a program to try both sets of rules on a bunch of Flavors-based
programs and show the difference not only in the class precedence list,
but in the inheritance of methods.  I haven't fully evaluated the
results yet, but they seem to show that the Gabriel algorithm, although
it seems very straightforward, actually produces rather surprising
results.  Here is an example that I boiled down from a real Flavors
example (the real example had a lot more classes, but the bulk of them
were irrelevant to the issue).  I changed all the names to protect the
innocent:

(DEFCLASS PPTEST1 (PPTEST-MIXIN PPTEST2 PPTEST3) ())
(DEFCLASS PPTEST-MIXIN (PPTEST3) ()) 
(DEFCLASS PPTEST2 (PPTEST-INTERMEDIATE-1) ())
(DEFCLASS PPTEST3 (PPTEST-INTERMEDIATE-2) ())
(DEFCLASS PPTEST-INTERMEDIATE-1 (PPTEST-BASE) ())
(DEFCLASS PPTEST-INTERMEDIATE-2 (PPTEST-BASE) ())
(DEFCLASS PPTEST-BASE () ())

Flavors order:
  PPTEST1, PPTEST-MIXIN, PPTEST2, PPTEST-INTERMEDIATE-1, PPTEST3,
  PPTEST-INTERMEDIATE-2, PPTEST-BASE, T
Gabriel order:
  PPTEST1, PPTEST-MIXIN, PPTEST2, PPTEST3,
  PPTEST-INTERMEDIATE-2, PPTEST-INTERMEDIATE-1, PPTEST-BASE, T

Here the surprising thing is that PPTEST-INTERMEDIATE-1 is made less
specific than PPTEST-INTERMEDIATE-2.  That's because PPTEST2 comes
-after- PPTEST3 in the preorder treewalk, even though PPTEST2 is
explicitly specified to come before PPTEST3 in the class precedence
list.  PPTEST3 sneaks into the preorder treewalk early via PPTEST-MIXIN,
but cannot be earlier than PPTEST2 in the class precedence list.

The preorder is:
  (PPTEST1 PPTEST-MIXIN PPTEST3 PPTEST-INTERMEDIATE-2
   PPTEST-BASE PPTEST2 PPTEST-INTERMEDIATE-1)

I think this shows that the preorder treewalk is not a very good model
of the desired precedence order.  It's intended as an approximation to
the Flavors rule of putting things in as they are encountered in the
treewalk (that damn rule for which we have yet to come up with a
coherent statement, except in Lisp code, that makes sense to anyone),
but it's an insufficient approximation.

It's true that the user did not explicitly declare that
PPTEST-INTERMEDIATE-1 is more specific than PPTEST-INTERMEDIATE-2, but
it's a surprise to find that the superclasses are in the reverse order
of the subclasses.  For more discussion of that, see the message I sent
on 22 November.

I'm not sure yet where we should go from here.  Flavors-based programs are
the only reservoir of real-world examples easily available to me.  Someone
might want to argue that they are all garbage and we have no lessons to
learn from them, but I won't be convinced by anything less than another
body of real-world experience that produces opposite conclusions.  Probably
the most productive thing for me to do next would be to think about a
coherent statement of that Flavors rule designed to fit into the framework
of Dick's explanation of class precedence computation, where the preorder
treewalk is now.

I haven't tried coding Danny's algorithm (proposed a month or two ago)
yet.  I wonder if it does the same thing as either of these other
algorithms.