Technical corrections in 87-002

[kempf%hplabsz@hplabs.HP.COM]

Dick:

	Apologies if this arrives more than once. Our mail system is
changing.
	
	The formal specification of method application and combination
is completed, and a couple of omissions, typos, and other 
technical errors were found. While I agree with Moon that it probably
isn't a good idea to inject a level of formalism into CLOS beyond that
customary for the Common Lisp community, I hope that the results of
work from those who are interested in such formalism can be fed back
into the design process, in the spirit of trying to make the CLOS
specification as precise as possible.

Here are the corrections:

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).

2) As noted in the followup to my posting of the preliminary formal 
specification for method applicaton and combination, the phrase "either 
method may precede the other" on p. 1-21, last paragraph is not technically 
correct, since the two methods are incomparable with regard to precedence. The 
algorithm is nevertheless sound, because it describes sorting of method
equivalence classes rather than methods, and precedence between equivalence
classes, so the ordering of elements in a specific equivalence class is
arbitrary.

3) With reference to my original posting, the case of both specializers
being quoted objects cited on pg. 1-22, paragraph 3 cannot occur at that
point in the algorithm. Either one or the other can be a quoted object,
but since , by that point in the algorithm: a) the two methods 
being compared must differ on the parameter specializer, and, b) in
order for a method to be applicable at all and the specializer to be
a quoted object, the specializer must be EQL to the parameter, this 
condition cannot occur. 

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;

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

In the first step, cpl := [c1] and R := R\{(c1,c2)}, where A\B denotes
the set A with all elements of A INTERSECT B removed (quotient set). 
Next step: cpl := [c1 c2] and R := {(c2,c3) (c2,c4)}. Now the set of
classes without predecessors is {c3 c4}. Then, according to the
description of the algorithm on pg. 1-15 paragraph 3, j=2 is the
largest number such that "there exists i=3 with c3 being the direct
superclass of c2," but i=4 also holds with this property, so it
cannot be determined whether c3 or c4 should be added to the class
precedence list. Requiring the minimal i to be used will remove
the ambiguity, in the example, making c3 the next element of the cpl.

I hope these corrections can be added to the next draft of the
CLOS document.



	







	Jim Kempf	kempf@hplabs.hp.com