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.