CPL Tiebreaker

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

    Date: 29 Jan 87  0206 PST
    From: Dick Gabriel <RPG@SAIL.STANFORD.EDU>

    I think I found the tiebreaker....
    ....is based on this reasoning by Danny (I'll paraphrase):

    ``If the user has a class and splits that class into two classes with no
    other references to the direct superclass, there should be no chance of
    any interaction with any other class used as a mixin. Hence one wants all
    superclasses of a class to follow as soon as possible after the class they
    are related to.''

I agree.

    This is very intuitive, and preorder treewalk is very intuitive. So
    we do Danny's condition first and then preorder treewalk.
    Danny's condition means this: 

    We define a relation called unique direct subclass. C is the unique direct
    subclass of D if C is the only direct subclass of D.  If class X was just
    output and X is a unique direct subclass of some class D, D immediately
    follows X.  Otherwise, ties are broken by preorder treewalk (not
    last-visited).

I don't think this really makes it, although it comes quite close and has
very much the character of what I've been looking for.  One problem is that
a class with two direct subclasses shouldn't really be treated completely
differently from a class with one direct subclass.  A worse problem is
multiple superclasses: a single class X can have two direct superclasses Y
and Z, where X is a unique direct subclass of both Y and Z.  Y and Z can't
both go immediately after X, and furthermore when you put in Y you can get
direct superclasses of Y, which must go either before or after Z.  When I
tried this algorithm it soon foundered on those problems, but it did
stimulate me to think of another algorithm:

When topological sort finds multiple candidates to go in next, choose the
candidate that has a direct subclass rightmost in the class precedence list
computed so far.  If that subclass has more than one direct superclass
among the candidates, take the superclass that is most specific according
to the subclass's local precedence order.  In more technical language,
let {N1,...,Nm} be the candidates to go in next and {C1,...,Cn} be the
class precedence list constructed so far; C1 is the starting class and
is most specific, Cn is least specific.  m>=2, n>=1.  For i from n down
to 1, let {S1,...,Sk} be the direct superclasses of Ci, k>=1, then for
j from 1 up to k, if Sj is an element of {N1,...,Nm}, set Cn+1 = Sj and
proceed with the topological sort.

This algorithm does a good job of keeping related classes together.  I like
this algorithm and I think we should adopt it.  I added the above
paragraph to the document version that Sonya just finished editing;
it's on SU-AI now and we will be proofreading it tomorrow.

My trial implementation of this algorithm is extremely stupid, involving
three nested loops and no optimization whatever, yet is not perceptibly
slower than any of the others I've been trying, which surprised me.  I'm
sure an algorithm wizard could write it much better.

I've tried this against all the flavors that happened to be defined in my
machine and it produces the same result except in the cases where the
flavors algorithm is broken.  I plan to try it on some other Flavors
programs later.  In the relatively simple cases (such as the ones I deleted
out of the message I'm replying to) this produces the same answer as the
previous Gabriel algorithm and the Bobrow algorithm.