🚀 go-pugleaf

In article <oun34tm3c7.fsf@lynx.cs.byu.edu>,
Kelly Hall <hall@cs.byu.edu> wrote:
>>>>>> "Lawrence" == Lawrence Kirby <fred@genesis.demon.co.uk> writes:
>    Lawrence> An O(log N) stack depth is generally not a problem. I
>    Lawrence> guess you could say that is finite because there are
>    Lawrence> typically practical upper bounds to N.
>
>Tail recursion is implemented by all non-stupid compilers the same way
>as the imperative (goto) version.  Gcc will do this, whether or not
>your favorite compiler will is a different matter.
>
>No stack problems at all.

I have seen several people claim that GCC does proper optimization
of tail calls, but also claims to the contrary.  I decided to test
it for myself with this little tail recursive program:

  #include <stdlib.h>
  #include <stdio.h>
  
  int evenp(long i)
  {
    if (i==0) return 1;
    return oddp(i-1);
  }
  
  int oddp(long i)
  {
    if (i==0) return 0;
    return evenp(i-1);
  }
  
  int main(int argc, const char *argv[])
  {
    if (argc!=2) 
      puts("Usage: oddp <number>");
    else if (oddp(abs(atol(argv[1]))))
      puts("Number is odd.");
    else
      puts("Number is not odd.");
    return 0;
  }

The sad truth is that this program, compiled with GCC 2.7.0 (-O3),
blows the stack when tested with a number large enough.  Tail calls
within a single function seems to be optimized, though, but this
limitation is really too restrictive for people who want to program
in a functional style (or translate functional programs to C.)

On the other hand, Suns unbundled C compiler (v3.0.1) seems to
handle this example well, as well as mutual recursion between
different compilation units.  The DEC OSF/1 compiler (v3.11 on an
Alpha) also does OK, but only within a single compilation unit.
More data points?

All in all, I don't think it's wise to count on tail call
optimization if you are aiming for portable C code.
--
Rickard Westman                   |   "Beware of the panacea peddlers:
Dept. of Computer Science         |    Just because you wind up naked 
Linköping University              |    doesn't make you an emperor."  
Sweden                            |              - Michael A Padlipsky