On Wed, Nov 26, 2014 at 4:19 PM, James Crist <[email protected]> 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:
This is awesome. Have you seen the previous discussions on pattern
matching on this mailing list (I think there are also wiki pages).
They focus more on features than performance, but it's worth looking
at.
>
> 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.
I've never seen that, and skimming through 'git grep match' I don't
see any instances where the match isn't assigned to a variable
(although I didn't check the context to see if that variable is used
in a non-boolean context).
>
> - 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.
Interesting. Why is that?
>
> - 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?
I can't think of use-cases, but that doesn't mean that they aren't
there. The only case I can think of where you would want to look at
multiple matches is if you are looking for a match with a specific
structure, and ideally, the API for that would be to put that
structure on the Wild object somehow (like a boolean expression that
has to be true for the Wild to match) and the algorithm would check
this automatically.
>
> - 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?
Whichever one is the correct behavior for a dispatch system. I *think*
that means specific, but I could be getting it backwards.
I'm assuming that the whole point of having a set of patterns rather
than a single pattern at a time is so you can do this.
>
> - 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.
Let's look at the code first, and then figure this out.
>
> - 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?
The commutative assumption is a mess anyway. It's a very different
assumption than every other assumption in the assumptions system for a
few reasons. The main thing is that it's kind of strange to call a
symbol commutative or noncommutative as commutativity is a property of
two expressions and an operator (A, B, and * in A*B).
For associativity, we can add one if it helps, but I think for now
only operators that subclass from AssocOp automatically associate
(it's a bad situation, though, because one, we shouldn't force people
to subclass to mark objects as having a property, especially if that
class wants to add behavior, and two, AssocOp is really
AssocOpWithIdentity). And also, of course, the same issue applies here
that associativity is really a property of the operator *and* the
objects applied on that operator, especially if we dispatch operators
so that they mean different things depending on their arguments (for
instance, A*B*C is *not* associative if A, B, and C are matrices and
we care about computational complexity).
Aaron Meurer
>
> - 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 [email protected].
> To post to this group, send email to [email protected].
> 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.
--
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 [email protected].
To post to this group, send email to [email protected].
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/CAKgW%3D6KZht0VYghd5zLzzdPoM_m7sb7m685isKryvv9O%3D9g01w%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.
