| Up | Next | Prev | PrevTail | Tail |
PM is a general pattern matcher similar in style to those found in systems such as SMP and Mathematica, and is based on the pattern matcher described in Kevin McIsaac, “Pattern Matching Algebraic Identities”, SIGSAM Bulletin, 19 (1985), 4-13.
Author: Kevin McIsaac.
PM is a general pattern matcher similar in style to those found in systems such as SMP and Mathematica, and is based on the pattern matcher described in [McI85]. The following is a description of its structure.
A template is any expression composed of literal elements, e.g. 5, a, or a+1, and specially-denoted pattern variables, e.g. ?a or ??b. Atoms beginning with ? are called generic variables and match any expression.
Atoms beginning with ?? are called multi-generic variables and match any expression or any sequence of expressions including the null or empty sequence. A sequence is an expression of the form [a1,a2,...]. When placed in a function argument list the brackets are removed, i.e. f([a,1]) -> f(a,1) and f(a,[1,2],b) -> f(a,1,2,b).
A template is said to match an expression if the template is literally equal to the expression, or if by replacing any of the generic or multi-generic symbols occurring in the template, the template can be made to be literally equal to the expression. These replacements are called the bindings for the generic variables. A replacement is an expression of the form exp1 -> exp2, which means exp1 is replaced by exp2, or exp1 –> exp2, which is the same except exp2 is not simplified until after the substitution for exp1 is made. If the expression has any of the properties associativity, commutativity, or an identity element, they are used to determine if the expressions match. If an attempt to match the template to the expression fails the matcher backtracks, unbinding generic variables, until it reaches a place where it can make a different choice. It then proceeds along the new branch.
The current matcher proceeds from left to right in a depth-first search of the template expression tree. Rearrangements of the expression are generated when the match fails and the matcher backtracks.
The matcher also supports semantic matching. Briefly, if a subtemplate does not match the corresponding subexpression because they have different structures, then the two are equated and the matcher continues matching the rest of the expression until all the generic variables in the subexpression are bound. The equality is then checked. This is controlled by the switch semantic. By default it is on.
The template temp is matched against the expression exp. If the template is literally equal to the expression T is returned. If the template is literally equal to the expression after replacing the generic variables by their bindings then the set of bindings is returned as a set of replacements. Otherwise 0 (nil) is returned.
A “literal” template:
m(f(a), f(a)); t
Not literally equal:
m(f(a), f(b)); 0
Nested operators:
m(f(a,h(b)), f(a,h(b))); t
“Generic” templates:
m(f(a,b), f(a,?a));
{?a -> b}
m(f(a,b), f(?a,?b));
{?b -> b, ?a -> a}
The multi-generic symbol ??a matches the “rest” of the arguments:
m(f(a,b), f(??a));
{??a -> {[a, b]}
but the generic symbol ?a does not:
m(f(a,b), f(?a)); 0
Flag \(h\) as “associative”:
flag(’(h), ’assoc);
Associativity is used to group terms together:
m(h(a,b,d,e), h(?a,d,?b));
{?b -> e, ?a -> h(a,b)}
“plus” is a symmetric function:
m(a+b+c, c+?a+?b);
{?b -> a, ?a -> b}
and it is also associative
m(a+b+c, b+?a);
{?a -> c + a}
Note that the effect of using a multi-generic symbol is different:
m(a+b+c,b+??c);
{??c -> [c,a]}
A template may be qualified by the use of the conditional operator _=, such!-that. When a such-that condition is encountered in a template, it is held until all generic variables appearing in logical_exp are bound.
On the binding of the last generic variable, logical_exp is simplified and if the result is not T the condition fails and the pattern matcher backtracks. When the template has been fully parsed any remaining held such-that conditions are evaluated and compared to T.
m(f(a,b), f(?a,?b_=(?a=?b)));
0
m(f(a,a), f(?a,?b_=(?a=?b)));
{?b -> a, ?a -> a}
Note that f(?a,?b_=(?a=?b)) is the same as f(?a,?a).
Substitute the set of replacements into exp, re-substituting a maximum of rept times and to a maximum depth depth. rept and depth have the default values of 1 and \(\infty \) respectively. Essentially, S is a breadth-first search-and-replace. (There is also a depth-first version, Sd(...).) Each template is matched against exp until a successful match occurs.
Any replacements for generic variables are applied to the r.h.s. of that replacement and exp is replaced by the r.h.s. The substitution process is restarted on the new expression starting with the first replacement. If none of the templates match exp then the first replacement is tried against each sub-expression of exp. If a matching template is found then the sub-expression is replaced and process continues with the next sub-expression.
When all sub-expressions have been examined, if a match was found, the expression is evaluated and the process is restarted on the sub-expressions of the resulting expression, starting with the first replacement. When all sub-expressions have been examined and no match found the sub-expressions are reexamined using the next replacement. Finally when this has been done for all replacements and no match found then the process recures on each sub-expression. The process is terminated after rept replacements or when the expression no longer changes.
The command
Si(exp, {temp1 -> sub1, temp2 -> sub2, ...}, depth)
means “substitute infinitely many times until expression stops changing”. It is short-hand for S(exp,{temp1 -> sub1, temp2 -> sub2,...},Inf, depth).
s(f(a,b), f(a,?b) -> ?b\^{}2);
2
b
s(a+b, a+b -> a{*}b);
b*a
“Associativity” is used to group \(a+b+c\) to \((a+b)+c\):
s(a+b+c, a+b -> a*b); b*a + c
The next three examples use a rule set that defines the factorial function. Substitute once:
s(nfac(3), {nfac(0) -> 1, nfac(?x) -> ?x*nfac(?x-1)});
3*nfac(2)
Substitute twice:
s(nfac(3), {nfac(0) -> 1, nfac(?x) -> ?x*nfac(?x-1)}, 2);
6*nfac(1)
Substitute until expression stops changing:
si(nfac(3), {nfac(0) -> 1, nfac(?x) -> ?x{*}nfac(?x-1)});
6
Only substitute at the top level:
s(a+b+f(a+b), a+b -> a*b, inf, 0); f(b+a) + b*a
If during simplification of an expression, temp matches some sub-expression, then that sub-expression is replaced by exp. If there is a choice of templates to apply, the least general is used.
If an old rule exists with the same template, then the old rule is replaced by the new rule. If exp is nil the rule is retracted.
temp ::- exp is the same as temp :- exp, but the l.h.s. is not simplified until the replacement is made.
Define the factorial function of a natural number as a recursive function and a termination condition. For all other values write it as a gamma function. Note that the order of definition is not important, as the rules are re-ordered so that the most specific rule is tried first. Note the use of ::- instead of :- to stop simplification of the l.h.s. hold stops its arguments from being simplified.
fac(?x _= Natp(?x)) ::- ?x*fac(?x-1); hold(fac(?X-1)*?X) fac(0) :- 1; 1 fac(?x) :- Gamma(?x+1); gamma(?X + 1) fac(3); 6 fac(3/2); gamma(5/2)
In future simplifications automatically apply replacements rep1, rep2, ... until the rules are retracted. In effect, this replaces the operator -> by :- in the set of replacements {rep1, rep2, ...}.
Delete the rules rep1, rep2, ....
As we said earlier, the matcher has been constructed along the lines of the pattern matcher described in McIsaac with the addition of such-that conditions and “semantic matching” as described in Grief. To make a template efficient, some consideration should be given to the structure of the template and the position of such-that statements. In general the template should be constructed so that failure to match is recognized as early as possible. The multi-generic symbol should be used whenever appropriate, particularly with symmetric functions. For further details see McIsaac.
f(?a,?a,?b) is better than f(?a,?b,?c_=(?a=?b)). ?a+??b is better than ?a+?b+?c....
The template f(?a+?b,?a,?b), matched against f(3,2,1) is matched as f(?e_=(?e=?a+?b),?a,?b) when semantic matching is allowed.
trpm
Produces a trace of the rules applied during a substitution. This is useful to see how the pattern matcher works, or to understand an unexpected result.
In general usage the following switches need not be considered:
semantic
Allow semantic matches, e.g. f(?a+?b,?a,?b) will match f(3,2,1), even though the matcher works from left to right.
sym!-assoc
Limits the search space of symmetric associative functions when the template contains multi-generic symbols so that generic symbols will not function. For example (a+b+c,?a+??b) will return
{?a -> a, ??b -> [b,c]} or
{?a -> b, ??b -> [a,c]} or
{?a -> c, ??b -> [a,b]}
but not {?a -> a+b, ??b -> c}, etc. No sane template should require these types of matches. However they can be made available by turning the switch off.
| Up | Next | Prev | PrevTail | Front |
Hosted by