I am currently implementing an expression evaluator (single line expressions, like formulas) based on the following:
- the entered expression is tokenized to separate literal booleans, integers, decimals, strings, functions, identifiers (variables)
- I implemented the Shunting-yard algorithm (lightly modified to handle functions with variable number of arguments) to get rid of parenthesis and order the operators with a decent precedence in a postfixed order
- my shunting-yard simply produces a (simulated) queue of tokens (by means of an array, my Powerbuilder Classic language can define objects, but only have dynamic arrays as native storage – not true list, no dictionary) that I evaluate sequentially with a simple stack machine
My evaluator is working nicely, but I am still missing an if() and I am wondering how to proceed.
With my shunting-yard postfixed and stack based evaluation, if I add if() as another function with a true and false parts, a single if(true, msgbox("ok"), msgbox("not ok")) will show both messages while I would like to show only one. This is because when I need to evaluate a function, all of its arguments has already been evaluated and placed on the stack.
Could you give me some way to implement if() in a lazy way?
I though about processing these as a kind of macro, but at early time I have not yet the condition evaluation. Perhaps that I need to use an other kind of structure than a queue to keep separately the condition and the true / false expressions? For now the expression is parsed before evaluation, but I also plan to store the intermediate representation as kind of precompiled expression for future evaluation.
Edit: after some though on the problem, I think I could build a tree representation of my expression (an AST instead of a linear token stream), from which I could easily ignore one or another branch of my if().
0
There are two options here.
1) Don’t implement if as a function. Make it a language feature with special semantics. Easy to do, but less “pure” if you want everything to be a function.
2) Implement “call by name” semantics, which is much more complicated, but allows compiler magic to take care of the lazy evaluation problem while keeping if as a function instead of a language element. It goes like this:
if is a function that takes two parameters, both of which are declared as “by name”. When the compiler sees that it’s passing something to a by-name parameter, it changes the code to be generated. Instead of evaluating the expression and passing the value, it creates a closure that evaluates the expression, and passes that instead. And when invoking a by-name parameter inside the function, the compiler generates code to evaluate the closure.
8
Rather than the function having the signature:
object if(bool, object, object)
Give it the signature:
object if(bool, object function(), object function())
Then your if function will call the appropriate function based on the condition, only evaluating one of them.
It is quite easy, if you compile everything lazily. You must have some means to see if a value is already evaluated, or if it needs more evlauation.
Then you can do the following: If it is a literal or variable (do you have those?, i.e. names of functions?), push it on the stack. If it is an application of a function, compile it separately, and push the entry point on the stack.
Execution of a program is, then, merely looping until the top of the stack is evaluated and not a function. If it is not evaluated or a function, call the code the top of the stack points to.