Pattern matching

Introduction

Pattern matching is an integral part of a computation toolkit. It allows to isolate and modify parts of an expression with replacement rules. A properly broad pattern matcher is effectively its own Turing complete programming language!

For example, Conway’s game of life can be completely emulated by pattern matching, where each cell together with its surrounding cells determined the future value of the cell.

Game of life

Other common uses of pattern matching is in regular expression (regex), widely used for matching patterns in text. The following pattern

^[a-zA-Z0-9]+@gmail\.com$

matches e-mail addresses with at least one alphanumerical character and ending in @gmail.com.

To faithfully parse an e-mail address, a horrendous pattern match is required!

Pattern matching is also ubiquitous in mathematics. For example, the recursive definition of the factorial function

\[ \begin{align} f(0) &= 1\\ f(n) &= n f(n - 1);\quad n > 0 \end{align} \]

is a pattern match. First, the pattern \(f(0)\) is tested. If it is matched, it is replaced by 1. Then the pattern \(f(n)\) is matched, where \(n\) needs to be positive and it is replaced by \(n f(n-1)\), where the \(n\) takes the value of the \(n\) matched in the pattern.

Symbolica has rich support for pattern matching. Let us see some examples where we match and replace all literal parts of the expression.

In this part we use the Python API. The Rust library examples will follow later. We match \(x\) in the expression \(x+f(x) + 5\) and replace it by 6.

from symbolica import Expression
x = Expression.var('x')
f = Expression.fun('f')
e = x + f(x) + 5
e = e.replace_all(x, 6)
print(e)

We get 11 + f(6)

To replace f(x) by 6, we change the pattern:

e = e.replace_all(f(x), 6)

which yields 11 + x.

Wildcards

Let us now try to replicate the factorial function pattern match mentioned above. For that we need to be able to match to any numerical value in the function f and we do not know that value in advance. Writing out an explicit rule for every desired number, e.g., f(40) = 40*f(39) is possible, but tedious. Instead, we use a wildcard that can match any subexpression. The specific rules will be explain later.

A wildcard is defined as a variable ending in a _ (note that the name of the Python variable does not matter). We define a wildcard n_ and write the rule:

from symbolica import Expression
n_ = Expression.var('n_')
f = Expression.fun('f')
e = f(4)
e = e.replace_all(f(0), 1)
e = e.replace_all(f(n_), n_*f(n_-1))
print(e)

This is almost perfect; the pattern still matches to negative numbers, and non-numbers. We can restrict the pattern by adding a third argument to replace_all:

e = e.replace_all(f(n_), n_*f(n_-1), n_ > 0)

Rules

We now set out all the rules for when patterns match.

Syntactic matching

Patterns match syntactically / structurally, which means that the patten must appear explicitly in the tree representation of the expression. For example, the pattern \(x^2\) is not found in the expression \((x+1)^2\), even though it appears in the mathematically equivalent (but structurally different) expression \(x^2+2x+1\).

The pattern does not necessarily have to appear verbatim in the tree structure though. Symbolica uses mathematical properties such as the symmetry of the multiplication and addition operator, and of symmetric functions, to match atoms in unordered fashion. For example \(x + z\) matches \(x+y+z\), even though \(y\) is “in between” in the normal form.

Since matches on products, sums and symmetric functions are unordered, in order to establish that there is no match, in the worst case all permutations or subsets have to be tested. This could be expensive. Providing constraints on the pattern, especially length constraints, will help reduce the cost.

Wildcards

Wildcards are variables ending in an underscore _. Wildcards can match any subexpression and will always include the operator it matches. For example, matching x_ on a*b*c yields:

flowchart TD
    Mul --> a
    Mul --> b
    Mul --> c

flowchart TD
    Mul --> a
    Mul --> b

flowchart TD
    Mul --> a
    Mul --> c

flowchart TD
    Mul --> b
    Mul --> c

flowchart TD
    Mul --> a

