I have added ~1700 ReplacementRules in ManyToOneReplacer. The .replace() has become very slow even for very small expressions(like 2*x).

File: https://github.com/parsoyaarihant/sympy/blob/502fd311d64155560383a5f4f3b2710c318dc410/sympy/integrals/rubi/patterns.py

Added Hopcroft-Karp algorithm in order to free MatchPy of its GPL dependency. Readapted from the C++ implementation in SymEngine.

Translating the C++ implementation in SymEngine back to Python.

I'm the author of the C++ implementation so no copyright notice mentioning SymEngine is necessary.

Hi, I implemented ~80 rules using ManyToOneReplacer for Rubi integration and MatchPy was able to match the subjects very quickly. However, when I added ~550 rules, there was significant decrease in speed while matching even smaller subjects.

It would be great if you could advice us on how to solve this issue.

Here are the files for our project:

Patterns: https://github.com/parsoyaarihant/sympy/blob/rubi4/sympy/rubi/patterns.py Constraint: https://github.com/parsoyaarihant/sympy/blob/rubi4/sympy/rubi/constraint.py All Rubi Files: https://github.com/parsoyaarihant/sympy/tree/rubi4/sympy/rubi

I wanted to know if matchpy supports optional arguments during match.

Mathematica: https://reference.wolfram.com/language/ref/Optional.html

Example:

>>> x = Symbol('x')
>>> a_ = Wildcard.dot('a', optional=1)
>>> a_free = CustomConstraint(lambda a, x: str(x) not in a.symbols)
>>> x_ = Wildcard.dot('x')
>>> pattern = Pattern(Mul(a_, x_), a_free)
>>> next(match(x, pattern))
{a: 1}

The code generator enforces the reading of all variables whenever a constraint has been encountered. In this PR, the constraint is check only if all variables have been read.

Furthermore, indentation has been changes to four spaces and a related bug forcing to always use bugs has been fixed as well.

In the current RUBI rules patterns in SymPy, the same constraint is defined many times. For example: CustomConstraint(lambda a, x: FreeQ(a, x)) has its definition repeated more and more, like in:

https://github.com/sympy/sympy/blob/628286fb5cc2248002bb0b141a911757a2e81fa7/sympy/integrals/rubi/rules/miscellaneous_algebraic.py#L22

and in the next rule the same constraint is redefined: https://github.com/sympy/sympy/blob/628286fb5cc2248002bb0b141a911757a2e81fa7/sympy/integrals/rubi/rules/miscellaneous_algebraic.py#L26

Python defines a new object for every new lambda definition, even if the functions return the same identical value.

Does this practice have some potential negative consequences, like:

• the size of the generated decision tree?
• the overall speed of MatchPy?

Hi, I am trying to define class ConstantWild (similar to ConstantSymbol you suggested earlier).

Here is the code:

from matchpy import Wildcard

class ConstantWild(Wildcard):
    def __init__(self, value):
        super(self.__class__, self).__init__(min_count=1, fixed_size=True, variable_name=str(value))
        self.value = value

    def __str__(self):
        return str(self.value)

The above code have same attributes as Wildcard.dot but I don't understand why it is giving errors.

Substitute now accepts custom sorting key to specify custom sorting for elements in Multiset.

This should solve the compatibility problem with SymPy which does not allow comparison operators (>, >=, <, <=) to be evaluated to booleans if the truth of the expression cannot be easily determined.

I could not find any documentation related to code generation. Last year @wheerd had written a code generation script for rubi in sympy. https://gist.github.com/wheerd/13ac5a0e9b560db6201d96136fa0bbcc

But code generated was huge so, It cannot be used. This year I have removed the repeated definition of constraints. So code generation should work probably.

However, I am unable to write the code generation script. Here is the new structure of rubi in sympy. Can someone update the gist accordingly?

rules = [] #list to keep track which rules has been applied
def cons_f1(m, x):
    return FreeQ(m, x)
