Revising Mathics3 pattern matching.

[rocky]

Mathics3 Pattern Matching is slow and it is on a critical path in M-expression evaluation. It has long been noted that it needs to be rethought/rewritten/revised.

Mathics3/mathics-omnibus#14 has some thoughts on ths.

[rljacobson]

@rocky inspired a few thoughts I have about Mathics and what the team might consider for improvements to pattern matching and parsing and operator support.

Pattern matching

My own project Loris isn't the right choice for pattern matching in Mathics. What is interesting about the algorithm in Loris is not that it is performant but that it can handle infinitary theories–but not as I've implemented it! However, I am working on something that might be a good fit, but it's a ways off from being functional, I'm afraid. It is a reimplementation of the fastest known expression matching algorithms and focuses on performance and on packaging the algorithms in a generic library.

I am also interested in implementing many-to-one matching, but I haven't really started down that road yet. (Many-to-one is especially important for computer algebra where multiple patterns need to be matched against the subject at once.) I'm aware of the recent literature on the subject, though.

For a pure Python pattern matching library, you probably want MatchPy—at the very least talk to its developers. MatchPy is the most capable expression matching library in Python as far as I know.

[mmatera]

I was looking at the MatchPy project, and I have seen that several of the bullet points in their roadmap are already working in our implementation. So, I guess it would be interesting to see if there is interest in working together.
Some time ago, we have speculated about splitting the pattern-matching code (mathics.core.pattern.*, mathics.core.rule.*, and mathics.builtin.base.PatternObject ) from the rest of mathics-core.

The biggest problem with this is that how the pattern matching is performed seems to depend on the evaluation context (in particular, the Evaluation and Evaluation.definitions objects). Then, a separate module would implement some kind of interface that matches both the interface of the (Base)Expression objects and the Evaluation/Definitions object.

[rljacobson]

What some systems do is construct a lightweight proxy DAG and match on that instead. The DAG is cached, so the overhead is minimal. This allows you to separate the pattern matcher from the native expression representation and gives you subtree sharing and cached preprocessing to support fancy-pants algorithms that can leverage it. Match-related properties can live in a small bit field in the DAG node, which means you don't have to design an expression's property store around the matcher—match-related properties need not be distinguished properties in the native expression representation.

I am still digesting the deeper subtleties of the literature and of the best implementations, of which subtleties there are many. Getting advice from experts is always a good idea.

[mmatera]

Regarding this, it seems that at least for the attributes, the evaluation context is just needed at the time in which the rule is created.

In[1]:= Print["Create rules for Q without attributes"];                                                                                                                       
Create rules for Q without attributes

In[2]:= rule = Q[_Integer,_Symbol]->True;                                                                                                                                     

In[3]:= ruled = Dispatch[{rule}];                                                                                                                                             

In[4]:= Print["Check the rules. Here are not applied."];                                                                                                                      
Check the rules. Here are not applied.

In[5]:= {Q[a,1,b]/.rule, Q[a,1,b]/.ruled}                                                                                                                                     

Out[5]= {Q[a, 1, b], Q[a, 1, b]}

In[6]:= Print["Now, we set the attribute 'Flat'"];                                                                                                                            
Now, we set the attribute 'Flat'

In[7]:= SetAttributes[Q, {Flat}];                                                                                                                                             

In[8]:= Print["The attribute is not taken into account:"];                                                                                                                    
The attribute is not taken into account:

In[9]:= {Q[a,1,b]/.rule, Q[a,1,b]/.ruled}                                                                                                                                     

Out[9]= {Q[a, 1, b], Q[a, 1, b]}

In[10]:= Print["Rebuild the rules:"];                                                                                                                                         
Rebuild the rules:

In[11]:= rule = Q[_Integer,_Symbol]->True;                                                                                                                                    

In[12]:= ruled = Dispatch[{rule}];                                                                                                                                            

In[13]:= {Q[a,1,b]/.rule, Q[a,1,b]/.ruled}                                                                                                                                    

Out[13]= {Q[a, True], Q[a, True]}

In[14]:= Print["Clear the attributes:"];                                                                                                                                      
Clear the attributes:

In[15]:= Attributes[Q]={};                                                                                                                                                    

In[16]:= Print["The rules remember the attributes from when they were defined"];                                                                                              
The rules remember the attributes from when they were defined

In[17]:= {Q[a,1,b]/.rule, Q[a,1,b]/.ruled}                                                                                                                                    

Out[17]= {Q[a, True], Q[a, True]}

This makes it more feasible to use the scheme with the light proxy that @rljacobson suggested. Still, for PatternTest, the evaluation context seems to be needed.