On Thu, Jul 08, 2004 at 11:51:10AM +0200, Andreas Rossberg wrote:
> David Brown wrote:
> >
> >In some functional languages (Scheme, specifically), tail recursion is
> >required to be implemented iteratively.  It is a common enough idiom,
> >and easy enough to implement, that it is generally done in functional
> >languages.  In fact, gcc does it in C, with enough optimization.
> 
> The latter is, to a certain extent, a myth.

> First, you have to distinguish between simple tail *recursion*, and the 
> much more general concept of tail *call*. I believe Scheme requires to 
> fully optimize the latter, and so it is done by all decent FPL 
> implementations. GCC does not do that, already falling short of mutually 
> recursive functions, IIRC.

I just tested it, and gcc did tail call of two, (simple) mutually
recursive functions.  If they aren't simple enough, it doesn't.

> Second, a C compiler can only optimize tail recursion under limited 
> circumstances, because generally the C language semantics prevent it 
> (once more due to pointers, particularly C allowing - and its libraries 
> relying on - taking the address of local variables). Last time I heard 
> of it, it was said that GCC is having a hard time doing anything 
> practically usefull at all.

C is certainly going to limit the cases where tail-call elimination can
be done.  It also isn't very obvious where it can, so it isn't useful to
depend on.

Many ocaml programs depend on tail-call elimination, although I don't
believe anything in the docs requires it to be done.

Dave

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners