Patterns

Patterns provide the principal way of analyzing ground expressions.

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 Env₁ and Env₂ be different variants of matching Ge against P. Consider all variables appearing in P. Since Env₁ and Env₂ are different, P must contain some variables whose values in Env₁ and Env₂ are different. Let V be the left-most of such variables, and compare the length of the values assigned to V by Env₁ and Env₂. If the value assigned by Env₁ is shorter than the value assigned by Env₂, then Env₁ is assumed to "precede" Env₂ (i.e. to take precedence over Env₂), otherwise Env₂ is assumed to "precede" Env₁.

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)}