CPL Computation

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

As I've mentioned earlier, I wasn't interested in proposing a new
definition of the CPL computation different from what Flavors presents but
in proposing a clear way of describing it.

I took Moon's suggestion and looked for a different ``tiebreaker'' from
preorder treewalk. I have a simple way to describe it, but the naive
implementation has bad running behavior. The fast version is describable,
but the description is horrendous. I think we want to consider what this
all means once the algorithms are presented.

The algorithm is precisely as before, but when the topological sort would
nondeterministically select one class from among a set of equally good
ones, you choose based on a last-visited preorder treewalk.

A last-visited preorder treewalk is defined in terms of the order in which
classes are visited while performing a process called ``walking from a
class.''  The following is a recursive definition of walking from a class.
Let C be a class and let {C1...Cn} be its direct superclasses in the local
precedence order.  To walk from C, first C is visited, then we walk from
C1, then we walk from C2, and so on until we finally walk from Cn.
If a class has been visited before, you ignore that visit. That is,
the order is the order in which the last visits to a node are made.

Normally, one computes the preorder treewalk order as a number attached to
the class. Again normally, this number is computed by performing the
preorder treewalk and INCFing a counter. In a preorder treewalk, when a
class already has a preorder number, you do not re-visit that class; the
modification to normal preorder treewalk to obtain last-visited preorder
treewalk is to eliminate this last pruning.  The tiebreaker simply looks
at these preorder numbers, choosing the class with the smallest preorder
number.

Notice that a lot of pruning might have been done by the original preorder
walk and that the last-visited preorder walk eliminates all of the
pruning.

Here is some crufty code to compute the normal preorder number into
a slot of the class called the PREORDER:

(defun preorder-walk (class)
 (cond ((< 0 (preorder class)))  ;already visited
       (t (setf (preorder class) (incf *preorder-counter*))
	  (dolist (superclass (direct-superclasses class))
           (preorder-walk superclass)))))

Here is the modified code:

(defun lv-preorder-walk (class)
 (setf (preorder class) (incf *preorder-counter*))
 (dolist (superclass (direct-superclasses class))
	 (lv-preorder-walk superclass)))

This is, of course, less efficient than the previous code, though it looks
simpler.  One can get a fast algorithm by doing what could be called a
reversed reversed postorder treewalk (``moonwalk,'' for short).

We define reversed postorder treewalk and then modify that to be reversed
reversed postorder treewalk.

A reversed postorder treewalk is defined in terms of the order in which
classes are visited while performing a process called ``walking from a
class.''  The following is a recursive definition of walking from a class.
Let C be a class and let {C1...Cn} be its direct superclasses in the local
precedence order.  Classes are visited unless they have already been
visited.  To walk from C, first we walk from Cn, then we walk from Cn-1,
and so on until we finally walk from C1.  Finally we visit C.  A reversed
reversed postorder treewalk visits classes in precisely the reverse order
that they are visited in a reversed postorder treewalk.

Implementationally, moonwalk isn't too bad. You place reversed postorder
numbers on each class at or above the class of interest, and ties are
broken by selecting the class with the largest reversed postorder number
(note that we chose the smallest number in the preorder tiebreaker).
Selecting the largest effects the second reversing.

Here is the code to do this:

(defun walk (class)
 (cond ((< 0 (rpostorder class)))
       (t (dolist (superclass (reverse (direct-superclasses class)))
	   (walk superclass))
	  (setf (rpostorder class) (incf *counter*)))))

This algorithm works on all of the examples I sent before plus the
two killers Moon sent Sunday.

The question now becomes: Is this what we really want? I claim that
it doesn't matter too much what the tiebreaker is, because it is always
possible to reformulate the lattice and use direct superclasses to
achieve the desired effect. The fact the there are millions of flavors
that use the moonwalk tiebreaker doesn't support the claim that
the moonwalk tiebreaker is right: Perhaps the flavors have been carefully
crafted to inherit properly.

The explicit local precedence orders are the means by which programmers
specify the ordering they want. The tiebreaker simply makes the total
order well-defined. The tiebreaker is not intended to be a ``model''
of the class precedence list. If the topological sort produces a unique
order, that order is intuitive; the cases where tiebreaking happens is
ad hoc and is no intuitive.

In the spirit of trying to figure out the New Flavors algorithm in order
to be able to present it well, my algorithms wizard and I have tried come
up with a more easily explainable algorithm that mimics the New Flavors
and does not have topological sort as an explicit part of it. We failed,
though we have not yet written down an example for which it fails.
[I only mention this because I promised to show this algorithm in my last
message.]

Finally, I'm not sure that the first of Moon's killers has a very intuitive
Flavors order. Here it is again:

(DEFCLASS PTEST1 (PTEST2 PTEST3 PTEST5) ())
(DEFCLASS PTEST2 (PTEST5) ())
(DEFCLASS PTEST3 (PTEST4) ())
(DEFCLASS PTEST4 () ())
(DEFCLASS PTEST5 () ())

The Flavors order is (ptest1 ptest2 ptest3 ptest4 ptest5).
Why is ptest4 before ptest5?  Here's what the thing looks like:


           top------
            |      |
           pt4     |
            |      |
      |-----------pt5
      |     |     /
     pt2   pt3   /
        \   |   /
         \  |  /
           pt1

pt5 is a direct superclass of pt1 and pt4 isn't.  One could argue that pt5
is the last of the direct superclasses, so it should come after the
earlier direct superclasses and all of their superclasses; in this case
you get to pt4 first because it is above pt3, which precedes pt5.  But,
does being mentioned first in a defclass count for anything? If so, you
get to pt5 by passing through the first of the direct superclasses of pt1
(pt1 to pt2 to pt5) whereas you get to pt4 by passing through the second
of the direct supeclasses of pt1 (pt1 to pt3 to pt4), and there are
exactly the same number of intermediate classes.  Everything says pt5
should precede pt4, but Flavors doesn't. I believe this to be a serious
problem.

Finally, my algorithms wizard and I studied the New Flavors CPL
computation description and think there is a performance problem with the
algorithm it describes. Consider the following graph of 4n+1 classes:

	(defclass Ai (Bi Ci) ())
	(defclass Bi (Di Ai+1) ())
	(defclass Ci (Di) ())
	(defclass Di () ())

for 0 <= i < n. 

Here are the classes for n=2.

	(defclass a0 (b0 c0) ())
	(defclass b0 (d0 a1) ())
	(defclass c0 (d0) ())
	(defclass d0 () ())
	(defclass a1 (b1 c1) ())
	(defclass b1 (d1 a2) ())
	(defclass c1 (d1) ())
	(defclass d1 () ())

The New Flavors algorithm, as described, seems to take n+1 passes, though
there is exactly one total order possible.

Given that reversed reversed postorder treewalk (or last-visited preorder)
is the tiebreaker, that there is at least one suspicious Flavors-order
example, that people can formulate their lattices as they want to get the
right inheritance, that there is no intuition to any order beyond what the
topological sort gives you, and there is a possible performance problem
with the algorithm described in the New Flavors document, I have now
flipped my bit on this issue from wanting to mimic the Flavors order
to insisting on preorder tiebreaker with topological sort.

			-rpg-