Class Precedence List

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

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?