On Thu, Jul 7, 2011 at 9:54 PM, Aaron Meurer <asmeu...@gmail.com> wrote:
> Hi everyone. > > As many of you may know, the main thing blocking the merge of my work > on the Risch algorithm (see my integration3 branch) is not any > deficiency in the algorithm, though there are several parts that are > still not implemented, but the lack of a so called "atomic > substitution" framework. The relevant issue here is 2026 > (http://code.google.com/p/sympy/issues/detail?id=2026). > > Basically, the following breaks the preprocessing code in risch_integrate: > > In [1]: exp(2*x).subs(exp(x), y) > Out[1]: > 2 > y > > I need a way for subs to behave exactly, so the above would return > exp(2*x). Thus, I have disabled this completely in my integration3 > branch, but this is only a temporary solution, as there is a lot of > code that relies on this behavior (especially in the series/limits > code), and it would be a regression anyway. > > So there needs to be a way to do > > >>> exp(2*x).subs(exp(x), y, atomic=True) > exp(2*x) > I would call it `exact`, not `atomic` since Atom already has a precise meaning in sympy. (cf issue 2026.) > Now, as it turns out, it has come up in other places that people want > control over the way that subs works in other ways. In the issue, I > talk about something called integer_powers, which would work like > > >>> exp(2*x).subs(exp(x), y, integer_powers=True) > y**2 > >>> exp(x).subs(exp(2*x), y, integer_powers=True) > exp(x) > I would call this `extractive` and allow only changes that extract_multiplicatively or extract_additively allow as applicable. Those extractive functions are suppose to only do extractions that `retain the original form` so a fraction shouldn't be extracted from an integer. Those are changes that I implemented in t2 which never made it to sympy. This would also apply to powers since the substitution code for powers would only work if the exponent of the old pattern were multiplcatively extractable from the expression. > > In other words, it does not do power manipulation in the replacement > unless the resulting power is an integer. This is needed in some > places such as the heurisch algorithm to ensure that the resulting > expression will be a polynomial (actually, a rational function) in the > substitution variable. In addition, there is also some concern about > the assumptions validity of certain algebraic substitution rules. See > issues 2081 and 2552. > > So in the interest of doing this right, I think there needs to be some > kind of hints mechanism to subs. My question is, what do you think > would be the best way to implement this? Presently the expand > function has something like this, but I'm not really convinced that > the way that it's implemented is a very good one. > > Here's (roughly) the way that subs works now: Basic defines two > methods, .subs and ._eval_subs. Basic.subs() is of course the user > level function that everyone calls, and pretty much no subclass of > Basic overrides it. The actual substitution happens in ._eval_subs, > which is also responsible for recursing the substitution down the > .args. Basic has a simple implementation, but most classes end up > overriding it (for example, exp has overridden it to allow the above > fancy algebraic substitution). > > What's the best way to implement the various hints I want to add to > .subs()? A few things to take into consideration: > > - .expand() works, as I mentioned earlier, by having > ._eval_expand_hint() methods. I don't think this is the best way, so > that's why I'm asking here to see if anyone has any better ideas. > > - It should remain backwards compatible with any class that defines > ._eval_subs(self, old, new). Unfortunately, there wasn't much > foresight when this was originally designed, so the protocol does not > call for any *args or **kwargs. However, that doesn't necessarily > weigh those options out, as we could easily make Basic.subs() check > for an old style definition and ignore hints in that case. > > - I haven't looked at it, but we might be able to implement at least > atomic substitution entirely in Basic (no class need override any > methods to get it to work). This is because it is so simple that the > default agnostic method might be able to do it entirely. The rule for > atomic substitution by the way is that expr.subs(old, new, > atomic=True) should replace old with new in expr if and only if old is > in expr.atoms(old.__class__). > > So I'm open to any ideas on how to implement this, API-wise. > > Also, Chris, did you start this at all in any of your branches and/or > are you willing to help with this? > My t2 had exact and atomic (sympy's def of atomic) implemented and *explicit algebraic* implemented which you reviewed but didn't want to get ready for 0.7 ( http://code.google.com/p/sympy/issues/detail?id=2026#c5 ) In trying to resurrect that I did a general cleanup in pull request https://github.com/sympy/sympy/pull/234 that stalled with no further suggestions from anyone but no clear +1. [Of course I am biased, but I like the organization of that request and would have used the hint given to subs to call the correct _eval_subs_foo routine. (If you read the final comment I made maybe you will understand the organization and whether Ronan's comments are valid or not.)] I think 3 _eval_subs_foo routines would be needed: _eval_subs_atomic, _eval_subs_exact, _eval_subs_extract ... and maybe the existing eval_subs if the extract doesn't match the expected current behavior. Also, `exact` and `atomic` might be made the same with a slight overhead by checking if expr is Atom or Function instead of just Atom. If you like what I've already done I might be able to be of help. Check out my t2 branch and https://github.com/sympy/sympy/pull/234 -- You received this message because you are subscribed to the Google Groups "sympy" group. To post to this group, send email to sympy@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.
