# Class Precedence List

• To: common-lisp-object-system@SAIL.STANFORD.EDU
• Subject: Class Precedence List
• From: Dick Gabriel <RPG@SAIL.STANFORD.EDU>
• Date: 30 Aug 87 1946 PDT

```On July 27 Kempf mailed a note about the description of the class
precedence list algorithm. Because I was away until yesterday, I
was not able to respond:

Kempf writes:

1) The use of the term "partial order" on pg. 1-15, paragraph 1
implies a relation on R which is reflexive, antisymmetric, and
transitive. From the text of the paragraph, this relation is
presumably the "is a subclass of" relation. However, earlier in
the document, reflexivity is explicitly excluded from the "is a
subclass of" relation (pg. 1-4, paragraph 3), since a class is
defined to be neither a superclass nor a subclass of itself.
Either the partial order needs to be replaced with a different
order not requiring reflexivity (semiorder, etc.)  or the "is a
subclass of" relation needs to be redefined so that it is
reflexive. Note that the latter solution is used in more
technical treatments of typing systems (e.g. Cardelli and
Wegner, Computing Surveys, 17, 1985, pp. 471-522).

Knuth points out that one can define partial orderings using ``less than
or equal'' and so does not require the antisymmetric condition. We should
be more explicit here about it and define the partial ordering on a true
reflexive, antisymmetric, and transitive relation.

Kempf writes:

4) The formal description of class precedence list calculation
on pg. 1-15, paragraph 3 is lacking a condition. In the third
line, it is not sufficient just to require the existence of an
index i, but also its minimality.  As a counterexample,
consider R := {(c1,c2) (c2,c3) (c3 c5) (c2 c4) (c4 c6)} The
inheritance graph for this is....

Well, this is the result of a misreading of the algorithm. However,
this is sufficient to require a rewrite of the description. As an aside
to JAK, let me point out the following: his example was:

c5  c6
|   |
c3  c4
|   |
\   /
\ /
c2
|
c1

The relations used to define the partial ordering are:
{(c1 c2)(c2 c3)(c2 c4)(c3 c4)(c3 c5)(c4 c6)}

The key one is that c3 precedes c4.

When the CPL is [c1 c2], there is only one class with no predecessors -
C3.

I believe the description of the algorithm to be correct, but I stand accused of
and confess to it being a difficult description. I will volunteer to try to fix
it up.

By the way, have we thought about various means of making the CPL more
accessible, such as what New Flavors does?

```