Awesome! That is one of the missing pieces for sympy for sure!
I would definitely have a look at the pattern matching of Mathematica,
to see what kinds of things are useful and needed for that type of
thing.
Cheers,
Brian
On Wed, Nov 26, 2014 at 3:19 PM, James Crist <crist...@umn.edu> 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
>
> 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.
>
> 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.
>
> - 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?
>
> - 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?
>
> - 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.
>
> - 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?
>
> - Jim
>
> --
> 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/42d9511d-e963-416f-9d4e-3e0435461422%40googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
--
Brian E. Granger
Cal Poly State University, San Luis Obispo
@ellisonbg on Twitter and GitHub
bgran...@calpoly.edu and elliso...@gmail.com
--
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/CAH4pYpTm%3DhK487L1TKtg7xxaSj3SuK53EKWF55ZThb9QjwUBng%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.
