Comments (24)
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.
from matchpy.
rubi_integrate(x**4*sqrt(a + b*x**2),x)
It results into a recursion error. Should I show the complete error message ?
from matchpy.
from matchpy.
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
from matchpy.
from matchpy.
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 ?
from matchpy.
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.
from matchpy.
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.
from matchpy.
from matchpy.
@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 ?
from matchpy.
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?
from matchpy.
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.
from matchpy.
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.
from matchpy.
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
from matchpy.
Yes. Is there any way to do it ?
from matchpy.
Also replace_all()
of matchpy.functions
module maintains an order. But is very slow for large number of rules.
from matchpy.
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.
from matchpy.
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.
from matchpy.
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.
from matchpy.
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.
from matchpy.
Can you provide examples of cases where you would want to get such warnings?
- For something like
f(x) -> g(x)
andf(x) -> h(x)
, it should be trivial. - For
f(x, y) -> ...
andf(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.
from matchpy.
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.
from matchpy.
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?
from matchpy.
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))
andf(x)
? Can we know thatf(g(x))
will be matched first if we are using the many to many replacer?
No, the order is arbitrary.
from matchpy.
Related Issues (20)
- Wildcard that matches multiple symbols HOT 1
- Create `new` class method on Symbol HOT 1
- ManyToOneMatcher: Position of constraints logic HOT 3
- GPL'd dependency: hopcroftkarp library HOT 6
- Usage of type unions HOT 1
- [Feature] Visualization of Expressions with Graphviz
- ANN: MatchPyCpp port to C++ HOT 7
- New release? HOT 5
- Remove dependency on pkg_resources/setuptools HOT 1
- Inconsistent output of match_anywhere HOT 4
- Improve checking correctness of input
- Match arbitrary function HOT 4
- One-to-one matching: symbols with variable_name do not work in commutative functions HOT 2
- substitute not working with SymPy HOT 11
- Optional wildcards to match the identity element of the current node HOT 7
- FreeQ equivalent in MatchPy? HOT 1
- New MatchPy version? HOT 5
- Expression matching with patterns without wildcards HOT 4
- Overridable node visitors instead of typed-nodes in expression trees HOT 2
- Project fails on test cases
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from matchpy.