On Thu, Jul 7, 2011 at 10:39 PM, Chris Smith <smi...@gmail.com> wrote: > > > 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.)
I originally called this exact, but I though atomic was a better name because of the invariant with .atoms(). Actually, thinking about this, exact might still be a better name. >> >> 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. Well, integer_powers isn't that great of a name, but extractive doesn't seem to be much better imo. But anyway, the actual names are irrelevant at this point, as they would be easy to change. >> >> 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. Well, you need to consider scalability. Right now, there are three methods, but it could grow. I already think we might need a forth hint, which would probably be called force, which ignores assumptions (e.g., in issue 2552, (sqrt(x)*sqrt(y)).subs(x*y, z, force=True) would produce sqrt(z) even if x and y are assumed to be complex). And I could easily imagine the use of even more fine grained control. expand() does this, with a lot of hints, and it's not a very good system in my opinion. Unlike expand(), subs wouldn't be called in multiple passes for each hint, but nonetheless, I still see the system as one that could be improved (though how, I am still not yet sure). Aaron Meurer > 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. > -- 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.
