Inside the Mathematica Pattern Matcher

Øyvind Tafjord

Wolfram Research, Inc

Outline

The pattern matcher at work

Overview of new functionality in 6.0

Tips and tricks for using the pattern matcher

Summary

The pattern matcher at work

The central principle of Mathematica is "everything is an expression". The pattern matcher help these expressions come alive.

The Mathematica pattern matcher finds matches between general expressions and patterns constructed from a variety of pattern objects. This is a central part of how Mathematica operates.

Writing optimal code for the pattern matcher is a bit of an art, often relying on subtle difference in how various patterns are handled. One of the goals of this talk is to provide some insights into this art and as a result getting you on your way to more writing more efficient Mathematica code.

Function definitions

Function definitions for a function f are really patterns associated with the symbol f.

f[x_]:=1/x

f[10]

f[0]

One can specify multiple definitions, typically the most specific ones will be tried first

f[0]=Infinity;

f[0]

?f

The actual transformation rules are stored in DownValues[f] for this case

DownValues[f]

Here's a more complicated example, redefining the Plus operation for expressions of the form g[x_]:

g/:g[x_]+g[y_]:=g[x+y]

The g/: makes sure this rule is associated with the symbol g, rather than the symbol Plus, which is important in order not to slow down the much more common Plus operations.

g[13]+g[10]

Building up programmatic structures from sets of such transformation rules is an essential part of what makes Mathematica tick. Here's a start of building up a sophisticated integral function by combining many such rules:

integrate[y_+z_,x_]:=integrate[y,x]+integrate[z,x]
integrate[c_ y_,x_]:=c integrate[y,x]/;FreeQ[c,x]
integrate[c_,x_]:=c x/;FreeQ[c,x]
integrate[x_^n_.,x_]:=x^(n+1)/(n+1)/;FreeQ[n,x]&&n!=-1
integrate[1/(a_. x_+b_.),x_]:=Log[a x+b]/a/;FreeQ[{a,b},x]
integrate[Exp[a_. x_+b_.],x_]:=Exp[a x+b]/a/;FreeQ[{a,b},x]

Here's an example of its use:

integrate[2x^4-5/(2a*x-7b)+2Exp[3x],x]

Matching multiple sequences

Patterns with multiple variable-length sequences are an important subclass of patterns.
Let's look at a simple example to get some insight into how Mathematica goes about finding a possible match.

data={3.5,2.3,4,7,11,10.7};

Checking whether data is of the form {reals, integers, reals}:

MatchQ[data,{__Real,__Integer,__Real}]

We can use this example to highlight one of the way in which the general pattern matcher algorithm differs from the string matching one, say for a similar example like

StringMatchQ["ab123c",LetterCharacter..~~DigitCharacter..~~LetterCharacter..]

General pattern matcher: Try all partitions of the expression into sequences, in a certain order
String pattern matcher: Match one sequence at a time, going from left to right (NFA)

To see what partitions Mathematica goes through, we can do the following trick:

MatchQ[data,{a__,b__,c__}/;(Print[{{a},{b},{c}}];False)]

In actuality, Mathematica will often bypass many of the partitions when the "obviously" cannot match.

Flat/Orderless matching

The number of partitions to try grows considerably when Flat and/or Orderless expressions are involved.

Here's a simple example:

a+b+c+d/.a+d->x

Mathematica finds a match even though a+d is not an actual subexpression of the original expression.

To get an idea of what subexpressions get might considered in a case like this:

a+b+c+d/.x_+y_:>z/;(Print[{x,y}];False)

It's a long list for such a small expression. Note that only sorted subexpressions are tried, consistent with the Orderless treatment, otherwise there would be even many more (note that this can lead to subtle issues when matching held expressions).

As an example of internal Mathematica optimizations, the original example

a+b+c+d/.a+d->x

Overview of new functionality in 6.0

Shortest/Longest

Shortest/Longest used to be called ShortestMatch/LongestMatch in string patterns (both forms are now supported for string patterns).

These commands give you detailed control over the order in which the sequence partitions are tried.

By default, the shortest sequences for the leftmost patterns are tried first, leading to behavior like:

{a,b,1,2,3,d,e,4,5}//.{a___,__Integer,b___}:>{a,foo,b}

If instead we want to make sure we grab all the integers, use Longest:

{a,b,1,2,3,d,e,4,5}//.{a___,Longest[__Integer],b___}:>{a,foo,b}

The second argument can give a more specific priority. By default, the leftmost pattern specification takes precedence.

{a,b,c,3.5,1.3,3,5,6,1.1,d,e,f}/.{___,x:Longest[___?NumericQ],y:Longest[___Integer],___}:>{Num[x],Int[y]}

