tail recursion optimization

[Rob MacLachlan <RAM@C.CS.CMU.EDU>]

    Date: Monday, 9 June 1986  21:52-EDT
    From: David C. Plummer <DCP at QUABBIN.SCRC.Symbolics.COM>
    To:   common-lisp at SU-AI.ARPA
    Re:   tail recursion optimization 

    Inline is orthogonal to tail recursion optimization.
    	(defun foo (a b) (declare (inline foo)) (foo a (+ a b)))
    is equivalent to
    	(defun foo (a b) (+a (+ a (+ a (+ a ...)))))
    and not
    	(defun foo (a b) (loop (psetq a a b (+ a b))))

Yes, but I didn't say that the tail-recursive call should be
considered INLINE; I just said that it could be forced to be a full
function call by declaring it NOTINLINE.  NOTINLINE isn't the opposite
of INLINE, since NOTINLINE affects things which were never declared
INLINE and is mandatory rather than advisory.  NOTINLINE is an
important declaration in Common Lisp since it provides a way to tell
the compiler not to make any assumptions about the definition of a
function.  I don't know to what extent current compilers do this, but
I think that when a function is declared NOTINLINE, is should be
called exactly as given, regardless of what the function is.  This
inhibits any optimization of the call.  It would be incorrect to
compile (+ (+ 3 4) 5) as 12 or even as (+ 3 4 5) if + was declared
NOTINLINE.

Making the function be lexically defined within the body of DEFUN is a
clean solution, but it does have some problems.  Every implementation
would be required to make defun close over the definition at DEFUN
time.  This would require every implementation to be changed, and
would put a serious strain on some.  In particular, in the current
PERQ Spice Lisp implementation, the only way to do this would be to
make every function a lexical closure.  It also have the problem that
this early binding of the name becomes a mandatory part of the
semantics, and thus couldn't be inhibited by a compiler switch.

  Rob