`MatchQ[1 + 2 x, (a_. + b_. x_Symbol)]` incorrectly failing

[rocky]

Description

MatchQ[1 + 2 x, (a_. + b_. x_Symbol)] also returns False when it should return True.

How to Reproduce

$ mathics
In[1]:= MatchQ[1 + 2 x, (a_. + b_. x_Symbol)]
Out[1]= False (* Wrong *)

In[2]:= MatchQ[2 x, (a_. + b_. x_Symbol)]
Out[2]= True (* Correct *)

Additional context

This comes from trying to get Rubi working. The function in that, which is failing is called Default[]

[aravindh-krishnamoorthy]

The issue (for now) is mainly with matching patterns that have a dot like a_. + b_. x_Symbol above. Here, the dot means that the pattern matches not just an expression of type a + b x but also 1 + x, b x, x, and so on. The function Default[] is a Wolfram Language function, which informs the pattern matcher on what the "default" values for a and b are, when omitted. So, x is internally matched to a_. + b_. x_Symbol as Plus[Default[Plus, 1], Times[Default[Times, 1], x] where Default[Plus, 1] = 0 is the default argument (additive identity) for Plus, and similarly 1 for Times.

I started very recently with Mathics, so there may be errors in the analysis below.

From what I gather, the problem seems to be that when matching 1 + 2 x to a_. + b_. x_Symbol, in line 465,

mathics-core/mathics/core/pattern.py

Lines 462 to 467 in bf6a8c0

	if isinstance(expression, Expression):
	try:
	basic_match_expression(self, expression, parms)
	except StopGenerator_ExpressionPattern_match:
	return

the exception StopGenerator_ExpressionPattern_match is raised WITHOUT a full match.

The exception is raised because the condition candidates < match_count[0] is met:

mathics-core/mathics/core/pattern.py

Lines 830 to 831 in bf6a8c0

	if candidates < match_count[0]:
	raise StopGenerator_ExpressionPattern_match()

However, inspecting the pattern at this point reveals that:

(Pdb) unmatched_elements
(<Integer: 1>, <Expression: <Symbol: System`Times>[<Integer: 2>, <Symbol: Global`x>]>)
(Pdb) element
<ExpressionPattern: System`Times[System`Optional[System`Pattern[Global`b, System`Blank[]]], System`Pattern[Global`x, System`Blank[System`Symbol]]]>

I'd expect a match here between the second tuple element and the expression pattern.

However, for 0 + 2 x, unlike for 1 + 2 x, basic_match_expression(self, expression, parms) does not match, but instead, the match is performed in

mathics-core/mathics/core/pattern.py

Lines 468 to 469 in bf6a8c0

	if A_ONE_IDENTITY & attributes:
	match_expression_with_one_identity(self, expression, parms)

. So, that seems to be a different case.

I'll try to debug a bit more tomorrow.

[rocky]

However, inspecting the pattern at this point reveals that:

(Pdb) unmatched_elements
(<Integer: 1>, <Expression: <Symbol: System`Times>[<Integer: 2>, <Symbol: Global`x>]>)
(Pdb) element
<ExpressionPattern: System`Times[System`Optional[System`Pattern[Global`b, System`Blank[]]], System`Pattern[Global`x, System`Blank[System`Symbol]]]>

A small side note. Personally, I find

(<Integer: 1>, <Expression: <Symbol: System`Times>[<Integer: 2>, <Symbol: Global`x>]>)

more work than I want to put in to understand. If you install trepan3k and the as yet unreleased trepan3k plugin for Mathics3 then you can see the internal Mathics3 structures printed more like they appear in Mathics3 (along with some pygments coloring)

[rocky]

The issue (for now) is mainly with matching patterns that have a dot like a_. + b_. x_Symbol above. Here, the dot means that the pattern matches not just an expression of type a + b x but also 1 + x, b x, x, and so on.

Here is a guess at what might be wrong. WMA reduces expressions to a standard form. And a reason for doing this is so that when trying to match expressions against a pattern, the pattern-matcher does not have to consider both 1 + x and x + 1 . After reducing to standard form, these are the same thing.

So possibly we are not reducing to standard form (which might also include the pattern) when we should be?

[aravindh-krishnamoorthy]

I looked at

MatchQ[1 + 2 x, (a_. + b_. x_Symbol)]

since with Hold[], the given pattern in the issue title fails in expreduce and Mathematica as well:

~/git/expreduce$ go run expreduce.go
Welcome to Expreduce!

In[1]:= MatchQ[Hold[1 + 2 x], (a_. + b_. x_Symbol)]
Out[1]= False

In[2]:=

