How is pattern specificity decided?

Question

Mathematica has a notion of pattern specificity, which is a partial ordering on patterns.

The rules (e.g. DownValues, SubValues, etc) attached to a symbol are linearly ordered, with this ordering determined by the order in which the values and the specificity ordering.

During evaluation, the rules are tried according to this ordering.

As each rule is added, if its left hand side is more specific than the left hand side of an existing rule, it is inserted before the first such existing rule, and otherwise it is added at the end. This is briefly described in the Mathematica documentation, at http://reference.wolfram.com/mathematica/tutorial/PatternsAndTransformationRules.html.

The general intention of pattern specificity is that it corresponds to the range of expressions that the pattern could match. The actual implementation of pattern specificity in Mathematica is much weaker, of course; this ideal notion of specificity would of course be undecidable. As an example, _?f and _?g are considered incomparable for any expressions f and g even though in the ideal partial ordering _?True& would be less specific than _?False&. To my knowledge, pattern specificity is a weakening of the ideal notion of specificity (that is, if p is considered more specific than q, then p matches a strict subset of the expressions that q matches), although there may well be some interesting counterexamples!

One can 'experimentally' examine the partial ordering of pattern specificity using the following commands:

SetAttributes[{PatternsComparableQ, PatternsOrderedQ}, HoldAll]  
PatternsComparableQ[f_, g_] := Module[{x, y},
  x[HoldPattern[f]] := 1;
  x[HoldPattern[g]] := 2;
  y[HoldPattern[g]] := 3;
  y[HoldPattern[f]] := 4;
  DownValues[x][[1, 1, 1, 1]] === DownValues[y][[1, 1, 1, 1]]
  ]   
PatternsOrderedQ[_[f_, g_]] := Module[{x, y},
  x[HoldPattern[f]] := 1;
  x[HoldPattern[g]] := 2;
  y[HoldPattern[g]] := 3;
  y[HoldPattern[f]] := 4;
  DownValues[x][[1, 1, 1, 1]] === DownValues[y][[1, 1, 1, 1]] === HoldPattern[f]
  ]
