Patterns may contain symbols, parentheses, and variables. For example:
A B C
tX (eY B)
A pattern may be regarded as representing the set of all ground expressions that can be
produced from the pattern by replacing the pattern's variables by some values consistent with
the types of the variables. For example, the pattern A eX represents the set
of ground expressions beginning with the symbol A, and the pattern sX
sY the set of ground expressions consisting of exactly two symbols.
If there are several occurrences of the same variable in a pattern, all the occurrences must
be bound to the same value. For example, the pattern tX tX represents the set
of ground expressions consisting of two equal terms.
Let Ge be a ground expression, and P a pattern. Then
Ge can be matched against P to determine whether
Ge has the structure specified by P. If so, the matching
of Ge against P is said to succeed, otherwise to fail.
If the matching of Ge against P succeeds, the variables
appearing in P are bound to the corresponding components of
Ge. Thus, the result of matching Ge against
P is an environment Env. For example, the result of matching
the ground expression AAA BBB CCC against the pattern eX sY
is the environment {eX = AAA BBB, sY = CCC}.
Now let us try to match the ground expression A B C against the pattern
e1 sX e2. It can be easily seen that the matching can succeed in three
different ways, resulting in three different environments:
{e1 = , sX = A, e2 = B C}
{e1 = A, sX = B, e2 = C}
{e1 = A B, sX = C, e2 = }
What is to be considered the result of matching in such situations? Refal Plus solves the
problem in the following way. All variants of matching are considered to be acceptable, but
some of variants "take precedence" over others.
More specifically, let Env1 and Env2
be different variants of matching Ge against P. Consider all
variables appearing in P. Since Env1 and
Env2 are different, P must contain some
variables whose values in Env1 and
Env2 are different. Let V be the left-most of
such variables, and compare the length of the values assigned to V by
Env1 and Env2. If the value
assigned by Env1 is shorter than the value assigned by
Env2, then Env1 is assumed to
"precede" Env2 (i.e. to take precedence over
Env2), otherwise Env2 is assumed to
"precede" Env1.
For example, matching the ground expression (A1 A2 A3) (B1 B2) against the
pattern e1 (eX sA eY) e2 results in the following set of environments
{e1 = , eX = , sA = A1, eY = A2 A3, e2 = (B1 B2)}
{e1 = , eX = A1, sA = A2, eY = A3, e2 = (B1 B2)}
{e1 = , eX = A1 A2, sA = A3, eY = , e2 = (B1 B2)}
{e1 = (A1 A2 A3), eX = , sA = B1, eY = B2, e2 = }
{e1 = (A1 A2 A3), eX = B1, sA = B2, eY = , e2 = }
where the variants of matching are listed in accordance with their precedence, i.e. the first
variant comes first, etc.
If the variants of matching are ordered as described above, the matching is said to be done
from left to right. Refal Plus, however, enables the matching to be also done from right to
left, which means that, instead of comparing the values of the leftmost variable, we have to
compare the values of the right-most variable. The direction of matching can be changed by
prefixing the key word $r to the pattern. For example, if the ground
expression (A1 A2 A3) (B1 B2) is matched against the pattern $r e1
(eX sA eY) e2, the set of variants of matching will be ordered as follows:
{e1 = (A1 A2 A3), eX = B1, sA = B2, eY = , e2 = }
{e1 = (A1 A2 A3), eX = , sA = B1, eY = B2, e2 = }
{e1 = , eX = A1 A2, sA = A3, eY = , e2 = (B1 B2)}
{e1 = , eX = A1, sA = A2, eY = A3, e2 = (B1 B2)}
{e1 = , eX = , sA = A1, eY = A2 A3, e2 = (B1 B2)}