Proposal for a new pattern matching

Francesco Bonazzi edited this page Mar 20, 2017 · 12 revisions
Clone this wiki locally

Currently, the are two algorithms providing pattern matching in SymPy, the .match( ) provided by SymPy's core and the unify module. .match( ) is mathematically aware, while the unification module provides a structural matching.

In the unification module there is no distinction between expression and pattern, there are just two expression and wildcards can be placed in both of them. Unification provides a substitution for the wildcards such as the two expressions become the same, while in ordinary pattern matching wildcards can be only in the pattern, not in the expression.

In both modules, the matching acts on the whole expression, not on subexpressions. Wolfram Mathematica has a powerful matching and term rewriting system, which acts on expression trees by matching subtrees of expressions.

General idea

The idea about a new pattern matching is to provide matching on subtrees, enabling more options to be available on wildcards (such as optionality, types allowed to be matched, assumptions on wildcard, filtering conditions, information on whether it has to be o node or a subset of a node's children).

Strictly speaking, there should be a generalization of subtree searches, as one may be interested to match x and y in f(x, y, z) disregarding z, so maybe a tuple (x, y) can represent the matched expression (losing info about f and z).

Unification is not needed, most cases involve an expression without wilds, and rules to rewrite it or find subexpressions.

There should be minimal mathematical sensitive behavior, provided by the canonicalization of the pattern. For example the pattern w+x should match x+y yielding {w: y}, even if the order is not the same. It is better to avoid all complications derived by the mathematically-sensitive pattern matcher in SymPy's core, that means, w1*z matched against the expression y should return {} (no match), and not expressions such as {w1: y/z}. The only mathematical sensitive operations should be the canonicalizations of the pattern and the expression, after that only structural matching should happen.

For a mathematically sensitive pattern matcher, there should be support to construct advanced patterns, such as OR expressions along the pattern tree.

Pattern uses

Patterns can be used to:

  • match the wildcards to a subtree in the expression.
  • extract subexpressions.
  • rewrite rules: replace the pattern by another expression (possibly containing the wilds).
  • pattern dispatching of functions (i.e. define a function to be dispatched according to matching expressions).

Behaviour

Pattern matching should never raise any error. The unify module rewriterule raises an error if the rewrite rule did not apply. A better behaviour is to just return the expression unmodified. Maybe there could be two functions, e.g. rewrite and rewrite_with_counter. The second would return the modified expression and the number of replacement events.

There should also be support to go to the next match, in case a pattern can be matched in many different ways.

There should also be support for exhaustive replacement, meaning a replacement rule applying recursively until the expression is no longer affected by it.

Proposals

Wildcard objects (old idea)

NOTE: this idea may be too cumbersome.

Create wildcard objects such as

  • WildNode ==> matches a tree node.
  • WildSequence ==> matches a tuple of node siblings.

For example

>>> wn1 = WildNode('wn1')
>>> wn2 = WildNode('wn2')
>>> ws = WildSequence('ws')
>>> match(f(x, y, z), wn1(x, y, wn2))
{wn1: f(x, y, z), wn2: z}
>>> match(f(x, y, z), f(ws, wn1))
{ws: (x, y), wn1: z}
>>> match(f(x, y, z), ws)
{ws: f(x, y, z)}
>>> match(f(x, g(y, z), w), g(ws))
{ws: (y, z)}

Example: replace all occurrences of w_*conjugate(w_) by abs(w_)**2

>>> replace(sin(u*conjugate(u))+exp(a+z*o*conjugate(o)), {wn1*conjugate(wn1): abs(wn1)**2})
sin(abs(u)**2) + exp(a+z*abs(o)**2)

WildNode just matches a single node, not a sequence:

>>> replace(u*o*conjugate(u*o), {wn1*conjugate(wn1): abs(wn1)**2})
u*o*conjugate(u*o)

WildSequence would work in this case:

>>> replace(u*o*conjugate(u*o), {ws*conjugate(ws): abs(ws)**2})
abs(u*o)**2

Multiple patterns

A list of pattern could be provided:

>>> match(f(x), [f(wn1), wn2(wn1)])
{wn1: x}
>>> match(g(x), [f(wn1), wn2(wn1)])
{wn1: x, wn2: g(x)}

Or conditions

Proposal: PatternOr function, creates many possible matching patterns, splitting the pattern at the node it is found:

>>> match(f(x), [PatternOr(f(wn1), g(wn1))])
{wn1: x}

Optional wilds

Wilds that need to be matched:

>>> match(f(x), f(wn1, wn2), optional=(wn2,))
{wn1: x, wn2: None}

Default values for unmatched wilds

>>> match(f(x), f(wn1, wn2), default={wn2: S.Zero})
{wn1: x, wn2: 0}

Type wilds can match

TODO: decide how to distinguish subtypes and exact type matches.

>>> match(f(x), wn1, typeis={wn1: Function})
{wn1: f(x)}
>>> match(f(x), wn1, typeis={wn1: Symbol})
{wn1: x}

Alternative: a Match object

A Match object could represent an alternative without wildcard classes. Consider this example:

>>> a, b, x, y = symbols("a b x y")
>>> m = Match(a+sin(b), wild=(b,), wildseq=(a,))
>>> m.match(3+x+sin(y))
{a: 3+x, b: y}

No Wildcard objects have been used. That is, first argument of Match has an expression to match, its parameters define which variables should behave as wildcards and which type of wildcards they should be.

Transformation rules

In order to apply transformations, one may define something similar, let's say a TransformationRule object:

>>> a, b, x, y = symbols("a b x y")
>>> tr = TransformationRule(a+sin(b), sin(a)*cos(b), wild=(b,), wildseq=(a,))
>>> tr.transform(3+x+sin(y))
sin(3+x)*cos(y)

or as an alternative declaration:

m = Match(a+sin(b), wild=(b,), wildseq=(a,))
tr = TransformationRule(m, sin(a)*cos(b))

Pattern dispatch

Using decorators to define a function f to be dispatched according to pattern matching rules:

@patterndispatch(g(wn1))
def f(expr, matches):
    ...

@patterndispatch(wn1)
def f(expr, matches):
    ...

So

>>> f(g(x))  # calls first function, with expr=g(x) and matches={wn1: x}
>>> f(3)     # calls second function, with expr=3 and matches={wn1: 3}

Without pattern dispatching: list of rules

A simpler step could be given by matching lists. Using Match or TransformationRule objects, one could put them sequentially and create and object that applies them sequentially until the first one is found.

Some examples from Mathics

Mathics is an open-source clone of Mathematica (Mathics is GPL, unfortunately). In any case, Mathics implements the rewrite capabilities and predicate dispatch of Mathematica.

Mathics' code is open source and available on github for review: https://github.com/poeschko/mathics

Unfortunately, being GPL, it's code cannot be copied into SymPy, it has to be rewritten from scratch.

Predicate dispatch

By predicate dispatch it is meant a pattern dispatch endowed of conditions.

Predicate dispatch example:

In[1]:= f[x_] = 1
Out[1]= 1

In[2]:= f[x_Integer] = 2
Out[2]= 2

In[3]:= f[x_Integer] = 3 /; x> 5
Out[3]= 3 /; x > 5

In[4]:= Definition[f]
Out[4]= f[x_Integer] /; x > 5 = 3
        
        f[x_Integer] = 2
        
        f[x_] = 1

Here, f has been defined three times. In the definition of f, the matching set is sorted to allow more specialized matches to have priority over less specialized ones.

It is possible to see how this dispatching selects the correct function:

In[8]:= f[3/2]
Out[8]= 1

In[9]:= f[2]
Out[9]= 2

In[10]:= f[7]
Out[10]= 3

Mathematica documentation

Mathematica stores information about predicate dispatching in a list, which can be retrieved by the DownValues command:

http://reference.wolfram.com/mathematica/ref/DownValues.html

Technically, one could use a more advanced data structure to store pattern expressions in order to have a more efficient predicate dispatching mechanism, like Tries or DAGs, but a simple list would be a good start.

Other information about the definition mechanism in Mathematica:

http://reference.wolfram.com/mathematica/tutorial/ManipulatingValueLists.html

How the ordering of definitions works in Mathematica:

http://reference.wolfram.com/mathematica/tutorial/TheOrderingOfDefinitions.html

The point is, the set of all possible predicate dispatches is a partially ordered set, i.e. for some pairs there is a clearly defined order of priority, for other pairs there is none. In case of ambiguities there can be various solutions, such as either using the first or last defined pattern, or raising an error when calling an ambiguous pattern.

Predicate dispatching ambiguities

An example of ambiguous definition:

In[11]:= g[x_, y_Integer] = 1
Out[11]= 1

In[12]:= g[x_Integer, y_] = 2
Out[12]= 2

how it is evaluated:

In[13]:= g[3/2, 1]
Out[13]= 1

In[14]:= g[1, 3/2]
Out[14]= 2

This case is ambiguous, it is set to the last definition:

In[15]:= g[1, 1]
Out[15]= 2

In general, it is better to raise an exception when trying to call a function with an ambiguous dispatch.

Orderless attribute

Note the attribute orderless, which is used to mark the expression heads as having orderless parameters. Some matching examples:

In[5]:= f[a, b] /. f[b, a] -> {{a}, {b}}
Out[5]= f[a, b]

In[6]:= SetAttributes[f, Orderless]

In[7]:= f[a, b] /. f[b, a] -> {{a}, {b}}
Out[7]= {{a}, {b}}

Input number 5 has not been muched, because f[a, b] != f[b, a]. In input number 7, f has been marked as Orderless, so that f[a, b] == f[b, a]. The orderless attribute is a bit a problem for SymPy, as the operator's orderlessness may depend on the parameter types. Wolfram Mathematica uses, for example, two distinct operators to denote multiplication and matrix multiplication, and the matrix multiplication is clearly not orderless. SymPy uses the same operator for both (*), so the match is more complicated.

Orderless and SymPy

There is a problem in porting Mathematica's pattern matching into SymPy, as SymPy's Mul objects distinguishes between commutative and non-commutative arguments. In Mathematica either all arguments are commutative or none. Mathematica has a distinct product operator for matrices, the Dot or ., while ordinary product is Times. Consider:

In[1]:= Attributes[Dot]
Out[1]= {Flat, OneIdentity, Protected}

In[2]:= Attributes[Times]
Out[2]= {Flat, Listable, NumericFunction, OneIdentity, Orderless, Protected}

Dot does not have the Orderless attribute. One way to deal with this would be to assign an equivalent of Mathematica's attributes to the node and its children types. Otherwise the matcher should be able to distinguish between commutative and non-commutative arguments when constructing subsets and subranges.

Subsets and subranges

In Mathics there is support to generate subsets and subranges lazily, as found in:

https://github.com/poeschko/Mathics/blob/master/mathics/core/util.py

Unfortunately this is GPL-licensed. In calculating subsets, it emerges the problem of commutative/noncommutative arguments, the subset generator should take care of which elements cannot commute and respect their order.

Typed patterns

In SymPy patterns nodes a classes. This is more complicated with respect to Mathematica, as there are issues with class inheritance. A subclass shall match its parent, but in case its parent's constructor accepts different parameters, strange things may happen. Consider the example:

class A(Basic):
    def __new__(cls, a):
        return Basic.__new__(cls, a)

class B(A):
    def __new__(cls):
        return Basic.__new__(cls)

What would happen if B() has to match A(2), or vice versa?