PatternsOrderedQ[x_] := OrderedQ[x, PatternsOrderedQ[{#1, #2}] &]

Now, my question:

How is pattern specificity determined in practice?

A perfect(!) answer might include an algorithm reproducing the results of PatternsComparableQ and PatternsOrderedQ above, without interacting with the state of the kernel via DownValues et al. I'd also be interested in pointers to documentation, or informal descriptions of the algorithm used.

(I'm also aware of Internal`ComparePatterns which I learnt about in this excellent answer to a related question, but as it is known to "make mistakes" and doesn't appear to actually be used in ordering the rules attached to symbols, I'm not sure it's relevant.)

Answer 1

If I understood your question, I assumed you are asking what determines the order of execution of patterns. If we assume Mathematica a black box with an input and and output, we can consider the input the domain of an "ordering function" and the output its range. An injective function is a one to one map so that each element in the domain maps to a single element in the range. Since the documentation reads

A pattern like F[x__,y__,z__] can match an expression like F[a,b,c,d,e] with several different choices of x, y, and z.

this implies that the there can be different pattern matches for the same input (that is not injective). A surjective function is one in which every element in the range has at least one element in the domain that maps to it (there are no left over elements in the range which are not mapped to from an element in the domain or to use an alternative terminology the codomain is equivalent to the range). This is how I initially read the documentation, but upon reflection, I'm not sure that this actually applies to the order in which the patterns are executed, but only to which of the relatively larger/smaller sized of patterns are matched first, since the two can not at times be distinguished.

It seems to me that they are ordered sequentially as specified in the order they are listed in their downvalues. As I reflect on this more, I do not understand the equivalences you test in the two lines

DownValues[x][[1, 1, 1, 1]] === DownValues[y][[1, 1, 1, 1]]

and

DownValues[x][[1, 1, 1, 1]] === DownValues[y][[1, 1, 1, 1]] === HoldPattern[f]

so I'm not sure they test for the same execution order or some slight permutation of the execution order with the order in which the last two elements being potentially exceptional. Perhaps as a result, I have missed the entire point of your code.

I say this because of the statement in the documentation

In general, when there are multiple or in a single function, the case that is tried first takes all the __ and ___ to stand for sequences of minimum length, except the last one, which stands for "the rest" of the arguments.

that I read to mean that elements in the downvalue list are executed sequentially, except perhaps the last one, which may be executed in a different order. If that is true then for a given binary relation <=, all the elements in the downvalue list would form a total order, each preceding the other in execution, except perhaps the last, which may be executed before or after the penultimate value in the list. However, as I read it again, perhaps this should be interpreted as the downvalue list will be executed as always either always shortest match first or longest match first, except the last. However, in that case, wouldn't this still mean that the effective execution order too would also be reversed for the last two elements?

I must confess to not knowing enough of the internals to say, but primarily sought clarification, since it seemed to me, at least initially that there are two distinct issues that might determine "specificity", namely which elements in a list are executed first and the scope (size) of the pattern, which may or may not imply execution order as given in the downvalue lists, since one must take into account the (possible?) exceptional behavior of "rest" and it was unclear to me which you meant.

It seems to me that magma's suggestion that the evaluation order is determined at least at some point by some arbitrary order, lexicographic ordering being a likely possibility. This sounds reasonable, since there would be no way for Mathematica to decide how to order the execution of an expression in a HoldPattern expression until execution actually takes place at which point the execution order has already in effect been decided.

Your question does seem an important one given that the order in which pattern matches are executed could influence what matches are obtained, a situation similar to that described by Wellin (2013; Chapter 10.4) dealing with stemming of words, where numerous exceptional cases are likely to be encountered and in which the order of execution becomes critical. Use of Regular expressions with backtracking or forward offset could likewise potentially generate unexpected results, although this would presumably be more of an issue for matching within strings or substrings than for matching list elements.

Answer 2

It seems the behaviour of Internal`ComparePatterns changes from version to version. On 10.4.1 I get

Internal`ComparePatterns[(_) .., __]
Internal`ComparePatterns[__, (_) ..]
(*=>*)
"Specific"
"Incomparable"

while you reported

Internal`ComparePatterns says that __ and (_).. are each more specific than the other, while my 'experimental' approach above says they are incomparable.

It seems to me that now Internal`ComparePatterns gives "Specific" if the first pattern is more specific, and "Incomparable" in almost all other cases. It returns "Disjoint" when given 2 non-pattern expressions, but the internal rule in this case seems to be to use the canonical ordering (Order).

Using these observations I have constructed a PatternOrder (modeled after Order) using your approach relying on the kernel (slightly modified) and a PatternOrderI using Internal`ComparePatterns which seem to agree on everything I tried.

PatternOrder(I):

ClearAll@PatternOrder;

PatternOrder::usage = "PatternOrder[pattern1,pattern2] gives 1 if \
pattern1 is considered more specific than pattern2, -1 if pattern2 is \
more specific than pattern1, and 0 otherwise."

PatternOrder[pattern1_, pattern2_] := Module[{d12, d21},
  d12[pattern1] = 0;
  d12[pattern2] = 0;

  d21[pattern2] = 0;
  d21[pattern1] = 0;

  If[
   (DownValues@d12 /. d12 -> d21) === (DownValues@d21),
   (*these patterns can be put into a definite specifity order*)
   If[
    Position[DownValues@d12, 
      Verbatim@HoldPattern[d12@pattern1]] === {{1, 1}},
    1(*pattern1 is more specific*),
    -1
    ]
   ,
   (*else they where not rearranged, thus considered equally specific*)


   0
   ]
  ]

ClearAll@PatternOrderI;
PatternOrderI[p : PatternSequence[pattern1_, pattern2_]] := Switch[
   {
    Internal`ComparePatterns @@ {p},
    Internal`ComparePatterns @@ Reverse@{p}
    },

   {"Specific", "Incomparable"}, 1,
   {"Incomparable", "Specific"}, -1,
   {"Incomparable", "Incomparable"}, 0,
   {"Disjoint", "Disjoint"}, Order @@ {p}
   ];

Example (showing some limitations of the Wolfram Language ordering algorithm):

PatternOrder[x_, 1] === -1
PatternOrderI[1, x_] === 1
PatternOrder[g[_, _List], g[_, {___}]] (*gives -1, but should be 0*)
PatternOrder[g[{}, _List], g[_, _List]] === 1
PatternOrder[g[{}, _List], g[_, {___}]] (*gives 0, but should also be 1*)

Unit Test comparing PatternOrder and PatternOrderI, ensuring they agree:

PatternOrdersAgree[a_, b_] := 
  PatternOrder[a, b] == PatternOrderI[a, b] && 
   PatternOrder[b, a] == PatternOrderI[b, a];

testSet = {
   {x_, 1},
   {g[_, _List], g[_, {___}]},
   {g[{}, _List], g[_, _List]},
   {g[{}, _List], g[_, {___}]},
   {g[a], g[_]},
   {a, b},
   {g[a], g[b]},
   {__, (_) ..}
   };

PatternOrder @@@ testSet
PatternOrderI @@@ testSet
PatternOrdersAgree @@@ testSet
(*=>*)
{-1, -1, 1, 0, 1, 1, 1, -1}
{-1, -1, 1, 0, 1, 1, 1, -1}
{True, True, True, True, True, True, True, True}

Use PatterOrderI with caution, it might not always agree (I'd be interested in hearing about patterns on which it disagrees with PatternOrder).

Now of course, even if we can simulate the pattern ordering with Internal`ComparePatterns that still doesn't tell us the algorithm used internally. This might forever remain an implementation secret, like the 'canonical order'.

Answer 3

As a relative newbie still just trying to learn how to use patterns, your notion of "specificity" seems unclear to me, perhaps because I am in way over my head already. Nevertheless, uneducated, but earnest fools go where wiser men dare not tread.

According to the documentation (http://reference.wolfram.com/language/tutorial/PatternsAndTransformationRules.html):

A pattern like F[x__,y__,z__] can match an expression like F[a,b,c,d,e] with several different choices of x, y, and z. The choices with x and y of minimum length are tried first. In general, when there are multiple __ or _ in a single function, the case that is tried first takes all the __ and _ to stand for sequences of minimum length, except the last one, which stands for "the rest" of the arguments. [emphasis mine; in your example ignore z]

and also:

The order in which the different cases are tried can be changed using Shortest and Longest.

The first implies that the order in which rules in Mathematica are applied is not injective. However, because the ordering of "rest" is potentially treated differently presumably, to force the outcome to encompass the "universe of all potential patterns, it would seem, to me at least, that after all pattern matching is done (ultimately evaluated) in whatever order, all elements of the domain that do form a match are mapped into the range (result of the function), with no member of the range without an element in the domain and hence, the final "rule ordering function" used by Mathematica is necessarily surjective (the inverse image of the result is a restriction of the domain as one should expect). However, because rest can potentially be evaluated in a different order it is unclear to me if the internal ordering function itself can be truly regarded as surjective.

It would seem to me that because the potential behavior of "rest" depends entirely on the composition of the domain, it is unclear to me that whether or not the "rule" establishing the order in which rules are evaluated is always a partial order. A partial order assumes asymmetry, that is if a ≤ b and b ≤ a then a = b [or in the case here a === b]. Also, as you point out, for any two elements a, b, of a partially ordered set, if a ≤ b or b ≤ a, then a and b are comparable. Otherwise they are incomparable. However, again it is unclear to me if the potentially exceptional behavior of "rest", might not by default make some pattern comparisons always "comparable" by default since rest is allowed to potentially vary the order as required to insure decidability.

Consequently, even though you say:

As an example, _?f and _?g are considered incomparable for any expressions f and g even though in the ideal partial ordering _?True& would be less specific than _?False&.

it is unclear to me that this is always true, because for some domains this might well be false as a result of the order in which "rest" is evaluated in exceptional situations, where it may be evaluated in "exceptional order" (longest to shortest, rather than the reverse, when as with the default ordering (shortest matches precede longer matches, or visa versa depending upon whether a non-default choice has been made). However, I'm not sure about this, since Downvalues[] seems to always process its list of expressions for a given function in index order, regardless of in what order they are defined, which would seem to imply that "rest" would always be treated last, but again perhaps when evaluated as a rule in non-standard order. Thus, the final order the rules are evaluate might depend on the domain under consideration. Expressions with the head Symbol seem to always listed last, evidently in reverse order of their definition, as one would expect, when index order is ambiguous.

ie (using multiple definitions of f[x_], only one of which could be acceptable:

ClearAll["Global`*"]
f[x_] := x^2
Head[%]

Out[102]= Symbol

f[x_] := x^3
Head[%]

Out[104]= Symbol

f[2] := 3;
f[1] := 2;
DownValues[f]

Out[107]= {HoldPattern[f[1]] :> 2, HoldPattern[f[2]] :> 3, HoldPattern[f[x_]] :> x^3}

ClearAll["Global`*"]
f[x_] := x^3
Head[%]

Out[110]= Symbol

f[x_] := x^2
Head[%]

Out[112]= Symbol

f[2] := 3;
f[1] := 2;
DownValues[f]

Out[115]= {HoldPattern[f[1]] :> 2, HoldPattern[f[2]] :> 3, HoldPattern[f[x_]] :> x^2}

Perhaps the unevaluated expressions to generated by a pattern that could in some way be returned with HoldPattern that could be manipulable symbolically to elucidate the execution order, but those more familiar than I with symbolic manipulation might know a way to do this. Presently, I don't.

Presumably, unlike a comparison of elements within a partial order, the mechanism deciding the ultimate order the rules are applied can take only one path (the actual order it executes), without bifurcation rather than potentially multiple paths of comparison within the lattice of possibilities as is the case for a partial order. As you note, this can not be undecidable, since otherwise Mathematica might not for some domains be able to return a result. Hence, the internal ordering mechanism for rule evaluation might be more analogous to a (not fully predictable?) piece-wise function rather than a partial order.

Nonetheless, these considerations don't really establish a satisfactory an answer to your question. Nonetheless, they might prompt further discussion that clarifies your notion of "specificity" in this context. Its seems to me that although shorter potential pattern matches will always be contained in longer ones, whereas the reverse could never be true unless the lengths of the matches are of equal length, the potentially exceptional behavior of "rest" might, nonetheless, create an unpredictable order of execution. Hence, "specificity", at least in this sense, should not be be conflated with the behavior of the ordering mechanism for rule evaluation.

In any event, thank you for helping me learn. A more complete understanding of execution order would be helpful.