Improve function simplify in non-commutative contexts

[samueltlg]

The bugs/limitations
The simplify function currently exhibits limitations and in some scenarios 'bugs' when simplifying in either (or both) a non-commutative context over the operators of addition and multiplication (whilst notably, associativity still remains).

Broadly, the bug(s) can be narrowed down to unevaluated constant/numeric operations in expressions constituted by addition or multiplication (or their inverses of subtraction/division) for a number of expression configurations, where evaluation can be understood as mathematically valid (given the context) in these scenarios.

The limitations can be understood similarly as failure of matching standard/non-function rule application for these same operators in this context and for similar expression arrangements.

To illustrate:

(for the 'bugs')

// In a non-commutative context...
// 'constant * constant' or 'constant + constant' evaluates, e.g.:
'2 * 2 -> 4'
'3 + 3 -> 6'

// Join these expressions with the same operator with at least one leading non-constant node ('v') however..
'v * 2 * 2'
'v + 3 + 3'

//.. and the simplified expression remains the same as if unsimplified

// The same goes for trailing numeric expressions which also include inverse operators/operations
// Simplifying the following:
'v * 8 / 4 * 2 * 3  -> LHS'
'v - 3 + 2 - 4'      -> LHS'   // (well, with the first subtraction op. flattened, so truthfully 'v + -3 + 2 - 4'

// Additionally, these numeric sub-expressions remain non-simplified when 'wedged' between non-constant nodes
// Such that
'b*c*2*2*2*c*b'
'b+c+2+2+2+c+b''

// both remain unchanged

And with regards to the 'limitations':

/*
 * Where rule
 *
 * 'v*v -> v^2'
 *
 * is expected to apply
*/

// exprs. with successful application for this rule
'a*a'
'a*a*2'
'a*a+2'
..

// and unsuccessful
'2*b*b'        // e.g. expr. of form 'c * v * v'
'2*b*b*2'      // expr. of form 'c * v * v * c'
'2*b*b*3*b*b'  // expr. of form 'c * v * v * c' * v * v


/*
 * Where rule 
 *
 * 'v   * ( v   * n1 + n2)'
 *
 * is expected to apply
*/
// successful app.
'd*(d*2+3)'
'd*(d*e+f)'
'd*(d*e+f)*2'
'd*(d*e+f)*v'
'd*(d*e+f)*...'

// unsuccessful app.
'2*d*(d*e+f)'
'2*2*d*(d*e+f)'
'g*d*(d*e+f)'
'(n1*n2..*..nx)*d*(d*e+f)' // excluding expressions where '(n1*n2..*..nx)' is eliminated, such as evaluating to '1'


/*
 * And rule  'n^n1 * n^n2 -> n^(n1+n2)'
*/
// successful
'a^2*a^2'
'a^2*a^2*b'
'a^2*a^2*2'
'a^2*a^2*...

// unsuccessful
'...*a^2*a^2*2'


/*
 * The same pattern repeats for remaining 'collect like factor' rules.
 *
 * Further, the same applies to rules for the other commonly accepted commutative operator: addition.
 * Namely those bannered under 'collect like term' rules, including (rules):
 *
 *  'n+n            -> 2*n'        (e.g. rule does not apply for 'constant + n + n')
 *  'v*n + v        -> v*(n+1)'    (e.g. rule does not apply for 'constant + v*n + v')
 *  'n3*n1 + n3*n2  -> n3*(n1+n2)' (similar again)
 * 
 * **Note** that this absence of rule-application is still the case for (collect like term) rules marked
 * with property 'assuming.add.commutative' set to 'false', such as for rules 'n1*n3 + n2*n3 -> (n1+n2)*n3'
 * and  'c*n + c -> c*(n+1)'
*/

To Reproduce
Call the mathjs.simplify function on the expressions given in the examples, with the options argument including the following context property:

context: {
  add: {
    associative: true,
    commutative: false,
  },
  multiply: {
    associative: true,
    commutative: false,
  },
},

or, with only one of these properties set to have a non-commutative context.

Issues discussed in #2817

^{Originally posted by samueltlg October 17, 2022}
Hello,

