Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

share|improve this question

3 Answers 3

up vote 9 down vote accepted

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.

share|improve this answer
    
I'm not sure, but should "closure" be "thunk"? Hmm, maybe not; just looked at the wikipedia page: "a thunk is a parameterless closure". –  user39685 Mar 14 '13 at 16:44
    
When you say "call by name" are you referring to globally? Alternatively to global call-by-name is just implementing a closure type, then the if function just takes 3 closures and evaluates two (condition and then or else), but not everything need be recognized as a closure such as full call-by-name semantics –  Jimmy Hoffa Mar 14 '13 at 16:46
    
@Matt: The term "thunk" can mean several other things in the context of programming, and "parameterless closure" is not the first one I think of when I hear it. "Closure" is a lot more unambiguous. –  Mason Wheeler Mar 14 '13 at 16:46
1  
@JimmyHoffa: When I say "call by name", I'm referring to a specific style of setting up a function argument, which should be optional. Much like many existing languages will allow you to choose to pass a parameter by-value or by-reference, for this scenario you need the choice to pass by-name. –  Mason Wheeler Mar 14 '13 at 16:50
    
While your suggestion about "call by name" semantics shown me some interesting points, it is a bit overkill for my evaluator that is not a complete compiler, as my function calls are single-line (think about MS-excel formulas). I am thinking I could add a step after the queuing of tokens by doing a pseudo-evaluation of the stack to deduce the calling tree. It should be easier to know from the tree the branches to discard. –  Seki Mar 14 '13 at 17:38

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.