[plt-scheme] guido on tail recursion

From: Eli Barzilay (eli at barzilay.org)
Date: Sat Apr 25 19:01:27 EDT 2009

On Apr 25, Prabhakar Ragde wrote:
> 
> Or the doofus-in-the-devel-tools, GCC, which will optimize a tail
> call if and only if the return type and space requirements for
> parameters for the called function exactly match those of the
> current function. Write mutually-recursive even? and odd?, stick a
> gratuitous local variable into one, and watch the stack overflow.
> 
> Perhaps I shouldn't apply the term "doofus" to GCC, though, as it at
> least tries, unlike CPython. (And the JVM...) --PR

(This is now well off-topic, but I can't resist...)

I once looked at the code that GCC generates for mutually recursive
even/odd, with tail-call optimizations, and the machine code really
impressed me.  Doing that again, I get this with -O2 (translating the
assembly code):

    is_odd:
      if n=0 return 0
      n -= 1
    is_even:
      if n=0 return 1
      n -= 1
      goto is_odd

and with -O3, the implicit loop is unrolled a few times (also
hand-translated):

    is_even:
      if n=0 return 1
      if n=1 return 0
      if n=2 return 1
      if n=3 return 0
      if n=4 return 1
      if n=5 return 0
      A := n-6
      if A=0 return 1
    loop:
      if A=1 return 0
      if A=2 return 1
      if A=3 return 0
      if A=4 return 1
      if A=5 return 0
      if A=6 return 1
      if A=7 return 0
      if A=8 return 1
      if A=9 return 0
      A := A-10
      if A=0 return 1
      goto loop

-- 
          ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
                  http://www.barzilay.org/                 Maze is Life!


Posted on the users mailing list.