search

HPAC / matchpy

A library for pattern matching on symbolic expressions in Python.
MIT License
163 stars 25 forks source link

Multiple pattern matched in ManyToOneReplacer #30

Open ashishkg0022 opened 6 years ago

ashishkg0022 commented 6 years ago

How MatchPy manages patterns that match multiple rules. In rubi module of sympy , it results in recursion errors. Is there any way to handle the recursion errors ?

wheerd commented 6 years ago

You need to make sure that the rules lead to replacements that are not matched by the same rule again and again. Otherwise, you get an infinite loop. Probably some of the constraints are not working correctly. But it is hard to tell without a concrete example.

ashishkg0022 commented 6 years ago 
rubi_integrate(x**4*sqrt(a + b*x**2),x)

It results into a recursion error. Should I show the complete error message ?

wheerd commented 6 years ago

That would be great.

⁣Sent from Blue ​

On Mar 20, 2018, 07:13, at 07:13, Ashish Kumar Gaurav notifications@github.com wrote:

rubi_integrate(x**4*sqrt(a + b*x**2),x)

It results into a recursion error. Should I show the complete error message ?

-- You are receiving this because you commented. Reply to this email directly or view it on GitHub: https://github.com/HPAC/matchpy/issues/30#issuecomment-374487471

ashishkg0022 commented 6 years ago 
RecursionError                            Traceback (most recent call last)
<ipython-input-5-defee0be9862> in <module>()
----> 1 rubi_integrate(x**4*sqrt(a + b*x**2),x)

~/sympy/sympy/integrals/rubi/rubi.py in rubi_integrate(expr, var, showsteps)
    203         return S(expr)*var
    204 
--> 205     result = rubi.replace(Integral(expr, var))
    206 
    207     return result

~/matchpy/matchpy/matching/many_to_one.py in replace(self, expression, max_count)
    795                 try:
    796                     replacement, subst = next(iter(self.matcher.match(subexpr)))
--> 797                     result = replacement(**subst)
    798                     expression = functions.replace(expression, pos, result)
    799                     replaced = True

~/sympy/sympy/integrals/rubi/rules/binomial_products.py in <lambda>(b, n, a, p, m, x)
    412         k = GCD(m + S(1), n)
    413         return Subst(Int(x**(S(-1) + (m + S(1))/k)*(a + b*x**(n/k))**p, x), x, x**k)/k
--> 414     rule79 = ReplacementRule(pattern79, lambda b, n, a, p, m, x : With79(b, n, a, p, m, x))
    415     rubi.add(rule79)
    416 

~/sympy/sympy/integrals/rubi/rules/binomial_products.py in With79(b, n, a, p, m, x)
    411     def With79(b, n, a, p, m, x):
    412         k = GCD(m + S(1), n)
--> 413         return Subst(Int(x**(S(-1) + (m + S(1))/k)*(a + b*x**(n/k))**p, x), x, x**k)/k
    414     rule79 = ReplacementRule(pattern79, lambda b, n, a, p, m, x : With79(b, n, a, p, m, x))
    415     rubi.add(rule79)

~/sympy/sympy/integrals/rubi/utility_function.py in Int(expr, var)
    160 def Int(expr, var):
    161     from sympy.integrals.rubi.rubi import rubi_integrate
--> 162     return rubi_integrate(expr, var)
    163 
    164 def Set(expr, value):

... last 5 frames repeated, from the frame below ...

~/sympy/sympy/integrals/rubi/rubi.py in rubi_integrate(expr, var, showsteps)
    203         return S(expr)*var
    204 
--> 205     result = rubi.replace(Integral(expr, var))
    206 
    207     return result

RecursionError: maximum recursion depth exceeded
wheerd commented 6 years ago

That is nothing that can be changed in MatchPy. It seems that the replacement functions are calling the integration replacement recursively. That can lead to infinite recursion if the new term is not simpler than the original one.

⁣Sent from Blue ​

On Mar 20, 2018, 07:31, at 07:31, Ashish Kumar Gaurav notifications@github.com wrote:

RecursionError                            Traceback (most recent call
last)
<ipython-input-5-defee0be9862> in <module>()
----> 1 rubi_integrate(x**4*sqrt(a + b*x**2),x)

~/sympy/sympy/integrals/rubi/rubi.py in rubi_integrate(expr, var,
showsteps)
   203         return S(expr)*var
   204 
--> 205     result = rubi.replace(Integral(expr, var))
   206 
   207     return result

~/matchpy/matchpy/matching/many_to_one.py in replace(self, expression,
max_count)
   795                 try:
