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

Re: Technical corrections in 87-002

Sorry it's taken so long to answer this. 

JAK> As a counterexample, consider R := {(c1,c2) (c2,c3) (c3 c5) (c2 c4) (c4
JAK> c6)}

This is, in fact, incorrect, as Danny pointed out. It should be:

	R = { (c1,c2),(c2,c3),(c3,c4),(c3,c5),(c4,c6) }

by the algorithm at the top of pg. 1-14. But see below for more.

JAK> The inheritance graph for this is;

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

DB> This counterexample is wrong in that the inheritance graph must specify
DB> a local ordering of c3 and c4 (if vertical  means direct superclass and
DB> horizontal is an ordered list.

The intention was that the numbers would indicate the local precedence
ordering. Thus the CLOS definitions would look like:

(defclass c6 () ...)
(defclass c5 () ...)
(defclass c4 (c6) ...)
(defclass c3 (c5) ...)
(defclass c2 (c3 c4) ...)
(defclass c1 (c2) ...)

In fact, the counterexample is wrong, but the interesting fact is
WHY. The counterexample was generated by looking at the pie example
on pg. 1-15, where R is given as:

	R = { (pie,apple) (pie,cinnamon),(apple,cinnamon),(apple,fruit),

However, this is incorrect. The correct value of R before the start
of CPL construction is:

	R = { (pie,apple),(apple,cinnamon),(apple,fruit),(cinammon,spice),

This follows by merging the R(C) for each of the classes:

	R(pie) = { (pie,apple),(apple,cinnamon) }
	R(apple) = { (apple,fruit) }
	R(cinnamon) = { (cinnamon,spice) }
	R(fruit) = { (fruit,food) }
	R(spice) = { (spice,food) }
	R(food) = { (food,T) }

Thus the entry (pie,cinnamon) in R is incorrect, and leads to a lack
of the local precedence order being reflected in R.

The R in the counterexample was constructed directly from this example.

Perhaps someone has noted this before and corrected it. In any event,
I suspect that some of the confusion expressed by Sherlis and others
at the March meeting may have been a result of trying to understand
the algorithm via the example. We have had several people here run
into that problem.

DB> The partial order relationship that Dick defines is the one using the
DB> relation "is the same or is subclass of"  This one is reflexive, though
DB> we don't have a simple name for it.

This relationship should be sufficient, but I think it should be
made explicit on the top of pg. 1-14. We need not have a simple name,
as long as it is defined. Leaving it implict leaves room for confusion.

I hope whoever is the current custodian of 87-002 can make these corrections.