From: Michael P. Smith
Subject: Tail Recursion Optimization
Date:
Message-ID: <12198@duke.cs.duke.edu>
I made a discovery recently I found shocking: TI Common Lisp on the
Explorer does not properly treat tail recursion. In fact, the
tail-recursive factorial ran out of push-down list (control stack)
before the naive-recursive version did!
When I compiled and disassembled versions of the fibonacci function, the
tail-recursive and do-loop versions were virtually indistinguishable in
Sun Common Lisp, but the compiled and disassembled tail-recursive version
under TICL still had the recursive call.
Can anyone explain the reason for this? Are there other lisp compilers
out there that do not treat tail recursion iteratively?
Michael P. Smith
In article <·····@duke.cs.duke.edu> ···@duke.UUCP () writes:
>I made a discovery recently I found shocking: TI Common Lisp on the
>Explorer does not properly treat tail recursion. In fact, the
>tail-recursive factorial ran out of push-down list (control stack)
>before the naive-recursive version did!
[...]
>Can anyone explain the reason for this? Are there other lisp compilers
>out there that do not treat tail recursion iteratively?
>
> Michael P. Smith
If I remember the Explorer correctly (I've been on Symbolics
exclusively for 3 years now), I believe that there is a documented
flag that you can set to make the compiler properly remove
tail-recursion. I believe that the justification for the default
behavior was that it improved debugging, because in the case of an
infinite loop you could immediately see which function was the
culprit.
The Symbolics doesn't remove tail-recursion either, for the same
reason, and there's no flag.
--John
John Nienart
NASA Ames Research Center
Internet: ·······@turing.arc.nasa.gov