Use fraction numbers to avoid rounding (wip)

kevinbarabash commented 7 years ago

My first attempt to address https://github.com/socraticorg/mathsteps/issues/64.

Output from test.js to solve x - 3.4 = ( x - 2.5)/( 1.3):

x - 3.4 = 0.(769230)x - 1.(923076)
(x - 3.4) - 0.(769230)x = (0.(769230)x - 1.(923076)) - 0.(769230)x
0.(230769)x - 3.4 = (0.(769230)x - 1.(923076)) - 0.(769230)x
0.(230769)x - 3.4 = -1.(923076)
(0.(230769)x - 3.4) + 3.4 = -1.(923076) + 3.4
0.(230769)x = -1.(923076) + 3.4
0.(230769)x = 1.4(769230)
(0.(230769)x) / 0.(230769) = 1.4(769230)/0.(230769)
x = 1.4(769230)/0.(230769)
x = 6.4

The numbers in extra brackets represent the repeating section of the decimal. There's still lots to do, but this gives me confidence that it's doable.

evykassirer commented 7 years ago

I'll take a look early this week - today I've been a bit sick and now am finishing up some homework ^_^

thanks for working on this - soo cool!

kevinbarabash commented 7 years ago

TODO:

[ ] add Options param
[ ] make sure test suite is passing
[ ] fix division bug in lib/simplifyExpression/arithmeticSearch/index.js
[ ] update _toTex method to display repeated part of decimal with \overline
[ ] verify that (de)serialization of math.js data structures still work

I was thinking about repeat bar vs. ellipses and ellipses makes more sense when truncating output of irrational numbers.

kevinbarabash commented 7 years ago

I tried to make some more progress here, but the back-and-forth conversions to strings by ContentNode is really getting me down. Some fractions result have really long repeaters, 600/791 has a repeater that's over 100 characters long. It would be much better if we could keep everything a fraction object (or a complex object) all the time and just call methods on those objects.

Unfortunately, mathjs likes to convert everything to a string and then convert it back to object during eval. Before eval happens it calls _compile on each node which converts it to a different string depending on the number config (BigNumber vs Fraction).

I'd like to make a suggestion: replace mathjs. The main parts of mathjs that I see we're using are the parser and the eval code. Both of these are relatively easy to replace considering most of the heavy lifting for evaluation would be done by fraction.js anyways.

Benefits:

more easily change which numbers we're computing with, e.g. fractions, complex numbers
have a more regular AST, right now we have EquationNode but we're bound to add more as we go
avoid re-parsing things over and over
have a parser that produces a flattened tree by design
smaller bundle size

evykassirer commented 7 years ago

I agree the string thing is pretty annoying, and makes more messy code around the codebase (would some helper functions make it a bit less gross?)

In general I think your suggestion is quite reasonable - having something more custom to our project would be really nice. The one thing is that we've been building a relationship with mathjs, and they mention our project on their website. Their community is pretty big and pretty cool, and it'd be nice to keep that relationship with them. Not sure how to balance that with the benefits of creating our own custom parser.

Thoughts?

evykassirer commented 7 years ago

cc @aelnaiem

aelnaiem commented 7 years ago

Good point and insight into how we use mathjs. Do you have an alternative parser in mind or would would we need to create one first?

kevinbarabash commented 7 years ago

I have a parser that I'd written a while ago for creating a flattened math AST similar to what mathsteps uses. It was for a hackathon project to allow users to manipulate algebraic expressions/equations so that they could solve them step-by-step instead of just typing in the answer.

I've made some changes recently to bring the AST closer in line with what mathjs produces. It needs a little work, mainly tests. It doesn't cover everything that mathjs' parser does, but I think it covers everything we'd need for now except for absolute value. I'll add that shortly.

https://github.com/kevinbarabash/math-parser

kevinbarabash commented 7 years ago

I've added support for absolute value and inequalities to math-parser.

aelnaiem commented 7 years ago

That's really great Kevin! I think the parsing abstraction is pretty contained if I remember correctly, so it should be pretty straight-forward to swap the parser and see what breaks. We would also want to replace the eval? I particularly appreciate that your parser deals with equations. Very cool 😄

kevinbarabash commented 7 years ago

