Parse/evaluate expressions which are dependent on each other

[Rex90]

I'm not sure if I'm missing something here but is there a way to compile a set of expressions into a dependency tree?

Eg provide expressions

Y = 1 + X
X = 1/Z
Z = 5

Is there a way to eval these 3 expressions in the correct order such that mathjs doesnt complain about missing variables in the scope?

Thanks
Armen

[FSMaxB]

There is no builtin way to do that.

You would have to parse all statements into an expression tree with math.parse(...) and then manually find all the SymbolNodes and AssignmentNodes to figure out the dependencies.

[Rex90]

Sounds like a good feature for a plugin :) will work on this if i find the time

[josdejong]

Sounds like a good feature for a plugin

Well, we recently introduced algebra functions simplify and derivative and have plans for integral. One other important function that we would like to support is solve. Sounds like that's what you need here, like solve([Y = 1 + X, X = 1/Z, Z = 5]) :D

[Rex90]

Yup - ideally you can define an expression environment and The depdency tree can be built e.g.

var env = math.parser()
env.addExpression('x=1+y')
env.addExpression('y=z/2')
env.solve(scope)

Or something like that :)

[caseygrun]

Hey, I've actually implemented this idea and I'm interested in suggestions for the API. My idea was actually to implement a spreadsheet-like functional program using Math.js—multiple statements could be incorporated into a document and would be evaluated in order of dependency. The approach is as @Rex90 described—first a dependency graph is built, then the graph is evaluated starting from the leaves.

My API is really simple right now:

evalSystem(['x = 2 y', 'y = z', 'z = 4']) // = {0: '8', 1: '4', 2: '4' }

or arbitrary keys can be assigned:

evalSystem({'A1': 'x = 2 y', 'B2': 'y = z', 'C3': 'z = 4'}) // = {'A1': '8', 'B2': '4', 'C3': '4' }

(There's a helper function and some small classes which build the dependency graph)

So my questions are:

• Would this be something appropriate for a pull request to Math.js, or better as a standalone plugin?
• Would it be helpful to keep track of everything in a Parser (or something similar), as @Rex90 has suggested?

(The algorithm I used is borrowed from the Python-based spreadsheet Dirigible, specifically here and here)

[Rex90]

Nice one @caseygrun. I think it would be helpful to have it set up in such a way that the variables can be passed in without having to redefine the formulas; i.e. A scope that can be updated independently. I have implemented something like this myself as well using a js dependency graph library next to Mathjs. I haven't posted it because not well written :)

[josdejong]

@caseygrun that sounds really promising! Yes we definitely want to have a solver in math.js. Is the algorithm you use only suitable for a structure like variable = expr, or can it also solve arbitrary equations like evalSystem('2x + 4 = 5x - 2')?

About your API: shouldn't the first example with an Array as input return an array as output?
I think the API with an object as input is nice and has value, it makes it much easier in an application like your spreadsheet to map results back to specific fields on the screen or somewhere else (it keeps the expressions unordered and bound to an id).

[caseygrun]

It's only suitable for variable = expr or function(params) = expr. (I'm working on extending it to support AccessorNodes, but I'm still thinking about the best way to implement this). The structure right now is basically to consider the symbols to be labels on directed edges between a graph of statements. To figure out how two statements are related, you just look at which symbol(s) are defined on the LHS and which symbol(s) are accessed on the RHS. For example:

x = 2 y # statement (1)
y = 5 # statement (2)
x # statement (3)

Statement (1)'s RHS includes y which is in the LHS of statement 2, so (2) depends on (1). Statement (3) depends on 1 because 3's RHS contains x (I consider (3) to have no LHS since it doesn't define any symbols). This doesn't tell you how the statements are related, just in what order you need to evaluate statements.

The solve function you're describing, which definitely sounds useful, would probably be better implemented through elementary algebraic manipulation, as is done in algebra.js and/or through a pattern-matching approach as you've done in simplify. I was thinking how it may be useful to expose some of the internals of simplify, which could be used to build other helpful CAS-type functions like expand, factor, etc. (see e.g. the functions for formula manipulation from Mathematica). This could be the foundation for an algebraic solve. Once the architecture is in place to manipulate an equation into a recognizable algebraic form, it would be straightforward to tack on linear, polynomial, etc. equation solving using tools you've already built for matrices. What do you think?

re: API/arrays as output: Sure, I consider arrays and objects the same right now, it's just that the "keys" of an array are the indices. I'm more wondering 1) whether it makes sense to expose the whole thing as a separate plugin (or as part of the core library), and 2) if it would be better as a single function or as a sort of stageful object like @Rex90 describes. I like the idea of a stateful object, particularly for the spreadsheet-type application, because it would be nice to keep the dependency graph around if I could update it piecemeal as expressions are rewritten (rather than having to rebuild the whole thing).

