I should correct my previous e-mail and say that the popularity of *this kind of rich pattern matching* has been dead since the 90s.
On Thu, Jul 17, 2014 at 7:07 PM, Matthew Rocklin <mrock...@gmail.com> wrote: > 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-FetK73aQ%3D6JWXsj7kpoxW4dgNPsrifE%3DCLZsOt9VhOKw%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
