flowchart LR Mul --> a

# 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.

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
= Expression.var('x')
x = Expression.fun('f')
f = x + f(x) + 5
e = e.replace_all(x, 6)
e print(e)
```

We get `11 + f(6)`

To replace `f(x)`

by `6`

, we change the pattern:

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

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
= Expression.var('n_')
n_ = Expression.fun('f')
f = f(4)
e = e.replace_all(f(0), 1)
e = e.replace_all(f(n_), n_*f(n_-1))
e 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.replace_all(f(n_), n_*f(n_-1), n_ > 0) e `

## 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 the following options:

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

Note that the empty set is one of the options. Because of the rule of syntactic matching, the pattern `y + x_`

is not present in the expression `y`

even though `x_`

can be the empty set.

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

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

When a wildcard that matches multiple arguments is used outside of a function context on the right-hand side of a replacement, the matched arguments will be wrapped in the internal function `arg`

. For example:

`= f(1,2).replace_all(f(x_), x_) e `

yields `arg(1,2)`

. An `arg`

function that is placed into a function context again, is flattened during normalization, e.g., `f(arg(1,2)) = f(1,2)`

.

### Repeated wildcards

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

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

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:

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

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:

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

will yield `f(1)`

, since `x_`

matches `f(x)`

.

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

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

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,

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

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.

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

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

then only `e2`

and `e3`

will give `1`

.

Restricting the wildcard length of `x_`

to 1,

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

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

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

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:

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

##### 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
= Expression.var('x_')
x_ = Expression.fun('f')
f = f(1)*f(2)*f(3)
e = e.replace_all(f(x_), 1, x_.req(lambda m: m == 2 or m == 3)) e
```

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
= Expression.vars('x_', 'y_')
x_, y_ = Expression.fun('f')
f = 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)) e
```

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
= Expression.var('x_')
x_ = Expression.fun('f')
f = f(1)+f(2)+f(3)
e
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
= Expression.var('x_')
x_ = Expression.fun('f')
f = f(f(1))
e
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
= Expression.var('x_')
x_ = Expression.fun('f')
f = f(1)*f(2)*f(3)
e 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
= Expression.vars('x','x_')
x, x_ = Expression.fun('f')
f = f((x+1)**2)
e print(e.replace_all(f(x_), f(Transformer.expand(x_))))
```

## Examples

#### Multiple matches

```
from symbolica import Expression
= Expression.vars('x_', 'y_', 'z_', 'w_', 'a_')
x_, y_, z_, w_, a_ = Expression.funs('f', 'g')
f, g = f(1,2,3,4)*g(5,2,3,6,7)
e 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
= Expression.vars('x', 'y', 'z', 'n_', 'x_')
x, y, z, n_, x_ = x**2*(y+z) + x**3*(y+z**2)
e
# match returns a dictionary that maps every wildcard to its value
= [(m[n_], m[x_]) for m in e.match(x**n_*x_)]
coeff_list for (pow, content) in coeff_list:
print(x**pow, content)
```