Multiple pattern matched in ManyToOneReplacer

[ashishkg0022]

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]

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]

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

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

[wheerd]

That would be great.

⁣Sent from Blue ​

On Mar 20, 2018, 07:13, at 07:13, Ashish Kumar Gaurav [email protected] 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]

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]

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 [email protected] 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]

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]

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]

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]

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 [email protected] 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]

@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]

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]

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]

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]

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:

• 1, 5
• 3, 4
• 6, 8

[ashishkg0022]

Yes. Is there any way to do it ?

[ashishkg0022]

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

[hbarthels]

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]

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]

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]

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]

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

• For something like f(x) -> g(x) and f(x) -> h(x), it should be trivial.
• For f(x, y) -> ... and f(a, y) -> ..., I'm already not so sure. This is a simple example, but I have the feeling that in the most general case (with associativity, commutativity, sequence variables) this may get quite difficult.
• If you have the same patterns with different constraints, it's probably infeasible (if not undecidable), because we would need to reason about the semantics of the constraints.

[pauldj]

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]

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]

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.