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)