Execution of the AST

Now that the parser is finished, I worked on the AST execution. The simplest (and quite certainly not the smartest or most optimized) way to do it is simply have a "Execute" function on each of your statement nodes. For example our "2", "+", "1" tree would have the "+" on top, and if I call the Execute function it will then check the 2 children of the node and execute them as well. As in this case the children are static numbers they would simply return the value and my main node would then sum the 2 values.

The same concept works for much more complex trees with function calls, variables or  whatever you can put inside your AST.

But what if you want to execute multiple "statements" like lines of code? Well simply you have an array of statements and you go through it from first to last.

For a procedural language (as it is in our case) we have a first "pass" of execution which will store the functions in the "known function list" and then when needed run them.

Variable scopes can is another issue to deal with when you develop a language. A variable defined in a block (like in a function) should not be accessible outside of the block. A simple way to implement it is to have an "execution environment" which contains all the variables in the scope, and once you enter a new scope you change your "execution environment".

All this is good, but what if we would like to gain speed? Multiple ways are open to optimize your script execution (only a few here but you may find many many more):

1. AST optimization which basically tries to simplify your AST for example to pre-calculate constant operations. If you write "2+3*2" it doesn't make sense to run the whole tree all the time and could be replaced with the same value: "8".
2. Loop unfolding: from a for loop, transform it to multiple lines of code, which would avoid to run checks and more which simply cost time.
3. Dead code removal: remove nodes which cannot be called
4. JIT like operations: you may transform your AST into something faster, in my example, transform my AST directly into Javascript and eval it having then the speed of Javascript and not the overhead of my AST on top.

All those can be done one after the other such to gain each time more speed. Of course the old statement that optimization tends to make the code harder to read is always true: if you implement AST optimization and JIT you will make your parser a lot more complex and harder to debug. So be sure it's really needed before entering this road.