[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: ECOOP Reaction to CLOS



Some comments on characterizing the class precedence list algorithm.
In my comments I will refer to this set of classes (slots omitted):

(defclass a (b c w))            w   x  w   y w  x
(defclass aa (b c d w))          \ /    \ /   \/
(defclass b (w x))                b      c    d   w
(defclass c (w y))                 \     |   /   /
(defclass d (w x))                   \   | /   /
(defclass w ())                        \ |/  /
(defclass x ())                          aa
(defclass y ())

We've seen these classes before.  By the rules in 87-002,
the CPL of a is (a b c w y x) and of aa is (aa b c d w x y).

    Date: Thu, 9 Jul 87 13:24:38 pdt
    From: Jim Kempf <kempf%hplabsz@hplabs.HP.COM>

    The inheritance graph is searched depth first, left to
    right, up to joins. Superclasses at joins are placed
    in the class precedence list at the last occurance,
    rather than the first, since such superclasses are
    usually more general than their subclasses, and classes
    at the end of the class precedence list should be more
    general than those at the beginning. The qualitative
    effect is to achieve a linearization of the inheritance
    graph, with more specialized classes at the head of
    the class precedence list and more general classes at
    the tail, keeping together groups of classes which occur
    together in the inheritance graph.

    A more detailed explantion should go into what can go wrong. The
    Ducournau and Habib paper discusses this in a more formal way....

I like this informal way of explaining it, except that I never figured
out precisely what "up to joins" means, and depending on the
interpretation of that phrase, this explanation could be incorrect.
When the depth first walk of the graph for aa above encounters w above
c, that's a join.  If it goes on to y, I don't think y is a join,
nevertheless y is not next in the CPL, x is.

    Date: 06 Jul 87  1130 PDT
    From: Dick Gabriel <RPG@SAIL.STANFORD.EDU>

    What would constitute an understandable characterization of the CPL?
    Here are some examples of approaches:

    1.  We could have a set of constraints on the classes such that the CPL
    is the unique total ordering satisfying those constraints.

If I understand the meaning of constraints as being additive, the
example above shows that it can't be done with constraints.  Taking a
and adding d to make aa reverses the order of x and y, thus whatever
constraint was controlling the order of x and y must have been removed
when d was added.  Perhaps this nonadditiveness is at the root of
people's difficulty in understanding the CPL computation.

    2.  We could have a set of inheritance situations such that when two
    graphs of classes were inherited in particular ways, the new CPL was
    predictable. For example, suppose we have 2 graphs, G1 and G2, with no common
    classes except for the class named T and suppose that C1 and C2 are the
    bottom-most classes of G1 and G2, respectively; then if a class C is
    a subclass of C1 and C2 in that order, the classes in G1 precede the classes
    in G2, and the classes in G1 are in the same order as they are in the CPL
    for C1 and similarly for G2; T comes last.

Characterization #2 is in fact true, and it's not too hard to see why.
Suppose G1A is the second class in C1's class precedence list.  After
topological sort has added C1 to C's cpl, the rule at the top of page
1-15 comes into play because either C2 or G1A could be next.  The rule
selects G1A.  By what amounts to induction, one can show that every
class in G1 will have a direct subclass to the right of C2's direct
subclass (C), and therefore every class in G1 will precede C2.  I believe
one can also show that the classes in G1 will appear in the same order in
C's cpl as in C1's cpl.  I don't think it's a coincidence that
characterization #2 is true, I think making it true was one of the
acceptance criteria for the CPL algorithm.

The problems occur just when G1 and G2 do have common classes (other
than T).