On Wed, Oct 24, 2012 at 8:22 AM, Matthew Rocklin <
mroc...@gmail.com> wrote:
>
>> I only have experience with matching expressions, particularly in the
>> ode module with classify_ode. If you want to match some complicated
>> expressions, you will run into some limitations soon. One issue is
>> that you can't match "n" terms, so for example, I had to write a
>> custom matcher for a linear ODE with constant coefficients (an*y^(n) +
>> ... + a1*y' + a0*y = g).
>
>
> I'm just trying to do fairly simple non-expr expressions. Here is an
> example.
>
> In [1]: p = Wild('p')
> In [2]: s = Union(FiniteSet(1,2,3), Interval(5, 7))
> In [3]: s.match(Union(p, Interval(5, 7)))
> TypeError: Input must be Sets or iterables of Sets
>
> Do we have a non-Expr wild?
I don't think we do, but I could be missing it.
I don't imagine it would be too hard to just create BasicWild, had
Wild subclass from it (and Symbol), and then move _matches_commutative
to Basic as you said, and change other commutative classes like Union
to call it.
>
>> Another issue is that the pattern matcher will give non-deterministic
>> results unless you specify the exclude keyword on the Wild objects
>> very carefully.
>
>
> Right, I'd actually like to explore this. I want all of the possible
> matches. This is one trivial way to defeat non-determinism :) Is there a way
> to explore the non-determinism here?
I see some potential issues with this. First is that depending on how
you define a match, you might have infinitely many possible results.
For examples, (x**n).match(p*q) might give x**n*1 or x**(n - 1)*x or
(x**n*a)*(1/a) or x**(n - a)*x**a (for arbitrary a). The third one in
particular sounds a little contrived, but consider if we had a*x**2 +
x, and we wanted to match against p*q, where q excludes x. We might
want that to give a*(x**2 + x/a). So it's not too far off to consider
"adding a new term" to a multiplication.
So it's clear that to do this, you need to make sure that the matching
is very precisely defined. Probably in an AST way more than a
mathematical way (but not necessarily). Another issue might be that
all possible matches might be large, possibly even combinatorially
large, depending on what your expression is.
With that being said, I think this is a good idea, and that you should
explore it.
>
>>
>> A third issue is that automatic simplification (and in many cases,
>> even non-automatic simplification, i.e., expressions being written in
>> different equivalent forms) can move an expression into a form that
>> the pattern matcher won't recognize. For example:
>
>
> In my particular case automatic simplification shouldn't be an issue but
> yes, I can see how this could be annoying. Presumably this would work if you
> built the expr and pattern with evaluate=False?
But even as I said, you run into issues with simplification that is
not automatic, i.e., the expression not being in exactly the form you
expect.
>
>> The good news is that there are a lot of good algorithms that you can
>> use to write custom targeted matching solutions. For example, with
>> the above, you could use some of the gcd algorithms (I'm not sure
>> which exactly; terms_gcd I think) to pull out the coefficient, if
>> that's what you want.
>
>
> Are there good general pattern matching/unification algorihtms? Something
> like risch or meijerint but for this domain?
Probably, but I don't know them. See what Mathematica does, as I've
heard it has good pattern matching.
>
>>
>> I thought we tried to document this a while back when we were fixing
>> some bugs. Are the inline comments and docstrings not enough?
>
>
> I was not sufficiently clever for this.
Well, the code is complicated, which is why we tried to document it.
If you can figure it out, perhaps you should document it some more.
Aaron Meurer