[plt-scheme] guido on tail recursion
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!