Google Summer of Code Week 8: Non-Commutative Wildcards

Posted on July 22, 2019 by Ankit Pandey

See the previous post for Week 7.

I spent most of this week rewriting the non-commutative matching code in Sympy’s core as Aaron suggested. The pull request for this rewrite is available at #17223.

Non-commutative matching in SymPy

SymPy already supports matching within non-commutative multiplication expressions. While I mentioned in my last blog post that this matching support was limited, I’ll go into a bit more detail about what those limitations (which sometimes produce wrong results) are:

No matching based on structure

Matching within commutative SymPy expressions allows for taking the structure of expressions into account. Two commutative SymPy expressions match only if both contain the same non-wildcard symbols:

m specifies that the expression must contain both x and y in addition to whatever the wildcard matches. For this reason, m matches x*y*z but not a*x*z.

The corresponding example for non-commutative expressions does not work as expected, as it does not match when we expect it to:

Expressions don’t respect non-commutativity

In instances where matching does seem to work, the non-commutativity of expressions is not respected:

The two expressions should not have matched, since the order of the non-commutative expressions were different. I reported this same error for matrix expressions in issue #17172.

Sub-expressions aren’t expanded

The matching code should be able to match portions of powers, which are represented differently in the SymPy AST. As an example, a non-commutative matcher such as AWAW (where WW is a wildcard) should match A2A^2 with {WA}\{W \mapsto A\} . I wasn’t able create a working example of this using the existing matching code.

Matching Implementation

Since order needs to be taken into account for matching non-commutative expressions, the new matching code essentially does what a regular expression matcher would do, with nodes taking the place of characters and wildcards taking the place of the .+ regular expression.

Next Steps

The matching PR still needs to be polished, and the related documentation needs to be updated, so I’ll be working on that. I’ll also start with extending matrix matching from this PR.