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

*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 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

**Follow-Ups**:**Re: CPL Update***From:*David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>

- Prev by Date:
**CPL Update** - Next by Date:
**Re: ---** - Previous by thread:
**CPL Update** - Next by thread:
**Re: CPL Update** - Index(es):