Support for non-flattened trees

[tkosan]

Continuing a discussion started in math-parser #12. One use case is to show computation order. Another use case is to teach how elementary algebra works in a way that is more directly linked to the laws of elementary algebra. Algorithms such as "Combine Like Terms" are useful for simplifying expressions using pencil and paper. However, they sacrifice mathematical detail for speed. I would like the option to also teach these sacrificed details because in the long term they are more important than being able to simplify quickly on paper.

[k4b7]

I'm interested in being able to describe what's going in terms of axioms and rule built on top of them. It think flattened trees are well suited to this b/c it's easier to describe the rules and apply the transforms.

I wrote a tool a while ago using flattened trees that allowed users to select parts of expressions and equations and perform transforms based on axiom (and related rules) called algebra-tool. I found that manipulating flattened trees was much easier than binary trees.

From the Operation section in spec.md:

Even though addition is a binary operation, expressions such as 1 + 2 + 3 should be parsed as a single n-ary addition operation. This is so that there is only one valid AST for the same expression.

The reason for this restriction is that hope that math-ast can become an interchange format for different tools and I was worried that if tools had to worry about supporting binary trees as well would make it hard to adopt.

Maybe we can have another "module" (for lack of a better term) of the spec for binary trees and then tools can advertise whether they support the "core" module or the "binary" module. We could also have tools for transforming back and forth between flattened trees and binary trees.

What I mean by "module" here is similar to how W3C has HTML and CSS specs with separate modules such as CSS Fonts Module which specifies all of the font stuff in CSS. I imagine that spec.md would become core.md and then we'd add a binary.md and maybe a geometry.md eventually to this repo.

[tkosan]

Just having tools for transforming back and forth between flattened trees and binary trees should be adequate for my use case.

I think we have similar math-related educational interests because I am also interested in describing how math works in terms of axioms and the rules that are produced from them (both at the object-level and at the meta-level). However, the following object-level axioms from the theory of elementary algebra each produce two rules (one rule is produced by reading the axiom left-to-right, and the other rule is produced by reading the axiom right-to-left. Each rule is useful because of the syntactic effect it produces at the object-level.):

Variables that end with an underscore match any subtree. 

The <- operator replaces any subtree in the original expression 
that matches the pattern in its left operand with the evaluated 
form of its right operand.

For every q, r, s ∈ ℝ

Axiom: q + r = r + q
Rule1: q_ + r_ <- r + q
Rule2: r_ + q_ <- q + r

Axiom: q + (r + s) = (q + r) + s
Rule1: q_ + (r_ + s_) = (q + r) + s
Rule2: (q_ + r_) + s_ <- q + (r + s)

Axiom: q*r = r*q
Rule1: q_*r_ = r*q
Rule2: r_*q_ <- q*r

Axiom: q*(r*s) = (q*r)*s
Rule1: q_*(r_*s_) = (q*r)*s
Rule2: (q_*r_)*s_ <- q*(r*s)

Axiom: q*(r + s) = q*r + q*s
Rule1: q_*(r_ + s_) = q*r + q*s
Rule2: q_*r_ + q_*s_ <- q*(r + s)

Axiom: (r + s)*q = r*q + s*q
Rule1: (r_ + s_)*q_ = r*q + s*q
Rule2: r_*q_ + s_*q_ <- (r + s)*q

How does one teach these object-level axioms and rules without using binary trees? Manipulating flattened trees is indeed easier than manipulating binary trees. However, if the goal is to solve math problems easily instead of achieving deep mathematical understanding, the easiest way I can think of is to just use a conventional CAS to solve the problems.

Also, I don't know if it is possible to teach the axioms and rules of the meta-theory of elementary algebra without using binary trees. I am hoping mathsteps will be helpful for determining this.

Your algebra-tool is great! I immediately saw ways to enhance it to support the approach to teaching math I have in mind.

[k4b7]

Axiom: q + r = r + q
Rule1: q_ + r_ <- r + q
Rule2: r_ + q_ <- q + r

Rule1 and Rule2 seem to be the same to me. They both swap operands. The double linked list I used in algebra-tool made commutating operands really easy because each + was a node in the list too. You just had a find the + you want to swap operands on and then do some pointer manipulation. This draft spec only has a single 'add' so specifying what to swap is a little more difficult because now we have to specify two adjacent indices, e.g.

swap(( add p q r s ), 1, 2) => ( add p r q s )  // same for 'mul'

Associative property is definitely needs a binary tree structure. math-parser already produces appropriate trees:

parse("q + (r + s)") => ( add q ( add r s ) )
parse("q * (r * s)") => ( mul q ( mul r s ) )

Although the draft spec makes the following statement:

Even though addition is a binary operation, expressions such as 1 + 2 + 3 should be parsed as a single n-ary addition operation. This is so that there is only one valid AST for the same expression.

The AST supports binary use cases and in this case math-parser implements behavior that's useful for this use case. Does this meet your needs?

Your algebra-tool is great! I immediately saw ways to enhance it to support the approach to teaching math I have in mind.

Thanks. I'm curious what enhancements you think would be useful.

[tkosan]

You got me on the redundant commutative rules, I overlooked those :-)

I'm curious what enhancements you think would be useful.

The initial enhancement I have in mind it to add an interactive tree to the application similar to what is shown in the following research paper:

Structure in Algebra

This research indicates that the first thing students should be taught about algebra is that expressions have structure, and binary trees work well for this purpose. Flattened trees may also work, but research would need to be done with them to determine this.

so specifying what to swap is a little more difficult because now we have to specify two adjacent indices, e.g.
swap(( add p q r s ), 1, 2) => ( add p r q s ) // same for 'mul'

I can see how to implement swap in a program, but if the goal is to teach students the rules of elementary algebra, how does swap enable them to do this since it hides the commutative rules of addition and multiplication in an algorithm?

The AST supports binary use cases and in this case math-parser implements behavior that's useful for this use case. Does this meet your needs?

Yes, it meets my needs. You can close this issue if you would like.

[k4b7]

if the goal is to teach students the rules of elementary algebra, how does swap enable them to do this since it hides the commutative rules of addition and multiplication in an algorithm?

The program can store additional information about the transformations that are being done and communicate that to the student in a way that will help them learn the concept. In this case we might store the step as commute q r and the following could be displayed to the student to communicate which rule was being used in the transform:

   p + q + r + s
= p + (q + r) + s    // associativity
= p + (r + q) + s    // substitution property and commutative property of addition
= p + r + q + s       // associativity

The way I look at the AST, is it only stores the state of the expression/equation at each step, but it doesn't really know about the what was done to move from step to another or even that this is a valid set of steps. That's a set of rules and logic that can be layered on top of the AST and maybe over time we'll develop common ways for communicating that as well.

Flattened trees may also work, but research would need to be done with them to determine this.

I'd be interested in reading that research if it was ever done. It would be interesting to compare the efficacy of teaching binary trees vs. flattened trees.