[josdejong]

Thanks for your explanation. So if I understand it your current solution is sort of a "variable resolver", and indeed not an algebraic solver. For math.js I would indeed like to see an algebraic solver, which can also take a set of expressions into account like in your solution. This solve function can probably reuse some internals of simplify. Just let me know if you're interested in creating this algebraic solver :).

1. I think if we would integrate evalSystem with it's current functionality into mathjs would only do a small part of what I would like it to do (and that probably confuse/disappoint users). So in this state I think it's best to publish your solution as a separate library. As soon as it's super-powered by an algebraic solver we can integrate it in math.js under the name solve. That would be awesome.
2. In order to have this function efficiently with larger spreadsheets it's necessary to keep everything in memory and only update changed cells/expressions. It would be a fine solution to create something similar to Parser in mathjs, which keeps the state internally. I suppose you would get an API with methods to add/replace/remove/get individual expressions. It could be interesting to see if you can come up with a functional approach (inspired by React for example), which could be something like var state = evalSystem(newExpressions, prevState) so the evalSystem only has to update changes. Just thinking aloud.

[firepick1]

On a related note, I've run into a serious performance issue with derivative. My Javascript neural network framework relies heavily on derivative for gradient descent and mathjs is struggling with expression parse trees of 5,000 nodes (!). I've separately implemented an Optimizer that memoizes sub expressions. https://github.com/firepick/kinann/blob/master/src/Optimizer.js

Optimizer does actually tease out the dependencies of an expression and memoizes them for evaluation. I'm now actually contemplating writing a derivative method for Optimizer to see if I can get something to deal with my gnarly math expressions.

I've nothing to report just yet, but wanted to bubble this up as an FYI about the problem I'm trying to tackle in this problem space.

[josdejong]

Thanks @firepick1. I guess there is room for performance improvements in the parser. Do you have any concrete ideas from your experience? If so, we could discuss them in a separate topic, you can simply open a new topic "Improve performance of derivative".

[firepick1]

New thread posted. :)

I do have a hunch the dependency issue of this thread
and the performance issue have a common set of solutions.
The optimizer I wrote takes a huge expression and constructs
an ordered list of subexpression dependencies s that can be evaluated sequentially
when compiled. Although not a direct solution to the OP question,
I think that a dependency tree of common subexpressions is
required to improve performance as well. I am very curious to
see how all this works out as we work to tackle our respective issues.

[josdejong]

Related: #907

[rmickus]

I've run into a similar issue. Here's the post I made:

I have an application where certain equations rely on other equations. The ordering of the dependencies of equations is not known at run time. So I would like to be able to use a scope to recursively evaluate each expression without throwing errors. Right now I can't seem to figure this out and was curious if this feature is possible.

For example, If I have in my scope:

let scope = { a: "4 + 3", b: "a + 3" }

And I want to evaluate the value of b like:

math.parse("b").compile().evaluate(scope)

I expect to see the value 10, but instead I get:

a + 3

Okay, not a huge deal. I can just run a while loop that stops when I see a number. But If I evaluate 'a + 3' in the same manor, I get the following error:

Uncaught Error: Cannot convert "4 + 3" to a number

So again, to reiterate my question, is it possible to recursively evaluate expressions within the MathJS library? If so, please point out my mistake, and if not, perhaps this might be a feature to consider?

[josdejong]

👍 thanks for sharing here.