Fix for pattern matching
Dear all, while using GiNaC, I came across a strange behaviour with pattern matching in products having more than one wildcard. The match succeeded in a probablistic fashion. My conclusion is, that expairseq::match dishonors the rule, that repl_lst will remain unchanged whenever false is returned. See the attached patch, which solves the problem for me. Anyway, I started to think about the whole matching mechanism. Wouldn't it be much easier, if the matching was done from the patterns perspective? A wildcard would know itself to match to anything. And it might be possible to match a single object to a product of this object and a global wildcard, since expairseq would know how to handle that. See for example 'sin(phi).match(sin(wild(0))*wild(1))'. There could be wildcards matching to everything not containing a specified Symbol. And in every case basic would only need to check for type equality and matchable operands. I think one can even implement that preserving the current interface by calling an internal virtual match with interchanged operands. Any thoughts on that? Best wishes, Matthias Dellweg
Hi, On Thu, Dec 5, 2013 at 1:11 PM, Matthias Dellweg <dellweg@tp1.uni-duesseldorf.de> wrote:
while using GiNaC, I came across a strange behaviour with pattern matching in products having more than one wildcard. The match succeeded in a probablistic fashion.
Could you please give some examples so I can make a proper test case?
My conclusion is, that expairseq::match dishonors the rule, that repl_lst will remain unchanged whenever false is returned. See the attached patch, which solves the problem for me.
Thanks for the patch. I've glanced through it and it looks reasonable. I'll do more test and merge it during the next week (I'm a bit busy at the moment). Best regards, Alexei
Am Fri, 06 Dec 2013 10:47:19 +0200 schrieb Alexei Sheplyakov <alexei.sheplyakov@gmail.com>:
while using GiNaC, I came across a strange behaviour with pattern matching in products having more than one wildcard. The match succeeded in a probablistic fashion.
Could you please give some examples so I can make a proper test case?
Try this: exmap repl_lst; cout << (t*t*exp(t*A)).match(pow(t, wild(0))*exp(wild(1))*A, repl_lst) << repl_lst << endl; It turns out, my repl_lst was actually prefilled by a failed match before. It didn't fail on its own. But it must somehow be possible to create a Situation where a single match triggers this problem on its own. Kind regards, Matthias
Am Sat, 07 Dec 2013 00:03:30 +0100 schrieb Matthias Dellweg <dellweg@tp1.uni-duesseldorf.de>:
But it must somehow be possible to create a Situation where a single match triggers this problem on its own.
Finally found it: for i in $(seq 1 30); do echo 'match((exp(A)*sin(x))+(exp(B)*sin(y)), (exp(A)*sin($0))+(exp(B)*sin($1)));' | ginsh ; done without the patch it fails approximately in one out of four cases. With the patch it seems to succeed every time. Kind regards, Matthias Dellweg
Hi, Matthias, On Mon, Dec 9, 2013 at 3:08 PM, Matthias Dellweg <dellweg@tp1.uni-duesseldorf.de> wrote:
Finally found it:
for i in $(seq 1 30); do echo 'match((exp(A)*sin(x))+(exp(B)*sin(y)), (exp(A)*sin($0))+(exp(B)*sin($1)));' | ginsh ; done
without the patch it fails approximately in one out of four cases. With the patch it seems to succeed every time.
Thanks a lot. I've committed the fix and a test case (almost a week ago, sorry for a late notification). Best regards, Alexei
Am Wed, 18 Dec 2013 21:29:51 +0200 schrieb Alexei Sheplyakov <alexei.sheplyakov@gmail.com>:
Hi, Matthias,
On Mon, Dec 9, 2013 at 3:08 PM, Matthias Dellweg <dellweg@tp1.uni-duesseldorf.de> wrote:
Finally found it:
for i in $(seq 1 30); do echo 'match((exp(A)*sin(x))+(exp(B)*sin(y)), (exp(A)*sin($0))+(exp(B)*sin($1)));' | ginsh ; done
without the patch it fails approximately in one out of four cases. With the patch it seems to succeed every time.
Thanks a lot. I've committed the fix and a test case (almost a week ago, sorry for a late notification).
Best regards, Alexei _______________________________________________ GiNaC-devel mailing list GiNaC-devel@ginac.de https://www.cebix.net/mailman/listinfo/ginac-devel
Hi Alexei, did you check, whether your test fails probablistically within one single process? I thougt the sorting order depends on the memorylayout of the program. Therefor it was stable inside the debugger or one process, but unstable accross several runs of the program. And again: What do you think about inverting the matching from the expression trying to match a pattern to the pattern trying to fit to an expression? Best wishes, Matthias
participants (2)
-
Alexei Sheplyakov
-
Matthias Dellweg