Re: CPL Update

[Danny Bobrow <Bobrow.pa@Xerox.COM>]

    I'm also working on finding a New Flavors equivalent that works
    within the topological sort framework. I have one such equivalent,
    which can be explained in either of two ways.  I think I have a
    second algorithm that produces the same results as the New Flavors
    algorithm which can be described differently from the topological
    sort algorithms and the New Flavors algorithm - it is of the form
    of a certain weird treewalk and doesn't do multiple depth-first
    walks.


I think that your algorithm would work the same as New Flavors if you
used a last-visited walk, that is used the following algorithm for your
walk to dismbiguate in case of choice.  In my hand simulations of your
algorithm it does:

``A last-visited 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.  Nodes are visited unless they WILL BE LATER visited.  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.''  

This is equivalent to laying out a linearization visiting each class as
many times as you get to it, and removing all but the last occurrence.

(Also sometimes described as left-to-right depth first up to joins.)

        I haven't tried coding Danny's algorithm (proposed a
        month or two ago) yet.  I wonder if it does the same thing as
        either of these other algorithms.

    I've been playing around with this (code from Gregor's message
    of Dec 2). It usually does what I consider the right thing, but
    sometimes it does something different from both Gabriel and Flavors
     I haven't been able to boil that down to a small test case
    yet.  The Bobrow algorithm also goes into an infinite loop in some
    cases (again, not yet boiled down to a simple case).

It is my belief that Gregor's code was an implementation of my
algorithm, so you need not recode  -- I would be very interested in a
simple example for Gregors code, or even a complex one that I could look
at and analyze. 

General conclusion.  In all the cases I have seen, I have agreed that
the New Flavors ordering is good.  I believed my algorithm also computed
it.  Dave, could you  try my variation on Gabriels algorthm against the
new Flavors system?

  danny