Efficiently calculating expressions at run-time

[Ganado]

In my code, I have something like this

//assign Z
for (int i = 0; i < Iterations; i++)
{
   Z = Z * Z + C; // Your classic fractal
   //test for divergence of Z
}

This works fine, but I wanted to expand the potential of all the different things that could be done inside that for loop. What I've been working on is trying to move expressions like these to a file that would be read at run-time.

So for example, the contents of the file would be
Z = Z * Z + C

I worked on a "parser" for this type of equation, implementing the algorithm suggested here http://stackoverflow.com/a/47717 using a stack.
Basically my hypothetical code now looks like this:

//for each pixel:
for (int i = 0; i < Iterations; i++)
    Z = evaluate_file_expression(Z, C) 

...where the evaluate function would have to re-do all the pops and pushes each time, for each iteration... for each pixel.
Is there any way to do the equivalent of the above code without having to re-parse the equation each time? I hope that makes sense, it probably doesn't.

As an aside,
It'd be amazing to see the inner-workings of something like Mathematica, where one can do f[x_,y_] = x^2 + 2 y
and then evaluate f[2, 3] on the fly. Although now that I've typed this, the more I doubt there is a way to not have to re-parse the expression each time and do all the pops and pushes.
Perhaps I should also make data to quantify just how much slower
Z = evaluate_file_expression(Z, C);
is from
Z = Z * Z + C;

[JLBorges]

> Is there any way to do the equivalent of the above code without having to re-parse the equation each time?

Parse the file once and create an AST object which can then be reused.
The interpreter design pattern would be relevant.
https://en.wikipedia.org/wiki/Interpreter_pattern

[Ganado]

Thank you for the reply.
So with this, I would only use the original algorithm (the shunting yard) once, and then this object created could be reused more efficiently? Still reading up on the abstract syntax tree and the interpreter pattern you have linked, I will bump or make a new threads if I have questions on those, much appreciated.

[JLBorges]

For this, I would favour a Pratt parser over one using the shunting yard algorithm.
http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/

[Ganado]

Guess I'm still having a hard time wrapping my head around this.

Do I have this correct:
The Pratt parser or the shunting yard would be run only once at the start when the equation file is first loaded, and then this would be turned into an intermediate "abstract syntax tree"? Then, the program would have to traverse the abstract syntax tree with the current values of Z and C every single iteration to evaluate an answer?

I was doing some more searching and found this question on SO
http://stackoverflow.com/questions/6713983/custom-interpreter-for-mathematical-expressions
which actually seems quite similar to what I was trying to, I think.

So basically, I'm going to have >10x slower calculation speeds if I try to load an expression from a file as opposed to hardcoding Z= Z^2 + C in a particular function, no matter how good the code is? Seems a bit sad, especially when every pixel calculation counts when making a high-resolution image.

[JLBorges]

no matter how good the code is, it will certainly be slower. But Z= Z^2 + C won't be >10x slower.

The expression Z= Z^2 + C can be entirely inlined by the compiler if it is in the source code; the tree-walking is done at compile-time. For an AST which is known only at runtime, the the tree-walking has to be done at run-time; at least once if there is a jitter (like the one found in the CLR), and for each evaluation if the code is not just-in-time compiled.

With the kind of implementation that we are talking about, the AST Z= Z^2 + C,

                            +
                            
                            |
                            |
                    __________________        
                    |                |
                    |                | 
                                     
                    *                C 
                    
                    |
                    |
            __________________       
            |                |
            |                |
            
            Z                Ze

would require as extra either five function calls or more than a dozen extra stack operations.

[Ganado]

Hi, just wanted to let you know I finally got around implementing my first version of this. Thanks for deciphering my questions.

given equation_test1.txt
Z * C

#elif FRACTAL_MAIN == 3
#include "EquationTree.hpp"
int main(int argc, char* argv[])
{
    using namespace std;
    EquationTree<int> tree("equation_test1.txt");
    tree.set("C", 5);
    tree.set("Z", 11);
    cout << "Result = " << tree.result() << endl;
}

It correctly displays 55. Gonna bug test with bigger equations and complex numbers, next.

Basically I created an "expression tree" at the beginning, structured like the picture in your last post.
It contains nodes for the operations and leaves.
My set function sets an unordered_map of the variable name to its value,
and my result function traverses the tree, doing each operation between nodes as it goes.

I think I understand now that it is not possible to bypass the traversal of the tree each iteration, but once I get my program done I will test to see just how much slower it is than hardcoding Z = Z*Z + C or similar, more complex expressions. Hopefully it won't be disastrously slower.


Guess I should re-name the class to ExpressionTree but that's not important ;p