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:
.. code-block:: reform
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
.. code-block:: reform
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
.. code-block:: reform
expr F = f(1+x,3);
apply {
id f(x?,3) = x?;
}
yields
.. code-block:: reform
1+x
A pattern at the ground level (not inside functions) can match to
a subpart of the factors:
.. code-block:: reform
expr F = f(1)*f(f(4*x));
apply {
id f(f(y?)) = y?;
}
yields
.. code-block:: reform
f(1)*x*4
If the pattern contains a term with multiple wildcards, the number needs
to match exactly.
.. code-block:: reform
expr F = f(x1*x2);
apply {
id f(y1?*y2?) = f(y1,y2);
}
yields
.. code-block:: reform
1+x
So,
.. code-block:: reform
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:
.. code-block:: reform
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.)
.. code-block:: reform
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:
.. code-block:: reform
expr F = g(4);
apply {
id f?(x?) = f?(x? + 1);
}
yields ``g(5)``.
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:
.. code-block:: reform
expr F = f(1,2,3,4);
apply {
id f(?a,4) = f(?a);
}
yields
.. code-block:: reform
f(1,2,3)
Using a combination of ranged wildcards and wildcards, some complex patterns can
be matched:
.. code-block:: reform
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
.. code-block:: reform
f(1,2,4,1,2)
Note that ranged wildcards can be empty.
Many-mode
----------------
The ``many`` option can be used to let reFORM apply a pattern to the input
as often as possible.
.. code-block:: reform
expr F = x^2;
apply {
id many x = 5;
}
yields
.. code-block:: reform
25
A more complicated example is shown below:
.. code-block:: reform
expr F = x*y^4*z;
apply {
id many x?*y^2 = f(x?);
}
yields
.. code-block:: reform
f(x)*f(z)
Obtaining all matches
---------------------
All matches can be obtained using the ``all`` option to ``id``.
For example:
.. code-block:: reform
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
.. code-block:: reform
f(x3,x4,x5)+f(x5,x6,x3)