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

Tail Recursion in Common Lisp ???

    Date: Fri, 18 Jul 1986  12:44 EDT
    From: "Scott E. Fahlman" <Fahlman@C.CS.CMU.EDU>

    It is my belief, based on what I know of the constraints various groups
    feel they are working under, that there is no chance in hell that
    required tail-recusrion removal will be added to Common Lisp in the near
    future.  There's just no point in discussing this further.  If you want
    a guarantee that tail-recursion will be handled well, use Scheme or that
    subset of Common Lisps that are able to support this; if you want a
    guarantee that your code will be efficient in Common Lisp, use DO.

    I believe that tail-recursion removal will be ALLOWED in the final spec,
    though some groups read the current manual as requiring a full call,
    even from a function to itself, in case someone has installed a new
    definition for FOO in the middle of running FOO.  We will discuss this
    and, I hope, find a set of rules under which tail-recursion removal is
    legal (but not required) unless the user has explicitly requested the
    full call.  We will of course try to clearly document exactly what is
    allowed and what is required in this area, once this has been decided.

    -- Scott

I agree with Scott's sentiment: we just can't require it now.  One minor
correction: the removal of tail recursion is not necessarily synonymous with
failing to examine the function cell at call time; that is, one might have
removal of tail recursion (stack doesn't grow when you do a tail-recursive
call) that is not implemented by a simple JUMP instruction back to the top of
the current procedure.  Tail-recursion removal is more general than
self-recursion removal.  For more flames, see my paper in Proc. ACM '77
National Conference.