Topological Ordering of Specializers

[scymtym]

As I wrote earlier, pattern-more-specific-p establishes a partial order on patterns which is similar to the subtype relation (See attached figures for examples; arrows point to "more specific"). The similarity being that the set of values matching a more specific pattern is a subset of the values matching a less specific pattern.

Furthermore, the dispatch strategy (considering only one argument and only pattern specializers) currently looks like this (unchanged compared to previous email):

1 for each "specializer cluster" C (explanation below), in any order:
2       for each pattern P in C, most specific first:
3               if P matches the argument:
4                       return generalizer object with
5                               all specializers in the "cluster" whose 
6                               pattern is P or a less specific pattern

The rationale being that a single successful match should be sufficient to determine all matching patterns (and thus accepting pattern-specializers) as well as binding the relevant pattern variables. This assumes that optima is smart enough to avoid unnecessary work when sequentially trying subsequently less specific patterns (in line 2).

Now the new issue: previously, I assumed patterns would form totally ordered "clusters" (actually connected components) under pattern-more-specific-p. This assumption is reflected in the algorithm above. However, the assumption is not true (again, see attached figures, ignore BUILT-IN-CLASS CONS …).

A new assumption could be that patterns form connected components in a DAG under pattern-more-specific-p. If I'm not mistaken, a suitable adaptation of the above algorithm would then be:

1 for each connected component C, in any order:
2       for each pattern P in C, in topological order, most specific first:
3               if P matches:
4                       return generalizer object with
5                               all specializers whose pattern is in the 
6                               transitive PATTERN-LESS-SPECIFIC-P-closure
7                               of { P }

Not sorting connected components for processing should have performance implications but should not affect the result of the computation since the sets of matching values should be disjoint.

One potential problem is that pattern-more-specific-p employs subtypep when comparing (type …) and class patterns (see specializer-dag-2 for excessive use of class patterns), making the resulting ordering

1. Independent of generalizer objects (convenient, maybe good)
2. Different from CLOS semantics (maybe bad)

specializer-dag-1:

specializer-dag-2:

[scymtym]

@csrhodes mentioning you so you get notified :)

[scymtym]

Updated version with highlighting of accepting specializers and corresponding subpatterns:

[scymtym]

As @csrhodes pointed out, the above algorithm will not work in cases like:

(cons x 1)
(cons 0 y)

and

(cons x 1)
(cons 0 y)
(cons x y)

[scymtym]

Extended visualization of the above problem with additional edges indicating known disjoint (<>) and potentially non-disjoint (/=) relations:

Next steps probably are

• Implement detection of disjoint/non-disjoint relations when possible. The above figure has been generated by a prototypical implementation of an approach similar to ftp://publications.ai.mit.edu/ai-publications/2001/AITR-2001-006.pdf (thanks @pkhuong for mentioning the paper)
• Develop and implement graph operations or other extensions of the algorithm described above to ensure correct results in case of non-disjoint relations.