cons1 = CustomConstraint(cons_f1)

def cons_f2(m):
    return NonzeroQ(m + S(1))
cons2 = CustomConstraint(cons_f2)

pattern1 = Pattern(Integral(x_**WC('m', S(1)), x_), cons1, cons2)
def replacement1(m, x):
    rules.append(1)
    return Simp(x**(m + S(1))/(m + S(1)), x)
rule1 = ReplacementRule(pattern1, replacement1)

I wanted to know if there is alternatative way to define constraint in matchpy. Example:

def FreeQ(vars, x): # returns True of any `var` contains `x`
	if any(i.contains(x) for i in vars):
		return False
	return True

def NonzeroQ(e): # returns True if `e` is not zero.
	return e != 0

pattern = Pattern(Int(Pow(Add(a_, Mul(b_, x_)), m_), x_), FreeQ(list(a, b, m), x), NonzeroQ(Add(m, 1)))

Thanks.

The hopcroftkarp library upon which this project depends is GPL'd.

I have re-implemented the Hopcroft-Karp algorithm in C++ as part of an attempt to make MatchPy usable in SymEngine (that is, SymPy's core rewritten in C++). I didn't perform extensive testing, so there may be bugs. That code can be translated into Python.

Mathematica has FreeQ to test whether an expression contains a symbol. This is very useful in pattern matching for equations as you can specify that, for example, in a * x + b == 0 the variables a and b should not contain the variable x.

In SymPy we are currently using things like CustomConstraint(lambda a, x: not a.has(x)), where a.has(x) is a SymPy expression that tells you if x is contained in the expression tree of a.

Would it make sense to add an optimized FreeQ-like tester that checks whether the variable is contained in the expression during the matching iteration of MatchPy?

When using the optional=value argument in Wildcard, one can specify which value to get in case no matching is found. The value has to be given for every wildcard.

In case of addition and multiplication, the usual optional values are the identity elements, zero and one respectively.

It would be nice to have the possibility to have the optional value to return the identity element of the current node, if available.

Calling sorted( ) in https://github.com/HPAC/matchpy/blob/5cae3f275e3a1f725518516bf3c700dc3be03a56/matchpy/functions.py#L87 fails with SymPy, as SymPy objects are not comparable with operators (<, <=, >, >=). Operators are overloaded in SymPy to create instances of inequality objects.

SymPy has a function called default_sort_key meant to deal with this problem:

from sympy import symbols
x, y, z = symbols("x y z")
from sympy.core.compatibility import default_sort_key
sorted([z, x, y], key=default_sort_key)

The question is, is it possible to modify MatchPy to specify a custom sorting key so that SymPy can specify the way its objects should be sorted?

Or is it an issue with Multiset?

In one-to-one matching, symbols that have a variable_name do not work in commutative functions. They seem to work correctly in many-to-one matching. Example:

from matchpy import Operation, Symbol, Arity, Pattern, match, ManyToOneMatcher

f = Operation.new('f', Arity.binary, commutative=True)
a_x = Symbol('a', variable_name='x')
a = Symbol('a')
b = Symbol('b')

subject = f(a, b)
pattern = Pattern(f(a_x, b))

print(list(match(subject, pattern)))

matcher = ManyToOneMatcher(pattern)
print(list(matcher.match(subject)))

This results in

[]
[(Pattern(f(a: x, b)), {'x': Symbol('a')})]

but it should result in

[{'x': Symbol('a')}]
[(Pattern(f(a: x, b)), {'x': Symbol('a')})]

So far, we don't have any tests that verify this functionality. Once it is fixed, we should add some.

Is there any way to match a function with a certain number of arguments? Suppose I've defined a binary function sum, is there a way to create a pattern f(a, b) that matches sum(x, y)?

To avoid issues such as #60, we should check that objects are created and functions are used correctly, at least in those cases where so far, incorrect input does not produce any errors.