|re: Tail recursion email@example.com (David Chase) (2000-08-13)|
|From:||David Chase <firstname.lastname@example.org>|
|Date:||13 Aug 2000 19:01:50 -0400|
Do any of the commonly-available compilers for "mainstream" languages
do tail recursion optimization? In particular, any C, c++, or Ada
Sun's C and C++ compilers did, 6 years ago, under suitable conditions.
The "under suitable conditions" restriction is a bit of a pain, since
you never really know if you're going to get the optimization, or not.
Suitable conditions are (I think)
1) Parameter area limits
a) if the recursive call has <= six words of parameters
b) if the recursive call has no more words of parameters
than the caller has.
2) Activation record pointer limits
a) Calling routine cannot also call "setjmp".
b) Calling routine cannot pass pointers to locals.
c) Calling routine cannot store pointers to locals in a global.
d) Calling routine cannot have inline assembly language.
e) Calling (C++) routine cannot have exception-handling
(finalizers, destructors to run) associated with the tail
a) If the return type of the tail-called routine was a structure,
there may have been restrictions on the return type of the calling
routine -- I believe it had to be void return, or same structure.
This seems "obvious" nowadays, but back in the good old days of
K&R C and misdeclared routines, one had to be careful not to
transform a bogus-but-working program into a bogus-but-crashing
program, where "bogus" means "contains ignorable infractions of
the recently approved Ansi C standard".
[Current versions of gcc turn direct tail recursion into loops quite
consistently, but not indirect. -John]
Return to the
Search the comp.compilers archives again.