[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: CPL Update
- To: RPG@SAIL.STANFORD.EDU
- Subject: Re: CPL Update
- From: Danny Bobrow <Bobrow.pa@Xerox.COM>
- Date: 27 Jan 87 09:26 PST
- Cc: common-lisp-object-system@SAIL.STANFORD.EDU
- In-reply-to: Dick Gabriel <RPG@SAIL.STANFORD.EDU>'s message of 27 Jan 87 00:27 PST
- Sender: 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
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
are visited while performing a process called ``walking from a class.''
The following is a recursive definition of walking from a class. Let C
a class and let C1...Cn be its direct superclasses in the local
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?
- Re: CPL Update
- From: David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>