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/