flowchart TD
    Mul --> b

flowchart TD
    Mul --> c

flowchart TD
    Mul

The cases where one or zero sub-atoms are matched is subject to downcasting. For example,

flowchart LR
    Mul --> a

is transformed to

flowchart LR
    a

which means that the atom type of x_ is no longer Mul. The atom type of the empty match is Empty. Downcasting ensures that repeated patterns such as x_*f(x_) match to x*f(x) even though the first x_ matches Mul Var x and the second one Arg Var x.

Function arguments behave analogously to the case of Mul described above, except that the order is preserved if the function is non-symmetric. The pattern matcher interprets function arguments as an operator of type Arg. For example, when matching f(x_) to f(a,b,c) the pattern matcher views the arguments as

flowchart TD
    Arg --> a
    Arg --> b
    Arg --> c

Repeated wildcards

A repeated wildcard means that the matched value must evaluate to exactly the same atoms. For example:

e = x*y*f(x*y)
e = e.replace_all(x_*f(x_), 1)

matches because x_ matches to x*y outside of the function and inside the function. See Examples for more complicated examples.

Precedence rules

The expression that is tested first is the root node with all its children. If that does not match, the subset of the root node with one sub-atoms removed is tested. If no match is found, two sub-atoms are removed, etc. Once all subsets are tested, the pattern matcher repeats the process for each of the sub-atoms as the new root.

For example, the pattern x_ will match any subexpression in any expression, so it will match the root first:

e = x*y*z
e = e.replace_all(x_, 1)

will yield 1, since x_ matches x*y*z.

In the following case the pattern matches at the root level, so a match is returned, even though the child would have matched too:

e = f(f(x))
e = e.replace_all(f(x_), f(1))

will yield f(1), since x_ matches f(x).

In the following case the root did not match, so the sub-atom is matched:

e = g(f(x))
e = e.replace_all(f(x_), f(1))

will yield g(f(1)), since x_ matches f(x).

replace_all will always replace the first match found for every non-overlapping match. To iterate matches, see Match iteration.

Ordering

A wildcard will match to a given set of atoms only once and it will have the order of the normal form. This means that for a symmetric function f(1,2,3), f(x_) will generate one match, x_ = 1,2,3, and it will never permute through all options (e.g. x_ = 2,3,1). Consequently,

f = Expression.fun('f')
f_sym = Expression.fun('fsym', symmetric=True)
e = f(3,2,1)*fsym(1,2,3)
e = e.replace_all(f(x_)*fsym(x_), f(1))

will not match.

Restrictions

Wildcards can be restricted based on arbitrary conditions.

Some built-in options are:

Wildcard length

Filter on the length of the wildcard before downcasting. The length is defined as the number of sub-atoms for Add, Mul, and Arg and is 1 for any other atom. By default a wildcard has a minimum length of 1.

Note

A function has a length of 1 (it counts as one atom) regardless of the number of arguments. This way x_ with a wildcard length of 1 matches f(...) regardless of the number arguments.

Let us restrict the wildcard x_ to a length between 2 and 3

e1 = f(1).replace_all(f(x_), 1, x_.req_len(2, 3))
e2 = f(1,2).replace_all(f(x_), 1, x_.req_len(2, 3))
e3 = f(1,2,3).replace_all(f(x_), 1, x_.req_len(2, 3))

then only e2 and e3 will give 1.

Restricting the wildcard length of x_ to 1,

e1 = f(x*y).replace_all(f(x_), 1, x_.req_len(1, 1))

we get the match x_ = x*y, even though x*y has a length of 2. This is because the length constraint is applied before downcasting.

A wildcard length restriction check is applied at any point that a wildcard is used and therefore

x*y*f(x*y).replace_all(x_*f(x_), 1, x_.req_len(2, 2))

does not match, since x_ has wildcard length if 1 inside the function argument. To restrict the length of the atom matched to x_ after downcasting, use a filter function.

