This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: proper tail recursion for gcc


John Vickers <John.Vickers@pace.co.uk> writes:

> Every argument frame written to the stack for a tail call
> has to start at the beginning of the argument frame of the caller:
> i.e. each tail caller in effect pops it's own arguments before pushing
> the tail callee's arguments.

Except if you use the typical C calling conventions, it is the caller
that is responsible for pushing the arguemnts (due to need for
handling varargs).  So if the called function also pops up the arguments,
you risk popping too much off, which could clobber the stack (if for
example signals are pushed on the same stack).

That is why a tail-call-elimination works so much better if you use
a calling convention where the callee pops the arguements.

> Otherwise tail recursion between two functions with different sized
> argument frames would use unbounded memory.

There is a risk of that.  Of course the stack would grow much faster
if you just did the recursive calls, but you can't guarantee that
slower that a long loop won't overflow the stack.

However, if you wanted to compile a langauge like Scheme, you could
use a convention where all Scheme procedures take the same number
of arguments (from the compiler's point of view) by using a list
argument.  If you restrict yourself to handling tail-call-elimination
where the caller and calle have the same parameter and return types
(which is all that is really needed for implementing Scheme) the
problem is a lot easier.

> > And even if it has been compiled with a frame pointer, there can
> > be a stack overflow if the call is done in a loop with many iterations.
> 
> What is this "loop" construct of which you speak ?

In Scheme, there is no "loop" primitive.  Instead, there are two standard
pieces of syntactic sugar that are defined in terms of tail recursion.
More generally, a loop is just a special case of tail recursion.
-- 
	--Per Bothner
per@bothner.com   http://www.bothner.com/~per/

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]