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

*To*: Common-Lisp-Object-system@SAIL.STANFORD.EDU*Subject*: CPL Tiebreaker*From*: Dick Gabriel <RPG@SAIL.STANFORD.EDU>*Date*: 29 Jan 87 0206 PST

Ugh, bletch. I think I am really going to regret having written this message. I think I found the tiebreaker. It passes all of the hard intuitive cases, which I'll list below, along with all of the cases ever mailed out. The tiebreaker applies when there is more than one class with no predecessors. The tiebreaker has two cases. The first case is based on this reasoning by Danny (I'll paraphrase): ``If the user has a class and splits that class into two classes with no other references to the direct superclass, there should be no chance of any interaction with any other class used as a mixin. Hence one wants all superclasses of a class to follow as soon as possible after the class they are related to.'' This is very intuitive, and preorder treewalk is very intuitive. So we do Danny's condition first and then preorder treewalk. Danny's condition means this: We define a relation called unique direct subclass. C is the unique direct subclass of D if C is the only direct subclass of D. If class X was just output and X is a unique direct subclass of some class D, D immediately follows X. Otherwise, ties are broken by preorder treewalk (not last-visited). This means that we treat parts of the lattice that look like this: \|/ D | C /|\ as if they looked like this: \|/ (D,C) /|\ [Actually, the above picture is exactly how I looked when I discovered this tiebreaker.] Here are the hard cases: (DEFCLASS A (B C D E F) ()) (DEFCLASS B (F X) ()) (DEFCLASS C (F Y) ()) (DEFCLASS D (F X) ()) (DEFCLASS E () ()) (DEFCLASS F () ()) (DEFCLASS X () ()) (DEFCLASS Y () ()) (topologically-sort 'a) = (A B C D E F X Y) Well, this is simply preorder treewalk at work. (DEFCLASS PTEST1 (PTEST2 PTEST3 PTEST5) ()) (DEFCLASS PTEST2 (PTEST5) ()) (DEFCLASS PTEST3 (PTEST4) ()) (DEFCLASS PTEST4 () ()) (DEFCLASS PTEST5 () ()) (topologically-sort 'ptest1) = (PTEST1 PTEST2 PTEST3 PTEST4 PTEST5) In this one, PTEST3 is the unique direct subclass of PTEST4, so when PTEST3 is output, PTEST4 and PTEST5 could come next. Preorder would say PTEST5 is next, but Danny's rule overrides that. (DEFCLASS PPTEST1 (PPTEST-MIXIN PPTEST2 PPTEST3) ()) (DEFCLASS PPTEST-MIXIN (PPTEST3) ()) (DEFCLASS PPTEST2 (PPTEST-INTERMEDIATE-1) ()) (DEFCLASS PPTEST3 (PPTEST-INTERMEDIATE-2) ()) (DEFCLASS PPTEST-INTERMEDIATE-1 (PPTEST-BASE) ()) (DEFCLASS PPTEST-INTERMEDIATE-2 (PPTEST-BASE) ()) (DEFCLASS PPTEST-BASE () ()) (topologically-sort 'pptest1) = (PPTEST1 PPTEST-MIXIN PPTEST2 PPTEST-INTERMEDIATE-1 PPTEST3 PPTEST-INTERMEDIATE-2 PPTEST-BASE) This one is nearly the same as the one before. This addition condition adds no complexity to the algorithm, because we compute the in-degrees of each class at DEFCLASS time. -rpg-

- Prev by Date:
**Elaboration on the Non-intuitiveness of New Flavors Algorithm...** - Next by Date:
**Progress is Our Most Important Problem** - Previous by thread:
**Re: Progress is Our Most Important Problem** - Next by thread:
**CPL Tiebreaker** - Index(es):