CPL Computation

[David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>]

    Date: 27 Jan 87  1207 PST
    From: Dick Gabriel <RPG@SAIL.STANFORD.EDU>

    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. 

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

This is true.  I'm not sure that it's significant.  Does topological sort run
in linear time?

    Given ... that there is no intuition to any order beyond what the
    topological sort gives you ...

I agree with Danny's disagreement with this.  I'm interested in continuing
the search for an algorithm that is acceptable to your algorithms wizard
and at the same time provides the intuitive behavior.  It's getting late for
me, but I'll follow up on this tomorrow.