[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Class Precedence List
- To: common-lisp-object-system@SAIL.STANFORD.EDU
- Subject: Class Precedence List
- From: David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>
- Date: Tue, 6 Jan 87 00:53 EST
- In-reply-to: The message of 3 Jan 87 01:31 EST from Dick Gabriel <RPG@SAIL.STANFORD.EDU>
- References: <861122002029.5.MOON@EUPHRATES.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
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
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).