On Thursday, November 27, 2014 12:19:04 AM UTC+1, James Crist wrote: > > All, > > In my spare time, I've been working on implementing a fast pattern matcher > that accounts for Associative and Commutative symbols. It's going to be a > while before I'm ready to release the code (it needs some serious cleanup), > but as of now it is "partly functional". Some notation: > > T = set of known patterns. A trie like data structure is used to > preprocess these patterns to aid in fast matching. > s = expression to be matched > x, y = variables > a, b, c = constants >
That's cool. Is it addressing this issue? https://github.com/sympy/sympy/issues/7748 > Currently the matcher can determine what patterns in T match s, in the > presence of associative and commutative symbols, as long as the pattern is > "linear". By linear, I mean no repeated *variable* symbols (`x + y` is > acceptable, `x + x` is not). If no associative and commutative symbols are > present, it can also determine a match substitution to make `s` equivalent > with the pattern. > > You mean expressions like *Add(x, x, evaluate=False)* ? I think there should be a way to check where an expression is in a canonical order. > Some design questions before I continue work: > > - Is there any use for just determining what patterns match, without > generating a match substitution? Determining if a match exists is faster > than determining a specific substitution. However, in the presence of > nonlinear patterns a substitution needs to be found to verify the match is > valid. This decision determines how tightly coupled the two algorithms will > be. > I guess the primary usage of patterns lies in expression transformations. SymPy has a .match( ) to solve for wilds, and .has( ) to find whether a subexpression is in the tree expression. > > - Is there need for nonlinear patterns? I plan to account for them, but > they make the algorithm a bit more complicated. Nonlinear, AC pattern > matching is NP complete. Linear AC pattern matches can be found in > polynomial time. > > - In a general case, there can be many substitutions that match a specific > pattern mod AC. For example, given `t = x*y`, and `s = a*b*c`, this can > match with {x: a*b, y: c}, or {x:a, y: b*c}, etc... This is easy to account > for, and can be done lazily. Api-wise, are there cases where generating > more than one matching substitution are needed? > Maybe it is preferrable that the first lazily generated substitution appears in the same order as Mathematica's pattern matching. It would make Mathematica's code more easily portable to SymPy. > > - The algorithm lazily determines matches. Currently preference is given > to matching variables before constants, but it could go the other way > around. i.e. if T = {a + b, x + b}, and s = a + b, then the matcher will > find `x + b` before `a + b`. I'd rather not make this configurable, as it > complicates things. The question is, do we want the most general match > first, or the most specific? > > I think that, given a set of matching expressions, we should get the first lazy occurrence of the most specific of the expressions in that set. That is, if a pattern expression A matches a proper subset of pattern expression B, B should be discarded completely whenever A matches. - At the moment, the code is completely removed from dependence on sympy, > and can function on its own. As such, I'm planning on making it a separate > library that can be used by SymPy as a dependency. I understand we were > against that in the past, but this may be changing? I'd rather not maintain > two separate codebases. > What kind of AST are you matching? In sympy.unify, there's a function to transform a SymPy expression to a special type of AST object: https://github.com/sympy/sympy/blob/298bbdbafa26c45526c622374acd11ac05a357e6/sympy/unify/usympy.py#L44 > - There's a `commutative` assumption in sympy, but there doesn't seem to > be an `associative` one. How can I check if a function/operator is > associative? Does this information need to be kept elsewhere? > > Associativity is a property of the AST node, while commutativity is more complicated. In Mathematica there is Times[ ... ], which is fully commutative, and Dot[ ... ] which is non-commutative. In general, AST nodes has an attribute "Orderless" to make all of their args commutative among each other. Similarly, Maxima has *(mtimes ... )* and *(mnctimes ... )* for commutative and non-commutative multiplication nodes. SymPy associates commutativity with an assumption and/or the type of the argument. For example, two matrices usually do not commute. That is quite complicated to deal with. One last complication: have you had any thought of how this could be extended to an AST node containing a PermutationGroup instance determining how its arguments commute/anticommute? That could have some applications in the tensor module, but I guess it's hard or impossible to find a polynomial algorithm for that. By the way, are you using Wild objects, or are you specifying wilds by an extra parameter? In unify.rewriterule, you just put in two expressions, and specify which ones are variables (i.e. wilds) in another parameter. Furthermore, there is an option to put a filtering lambda function and assumptions, so that matches should be compatible with a test function and/or SymPy's new-style assumptions. https://github.com/sympy/sympy/blob/298bbdbafa26c45526c622374acd11ac05a357e6/sympy/unify/rewrite.py#L11 Assumptions awareness would be a desired feature. Any considerations about nodes marked as *one parameter identities*? That is, Add(x) = x, Mul(x) = x, i.e. nodes that are identities if there is just one parameter. -- 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/77a31c58-041b-4267-8d55-0817f061577a%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