The commit aravindh-krishnamoorthy@8fbd633 seems to fix this issue. With the additional Rubi bugfix in aravindh-krishnamoorthy@c0fb5d4 (adds HoldAll to Int[], which I had mistakenly removed during cleanup), several of Rubi's tests now pass.

Current Rubi codebase for mathics-core: https://github.com/aravindh-krishnamoorthy/mathics-core/tree/rubi

I'm still a novice with Mathics (and Python in general). Hence, I'm not fully sure if the fix in aravindh-krishnamoorthy@8fbd633 has unintended side effects. In my limited testing, it seemed to work.

Furthermore,

Mathics 7.0.1dev0
on CPython 3.11.10 | packaged by conda-forge | (main, Oct 16 2024, 01:27:36) [GCC 13.3.0]
using SymPy 1.13.3, mpmath 1.3.0, numpy 2.1.3, cython Not installed

...

In[2]:= MatchQ[1 + 2 x, (a_. + b_. x_Symbol)]
Out[2]= True

The bug seems to be that match_expression_with_one_identity() adds a default value {Global`b, 1} to the vars dictionary while matching the first part of the expression (in this case 1), which is not removed and interferes with the matching of the second part.

[rocky]

I looked at

MatchQ[1 + 2 x, (a_. + b_. x_Symbol)]

since with Hold[], the given pattern in the issue title fails in expreduce and Mathematica as well:

I started this issue without the "Hold", and it was suggested that "Hold" was needed. I've changed the issue without the "Hold" now.

That just isolating what the issue is, seems to be a challenge in of itself. Another reason we should make more effort to find a minimal case.

Often when one does that, one is very close to understanding what the problem is. And this is not something that needs either Mathics3 or Python experience to do.

I'm still a novice with Mathics (and Python in general). Hence, I'm not fully sure if the fix in aravindh-krishnamoorthy@8fbd633 has unintended side effects. In my limited testing, it seemed to work.

As you suggest, it might be this is fixing problems in one area while adding some in another area. That function was added for a reason -- what though I don't know.

I will note however that older versions of the code contained this commented out:

# and 'OneIdentity' not in (expression.get_attributes(evaluation.definitions) | expression.get_head().get_attributes(evaluation.definitions)):

The simplest thing to do would be to submit a PR for this which will cause the tests to get automatically run. (In your repository you could do the same thing, or look at how tests get run and run them locally).

With the PR in place it will be easier for @mmatera to look at. He was the last person to touch this area, and he know far more about this topic than I do.

The bug seems to be that match_expression_with_one_identity() adds a default value {Global`b, 1} to the vars dictionary while matching the first part of the expression (in this case 1), which is not removed and interferes with the matching of the second part.

Again, there probably a reason why this was added. I have no idea what that reason is though.

[mmatera]

@rocky, regarding the test case: the problem with MatchQ[0 + 2 x, (a_. + b_. x_Symbol)] was that you were not tested what you attempted to test: The 0 goes away before MatchQ gets evaluated. So, to test that case, what you want is
MatchQ[Hold[0 + 2 x], Hold[a_. + b_. x_Symbol]]

To test the Optional and Default behavior, you need to test them also by applying rules like:

Hold[0 + 3*a] /. {p_. + q_Integer * s_. :> {p, q, s} }

3*a + b /. {p_. + q_Integer * s_. :> {p, q, s} }

[rocky]

Ok. Yes, I see that running MatchQ with an 0 + 2 x expression is the same as 2 x.

However, we are missing the broader point - what we are interested in is trying to isolate the problem experienced in trying to run Rubi. If you look at the current description, you'll see that I dropped the 0 +. And previously I dropped the ^1 and ^n since those were not relevant. And changed the delayed assignment into MatchQ since this probably narrows where the problem is as well.

If there is some other example that narrows this even further, for example, I tried omitting the multiplication, that would be interesting. What we are trying to get is a concise description of what bugs we have in Mathics. Right now these two examples are the best we have so far.

[aravindh-krishnamoorthy]

A small side note. Personally, I find

(<Integer: 1>, <Expression: <Symbol: System`Times>[<Integer: 2>, <Symbol: Global`x>]>)

more work than I want to put in to understand. If you install trepan3k and the as yet unreleased trepan3k plugin for Mathics3 then you can see the internal Mathics3 structures printed more like they appear in Mathics3 (along with some pygments coloring)

Thank you for this! I revised my debugging technique based on your trepan3k and on this hack

https://github.com/aravindh-krishnamoorthy/mathics-core/blob/7ed4c11e39d7e39c4a824e9558b4fef0b8866b7e/mathics/builtin/system.py#L875-L896

