[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

tail recursion, again



    Date: Tue, 4 Sep 90 11:21:09 CDT
    From: lsmith@CLI.COM (Larry Smith)

    Last spring I got very frustrated with the Symbolics because the
    compiler could not optimize tail recursion. Does Genera 8 do any
    better?  

    Thanks,

    Larry Smith
    Computational Logic, Inc.  
[Disclaimer:  this is my personal understanding, not any official statement
from Symbolics.]

Genera uses stack frames to hold important information about the dynamic
state of the function running in the frame (e.g. if it has changed the
trap mode, if it has a presentation to a stack-consed object, if a trap
on exit has been requested via the debugger, if there is an open catch
or unwind-protect, etc.).  If you did the traditional tail-recursion
optimization you would only have one actual stack frame in which to
store this state for potentially a large number of recursive calls to
the same function.  This makes it much harder to do the 'traditional'
tail recursion optimization because you have to arrange to store this
state elsewhere, which would slow down all function call/returns. 

Unfortunately, it is the function call/return microcode in both the 36xx
and the Ivory that has to know about this state; since the latter is in
silicon, the chances of this ever being changed are pretty close to
zero.  This issue has been discussed internally within Symbolics many
times, and the concensus (if I understand it correctly) was that the
slow-down to all function calls wasn't worth the performance improvement
of the small percentage of tail-recursed function calls.