Improve Math Expression Parsing

[stardust66]

A long term optimization goal.

For reference, here's the pipeline for Desmos (from https://news.ycombinator.com/item?id=11369540):

For the tech crowd, I'll play the "what happens when you type a key on google.com?" game, only for Desmos:

1. Your keystroke is interpreted and typeset by the awesome, open source math typesetting library MathQuill: http://mathquill.com/
2. Mathquill notifies us that an expression has changed, and gives us a new LaTeX representation of it.
3. We send this new expression to a webworker, where we do all of our math processing. This lets us avoid blocking the UI thread, even if the user asks us to do something like a sum from one to a billion.
4. In the webworker, the expression LaTeX is parsed and analyzed for dependencies, variable assignments, and function definitions. We mark any other expressions that depend on symbols it exports as dirty, so that we can also reanalyze and replot them.
5. We compile the parsed expression (and any other expressions that need to be updated) to javascript by calling "new Function()" on a string representation. Since we need to evaluate these functions at thousands of points for plotting, we've found this to be much more efficient than an interpreter.
6. We plot all plottable functions (explicit functions of one variable, implicit functions of two variables, parametric equations, polar equations, inequalities, etc.), and analyze them for discontinuities and points of interest like minima, maxima, and zeros.
7. We send a representation of the plotted curves back from the webworker to the frontend, and they are plotted on the graph paper using the HTML5 canvas API.

[ChristopherChudzicki]

Cool find.

For reference, Math3D uses MathJS for parsing and compiling string representations of mathematical objects: http://mathjs.org/docs/expressions/parsing.html. A mathematical expression is parsed into a tree which can then be evaluated.

Actually, Math3D does a bit of pre-processing before passing the string to MathJS. The reason is to support functions like diff:

In Math3D
=========
f is a function
diff is a function 
diff(f) returns a new function, namely the derivative of f
diff(f)(t) means "derivative evaluated at point t"

but MathJS gets confused by diff(f)(t), thinking diff(f) and (t) are numbers that should be multiplied.

I suspect this MathJS approach is pretty slow compared to Desmos. However, we get all sorts of things for free like vectors and Matrices, which Desmos does not support (at the time of writing).