Pattern matching in GiNaC CVS

[Christian Bauer]

Hi!

I have committed my first attempt at implementing pattern matching facilities
in GiNaC to the CVS now. It consists of two new things:

 - a wildcard class
 - a match() member function

Wildcards have an unsigned label to allow having multiple different wildcards
in one pattern. They are constructed with "wild(label)" and denoted "$0", "$1",
"$2" etc. in the output and in ginsh.

The match() function checks whether an expression matches a given pattern and
if so, fills a list with relations of the form "$0 == foo", "$1 == bar", etc.
to show the subexpressions matched by the wildcards. In ginsh, match() returns
FAIL if there's no match, and the relation list otherwise.

The subs() function has been modified to allow wildcards in the patterns and
in the replacement expressions. Likewise, has() also understands wildcards.

Some examples in ginsh to show how it works, and to show that it is not really
intelligent (it's better than nothing, though):

> match(a^b,$1^$2);
[$1==a,$2==b]
> match(a^b,$1^$1);
FAIL
> match(a^a,$1^$1);
[$1==a]
> match(a^a,$1^$2);
[$1==a,$2==a]

> match((a+b)*(a+c),($1+b)*($1+c));
[$1==a]
> match((a+b)*(a+c),(a+$1)*(a+$2));
[$1==c,$2==b]
  (Unpredictable. The result might also be [$1==c,$2==b].)
> match((a+b)*(a+c),($1+b)*($1+d));
FAIL
> match((a+b)*(a+c),($1+a)*($1+c));
FAIL
> match((a+b)*(a+c),($1+$2)*($1+$3));
FAIL
  (The result is undefined. Here, "$1+$2" matches "a+b" with $1==b,$2==a and
   the second factor can no longer be matched. Such thing may or may not work,
   depending on the sort order.)

> match(2*(x+y)+2*z-2,2*$1+$2);
[$1==z,$2==-2+2*x+2*y]
  (This is also ambiguous. Another possibility would be [$1=x+y,$2=2*z-2].
   It also shows that it is a syntactic match.)

> match(a+b+c,a+$1);
[$1==c+b]
> match(a+b+c,b+$1);
[$1==c+a]
> match(a+b+c,c+$1);
[$1==a+b]
> match(a+b+c,a+c+$1);
[$1==b]
  (A single wildcard in a sum or product gobbles up all remaining unmatched
   terms.)
> match(a+b+c,a+$1+$2);
[$2==b,$1==c]
  (Pure coincidence. It may also have happened that one of the wildcards
   eats the "a", causing the match to fail. But matching with "a+$1" as
   above is 100% reliable.)

> subs(a^2+b^2+c^2,$1^2==$1^4);
b^4+a^4+c^4
> subs(a^3+b^3+c^3,$1^2==$1^4);
b^3+c^3+a^3
  (It's still not an algebraic substitution...)
> match(a*b^2,a*b*$1);
FAIL
  (...let alone an algebraic match.)
> match(a*b^2,a^$1*b^$2);
FAIL
  (Likewise. The matching is purely syntactic.)

> subs(sin(x+y)^2+cos(x+y)^2, cos($1)^2==1-sin($1)^2);
1
  (Straightforward now.)

> subs(a+b+c,a+b==e);
c+a+b
  (Once again, we still don't do an algebraic substitution.)
> subs(a+b+c,a+b+$1==e+$1);
c+e
  (But this works.)
> subs(a+b,$1+a==2*$1);
2*b
> subs(a+b,$1+b==2*$1);
2*a
> subs(a+b,$1+$2==$1*$1);
b^2
  (Another random result, a^2 would also be possible.)
> subs(a+b,$1+$2==$1*$2);
a*b
> subs(a+b+c,$1+$2==$1*$2);
c*(a+b)
  (As you probably would have guessed by now, it might also have been any of
   the two other permutations of a, b and c.)
> subs(a+b+c,$1+$2+$3==$1*$2*$3);
c*a*b
  (This works again.)

> subs(sin(1+sin(x)),sin($1)==cos($1));
cos(1+cos(x))
  (This is the way it works now...)

> has(a^2+b^2+c^2,$1^2);
1
> has(a^2+b^2+c^2,$1^3);
0
> has(a^2+b^2+c^2,$1+$2);
1

Indices are currently matched by index value only. This will change.

You are encouraged to try this for yourself and find bugs. Any suggestions
are welcome as long as they are easy to implement. :^)

Bye,
Christian

-- 
  / Coding on PowerPC and proud of it
\/ http://www.uni-mainz.de/~bauec002/