Recognizing Tail-recursive functions with Flex+Bison and convert code to an Iterative form

Question

I'm writing a calculator with an ability to accept new function definitions. Being aware of the need of newbies to try recursive functions such as Fibonacci, I would like my calculator to be able to recognize Tail-recursive functions with Flex + Bison and convert code to an Iterative form. I'm using Flex & Bison to do the job. If you have any hints or ideas, I welcome them warmly. Thanks!

EDIT:

Let's not worry about C or C++ output from Flex & Bison. Mainly I want an idea or a hint. Thanks.

Answer 1

As I suggested in my comment, this is not an issue at all for the lexer, and possibly only slightly so for the parser. If you have a function something like this:

func f( a ) 
    if ( a == 0 )  
       return a
    return f( a - 1 )

then for a typical C compiler it would be up to the optimiser/code generator to convert that recursive call to a loop. Of course, in an interpretive calculator, you can be much more flexible, but I'd suggest that it's still one of the last processes that should perform the tail call removal, not the first ones.

Answer 2

The advice I've always heard is: Don't implement tail recursion detection if you can instead implement tail call detection. A lot more methods end with a call to another method than a call to themselves.

If your call stack is not important to the end user/developer (ie, tail call elimination in Java would negate much of the value of the Stack Traces, unless handled very cleverly), then you should look at this route instead.

Answer 3

Suppose you have a function...

def func(args)
   #stuff
return func(otherargs)

then note that the AST will have something like return -> func -> otherargs, with some annotations about types and whatevers. When you walk it and note that there exists return F where F is the current function frame, you can transform that into PUSH ARGS, GOTO F, instead of fully forming the stack frame and so forth. You'll have to fiddle the return values yourself.

Also note this will be substantially harder if you want to walk-and-execute, instead of having a multipass system. My instinct suggests that walk-and-execute will require a lookahead.

And, no, I don't think bison will do this for you without chaining parsers. You are analyzing semantics in a context-sensitive fashion.