796                     replacement, subst =
next(iter(self.matcher.match(subexpr)))
--> 797                     result = replacement(**subst)
798                     expression = functions.replace(expression, pos,
result)
   799                     replaced = True

~/sympy/sympy/integrals/rubi/rules/binomial_products.py in <lambda>(b,
n, a, p, m, x)
   412         k = GCD(m + S(1), n)
413         return Subst(Int(x**(S(-1) + (m + S(1))/k)*(a +
b*x**(n/k))**p, x), x, x**k)/k
--> 414     rule79 = ReplacementRule(pattern79, lambda b, n, a, p, m, x
: With79(b, n, a, p, m, x))
   415     rubi.add(rule79)
   416 

~/sympy/sympy/integrals/rubi/rules/binomial_products.py in With79(b, n,
a, p, m, x)
   411     def With79(b, n, a, p, m, x):
   412         k = GCD(m + S(1), n)
--> 413         return Subst(Int(x**(S(-1) + (m + S(1))/k)*(a +
b*x**(n/k))**p, x), x, x**k)/k
414     rule79 = ReplacementRule(pattern79, lambda b, n, a, p, m, x :
With79(b, n, a, p, m, x))
   415     rubi.add(rule79)

~/sympy/sympy/integrals/rubi/utility_function.py in Int(expr, var)
   160 def Int(expr, var):
   161     from sympy.integrals.rubi.rubi import rubi_integrate
--> 162     return rubi_integrate(expr, var)
   163 
   164 def Set(expr, value):

... last 5 frames repeated, from the frame below ...

~/sympy/sympy/integrals/rubi/rubi.py in rubi_integrate(expr, var,
showsteps)
   203         return S(expr)*var
   204 
--> 205     result = rubi.replace(Integral(expr, var))
   206 
   207     return result

RecursionError: maximum recursion depth exceeded

-- You are receiving this because you commented. Reply to this email directly or view it on GitHub: https://github.com/HPAC/matchpy/issues/30#issuecomment-374490655

ashishkg0022 commented 6 years ago

Last year you suggested to use multilple macthers for cases to handle multiple rules

And yes, the order in which rules are applied is not really deterministic. If you need a specific order between certain rules you could use multiple matchers

Can you explain it ?

wheerd commented 6 years ago

I mean that when you have rules like f(a) and f(x_) where the latter is more general than the former, then the order can be important. If a single ManyToOneMatcher is used the order in which those patterns are matched is not guaranteed. It is non-deterministic. If the order in which some of the rules are applied (which I believe is the case for RUBI) is important, you need multiple matchers to ensure that order is kept.

corywalker commented 6 years ago

Mathematica attempts to rank the specificity of downvalues. For example, f(a) would have higher specificity than f(x_), thus it would be checked first when evaluating f. The specificity function is not perfect and seems to change between versions, but if MMA gets the order wrong then it can be overridden.

Interestingly for RUBI this ordering does not seem to matter much. For many of the rules, they can simply be checked in the order in which they are defined and the integration rules work just fine.

wheerd commented 6 years ago

But that is what I mean. The order of the rules matters. Many-to-one matching means that all patterns are matched simultaneously. Hence it is not deterministic in which order matches are found.

⁣Sent from Blue ​

On Mar 21, 2018, 07:41, at 07:41, Cory Walker notifications@github.com wrote:

Mathematica attempts to rank the specificity of downvalues. For example, f(a) would have higher specificity than f(x_), thus it would be checked first when evaluating f. The specificity function is not perfect and seems to change between versions, but if MMA gets the order wrong then it can be overridden.

Interestingly for RUBI this ordering does not seem to matter much. For many of the rules, they can simply be checked in the order in which they are defined and the integration rules work just fine.

-- You are receiving this because you commented. Reply to this email directly or view it on GitHub: https://github.com/HPAC/matchpy/issues/30#issuecomment-374845604

ashishkg0022 commented 6 years ago

@wheerd , For example I have these list of rules:

pattern1 = Pattern(...........)
rule1 = ReplacementRule(pattern1, replacement1)
rubi.add(rule1)

pattern2 = Pattern(...........)
rule2 = ReplacementRule(pattern2, replacement2)
rubi.add(rule2)

pattern3 = Pattern(...........)
rule3 = ReplacementRule(pattern3, replacement3)
rubi.add(rule3)

I want to match in the given fix order ( 1 -> 2 -> 3). Is there any way for this ? Or can you give an example using multiple matcher to perform this ?

hbarthels commented 6 years ago

Our many-to-one matching algorithms don't support this. How to do this depends on the actual problem. If you only have three rules that you want to match one after another, there is no reason to use many-to-one matching at all: You could simply do this "manually".

