How to implement lazy evaluation of if()

Question

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().

Answer 1

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.

Answer 2

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.

Answer 3

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.