[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
tail recursion, again
Date: Sun, 9 Sep 1990 12:30 EDT
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
Computational Logic, Inc.
[Disclaimer: this is my personal understanding, not any official statement
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.
There are two kinds of "tail recursion" optimizations. Something like
(defun foo (n)
(if (= n 0)
(foo (1- n)))))
isn't tail recursive since there is state when FOO calls itself.
However, it can still be turned into something like:
(defun foo (n)
(cond ((= n 0)
(t (setq n (1- n))
because the catches can all be collapsed into a single catch. This is
the case you were talking about, and would would be hard for us to do.
Quite a bit easier (on Ivory, anyways) is the case where there is a call
to any function for destination return with no cleanups needing to be
done. Trap on exit would work well enough.