Here we specify that it's more important to get all the integers first:

{a,b,c,3.5,1.3,3,5,6,1.1,d,e,f}/.{___,x:Longest[___?NumericQ,1],y:Longest[___Integer,2],___}:>{Num[x],Int[y]}

It also works with Optional arguments (indepently of other variable-length patterns).

Clear[f]

f[x_:a,y_:b,z_:c]:={x,y,z}

By default, optional arguments are filled in left to right:

{f[1],f[1,2],f[1,2,3]}

Here we specify that the second argument should be filled first, then the third:

f2[Longest[x_:a,1],Longest[y_:b,3],Longest[z_:c,2]]:={x,y,z}

{f2[1],f2[1,2],f2[1,2,3]}

It works with Orderless functions as well.

g@@Range[10]

Attributes[g]={Orderless};g@@Range[10]/.g[___,x:Longest[__?PrimeQ],___]:>{x}

This is a very inefficient way to do find prime numbers, of course...

Differences with string pattern matcher

Note that using these constructs, we can find the globally longest sequence in an expression:

{a,1,b,2,3,c,4,5,6,d}/.{___,x:Longest[__Integer],___}:>{x}

It's hard to get such things directly with a left-to-right matcher, as in the string patterns. The best you can do here is to first get all sequences and then find the longest one

StringCases["a1b23c456d",DigitCharacter..]

Nevertheless, the latter approach will tend to be significantly faster. In general, the expression patterns with multiple variable-length sequences tend to be slow (due to the number of partitions involved), and it's often better to reformulate the problem to avoid them.

Another difference between the general and string matchers, due to historical reasons, is that the default length priority is Shortest for general patterns, and Longest for string patterns.

{1,2,3,a,b,c}/.{a__Integer,___}:>{a}

StringReplace["123abc",a:DigitCharacter..~~___:>a]

{1,2,3,a,b,c}/.{Longest[a__Integer],___}:>{a}

StringReplace["123abc",Shortest[a:DigitCharacter..]~~___:>a]

Also, the second argument of Shortest/Longest is not supported for string patterns, as it doesn't make sense in the string matcher algorithm.

PatternSequence

PatternSequence lets you set up a sequence of pattern elements, which can be named etc.

MatchQ[{a,b,a,b,a,b},{PatternSequence[a,b]..}]

MatchQ[{a,b,a,b,a,b,b,a},{PatternSequence[a,b]..}]

PatternSequence[] is useful to represent "nothing". It's like Optional without having to specify a default value.

MatchQ[{1,2,3,4},{1,2,3,4,5|PatternSequence[]}]

Here we name the sequence consisting of "anything" followed by a 2.

{a,1,b,2,c,3}/.{___,x:PatternSequence[_,2],___}:>{x}

Repeated[sequence]

Before 6.0 this didn't work as one might have expected, but in 6.0 this functionality has been added:

MatchQ[{a,b,a,b},{(x__/;Length[{x}]==2)..}]

MatchQ[{a,b,a,b,b,a},{(x__/;Length[{x}]==2)..}]

Can handle cases where the various repeats are of different length:

MatchQ[{1,2,1,2,3,1,2},{PatternSequence[1,2,3|PatternSequence[]]..}]

Repeated[patt, {min,max}]

The second argument of Repeated/RepeatedNull can specify a certain number of repetitions (like {min,max} in regular expressions).

{1,2,2,3,3,3,4,4,4,4,5,5,5,5,5}//.{a___,Repeated[x_Integer,{3,4}],b___}:>{a,rep[x],b}

{1,2,2,3,3,3,4,4,4,4,5,5,5,5,5}//.{a___,Longest[Repeated[x_Integer,{3,4}]],b___}:>{a,rep[x],b}

OptionsPattern/OptionValue

OptionsPattern/OptionValue facilitates the use of options etc in user functions.

The old paradigm for options was something like:

ClearAll[f,g];
Options[g]={opt1->foo,opt2->bar};
g[x_,opts___?OptionQ]:={x,opt1/.Flatten[{opts}]/.Options[g]}

{g[10],g[15,opt1->100]}

For this most common case, the new way is more streamlined:

Options[f]={opt1->foo,opt2->bar};
f[x_,OptionsPattern[]]:={x,OptionValue[opt1]}

{f[10],f[15,opt1->100]}

The way this works is that OptionsPattern[], which is basically equivalent to ___?OptionQ,  secretely attaches itself to a hidden pattern variable, associated with the head f. OptionValue[opt] can then access this variable, as well as the default options for that head.

