Syntax
Pattern = DirectionDesignator PatternExpression.
DirectionDesignator = [ "$l" | "$r" ].
PatternExpression =
{ PatternTerm | NamedExpression }.
PatternTerm =
StaticSymbol | Variable |
"(" PatternExpression ")".
A pattern is a pattern expression, which may be preceded by a direction designator
$l or $r. The designator $l indicates
that the pattern matching must be done from left to right. The designator
$r indicates that it must be done from right to left. If the direction
designator is omitted, the designator $l is implied.
If two different variables appear in the same pattern expression, they must have different
indices.
Pattern Matching
An environment Env is said to be a result of matching a ground expression
Ge against a pattern P in an initial environment
Env0, if the following conditions holds.
-
The environment Env is an extension of
Env0, i.e. dom[Env] includes
dom[Env0], and for all V in
dom[Env0] holds
Env(V)=Env0(V).
-
If each variable V appearing in P is replaced with
Env(V), and the direction designator is removed, the ground
expression thus obtained is Ge.
This environment Env is said to be a variant of matching
Ge against P in the environment
Env0, and the set of such variants of matching is denoted by
Match(Env0,Ge,P).
The set Match(Env0,Ge,P) is assumed to be equipped with the
order relation defined by the following rules.
Suppose Match(Env0,Ge,P) contains two different variants of
matching Env1 and Env2. Consider all
occurrences of variables in P.
If P has the direction designator $l, find the leftmost
occurrence that is given different values by the matching variants
Env1 and Env2.
If P has the direction designator $r, find the rightmost
occurrence that is given different values by the matching variants
Env1 and Env2.
Suppose the occurrence found is an occurrence of a variable V. Then
compare Env1(V) to Env2(V). If
Env1(V) is shorter than Env2(V),
then Env1 is taken to precede Env2.
Otherwise Env2 is taken to precede
Env1.
A finite sequence of environments Env1,
Env2, ..., Envn is written as
[Env1, Env2, ... , Envn], and the
empty sequence as [].
[Env0]^[Env1,...,Envn] denotes
[Env0, Env1,..., Envn].
A judgment Env0 |- Ge : P =>
[Env1,...Envn] means that Match(Env0,Ge,P)
= {Env1,...,Envn}, where Envi
precedes Envj for all i<j.
Examples
Here are examples of patterns:
t.Head e.Tail
eX (eY)
eA '+' eB
$l eA '+' eB
$r eA '+' eB
Here are examples of pattern matching:
{} |- A () C D E : $l sX tY tZ e1
=> [ {sX = A, tY = (), tZ = C, e1 = D E} ]
{} |- 1 2 3 : $l eA eB => [
{eA = , eB = 1 2 3},
{eA = 1, eB = 2 3},
{eA = 1 2, eB = 3},
{eA = 1 2 3, eB = } ]
{} |- 1 2 3 : $r eA eB => [
{eA = 1 2 3, eB = },
{eA = 1 2, eB = 3 },
{eA = 1, eB = 2 3 },
{eA = , eB = 1 2 3 } ]
{eA = 1 2} |- $l 1 2 3 4 5 : eA eB
=> [ {eA = 1 2, eB = 3 4 5} ]