On Oct 7, 2012, at 10:43 AM, Sergiu Ivanov <[email protected]> wrote:
> On Sun, Oct 7, 2012 at 12:58 AM, Matthew Rocklin <[email protected]> wrote: >>> The idea X Inverse(X) => Identity(X.rows) is substantially simpler than >>> the >>> >>>> code that was necessary to encode this rule though. This is going to be >>>> a >>>> common sort of rule so this is the sort of thing we should generalize >>>> somehow. >>> >>> How about a predicate cancellable()? Thus, x (op) y will be >>> transformed into identity if cancellable(x, y). The generalised >>> function may then work as follows: >>> >>> def mat_cancellable(X, Y): >>> return Y == Inverse(X) >>> >>> cancel(composite_expression, mat_cancellable, I) >>> >>> where composite_expression is an instance of Mul, Add, MatMul, MatAdd, >>> etc. If it is possible to extract the identity from this operations, >>> then the third argument will be unnecessary. >> >> I wonder if there is a way to generalize this thinking so that it can be >> applied to more cases that aren't just cancellation. > > I'm not sure as to what exactly you refer to. I actually think that > in all cases where a pair x (op) y is transformed into identity one > has a monoid (M, (op)) with identity e, so that x (op) y = e. That > is, I actually think that all the cases where such reasoning is > applicable are cancellations in a monoid. > >>>> Ah, sorry, I was using pure in the sense of "lets just use this >>>> function, >>>> not a class that represents this function". I wasn't using "pure" in the >>>> side-effect-free sense. I do however think that this system should be >>>> (mostly) side-effect free (mostly for caching, profiling, debug, >>>> etc....) >>>> That's somewhat standard in SymPy though. >>> >>> Yes, and that's an advantage. Although functions with side-effects >>> should also be handled nicely, because, from what I know, there >>> actually are some mutable objects in SymPy. >> >> Rules as they're currently written only work on objects that inherit from >> Basic. All Basics are immutable. Rules assume immutability. The mutable >> types in SymPy (notably Matrix) do not inherit from Basic. > > Ah, I see; I thought Matrix inherited from Basic as well. Any mutable type will not inherit from Basic. > >>>>> Further, when you say "pattern matching triples", do you mean >>>>> representing rules as triples and having the application function >>>>> which checks whether its argument matches from-expr and satisfies the >>>>> condition, and then returns to-expr? >>>> >>>> Yes. I would like to write xxinv as >>>> X = Wild() >>>> xxinv = rule(X*Inverse(X), Identity(X.rows), True) >>>> or >>>> sym_transpose = rule(Transpose(X), X, X.is_symmetric) >>> >>> Looks very nice. Shouldn't be that hard to implement either, I think. >> >> This depends on pattern matching, a challenging problem. SymPy might have >> tools to handle it though. > > I'm not sure how well Wild works, but, apparently, we can use it to do > some pattern matching. I've never used Wild, though; I just assumed > that it's sufficiently powerful. If this is indeed the case, then the > format of rules you suggest should be straightforward to implement. Wild works well, but it's not expressive enough to match some things. For example, you could never create a pattern to match a polynomial an*x**n + ... a1*x + a0, because there's no way to express n coefficients. Also, for Wild to work, the expression had to be in exactly the form given, which is understandable, but it can lead to little gotchas if you forget to expand the input expression, or if some kind of auto simplification prevents you from being in the desired format. Another issue with Wild is that if you aren't careful (which usually means specifying the exclude keyword precisely) you can get nondeterministic results. For example, a, b = Wild("a"), Wild("b") (x*y).match(a*b) Could give four possible outputs ({a:x, b:y}, {a:y, b:x}, {a:1, b:x*y}, and {a:x*y, b:1}, and the last two are the ones that usually catch people off guard). I'm not sure if there's a pattern matching system that wouldn't have this issue, though. Aaron Meurer > > Sergiu > > -- > You received this message because you are subscribed to the Google Groups > "sympy" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/sympy?hl=en.
