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)