Questions on simplification context

[samueltlg]

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!

[samueltlg]

It is interesting, isn't it?

I am sure that in the case of example 1, I am simply lacking in mathematical comprehension; and by now I think that I have figured out why the current functioning is correct and that to permit its simplification in absence of commutativity would be mathematically invalid.
It is interesting to break it down and examine what 'commutativity' really means. If we break it down:

// The original example was '(2b) * (3b)', but to take a look at a simpler version first..
// '2b * 2': also not simplified in absence of commutativity of multiplication and addition
'= 2b * 2'
'= (2 * b) * 2'
' = (b + b) * 2'

// ^ We are saying that '(b + b) * 2' cannot be simplified when commutativity (namely,
// for multiplication) is not assumed.
// Does the property of commutativity then imply that:
'= 2 * (b + b)'

// .. is an acceptable operation, whilst '(b + b) * 2' is not? So, the absence of the law must mean
' (b + b) * 2   !==   2 * (b + b) '

// Which is a strange thing, because, at least according to mathjs, in the absence of commutativity:
'2 * 2  ===  2 * 2   === 4'
// and even:
'a * a   ===   a^2'

// ^ Ah, but that applies in those cases because the left operand and right
// operand are 'identical'? (e.g. the 'a' has the same 'identity' in the case of
// 'a * a' and so it can simplify to a^2?)

// Pfft.. but what is that saying of '(b + b)' / '2b'. That 'b' is not identical to 'b'?
// That '(b + b)' multiplied by itself (which is almost the same opening example
// of '2b * 3b'), cannot be simplified in the absence of commutativity?
'= (b + b) * (b + b)
'= 2b * 2b'

// Ah.. but '2b * 2b'   *is*  simplified (by mathjs, to '(2*b)^2'), whilst '3b * 2b' *is not*

// And so, if you really think about it, does the *absence* of the property of
// commutativity simply attribute special properties to variables/symbols in a symbol
// expression?... Such that:
'= b * b  ->  b ^ 2'

// Is accepted in the absence of commutativity (of multiplication), *but*:
'2b * 2b  ->  (b + b) * (b + b)')
// or
'2b  *  2b  ->  (b + b) * (b + b + b)'

// is not accepted
// indeed almost as if variables are attributed mystical properties,, (but only when they are
// multiplied by a (real?) number??)

// and you can end up in some strange places thinking about this!

I invite your thoughts on this.

On a lighter note, I believe that the second and third examples