Can you provide more information about the actual problem? What kind of dependencies between the rules do you have?

ashishkg0022 commented 6 years ago

Actually I have a lot of rules (~10, 000) . When an expression matches to multiple(2-3) rules, we want to follow a order.(order is known to us). If you want , I can make it more clear through code.

ashishkg0022 commented 6 years ago

https://github.com/ashishkg0022/rubi-structure/tree/master/way_2 Here there is sample code rules contain all replacementRules along with pattern. We are loading them in rubi.py . We are running rubi_integrate of rubi.py then .

In rules lets say, if rule12 and rule28 matches to an expression. We want rule12 to work first.

hbarthels commented 6 years ago

You want to use a many-to-one matcher whenever you have multiple rules and want to know which ones match. Think of a many-to-one matcher as parallel matching. Matching rules are returned in an arbitrary order, it's not possible to provide priorities (it might be possible for you to use the priorities to speed up matching a bit, but let's talk about that later).

The way I understand it, you have a tree (or forest) of dependencies (in addition to priorities, in case there are multiple successors). Something like: 1 -> 2 -> 3 2 -> 4 5 -> 6 -> 7 5 -> 8 Is this correct? If this is the case, you would want to use multiple many-to-one matchers, for the following sets of rules:

ashishkg0022 commented 6 years ago

Yes. Is there any way to do it ?

ashishkg0022 commented 6 years ago

Also replace_all() of matchpy.functions module maintains an order. But is very slow for large number of rules.

hbarthels commented 6 years ago

Also replace_all() of matchpy.functions module maintains an order. But is very slow for large number of rules.

This replace_all() does not use many-to-one matching, so it will be slow for large numbers of patterns. There is a ManyToOneReplacer which does that, but it's still not what you need because it does not take dependencies or priorities into account. So no, there is no way to do it just with MatchPy.

I would recommend you to implement this yourself. I don't think this functionality belongs into MatchPy, because it's quite specific to your problem.

The way I understand it, you need a tree structure that represents the dependencies between rules. If a node only has one successor, you can use one-to-one matching, otherwise you would want to construct a many-to-one matcher for each node in the tree. Do you have the dependencies and priorities in a format that allows to construct the tree programmatically? For 10k rules, you probably don't want to do that by hand.

Regarding that optimization that I mentioned earlier: All matching functions are generators, so they produce matches one after another (but in an arbitrary order). As soon as the matcher returns a match for the rule with the highest priority, there is no need to continue matching (what do you do if there are multiple matches for one rule?), so you can stop.

rwst commented 6 years ago

Rubi contains a lot of potential structure and matchpy is overkill for this problem, not only because parallel matching is overkill, but also because there are practically no sequential variables in the Rubi ruleset.

hbarthels commented 6 years ago

I don't know the Rubi rules well enough to say anything about many-to-one matching, but the fact that MatchPy supports sequence variables should not affect matching if you don't use them. From the algorithms perspective, sequence variables are almost the same as supporting associativity, so if you implement algorithms for one, you basically get the other for free.

saulshanabrook commented 6 years ago

Would it be possible to warn if we define replacements that lead to non determinism? I am trying to prevent this, but it would be nice if I had some automated checks for it since I have to be careful about it.

hbarthels commented 6 years ago

Can you provide examples of cases where you would want to get such warnings?

pauldj commented 6 years ago

Would it be possible to warn if we define replacements that lead to non determinism?

This problem is much more complicated than it sounds, as it requires looking for expressions that are matched by multiple rules. This might very well be an undecidable problem.

saulshanabrook commented 5 years ago

Any cases it could cover would be helpful. Even if it started with only the trivial cases you pointed out.

I am hitting these as I am defining indexing and shape rules for arrays: https://github.com/Quansight-Labs/uarray/blob/master/uarray/uarray.py based on A Mathematics of Arrays. It would just be helpful as another sanity check that I am defining reasonable replacement rules.

What about rules like f(g(x)) and f(x)? Can we know that f(g(x)) will be matched first if we are using the many to many replacer?

hbarthels commented 5 years ago

Any cases it could cover would be helpful. Even if it started with only the trivial cases you pointed out.

I'm somewhat skeptical about this. If we produce warnings in the trivial cases, what do we do for those cases where we can't say anything? If we don't produce any warnings, that might give a false sense of safety. Conversely, always producing warnings in those cases might be irritating.

Apart from that, I'm not enough of an expert in term rewriting systems to judge if it always makes sense to produce those warnings. There might be cases where there is nothing wrong with having a nondeterministic system.

What about rules like f(g(x)) and f(x)? Can we know that f(g(x)) will be matched first if we are using the many to many replacer?

No, the order is arbitrary.