Add option to apply a rule multiple times if the input pattern is matched multiple times

[kevinbarabash]

e.g. PRODUCT_RULE should be able to handle this case:

10^2 * 10^3 * x^a * x^b --> 10^(2 + 3) * x^(a + b)

[aliang8]

I believe mathstep already handles this. mathsteps does a TreeSearch (post and preorder depending on the simplification type) to apply a rule if it is matched more than once.

https://github.com/socraticorg/mathsteps/blob/master/lib/TreeSearch.js

[kevinbarabash]

If I'm understanding things correctly, once search returns a childNodeStatus where hasChanged() returns true, it propagates that change up without running simplificationFunction on any other nodes. There were a couple of rules in recent PRs that included code to apply a helper rule to multiple nodes within a sub-tree. It would be nice to abstract this out into a function so that we don't have to write similar code to do the same kind of work in multiple rules.

[aliang8]

Sorry, Kevin. I'm not quite following your train of thought there. But I can provide you with a better explanation of TreeSearch. Basically, given any expression/ast, say x^0 + x^0 + 3, TreeSearch will go through our list of simplification functions in the order that we listed them. In this particular example, it will attempt to apply all the rules on each part of the ast until there is a change (x^0, x^0, 3, x^0 + 3, x^0 + x^0 + 3). Once it reaches, REDUCE_ZERO_EXPONENT, a nodeStatus object is returned and we repeat the process again. REDUCE_ZERO_EXPONENT is then matched once more on x^0 + 3. In this manner, the same rule can be applied more than once if it it is matched multiple times on the input pattern.

I'm not sure which PRs you are referencing. Maybe you could elaborate a little more.

[kevinbarabash]

In #34 we apply the ADD_EXPONENT_OF_ONE_HELPER multiple times within ADD_EXPONENT_OF_ONE.

I'll have to step through the search function in https://github.com/socraticorg/mathsteps/blob/master/lib/TreeSearch.js to be sure, but it looks like as soon as https://github.com/socraticorg/mathsteps/blob/master/lib/TreeSearch.js#L45-L47 returns a node status that has changed, then we return before running https://github.com/socraticorg/mathsteps/blob/master/lib/TreeSearch.js#L60-L62.

[kevinbarabash]

Even though TreeSearch.js checks each search function in the list, it only applies one of them and only applies it once (afaict).

[aliang8]

@evykassirer may provide better insight than I can in terms of the functionality of TreeSearch and whether it does what we want it to

[evykassirer]

Yeah pretty sure that's true

What do you want math-rules to do though? Match a certain instance of a rule? Match every instance of it throughout the whole tree?

From my understanding, it was a single instance matcher, and a tool that could be used to see if a particular tree (at the top level) matched a rule. One you get deeper, you'll be wanting to return tree positions and stuff so whoever's using math-rules knows where all the rule matchings are (not sure if you were already planning on doing that)

For mathsteps, I'd rather use a single rule matcher, but if you want to add the option in math-rules I won't argue against it haha. I'm hoping to read through how all this stuff works in the next month or two so I can understand how the pieces fit together and and help work on it!

[tkosan]

A conventional CAS like MathPiper is designed to keep applying rules to an expression until the expression stops changing. These rule applications are not recorded, so a conventional CAS is not useful for step-by-step equation solving. The first thing I did when I started to give MathPiper step-by-step capabilities is to create a procedure that returned all the tree positions which matched a given pattern without applying any rules:

In> PositionsPattern('(2 + (b*c) / b - 3*d + e*f), q_*r_)
Result: ["2","1,2","1,1,2,1"]

The step-by-step code then inspects the subtrees that are at these positions to determine if a rule should be applied to them.

However, it is sometimes also useful to apply a rule using traditional CAS mode if the rule applications don't need to be recorded. For example, the following rule replaces all unary minus operators that have numbers as operands with multiplication:

equation := (equation /: [- q_Number? <- SubtractN(0,1) * q]);

I like the idea of having math-rules provide the option to apply a rule multiple times because it gives it useful conventional CAS capabilities in addition to its step-by-step capabilities.

[aliang8]

Thanks for the input guys :D Glad to get multiple perspectives on this.

[kevinbarabash]

I've create a new issue to return the paths of the nodes being modified in the input and output ASTs, see #40.