Type restriction

A wildcard can be restricted based on the atom type.

For example, x_ can only match a variable:

e1 = f(x).replace_all(f(x_), 1, x_.req_var(AtomType::Var))
Filter function

Custom filters can be added to restrict any wildcard. This is a function receives the wildcard name and its match expression as an argument and should return a boolean. If true, the match is accepted.

from symbolica import Expression
x_ = Expression.var('x_')
f = Expression.fun('f')
e = f(1)*f(2)*f(3)
e = e.replace_all(f(x_), 1, x_.req(lambda m: m == 2 or m == 3))
Tip

Since a Python function is called, this operation has significant overhead. For high-performance code, consider implementing the filer in Rust.

Comparison function

A more complicated class of custom filters is based on using the values of two wildcards.

from symbolica import Expression
x_, y_ = Expression.vars('x_', 'y_')
f = Expression.fun('f')
e = f(1)*f(2)*f(3)
e = e.replace_all(f(x_)*f(y_), 1, x_.req_cmp(y_, lambda m1, m2: m1 + m2 == 4))
Tip

In Python, restrictions can be chained using &.

Match iteration

It is possible to iterate through all matches without modifying the expression.

For example, here f(x_) is matched:

from symbolica import Expression
x_ = Expression.var('x_')
f = Expression.fun('f')
e = f(1)+f(2)+f(3)

for m in e.match(f(x_)):
    print(m[x_])

which yields

1
2
3

The match function returns a dictionary with the wildcard as keys.

The match function also yields nested matches:

from symbolica import Expression
x_ = Expression.var('x_')
f = Expression.fun('f')
e = f(f(1))

for m in e.match(f(x_)):
    print(m[x_])

which yields

f(1)
1

Replacements

We have already seen many examples of replacing all occurrences of a pattern in this section. An iterator over single replacements can be generated as well:

from symbolica import Expression
x_ = Expression.var('x_')
f = Expression.fun('f')
e = f(1)*f(2)*f(3)
for r in e.replace(f(x_), f(x_ + 1)):
    print(r)

which yields

f(2)*f(2)*f(3)
f(1)*f(3)*f(3)
f(1)*f(2)*f(4)

Transformers

Often the goal of a pattern match and replacement is to isolate a part of the expression and to modify it to something else. Rather than simply allowing one atom to be replaced by another, functions can be executed for the replacement instead. These are called transformers. A transformer takes a pattern with wildcards as an argument and executes an operation on it after the wildcards have been substituted.

For example:

from symbolica import Expression, Transformer

x, x_ = Expression.vars('x','x_')
f = Expression.fun('f')
e = f((x+1)**2)
print(e.replace_all(f(x_), f(Transformer.expand(x_))))

Examples

Multiple matches

from symbolica import Expression
x_, y_, z_, w_, a_ = Expression.vars('x_', 'y_', 'z_', 'w_', 'a_')
f, g = Expression.funs('f', 'g')
e = f(1,2,3,4)*g(5,2,3,6,7)
for m in e.match(f(x_,y_,z_)*g(w_,y_,a_)):
    print('{}\t{}\t{}\t{}\t{}'.format(m[x_], m[y_], m[z_], m[w_], m[a_]))

yields:

1        2        arg(3,4) 5        arg(3,6,7)
1        arg(2,3) 4        5        arg(6,7)
arg(1,2) 3        4        arg(5,2) arg(6,7)

Coefficient extraction

The coefficients of the polynomial x^2*(y+z) + x^3*(y+z^2) in x are matched:

from symbolica import Expression

x, y, z, n_, x_ = Expression.vars('x', 'y', 'z', 'n_', 'x_')
e = x**2*(y+z) + x**3*(y+z**2)

# match returns a dictionary that maps every wildcard to its value
coeff_list = [(m[n_], m[x_]) for m in e.match(x**n_*x_)]
for (pow, content) in coeff_list:
    print(x**pow, content)