But, I don't use trepan3k-mathics-debugger yet as I'm interested in the classnames, etc.

And the debugging process is like this:

$ export PYTHONBREAKPOINT=trepan.api.debug
$ mathics


Mathics 7.0.1dev0
on CPython 3.11.10 | packaged by conda-forge | (main, Oct 16 2024, 01:27:36) [GCC 13.3.0]
using SymPy 1.13.3, mpmath 1.3.0, numpy 2.1.3, cython Not installed
...

In[1]:= Breakpoint[]; MatchQ[x, x]
(mathics/builtin/system.py:896 @32): eval
<- 896         breakpoint()
R=> None
(trepan3k) break mathics/builtin/testing_expressions/expression_tests.py:64
Breakpoint 1 set at line 64 of file
        mathics/builtin/testing_expressions/expression_tests.py
Breakpoint is at offset 2 of eval()
(trepan3k) c
(mathics/builtin/testing_expressions/expression_tests.py:64 @2): eval
xx 64         try:
(trepan3k)

I will update to your workflow once I start debugging Wolfram Language code.

[rocky]

A small side note. Personally, I find

(<Integer: 1>, <Expression: <Symbol: System`Times>[<Integer: 2>, <Symbol: Global`x>]>)

more work than I want to put in to understand. If you install trepan3k and the as yet unreleased trepan3k plugin for Mathics3 then you can see the internal Mathics3 structures printed more like they appear in Mathics3 (along with some pygments coloring)

Thank you for this! I revised my debugging technique based on your trepan3k and on this hack

https://github.com/aravindh-krishnamoorthy/mathics-core/blob/7ed4c11e39d7e39c4a824e9558b4fef0b8866b7e/mathics/builtin/system.py#L875-L896

This would be good to put into mathics-core. @mmatera your thoughts?

But, I don't use trepan3k-mathics-debugger yet as I'm interested in the classnames, etc.

I don't understand what this means. If you load in the extension, you can still access class names and Python objects as before. It is just that when an underlying object is a Mathics3 object represented in Python, there is an additional command called printelement (with short alias pe) that will show it more as it would appear in Mathics3.

Later on, I will probably also add an option to show it in operator format rather than FullForm. But just this, I find useful.

The other thing this let's me do is filter the long call stack into more interesting points that are more akin to higher-level Mathics3 evaluations, e.g. what the evals and apply at the Mathics3 level are going on. It is an abbreviated Mathics3-level oriented backtrace.

And the debugging process is like this:

$ export PYTHONBREAKPOINT=trepan.api.debug
$ mathics

Yes, this is the more modern way of entering Python debuggers. I see I need to update the docs to mention this, I have just an example for remote execution. I will do this soon.

Mathics 7.0.1dev0
on CPython 3.11.10 | packaged by conda-forge | (main, Oct 16 2024, 01:27:36) [GCC 13.3.0]
using SymPy 1.13.3, mpmath 1.3.0, numpy 2.1.3, cython Not installed
...

In[1]:= Breakpoint[]; MatchQ[x, x]
(mathics/builtin/system.py:896 @32): eval
<- 896 breakpoint()
R=> None
(trepan3k) break mathics/builtin/testing_expressions/expression_tests.py:64
Breakpoint 1 set at line 64 of file
mathics/builtin/testing_expressions/expression_tests.py
Breakpoint is at offset 2 of eval()
(trepan3k) c
(mathics/builtin/testing_expressions/expression_tests.py:64 @2): eval
xx 64 try:
(trepan3k)

I will update to your workflow once I start debugging Wolfram Language code.

[aravindh-krishnamoorthy]

Thank you, @rocky. trepan3k is really cool.

I don't understand what this means. If you load in the extension, you can still access class names and Python objects as before. It is just that when an underlying object is a Mathics3 object represented in Python, there is an additional command called printelement (with short alias pe) that will show it more as it would appear in Mathics3.

Later on, I will probably also add an option to show it in operator format rather than FullForm. But just this, I find useful.

The other thing this let's me do is filter the long call stack into more interesting points that are more akin to higher-level Mathics3 evaluations, e.g. what the evals and apply at the Mathics3 level are going on. It is an abbreviated Mathics3-level oriented backtrace.

Sorry, I think I didn't explore the debugger sufficiently. The features look great; I'll take a closer look,

[rocky]

In[1]:= Breakpoint[]; MatchQ[x, x]
(mathics/builtin/system.py:896 @32): eval
<- 896 breakpoint()
R=> None
(trepan3k) break mathics/builtin/testing_expressions/expression_tests.py:64

@aravindh-krishnamoorthy Would you please put in a PR to add Breakpoint? Thanks.