Very Dull Message About Class Precedence Lists

[Dick Gabriel <RPG@SAIL.STANFORD.EDU>]

For those who are actively thinking about this issue, here is a followup
on my last message about topological sort. It mostly contains a bunch of
runs of a slightly modified algorithm. The modifications are that it now
reports when multiple orders are possible, and, when there is a choice
between several classes with no predecessors, the algorithm selects the
one that appear first in a preorder treewalk from the class for which the
class precedence list is being computed to the top of the lattice (viewed
as a tree). I believe that this algorithm produces the same results as
the New Flavors algorithm, but it is easier to explain: 1. Compute the
partial order relations; 2. topologically sort; 3. when topological sort
has a choice of several classes to put next, select according to preorder.

(init)
(defclass c1 (c2 c6 c5) ())
(defclass c2 (c3 c4) ())
(defclass c3 (c5) ())
(defclass c4 (c6) ())
(defclass c5 (top) ())
(defclass c6 (top) ())

(topologically-sort 'c1)
 = (C1 C2 C3 C4 C6 C5 TOP) 

(init)
(defclass c2 (c3 c4) ())
(defclass c3 (c5) ())
(defclass c4 (c6) ())
(defclass c5 (top) ())
(defclass c6 (top) ())

(topologically-sort 'c2)
  = (C2 C3 C5 C4 C6 TOP)  Multiple orders possible

(init)
(defclass c1 (c3 c2) ())
(defclass c2 (c3) ())
(defclass c3 (top) ())

(topologically-sort 'c1)
 = Inconsistent Lattice

(init)
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass c4 (c1 c2) ())
(defclass c5 (c3 c2) ())
(defclass c6 (c4 c5) ())

(topologically-sort 'c6)
 = (C6 C4 C1 C5 C3 C2 TOP)  Multiple orders possible

(init)
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass d4 (c3 c2) ())
(defclass d5 (c2) ())
(defclass d6 (c3 c2 d5 d4) ())

(topologically-sort 'd6)
 = Inconsistent Lattice

(init)
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass e1 (c1) ())
(defclass e2 (c2) ())
(defclass e3 (c3) ())
(defclass e4 (e3 e2 e1) ())
(defclass e5 (c1 c2) ())
(defclass e6 (c2 c3) ())
(defclass e7 (e5 e6 e4) ())

(topologically-sort 'e7)
 = (E7 E5 E6 E4 E3 E2 E1 C1 C2 C3 TOP)

(init)
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass d1 (c1) ())
(defclass d2 (c2) ())
(defclass e1 (d1 d2) ())

(topologically-sort 'e1)
 = (E1 D1 D1 C2 C2 TOP) Multiple orders possible

(init)
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass d1 (c1 c2) ())
(defclass d2 (c1 c3) ())
(defclass e1 (d1 d2) ())

(topologically-sort 'e1)
 = (E1 D1 D2 C1 C2 C3 TOP) Multiple orders possible

(init)
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass d4 (c3 c2) ())
(defclass d5 (c2) ())
(defclass d6 (c3 c2 d5 d4) ())

(topologically-sort 'd6)
 = Inconsistent Lattice

(init)
(defclass b1 (top) ())
(defclass b2 (top) ())
(defclass b3 (top) ())
(defclass b4 (top) ())
(defclass ex1-1 (b1 b3 b4) ())
(defclass ex1-2 (b2 b3) ())
(defclass example-1 (ex1-1 ex1-2) ())

(topologically-sort 'example-1)
 = (EXAMPLE-1 EX1-1 B1 EX1-2 B2 B3 B4 TOP) Multiple orders possible

(init)
(defclass b1 (top) ())
(defclass b2 (top) ())
(defclass b3 (top) ())
(defclass ex2-1 (b1) ())
(defclass ex2-2 (b2) ())
(defclass ex2-3 (b3) ())
(defclass example-2 (ex2-1 ex2-2 ex2-3) ())

(topologically-sort 'example-2)
 = (EXAMPLE-2 EX2-1 B1 EX2-2 B2 EX2-3 B3 TOP) Multiple orders possible

(init)
(defclass d0 (top) ())
(defclass d1 (top) ())
(defclass d2 (top) ())
(defclass d3 (top) ())
(defclass e (d0 d1) ())
(defclass f (d1 d2 d3) ())
(defclass g (d1 d2) ())
(defclass h (d0) ())
(defclass foo (e f g h) ())

(topologically-sort 'foo)
 = (FOO E F G H D0 D1 D2 D3 TOP) 

(init)
(defclass d1 (top) ())
(defclass d2 (top) ())
(defclass d3 (top) ())
(defclass d4 (d3 d2) ())
(defclass d5 (d2) ())
(defclass d6 (d3 d2 d5 d4) ())

(topologically-sort 'd6)
 = Inconsistent Lattice

(init)
(defclass g1 (top) ())
(defclass g2 (top) ())
(defclass g3 (top) ())
(defclass g4 (top) ())
(defclass g5 (g1 g2) ())
(defclass g6 (g2 g3) ())
(defclass g7 (g3 g4) ())
(defclass g8 (g4 g5 g6 g7) ())

(topologically-sort 'g8)
 = Inconsistent Lattice

(init)
(defclass this (is much) ())
(defclass is (too) ())
(defclass much (fun!) ())
(defclass too (top) ())
(defclass fun! (top) ())

(topologically-sort 'this)
 = (THIS IS TOO MUCH FUN!) Multiple orders possible

			-rpg-