Handling eval is next on my list. I'd like to avoid building eval methods into the nodes though and would rather have a separate function that evaluates an AST.

aelnaiem commented 7 years ago

Agreed that makes the most sense. Let me know how I can help

kevinbarabash commented 7 years ago

I spent some time last night better specifying the AST that the parser should generate. It diverges in places from the current AST, but I think it sets us up to be able to cover more math in a more regular way. I'll add a function that converts the new AST to an AST that aligns better with mathsteps' current AST to make the transition easier.

Please have a look at https://github.com/kevinbarabash/math-parser/issues/12. I'd love to get your thoughts.

@aelnaiem I could use some help verifying that the AST (after conversion) matches what mathsteps is currently using as well as actually swapping out the parser and eval in mathsteps when they're ready. Also, if there's any other work that needs to be on the parser or eval function, please add it to https://github.com/kevinbarabash/math-parser/issues.

aelnaiem commented 7 years ago

Agreed about representing more math in a regular way, it's clear that it's covering a lot of the representations that would be useful for mathsteps at least, and for other uses in the future. I think divergence would make sense especially as we would want to support things like sequences and relations within a single structure.

I also love that the tree would be flattened by default. Curious how you think I can best help. I recently started adding a goals and priorities doc which aims to capture the kinds of improvements we want to make. A project around improving the parsing and eval in this way could be something we add there, particularly as it could be a pre-requisite to so many other improvements.

One other improvement that I'm excited about making in terms of architecture is re-visiting NodeStatus and EquationStatus and coming up with something simpler that is consistent to the different types of problems that we'll want to provide step-by-step assistance for. Overall, I'm excited about the opportunities this would present for making the mathsteps code simpler and less bug-prone.

My major concern is by not using mathjs, we would lose out on the improvements that community will make to their parser as well.

kevinbarabash commented 7 years ago

Curious how you think I can best help.

Swapping out mathjs' expression tree for math-parser's AST. I have a rough plan for how that might happen:

write a function to convert the math-parser AST to match mathjs' expression tree (depends on https://github.com/kevinbarabash/math-parser/issues/8)
verify that both match for all expressions that we care about, maybe write a function that traverse either nodes from either tree and produces an s-expression string which can be easily compared
update helper functions to handle either type of node
replace method calls to .eval(), with an evaluate function that can accept either node
swap out the parser

I appreciate any help in this process as I'm very familiar with the mathsteps code base.

A project around improving the parsing and eval in this way could be something we add there, particularly as it could be a pre-requisite to so many other improvements.

Sounds good to me.

re-visiting NodeStatus and EquationStatus and coming up with something simpler that is consistent

+1

My major concern is by not using mathjs, we would lose out on the improvements that community will make to their parser as well.

Even in the current state, there are things mathjs can parse that I think we'd eventually find useful. There is, however, a mismatch between the use cases. I think the benefits we get from the new AST outweigh the cost of evolving the parser to handle new syntax.

kevinbarabash commented 7 years ago

I made some progress last night converting the math-parser AST to something very similar to the mathjs expression tree. It doesn't have any of the methods like eval on the nodes though. Here's the output from https://github.com/kevinbarabash/math-parser/blob/f7975c81381da885d7105730410ed7f09c1d1a52/demo.js:

original :    --2
printed  :    --2
expr     :    0.5 + atan2(1, 1) + 2 * 3 - 4 / 5
result   :    6.4853981633974485

math-parser AST
{ type: 'Operation',
  op: '-',
  args: [ { type: 'Number', value: '-2' } ] }

mathjs expression tree
{ type: 'OperatorNode',
  op: '-',
  fn: 'unaryMinus',
  args: [ { type: 'ConstantNode', value: '-2', valueType: 'number' } ] }

transformed math-parser AST with unary minuses applied to number nodes
{ type: 'Number', value: 2 }

The demo also shows that other transforms are possible on the AST by applying an Operation node with a unary minus to the Number node containing '-2'.

Sorry about the messiness of demo.js. I'll try to get some tests up over the next couple of days.

aelnaiem commented 7 years ago

Let's create a new issue for supporting this parser so others can track progress and we can organize what's needed for testing out the requirements.

evykassirer commented 7 years ago

done, #128

google / mathsteps

Use fraction numbers to avoid rounding (wip) #89