Firstly, I have entitled this discussion in a more general manner such as to keep the discussion open around the topic to which it pertains (I hope you don't mind).

I have been following the progression of this module for quite some time, particularly in the area of simplification/the 'simplify' function. (thank you by the way, to whomever concerned, for the ongoing developments that have occurred here). Consequently, I have also become familiar with the default simplify rule-list, particularly with regards to its ordering of rules.

I did have a question or two though, which I am anticipating may evoke simple answers.

When simplifying an expr. with addition and multiplication set to have a non-commutative context (but let's say associativity remains), the following simplify as expected (default ruleset assumed):

'a + a ->  2 * a'

'3*a + 3*a  ->  6 * a'

// implicit form of above
'3a + 3a  ->  6 * a'

// symbol multiplication
'a * a  ->  a^2'

However, there are a number of operations which possibly do not simplify as one would expect for this context:

// the following two equivalent examples are understandable, since it can be
// deduced that the parser does not treat 'constant * symbol' nodes, implicit
// or otherwise, as single 'units'
'2 * b * 3 * b  ->  LHS/unsimplified'
// implicit form
'2b * 3b  ->  LHS/unsimplified'

// However, the following few examples are not expected
//(an example like this being the instigator of this issue being raised
'(2b) * (3b)  ->  LHS/unsimplified'   //  (1)

// And a somewhat different example, but nevertheless related due to
// being present when in a non-commutative multiplication context
' b * 2 * 2 * 2  ->  LHS'  //  (2)

// And the third (incomplete simplification)
`b * b * b  ->  b^2 * b'  //  (3)

For example (1), unless there is something I am missing with regards to the mathematical properties of the multiplication operator (distributivity, maybe?), it seems that this should be simplifying to 6b^2.
(I say this, because for the case of addition, similar operations simplify fine, such as 3*a + 3*a -> 6 * a as given in the opening expected-output examples)
It seems as if, for the addition op., constant-symbol node pairs are understood as single 'units', whilst in the case of multiplication, this is not so?

For reference, here is the debug-output for a call to simplify on (1) with default-context:

Working on:  (2 b) * (3 b)
Applying log(e) -> 1 produced 2 * b * 3 * b
Applying n * n -> n ^ 2 produced (b ^ 2) * (2 * 3)
Applying n * n ^ n1 -> n ^ (n1 + 1) produced (b ^ 2) * 2 * 3
Applying simplifyConstant produced 6 * (b ^ 2)
Working on:  6 * (b ^ 2)

And with a non-commutative context for addition and multiplication:

Working on:  (2 b) * (3 b)
Applying log(e) -> 1 produced 2 * b * 3 * b
Applying simplifyConstant produced ((2 * b) * 3) * b
Applying n + n -> 2 * n produced 2 * b * 3 * b
Applying simplifyConstant produced ((2 * b) * 3) * b
Applying -n * n1 -> -(n * n1) produced 2 * b * 3 * b
Working on:  ((2 * b) * 3) * b
Applying log(e) -> 1 produced 2 * b * 3 * b
Applying simplifyConstant produced ((2 * b) * 3) * b
Applying n + n -> 2 * n produced 2 * b * 3 * b
Applying simplifyConstant produced ((2 * b) * 3) * b
Applying -n * n1 -> -(n * n1) produced 2 * b * 3 * b

Example (2) b * 2 * 2 * 2 -> LHS is a different 'issue'. I believe that this should simplify to b * 8. Commutativity is concerned with the ordering of operands, and considering that the context is still associative, the independent '2 * 2 * 2' expression should successfully evaluate?
^ Having spent quite a lot of time debugging and examining with the simplify function, I am aware here that this expr. remains un-simplified due to maths working with left-heavy binary node trees.., with that said, would the simplification procedure not benefit from an additional pass of the simplification-loop with the flatten-unflatten process flattening and unflattening to a right-heavy tree? (in the case that commutativity is disabled for at least one of its usual operators, but associativity remains).

And finally for example (3), similar to (1), I do not see a reason why this should not simplify further?

Best wishes, and hope to hear your thoughts!

[josdejong]

Thanks for your clear overview Samuel.

Anyone interested into looking into improving simplify with these suggestions? Help would be welcome.

[samueltlg]

Hi @josdejong. I believe that I may have an idea on how to tackle at least the constant simplification aspect, which I should be able to attempt over the coming few days. I may have to contact you for guidance or questions whilst in the process; if that is alright!

[josdejong]

That sounds promising @samueltlg , thanks! Yes you can for sure ask anything that is unclear. Sometimes it is handy to first explain the plan and optionally work out a minimal proof of concept, then discuss that and align on the approach, and only after that work out the details.

[samueltlg]

Hi @josdejong - thank you.

I was thinking that for this constant-evaluation problem, the procedure within simplifyConstant foldOp could be altered (in these contexts) such that the args array it is not iterated over just once (i.e. as is done currently Array's prototype-reduce). This way, evaluable sub-expressions for multiplication and addition operations, such as the 22 or 33 within a*2*2*b*3*3*c, could be accounted for, before then finally calling the original reduce procedure?
Simple, maybe; but do you spot any flaws with that?

[samueltlg]

Hi @josdejong , I have made some simple local proposed changes for the constant-evaluation aspect including tests, and it seems to be working!
Are you OK if I make a fork of these changes and submit a PR for you to take a look at? Best wishes

[samueltlg]

Or, perhaps, whichever method would be easiest such that not only this aspect but also the remaining improvements can be addressed in a branch, in order that that its pull-request can be understood as having covered everything in this issue/feature?

(i.e. the remaining task(s) will likely prove more difficult and possibly require more of your input!)

[josdejong]

Sounds good! If you have stuff working already on your machine, would it be easy for you to create a PR as a Draft? That would make it easier for me to really understand your solution. I'm curious to see your approach.

[samueltlg]

Hi Jos! I have issued the draft. Let me know what you think !

[samueltlg]

Hi Jos,
I should be able to work towards solving the remaining counterpart to this issue within the next week; being the issuing of a fix for the app. of 'standard' rules in a non-commutative context.
As I guess you can see, I have affiliated myself with the whole simplify process after working closely with it for a while, as evidenced by the fact that I had an idea of where to look for the constant eval. side !

I would reckon that this next part will be significantly more difficult to tackle, you probably agree..
My current feeling on how to approach this so far would perhaps be to work with and alter the 'expanded' rules since, it does appear, that for all of the examples listed in this discussion intro (constant + node [+-/*] .., and so on), it will only be the expanded rules which could potentially successfully apply (in a non-commutative context) anyway.
Does then anything come to mind for you with the suggestion of expanding the breadth of applicability for expanded rules (in this context) by increasing the current number of permutations for expanded matching by doing something like introducing an extra placeholder, such that a generated expanded rule of the I think usual form LHS [+*] _p1 could be further expanded to _p1 [+*] LHS [+*] _p2 (putting aside for the time being the extra procedural changes I'm sure will be required as a consequence) ?

Any intuitions on whether this is a good place to start? I wonder if it would incur a more-than-moderate performance penalty ?
Or any other thoughts?
All the best.