tail recursion, again

[Cyphers@JASPER.SCRC.Symbolics.COM (Scott Cyphers)]

    Date: Sun, 9 Sep 1990 12:30 EDT
    From: Reti@Riverside.scrc.symbolics.com

	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. 

There are two kinds of "tail recursion" optimizations.  Something like

(defun foo (n)
  (catch 'foo
    (if (= n 0)
	(bar)
	(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)
  (catch 'foo
    (tagbody
       loop
         (cond ((= n 0) 
	        (bar))
               (t (setq n (1- n))
		  (go loop))))))

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.