\chapter{PM: A REDUCE pattern matcher}
\label{PM}
\typeout{{PM: A REDUCE pattern matcher}}
{\footnotesize
\begin{center}
Kevin McIsaac \\
The University of Western Australia \\
Australia\\[0.05in]
e--mail: kevin@wri.com
\end{center}
}
\ttindex{PM}
PM is a general pattern matcher similar in style to those found in systems
such as SMP and Mathematica.
A template is any expression composed of literal elements ({\em e.g.\ }{\tt
5}, {\tt a} or {\tt a+1}) and specially denoted pattern variables
({\em e.g.\ }{\tt ?a} or {\tt ??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, {\em
i.e.\ }f([a,1]) $\rightarrow$ f(a,1) and f(a,[1,2],b) $\rightarrow$ 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 {\tt exp1 -> exp2}, which means exp1 is replaced by exp2, or
{\tt 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 reached a place were it can make a different choice.
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
\ttindex{SEMANTIC}{\tt semantic}. By default it is on.
\section{The Match Function}
{\tt M(exp,template)}\ttindex{M}
The template is matched against the expression. If the template is
literally equal to the expression {\tt 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 {\tt NIL} is returned.
\begin{verbatim}
OPERATOR F;
M(F(A),F(A));
T
M(F(A,B),F(A,?A));
{?A->B}
M(F(A,B),F(??A));
{??A->[A,B]}
m(a+b+c,c+?a+?b);
{?a->a,?b->b}
m(a+b+c,b+?a);
{?a->a + c}
\end{verbatim}
This example shows the effects of semantic matching, using the
associativity and commutativity of {\tt +}.
\section {Qualified Matching}
A template may be qualified by the use of the conditional operator
{\tt \_=',}\ttindex{\_=} standing for {\bf 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 {\tt 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 {\tt T}.
\begin{verbatim}
load_package pm;
operator f;
if (m(f(a,b),f(?a,?b_=(?a=?b)))) then write "yes" else write"no";
no
m(f(a,a),f(?a,?b_=(?a=?b)));
{?B->A,?A->A}
\end{verbatim}
{\typeout {This is not true}}
\section{Substituting for replacements}
The operator {\tt S}\ttindex{S} substitutes the replacements in an
expression.
{\tt S(exp,{temp1->sub1,temp2->sub2,...},rept, depth);}
will do the substitutions for a maximum of {\tt rept} and to a depth of
{\tt depth}, using a breadth-first search and replace. {\tt rept} and
{\tt depth} may be omitted when they default to 1 and infinity.
{\tt SI(exp,{temp1->sub1,temp2->sub2,...}, depth)}\ttindex{SI}
will substitute infinitely many times until expression stops
changing.
{\tt SD(exp,{temp1->sub1,temp2->sub2,...},rept, depth)}\ttindex{SD}
is a depth-first version of {\tt S}.
\begin{verbatim}
s(f(a,b),f(a,?b)->?b^2);
2
b
s(a+b,a+b->a*b);
a*b
operator nfac;
s(nfac(3),{nfac(0)->1,nfac(?x)->?x*nfac(?x-1)});
3*nfac(2)
s(nfac(3),{nfac(0)->1,nfac(?x)->?x*nfac(?x-1)},2);
6*nfac(1)
si(nfac(4),{nfac(0)->1,nfac(?x)->?x*nfac(?x-1)});
24
s(a+b+f(a+b),a+b->a*b,inf,0);
f(a + b) + a*b
\end{verbatim}
\section{Programming with Patterns}
There are also facilities to use this pattern-matcher as a programming
language. The operator {\tt :-}\ttindex{:-} can be used to declare
that while simplifying all matches of a template should be replaced by
some expression. The operator {\tt ::-} is the same except that the
left hand side is not simplified.
\begin{verbatim}
operator fac, gamma;
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)
\end{verbatim}