' b * 2 * 2 * 2  ->  LHS'  //  (2)
`b * b * b  ->  b^2 * b'  //  (3)

are incorrect/bugs, in any case.

[josdejong]

Thanks for your inputs Samuel.

I'm not sure if I follow what you mean. When you configure multiply to be non-commutative, it makes sense to me that multiply isn't simplified? I mean, you basically say changing something in the order of the arguments of multiply may give differing results, right? So then replacing and/or reordering arguments isn't safe to do in general?

Do you see concrete opportunities to improve the simplify logic?

[gwhitney]

I agree that there is no reason not to simplify b * 2 * 2 * 2 to b * 8 even without commutativity, so yes that is a shortcoming of the current set of rules. Similarly b * b * b = b^3 would be perfectly valid without commutativity, so it would be great to improve the rules so that happens.

Basically, when commutativity is off for an operation, simplify will not perform any operations which require swapping the order of two operands. So for example it cannot convert between 2 * b and b * 2. But ideally it will still find and use simplifications that don't require any such swaps, but you have found some cases in which it currently falls short of this ideal. As far as I am concerned, you could file those two as a bug.

[samueltlg]

Hi Jos and Glen,

I believe that in the case of the first example, I had worked myself into a confusion resulting from considering terms such as 2b as single-units, such that 2b * 2b would simplify: but for this to be so this would either be 1) (falsely) attributing commutativity to individual 2b terms, or 2) making manoeuvres assuming equivalency between 2b and b + b (within the 'proofs').
Nevertheless, it seems to be possible to wind oneself up into some peculiar mathematical domains that the brain struggles to compute, by playing around with expressions such as 2b * 2 or 2b*2b.

For example, it does seem to evoke questions around the topic of operator commutativity (and other properties) - 'are these properties only defined for a subset of operations for an operator, and if so, is the property (of commutativity) in fact not a property of binary operators but of operations?' <- (clearly it is the case that commutativity is not 'relevant' or affective for some operations since numeric expressions remain simplifiable.). Furthermore, it simply raises interesting questions about which algebraic entities are assumed to be taking the place of variables/symbols in such cases (indeed, I know that matricies may be a possible candidate here for a start).
I have not got the time right now to work through expressions such as in the examples, but I assure that it is at least somewhat interesting to play around with if one finds this interesting: at least, it was for me.

And shall I then open an issue to cover examples 2 & 3?
I initially thought that for exprs. such as (2) (b * 2 * 2 * 2), the issue was only present for constants; but also, expressions such as 2 * v * v * 3 * v * v do not simplify to the expected 2 * v^2 * 3 * v^2. Provided that associativity holds, this should also simplify too?

[gwhitney]

I think some of your confusion may stem from the fact that currently simplification considers whether commuting operands is allowed to be an all-or-nothing affair: if the context says multiplication is not commutative, then it will not change b*2 to 2b, even if multiplication of whatever sort of thing "b" might be by a real scalar value would commute. That's because currently mathjs does not track the mathematical "type" of each node in an expression, so it does not distinguish that some nodes might represent real scalars and others complex matrices, for example. Ideally (and possibly it might in some future world) mathjs would know that scalars times matrices commutes but matrix times matrix does not, etc. In the meantime there is just the one global "switch" in the context to allow or not allow any/all simplifications that require swapping the operands of * (and note that 2b is semantically identical to (2*b), so there is a * in there, too).

In any case, though, not being able to simplify b*2*2*2 to b*8 when commutativity is off, and similarly with b*b*b -> b^3 or 2*v*v -> 2*v^2 is a shortcoming of the current simplify (I will stop short of saying it is a "bug" because it's well known that "ideal simplification" is a computationally difficult task, so we will never get it perfect, and in some cases it's not clear what the "simplest" form of an expression is). So do feel free to file an issue with these cases -- but I can't promise prompt attention to the issue.

[samueltlg]

Yes, I think that a significant amount of confusion has arisen from the reason that you have given there. Indeed it can be a little confounding mathematically the encounter b *b being able to be simplified to b^2 whilst 2b*2 or similar exprs. do not (simplify futher); considering that the operation is occurring with a scalar as an operand (you have put it succinctly).

And for sure, I was reluctant to describe the latter issues as 'bugs', but remained in doing so due to my limited vocabulary in terms of categorising them there.

And thank you; for me, it is currently a somewhat significant issue. Would a pull-request be welcomed If I can get round to it? I understand that addressing these 'limitations' is not a simple matter, and again from spending ample time debugging through the simplify function, it looks as if at least some architectural changes or at minimum additions would be required for a fix. I appreciate the current work/source-code already, and do not as such seek to disturb and modify it.
(It seems to me that, as I have touched upon already, that a way of addressing exprs. including 2*v*v -> 2*v^2 (in the case of either non-commutative addition or multiplication) would be to firstly add a subsequent top-level simpify-loop where the supplied node is flattened<->unflattened to a right-heavy tree, and then within this loop and for 'standard'-rule application, do not flatten the tree prior to each attempted rule-match (applyRule), or otherwise simultaneously attribute non-associativity to these non-commutative ops also. I prophesize that this flattening should not occur, because it appears as if rules (specifically, expanded) have difficulty applying for flattened operations in the absence of commutativity: it looks as if currently, rule v*v->v^2 will not apply to 2*v*v (via the expanded rule form) due to these expanded rules not being able to match/detect adjacent non-placeholder (v/n/c node) matches; hence why a rule such as this does not apply when it appears that it should. Consequently the suggestion of a right-heavy non-flattened tree has come into play. Alternatively, perhaps the (expanded) rule-match procedure could be adjusted to (better) find matches in a non-commutative context?) Best.

[gwhitney]

Well, the first order of business is to have a focused issue report to work against, with all of the cases that you've uncovered where we agree there really is a problem. And note that (as I just verified) simplifyConstant does not collapse the constants in b*2*2 in a context in which multiply is not commutative. I would go so far as to say that is an outright bug.

As for resolving the issue once it is filed, well of course nobody ever minds a PR! However, simplify depends so heavily on simplifyConstant that I personally believe the resolution will need to begin there, and I doubt right-unflattening will be the answer inside simplifyConstant, as how would that help with something like b*c*2*2*2*c*b where the constants that need to be collapsed are "hidden" both from the left and right? (Maybe list such an example in your issue report.) Thanks. We will make progress on this one way or another, although I can't promise how rapid it will be.

[samueltlg]

Thank you Glen. I have opened and formalised the issue, which is hopefully adequate.