# 4. Pattern matching¶

Pattern matching is an essential part of a term manipulation system. It provides a way to modify a term by its shape and relations instead of by the actual contents. We introduce wildcards, which are denoted as letters followed by a question mark, to match to variables, numbers, and subexpressions.

Note

To see the output for the following examples, either a `print`

has to be added to the source code,
or reFORM must be run with the `-v`

command line option.

For example:

```
expr F = f(5);
apply {
id f(x?) = f(x? + 1);
}
```

will match the wildcard `x?`

to `5`

, consequently add 1 to it, and yield

```
f(6)
```

Note

Contrary to Form, the question mark is repeated on the right hand side!

A wildcard will match any function argument if it occurs by itself

```
expr F = f(1+x,3);
apply {
id f(x?,3) = x?;
}
```

yields

```
1+x
```

A pattern at the ground level (not inside functions) can match to a subpart of the factors:

```
expr F = f(1)*f(f(4*x));
apply {
id f(f(y?)) = y?;
}
```

yields

```
f(1)*x*4
```

If the pattern contains a term with multiple wildcards, the number needs to match exactly.

```
expr F = f(x1*x2);
apply {
id f(y1?*y2?) = f(y1,y2);
}
```

yields

```
1+x
```

So,

```
expr F = f(x1*x2*x3);
apply {
id f(y1?*y2?) = f(y1,y2);
}
```

does not match. In this previous case, there are multiple options. `y1`

could have matched to
`x1`

and to `x2`

. The match that reFORM picks is deterministic. If you want to obtain all options,
see the `id all`

option.

A wildcard can be restricted to a certain set of options:

```
expr F = f(f(4))*f(f(3));
apply {
id f(x1?{f(4)}) = f(x1);
}
```

will only match to `f(4)`

. The restriction can be any expression. However, at the moment
they are not allowed to include any wildcards. Additionally, for numbers you can use
number ranges in the sets: `<=5,>=5,<5,>5`

to match a number in a range relative to a
reference number (5 in this example.)

```
expr F = f(1)*f(4);
apply {
id f(x?{>3}) = f(x1 + 1);
}
```

will only change `f(4)`

.

Fractional numbers are allowed, i.e., `f(x?{>1/2})`

will work as intended.

A function name can also be a wildcard:

```
expr F = g(4);
apply {
id f?(x?) = f?(x? + 1);
}
```

yields `g(5)`

.

## 4.1. Ranged wildcards¶

The pattern matcher can also match ranges of function arguments using
ranged wildcards. These wildcard have a question mark on the front: e.g., `?a`

.

For example:

```
expr F = f(1,2,3,4);
apply {
id f(?a,4) = f(?a);
}
```

yields

```
f(1,2,3)
```

Using a combination of ranged wildcards and wildcards, some complex patterns can be matched:

```
expr F = f(1,2,f(3),4)*f(1,2,f(3));
apply {
id f(?a,x?,?b)*f(?c,x?,?d) = f(?a,?b,?c,?d);
}
```

yields

```
f(1,2,4,1,2)
```

Note that ranged wildcards can be empty.

## 4.2. Many-mode¶

The `many`

option can be used to let reFORM apply a pattern to the input
as often as possible.

```
expr F = x^2;
apply {
id many x = 5;
}
```

yields

```
25
```

A more complicated example is shown below:

```
expr F = x*y^4*z;
apply {
id many x?*y^2 = f(x?);
}
```

yields

```
f(x)*f(z)
```

## 4.3. Obtaining all matches¶

All matches can be obtained using the `all`

option to `id`

.
For example:

```
expr F = f(1,2,f(x1*x2,x3*x4,x5*x6),x1*x3,x3*x5);
apply {
id all f(1,2,f(?a,x1?*x2?,?b),?c,x1?*x3?) = f(x1?,x2?,x3?);
}
```

yields

```
f(x3,x4,x5)+f(x5,x6,x3)
```