Class Precedence List

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

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

    I've been searching for a way to explain the class precedence list
    computation that is simpler than the existing explanations.  I think we
    can explain it fairly well if we relax, a bit, the requirements of
    implementations, though we can certainly recommend that implementations go
    the extra distance. What I'm proposing is a subset of the behavior that
    the Moon algorithm has, but it is simple to explain and understand.

I'm not thrilled with any "standard" where it is legal for different
implementations to produce different results for the class precedence
list.  That could lead to needlessly obscure portability problems.
(I think Dick changed his mind on this, judging by a later message, but
I'd like to get explicit confirmation in case I'm jumping to conclusions.)

    ....If D is a direct superclass of C, where C is in CL, then (C,D) is in the
    partial order. If D1 and D2 are direct superclasses of C, where C is in
    CL, such that D1 precedes D2 in the local precedence order, then
    (D1,D2) is in the partial order. (Note, these correspond to Moon's rules 1
    and 2, but we explicitly list the pairs of relations, and we deal with
    direct superclasses only.)

These are identical to "my" rules 1 and 2.  If you thought those rules
didn't apply to direct superclasses only, then you were misled by the
inconsistent terminology in the concepts document (or by applying one
terminology while reading a version of it that was written with a
different terminology).

    Now we topologically sort the elements of CL. This is done as follows.
    Select a class C that is not preceded by any other. Put it first in the order.
    Remove C from CL and remove all pairs that mention it. This new CL is again
    partially ordered by the new pairs. Select a C that is not preceded by
    any other and put it next in the order. Continue until CL is empty.

This is a fairly good description of the Lisp code I mailed out some months
ago, except that it prefers treewalk order when it has a choice, rather than
making an arbitrary choice.  I can mail it out again if you like.

    If there are several total orders, the result of the topological sort depends
    on the order that the algorithm selects classes that are not preceded by
    any others. This depends, generally, on the order that the DEFCLASS's were
    evaluated.

    I propose that we require implementations to select a total order using an
    implementation of topological sort, and that we encourage implementations
    to signal an error when several total orders are possible.

The referenced message (sent 22 Nov 86) was a discussion of why this
(signal an error when several orders are possible) won't work.  Until I
did that research I had thought it was a good idea.

I don't see any harm in mentioning the concept of topological sort in the
documentation of how the precedence list is computed, although when we were
writing the Flavors documentation we decided that it obscured more than it
clarified.  Perhaps you feel the CLOS standards document is aimed at a more
mathematically sophisticated audience.

    [from a later message from Dick]
    I believe that this algorithm produces the same results as
    the New Flavors algorithm, but it is easier to explain: 1. Compute the
    partial order relations; 2. topologically sort; 3. when topological sort
    has a choice of several classes to put next, select according to preorder.

That sounds identical to the so-called New Flavors algorithm to me.  Is
this just an issue of the particular words used to describe it, or is
there something more going on that hasn't penetrated my head yet?

Danny: I may have missed your last message on the subject, since I only
remember messages containing algorithms that didn't work.  Could you
send me a message reference or at least a date?  (then I can retrieve
your message from one of the mailing list archives).