[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Tail Recursion in Common Lisp ???
- To: Fahlman@C.CS.CMU.EDU, Common-Lisp@SU-AI.ARPA
- Subject: Tail Recursion in Common Lisp ???
- From: Guy Steele <gls@Think.COM>
- Date: Mon, 21 Jul 86 17:32 EDT
- Cc: gls@AQUINAS
- In-reply-to: <FAHLMAN.12223695429.BABYL@C.CS.CMU.EDU>
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.
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