The benefit of pattern matching is that 10000 complex if-then-else constructions are hard to write well. Richard the popularity of pattern matching has been pretty much dead since the 90s. That being said it isn't a poor crutch, languages like Maude, Elan, and more recently Stratego/XT demonstrate proof of concept pretty well (IMO.) I would suggest reviewing these projects and their associated literature before deprecating it further.
Ondrej my understanding is that if you don't care about associativity/commutativity then you can do many-patterns-to-one-expression matching with a Trie <http://en.wikipedia.org/wiki/Trie>. If you do care about associative/commutative operators (which you probably do) then this is harder. The data structure I've heard tossed around is the discrimination net. I have a paper lying around on the topic that I can dig it up if someone is interested (thank you Mendeley.) Generally speaking this is a doable but difficult computer science problem. Known solutions exist but they're in papers, not in textbooks. I think that this work would be appropriate for a GSoC student over a summer or for a clever computer science student over a week or two. I don't personally expect any of the core-devs-with-other-jobs to get around to it for a while though of course I'd be thrilled if that were the case. (Prove me wrong Ondrej!) This is also the sort of thing that would benefit from a performant core. We would write patterns in SymPy and then match them using some C++ matching system. This is likely a purely structural operation and so shouldn't require any of the Python logic code. The patterns would probably translate well between SymPy and CSymPy. On Thu, Jul 17, 2014 at 6:38 PM, Ondřej Čertík <ondrej.cer...@gmail.com> wrote: > On Thu, Jul 17, 2014 at 7:27 PM, Richard Fateman <fate...@gmail.com> > wrote: > > Rubi is apparently structured so that at any time at most one rule will > be > > applicable, > > and it should be easy to figure out how to exclude everything else. I > think > > that > > Albert Rich even expressed the notion that Rubi did not actually need to > be > > structured as rules.. > > --- just If/then/else > > That's a good point --- it is my understanding as well, that the rules > are mutually exclusive. > So perhaps one doesn't need a general pattern matching for that, just > a specialized version, > essentially if/then/else, as you said. > > Ondrej > > > > > The point of the matching/ rule stuff in Macsyma (Maxima) is that > > if you are using a pattern to find A and B in > > z = A*x+B with A,B, free of x, then maybe you should compile the > match > > into a call to > > compute the simplified polynomial form of z as a linear polynomial in > x. > > Pick off the > > coefficients A and B. test them with whatever you need to do. e.g. A > is > > non-zero and > > of course free of x by construction. B is of course free of x as well. > > And there is no > > higher power of x. Instead of groveling around looking for terms to > > collect under the > > name A and B, rearranging stuff and discovering later that you have to > > rearrange again > > to satisfy predicates attached later... > > > > If pattern matching is a crutch, and a poor one at that, maybe its use > > should be > > limited, and its popularity toned down. > > > > RJF > > > > > > On Thursday, July 17, 2014 5:52:48 PM UTC-7, Ondřej Čertík wrote: > >> > >> On Thu, Sep 26, 2013 at 6:37 PM, Aaron Meurer <asme...@gmail.com> > wrote: > >> > My idea was to put assumptions on Wild expressions. I guess using the > >> > new assumptions system, the assumptions do not need to be, nor should > >> > they be, actually tied to the symbols. This will also make it easy to > >> > add assumptions about general expressions, not just Wilds (and make it > >> > easier to do the sorts of things Angus was talking about). So > >> > something like > >> > > >> > expr = x + 2 > >> > a = Wild('a', exclude=[x]) > >> > expr.match(x + a, assumptions=Q.positive(a)) > >> > > >> > would work, but for > >> > > >> > expr = x - 2 > >> > > >> > it would not match. > >> > > >> > One could then specify arbitrary assumptions, and match would refuse > >> > to return any result where the assumptions are False. Or you could add > >> > a flag to make it even stronger: don't return a result unless the > >> > assumptions are True (as opposed to None). > >> > > >> > This may be far reaching and could be a bad idea, but I think we could > >> > then extend the assumptions system to allow "assumptions" like > >> > Q.free_of(a, x) to mean that a does not depend on x, or > >> > Q.isinstance(a, Mul) to mean that a is a Mul. > >> > > >> > The new assumptions system is still relatively weak and needs to be > >> > integrated into SymPy better, so this would be a lofty goal. But > >> > assuming we can unify the system, and get something like > >> > https://code.google.com/p/sympy/issues/detail?id=3929, I think this > >> > would be a nice way to specify things, much better (and more powerful) > >> > than throwing a bunch of lambdas around. > >> > >> > >> So we definitely need to implement Rubi, I created an issue for it > >> with motivation + steps to do: > >> > >> https://github.com/sympy/sympy/issues/7749 > >> > >> a prerequisite and a separate issue is fast pattern matching, that can > >> handle ~10,000 rules quickly, which needs to be based > >> on a decision tree: > >> > >> https://github.com/sympy/sympy/issues/7748 > >> > >> I have explained in details how it could work there. So it will > >> require to rewrite the pattern matching, but I think most of the > >> things from the current one can be reused, essentially one just > >> traverses the expression tree just like now, but for all the rules at > >> once using a decision tree. > >> > >> The #7748 is independent of #7749, but I think both issues should be > >> solved concurently, as #7749 provides an application for #7748, that > >> needs to work well and fast. > >> > >> Ondrej > > > > -- > > You received this message because you are subscribed to the Google Groups > > "sympy" group. > > To unsubscribe from this group and stop receiving emails from it, send an > > email to sympy+unsubscr...@googlegroups.com. > > To post to this group, send email to sympy@googlegroups.com. > > Visit this group at http://groups.google.com/group/sympy. > > To view this discussion on the web visit > > > https://groups.google.com/d/msgid/sympy/7461f206-3ce2-49bb-bb43-a676ccec2091%40googlegroups.com > . > > For more options, visit https://groups.google.com/d/optout. > > -- > You received this message because you are subscribed to the Google Groups > "sympy" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sympy+unsubscr...@googlegroups.com. > To post to this group, send email to sympy@googlegroups.com. > Visit this group at http://groups.google.com/group/sympy. > To view this discussion on the web visit > https://groups.google.com/d/msgid/sympy/CADDwiVB7MshHjeB%3D7O1mYwUZbOORntq-H2LmNRQwXkzDqTiDHQ%40mail.gmail.com > . > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "sympy" group. To unsubscribe from this group and stop receiving emails from it, send an email to sympy+unsubscr...@googlegroups.com. To post to this group, send email to sympy@googlegroups.com. Visit this group at http://groups.google.com/group/sympy. To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAJ8oX-Gr4Wgk%2BAfuTUKXe_TwB5n7rPkGc%2Bdo-phaiS%2BkSoXgeg%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
