Tail Recursion

[Barry Margolin <barmar@THINK.COM>]

    Date: Wed, 22 Feb 89 09:27 EDT
    From: GODDEN%gmr.com@relay.cs.net

     >From: Jeffrey Mark Siskind <Qobi@zermatt.lcs.mit.edu> 
     >Jonathan Rees has a Scheme compiler for the 3600. I have never used it 
     >so I can't comment on its quality. Actually I would very much like 
     >the plain 3600 Common Lisp compiler to support tail recursion (and 
     >continuations as well --- though the latter would require some 
     >extensions to the language.) Many times I have taken to writing loops 
     >instead of tail recursive calls solely for performance reasons and 
     >would like to be able to stop that practise. 
     >        Jeff

    I thought the CL compiler DID support tail recursion properly?
    At least, when I disassemble tail-recursive code I see a CALL-1-RETURN
    which I have been (improperly?) assuming corresponded to a branch
    instruction, nicht wahr?  I know it says CALL in there, but it's
    different from the internal function calls.  Since the compiler knows
    it is to return the value of the call, i.e. it has recognized the
    tail-recursive situation, is call-1-return still doing all the
    unnecessary function call overhead anyway?  If so, why???????????

Yes, CALL-n-RETURN does a real function call.  It has precisely the same
semantics as CALL-n-MULTIPLE followed by RETURN-STACK.  The effect of
the -RETURN is to set a bit in the callee's stack frame (when you do
"Meta-L" in the debugger this is indicated by the message "Called to
return").  Then when the callee does a RETURN, it will pop both its
stack frame and any preceding frames that have the RETURN bit set.  The
purpose is to speed up function returning, since it is common to have a
deeply nested sequence of function calls that all just return the
results of their last call.

As to WHY they don't do tail call elimination, I can think of two
possible reasons.  One is that it would add complexity to the compiler,
which is already enough of a mess.  You need more than just a
CALL-n-RETURN instruction to do tail call optimization.  You also have
to push the arguments differently, so that they are put in the current
stack frame rather than a new one.  You COULD have the instruction shift
the arguments back into the current stack frame, but that makes
optimized tail calls expensive.  A decent tail-call optimizer requires
compiler support, and it's not trivial (I have a friend who is an MIT
Scheme maintainer, and he has some example code that he says no other
Scheme implementation optimizes properly).

The other reason is that eliminating tail calls makes debugging harder,
because frames will not show up in backtraces.  I expect that Lisp
implementations that do tail call elimination have a compiler option to
disable it for debugging.  But this would conflict with Symbolics's
philosophy that programs are never fully debugged and should always
provide full debugging information.  As a purchaser of software, I
personally am glad that the vendors are not able to compile away the
debugging features.

                                                barmar