[Speed Optimization] Evaluating user-defined expressions at runtime

[exception]

Greetings.
In a program the user may provide strings which contain arithmetic expressions which may include variables of the program and boolean expression whose atoms may include relations between arithmetic expressions. For example:

(e0[a0] * N(0,1) < U(0,1) * e1[a1]) || e[0][a1]

This expression would evaluate to "true" iff the attribute "a0" of element "e0" times a normally-distributed random variable with expectation value 0 and variance 1 is less than ... (I think you've got the idea...). Note that the type of e[0][a1] is "bool", whereas the rest are "double"s.

Now my profiler tells me that I want to improve my solution (in terms of speed), which uses Flex++ and Bison. (I need more than one parser and lexer, which didn't work with plain flex&bison due to name resolution problems, thus the C++ version which encapsulates them into namespaces).

I was now thinking that I could pre-compile the experssions (each is evaluated quite often, given that the variables have changed in the meantime or a random variable is included in the expression, this obviously cannot be optimized).

Questions:
(a) Do you have any suggestions on alternatives?
(b) Is there a readily-available solution I've overlooked?
(c) If you decided to pre-compile them, how would you do it? (I am still seeking a solution which does the user not require to have a (C++) compiler or, for that matter, anything not shipped with the software...)

Any thoughts would be appreciated.

[Zaita]

This is an interesting topic. Something I have discussed with a scientist at work in a fair bit of detail.

What you really need is a lazy-evaluating library of types. Then you can build up the equation at runtime and every-time you evaluate it the answer will be generated without having to re-interpret the expression.

I am not familiar with any currently existing lazy-evaluating math libraries. I have looked at developing my own, but am waiting for work to fund a project for it :)

[exception]

Thanks. Lazy evaluation is something I was always... to lazy to implement (although I have used lazy adaptive evaluation for simple robust geometric computations which was quite fun. So if you get these funds...)

For now, I think that I will precompile it. Since it is a science project anyways, the usability details can be... neglected.

[Zaita]

Sounds like the way to go. I'm quite keen to build a lazy-evaluating math library but I need to find some time outside of work, or project funding at work. I tend to avoid coding when I am not at work, so the latter is a better option.

[exception]

Hm, what would be the requirements for such a library that you could use it? I might have an idea how I could perhaps... persuade a prof to make this a research project. It seems interesting enough. (This would then be most likely a part of CGAL, the "Computational Geometry Algorithms Library". The prof in question has already participated e.g. in the original Number Type implementation/documentation. cf. http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/contents.html#part_III
However, everything in this library is generic, so it would be usable outside of CGAL as well.)
So, from how I see it at the moment, this would most likely another Number Type, which similarly to LEDA::REAL (which does lazy adaptive evaluation for real algebraic numbers over Q, as far as I know, however only for exact arithmetic, not for speed issues) does the work transparently.