CPL Tiebreaker

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

Ugh, bletch. I think I am really going to regret having written
this message. I think I found the tiebreaker. It passes all of
the hard intuitive cases, which I'll list below, along with all
of the cases ever mailed out.

The tiebreaker applies when there is more than one class with
no predecessors. The tiebreaker has two cases. The first case
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.''

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

This means that we treat parts of the lattice that look like this:

               \|/
		D
		|
		C
               /|\

as if they looked like this:

               \|/
              (D,C)
               /|\

[Actually, the above picture is exactly how I looked when I discovered
this tiebreaker.]

Here are the hard cases:

(DEFCLASS A (B C D E F) ())
(DEFCLASS B (F X) ())
(DEFCLASS C (F Y) ())
(DEFCLASS D (F X) ())
(DEFCLASS E () ())
(DEFCLASS F () ())
(DEFCLASS X () ())
(DEFCLASS Y () ())

(topologically-sort 'a) = (A B C D E F X Y) 

Well, this is simply preorder treewalk at work.

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

(topologically-sort 'ptest1) = (PTEST1 PTEST2 PTEST3 PTEST4 PTEST5) 

In this one, PTEST3 is the unique direct subclass of PTEST4, so when
PTEST3 is output, PTEST4 and PTEST5 could come next. Preorder would
say PTEST5 is next, but Danny's rule overrides that.

(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 () ())

(topologically-sort 'pptest1)
 = (PPTEST1 PPTEST-MIXIN PPTEST2 PPTEST-INTERMEDIATE-1 PPTEST3
    PPTEST-INTERMEDIATE-2 PPTEST-BASE) 

This one is nearly the same as the one before.

This addition condition adds no complexity to the algorithm, because
we compute the in-degrees of each class at DEFCLASS time.

			-rpg-