In more general situations, this will not always work. Then one can always fall back to explicitly naming the options and use the 3-argument form of OptionValue:

Clear[f];
Options[f]={opt1->foo,opt2->bar};
f[x_,opts:OptionsPattern[]]:={x,OptionValue[f,{opts},opt1]}

{f[10],f[15,opt1->100]}

An additional feature is that OptionsPattern can be given arguments listing either symbol(s) from which to derive default option values, or explicit default option values.

This paradigm can also be used directly in situations with no "implied" head:

{a->10,b->100,c->1000}/.OptionsPattern[]:>OptionValue[{a,b,c}]

{a->10,b->100,c->1000}/.OptionsPattern[{a->1,b->2,c->3,d->4}]:>OptionValue[{a,b,c,d}]

{PlotRange->100}/.OptionsPattern[Plot]:>OptionValue[{PlotRange,AspectRatio}]

Here we specify both a new explicit default option, as well as getting default options from the symbol Plot. For multiple matches, the one appearing first will be used.

{PlotRange->100}/.OptionsPattern[{AspectRatio->99,Plot}]:>OptionValue[{PlotRange,AspectRatio,Axes}]

To pass along a "filtered" list of options to another function, there's a new function FilterRules (replacing the old System`Utilities`FilterOptions).

This makes a new plotting function that supports all the options of Plot, together with a new option (MyPlotTitle) as well as a new default for ImageSize:

Options[MyPlot]:=Join[{ImageSize->Tiny,MyPlotTitle->"my plot"},Options[Plot]];

MyPlot[gr_,r_,opts:OptionsPattern[]]:=Plot[gr,r,Epilog->Text[OptionValue[MyPlotTitle],Scaled[{.5,.7}]],Evaluate[FilterRules[Join[{opts},Options[MyPlot]],Options[Plot]]]]

MyPlot[Sin[x],{x,0,10},MyPlotTitle->"Sine"]

Reordering definitions

Mathematica automatically tries to reorder function definitions so that more specific definitions are tried before more generic ones.

ClearAll[f]

f[x_]:=x^2

f[x_Integer]:=x^3

f[x_Integer?PrimeQ]:=x^4

?f

The reliability of this reordering was significantly improved 6.0. There is also now a system option to turn off the automatic reordering:

SetSystemOptions["DefinitionsReordering"->"None"]

ClearAll[f]

f[x_]:=x^2

f[x_Integer]:=x^3

f[x_Integer?PrimeQ]:=x^4

?f

SetSystemOptions["DefinitionsReordering"->"Default"]

This can speed up loading of files with thousands of definitions, for which you know that no reordering is needed. Remember to switch it back to "Default" afterwards though, or else the you may get unintended behavior from core system code.

Tips and tricks for using the pattern matcher

Rules get preprocessed, pure patterns do not

If a complicated pattern is used multiple times, consider associating it with a rule to avoid having to "compile" it multiple times:

rule={__h+__g+a_*b_.,a_,b_+c_}->True;

When a rule is evaluated, it secretely attaches a "compiled" version of the rule to the expression. Use this rule to match with an expression:

Replace[{h[x]+h[y]+g[1]+5,5,1+x},rule]

Do the matching many times, with an expression that trivially fails to match (to focus on preprocessing times):

Do[Replace[1,rule],{10000}]//Timing

Do the same matching in MatchQ, without using the preprocessed rule:

patt={__h+__g+a_*b_.,a_,b_+c_};

Do[MatchQ[1,patt],{10000}]//Timing

Note that the rule must be associated with a stored expression for the compiled rule to be stored:

Do[Replace[1,{__h+__g+a_*b_.,a_,b_+c_}->True],{10000}]//Timing

"Literal" patterns are very fast

Function definitions with no pattern elements use hash lookups and are very fast.

ClearAll[f,g]

This generates 10 literal function definitions:

Map[(f[#]=Random[])&,Range[10]];

?f

Let's do 1000 of them instead:

Clear[f,g]

Map[(f[#]=Random[])&,Range[1000]];

The definitions of g also include a pattern element (_).

Map[(g[#,_]=Random[])&,Range[1000]];

f[100]

g[100,a]

Do[f[100],{10^5}]//Timing

Do[g[100,a],{10^5}]//Timing

There's a very significant difference which will grow with the number of definitions (in the latter case, Mathematica iterates through all the rules)

A similar effect can be achieved for rule lists by using Dispatch:

rules=Map[#->Random[]&,Range[1000]];

Dispatch creates hashable versions of literal patterns:

drules=Dispatch[rules];

100/.rules

100/.drules

Do[100/.rules,{10^5}]//Timing

Do[100/.drules,{10^5}]//Timing

Use the string matcher if possible

If your problem is suitable for string matching, this will typically be much faster.

Here's a list of 1000 random integers between 0 and 50:

data=RandomInteger[50,1000];

Find where in the list the integer 25 appears:

Position[data,25]

Construct a string with the corresponding character codes (adding 32 to get more printable characters):

sdata=FromCharacterCode[data+32];

sdata

StringPosition[sdata,FromCharacterCode[25+32]]

Do[Position[data,25],{10000}]//Timing

Do[StringPosition[sdata,FromCharacterCode[25+32]],{10000}]//Timing

For more complicated patterns, the difference can be quite significant. Here we do a naive test whether there are two identical elements in a list (there are  better ways of doing this):

data=ReplacePart[Range[20],15->10]

MatchQ[data,{___,x_,___,x_,___}]

Do[MatchQ[data,{___,x_,___,x_,___}],{1000}]//Timing

sdata=FromCharacterCode[data+32];

StringMatchQ[sdata,___~~x_~~___~~x_~~___]

Do[StringMatchQ[sdata,___~~x_~~___~~x_~~___],{1000}]//Timing

Avoid the evaluator (? and /;)

Any time Mathematica has to "evaluate" an expression, there's a big framework involved of checking this and that, and it's relatively slow. If possible, this is good to avoid. In particular, for pattern matching, it is good to avoid using PatternTest (?) and Condition(/;) if at all possible.

Here are 1 million random integers:

data=RandomInteger[100,10^6];

Using __Integer rather than the equivalent __?IntegerQ is a lot faster:

MatchQ[data,{__Integer}]//Timing

MatchQ[data,{__?IntegerQ}]//Timing

If you need to use these, try to only invoke them at a late stage if other parts of the pattern could cause early rejection and avoid calling the condition. E.g.

{x_/;PrimeQ[x],2}

{x_,2}/;PrimeQ[x]

The latter pattern is probably better, since it will first test for the presence of a 2 (and a length 2 list) before trying the condition.

Multiple variable-length patterns can get slow

As we have already seen, multiple variable-length sequences in a pattern can cause a great number of partitions to be tried.
This is especially for Flat/Orderless functions, due to the number of partitions that need to be tested. 
Remember that _ counts as variable-length for Flat functions.

In many cases there are no good ways around this, and being able to find such matching is what makes Mathematica so good at transforming algebraic expressions, for instance. But faced with patterns like this, it's a good idea to at least consider if there are more straightforward ways to get the same result.

Recently on Mathgroup:

Ignore repeat elements in

Clear[f,g]

s={a,b,c,c,d,e,e,f,g,g,g,h,a,b};

The OP asked for a "rule-based" approach, one of which is (as suggested by many):

s //. {a___, x_, x_, b___} :> {a, x, b}

This is slow compared to more direct approaches, such as

First/@Split[s]

or the slightly faster

Split[s][[All,1]]

This will keep getting worse for longer inputs.

s=RandomInteger[5,1000];

Timing[s1=s //. {a___, x_, x_, b___} :> {a, x, b};]

Timing[s2=Split[s][[All,1]];]

s1===s2

Nested variable-length patterns can run into recursion problems

Here's a nested list of reals and integers:

data=Table[{RandomReal[],RandomReal[],RandomInteger[10]},{10^4}];

If the pattern consists of nested variable-length patterns of some complexity, OS-level recursion is used:

MatchQ[data,{{___Real,___Integer}..}]

For 10^5 elements this will run out of stack and silently crash the kernel. Instead one can try to rewrite such patterns, e.g.,

MatchQ[data,{{_Real,_Real,_Integer}..}]

or if that's not general enough, you could do something like

And@@(MatchQ[#,{___Real,___Integer}]&/@data)

But this is slow, better is something like:

rule={{___Real,___Integer}->True,_->False};

And@@Replace[data,rule,{1}]

Comparing timings:

MatchQ[data,{{___Real,___Integer}..}]//Timing

And@@Replace[data,rule,{1}]//Timing

And@@(MatchQ[#,{___Real,___Integer}]&/@data)//Timing

The advice to avoid nested variable-length patterns also hold for the string matcher.

Summary

Writing code that interacts efficiently with the Mathematica pattern matcher can be an art

But it is often worth spending some time comparing different approaches

Be aware of common pitfalls, such as complicated Flat/Orderless patterns

Consider turning your problem into a string matching problem, if possible

Avoid named patterns in Alternatives

On a related note: Wolfram Workbench has built-in Mathematica pattern matching for searching through large files of code - can operate on code without losing comments, whitespace, etc.