On May 2, 2010, at 10:46 AM, basti wrote: > The last few days I spent quite some time on understanding the pattern > matching and substitution logic in sympy and trying out ideas to > improve them. Now I feel able and willing to redesign most of the > stuff and will in the following give an overview about my plans. > > The ultimate goal is to have a matching algorithm which is mostly > described here: > http://github.com/bastikr/sympy/blob/match/doc/src/modules/matching.txt > > And a substitution algorithm described here: > http://github.com/bastikr/sympy/blob/subs/doc/src/modules/substitution.txt > > The best way to read these documents might be to fetch the > corresponding branches and build the docs to get nice html output. > (But since it's restructured text you can also read them directly) > > Maybe a short summary of the algorithms: > > * matching algorithm: > The matching rules will be controllable by hints which can be given to > the main match function. This function will check that all input > arguments are valid and pass on to a dispatching function which will > call for different input arguments specialized functions. (E.g there > are specialized functions for generic functions, Add, Mul, Pow, ...). > These specialized functions will try to match subexpressions to > corresponding subpatterns using special rules according to the given > hints. If something is matched a dictionary with the matched wilds is > returned (it's empty if there are no wilds) or None if the expression > does not match the pattern. > > * substitution algorithm > Substitution distinguishes between matching patterns which consist of > a single atomic object and complex patterns. Atomic substitution does > not care if the atom is a wild symbol or not - it stupidly just > replaces any occurrence by the substitution expression. This means > it's pretty fast but also less powerful than pattern matching. Pattern > matching tries to match subexpressions to the given pattern (using the > match algorithm) and if something matches it gets atomic substitution > rules for the wilds in the pattern. These rules are applied to the > substitution expression and the result is used as substitution for the > matched part in the expression. > E.g. this allows the following (x is a symbol, u is a Wild): > >>>> subs(2+x**4, c+x**u, u*x**(u-1)) > 4*x**3 > > > Now what will be the steps to achieve this aim: > > (1) Implement a generic "Hint"s model which can be used to store > values of different hints and also be used to find out interactively > what hints are possible. (This is already done in the hints branch and > might also be useful for other parts in sympy)
You might want to look at the switch manager that Chris has been working form in issue 1725. > > (2) Implement the atomic substitution method described in > substitution.txt (This can either be done directly in the Basic class > or alternatively in some separate module) > > (3) Complete the description of the matching algorithm in matching.txt > > (4) Implement the matching algorithm described in matching.txt in a > separate module. (This relies on the Hints model and the atomic > substitution method) > > (5) Implement the pattern substitution method described in > substitution.txt (Again either in a separate module together with the > atomic substitution method or directly in Basic) > > (6) Write the wrapping "subs" function. > > (7) Plug this new "subs" function in instead of the currently used > subs function. Some tests are expected to fail: Those which test > directly the substitution function have to be reviewed and might have > to be changed simply because other substitution behavior is expected > of the new substitution method. > Other test will fail because some algorithms will have to be adapted > to use the new substitution. > > (8) Remove old substitution code. > > (9) Do (7) and (8) with the "match" function. > > I'm not completely sure when it is a good point to merge back into > master. Maybe only after (7) and after (9). > > This is a pretty ambitious undertaking and might take some month to > accomplish. But before I start spending more time on this I want hear > the opinion of other developers. Do you think it's worth doing? And if > yes, do you have any tips, wishes or comments? Also help is of course > very much welcomed, just tell me what do you want to work on so that > we do not double the work! Yes, it is worth it! The ability to finely control subs alone will be worth it, (e.g., sin(x)**3.subs(sin(x)**2, 1 - cos(x)**2) will finally work and return sin(x)*(1 - cos(x)**2), which we can use to make trigsimp better). Also, matching is very buggy now, so if your new method can fix at least some of the issues at http://code.google.com/p/sympy/issues/list?q=label:Matching, that would be a great help too. I will take a read of your guides after they compile to see if I have any further comments. Aaron Meurer > > Sebastian > > -- > You received this message because you are subscribed to the Google Groups > "sympy" group. > To post to this group, send email to sy...@googlegroups.com. > To unsubscribe from this group, send email to > sympy+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/sympy?hl=en. > -- You received this message because you are subscribed to the Google Groups "sympy" group. To post to this group, send email to sy...@googlegroups.com. To unsubscribe from this group, send email to sympy+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sympy?hl=en.
