[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Tail Recursion in Common Lisp ???
- To: "Bernard S. Greenberg" <BSG@SCRC-STONY-BROOK.ARPA>
- Subject: Tail Recursion in Common Lisp ???
- From: STEVER%OZ.AI.MIT.EDU@XX.LCS.MIT.EDU
- Date: Fri, 18 Jul 1986 02:00:00 -0000
- Cc: Common-Lisp@SU-AI.ARPA
- In-reply-to: Msg of 17 Jul 1986 10:53-EDT from Bernard S. Greenberg <BSG at STONY-BROOK.SCRC.Symbolics.COM>
Date: Thursday, 17 July 1986 10:53-EDT
From: Bernard S. Greenberg <BSG at STONY-BROOK.SCRC.Symbolics.COM>
If the spec -allows- tail-recursion optimization, and "my"
implementation "supports" tail-recursion, then "I" can ... write a
"tail-recursive" program, which ... will blow the stack of most
certified implementations that do not "support" tail-recursion,
and is thus, subtly, not portable.
Which is why, even though tail recursion is an attribute of the
implementation, it might be nice for the standard to say something on
the issue (either a "yes, you can assume it" or "no, you can't.")
A lot of people, at least at MIT, are learning Lisp via SCHEME, so
they come out into the real world believing that tail recursion is a
safe way to do things.
Since I'm relatively new to the list, I'm not familiar with discussion
of iteration constructs at all. I sat down to write a quickie Common Lisp
program which used tail recursion, and was rather surprised when it
blew up. The last form in the body was an IF, in which both branches
called the toplevel function (I had hoped) tail-recursively.
Can this kind of iteration be \nicely/ expressed other ways?
Zetalisp's LOOP was able to give me what I wanted, expressed in a very
different way. But since it's not part of the standard (and I dislike
its non-LISPish syntax), I'd rather not use it.
A rough example of the kind of thing I was doing:
(defun remove (atom list)
(labels ((remove-1 (remaining result)
(cond ((endp remaining) result)
((eq (first remaining) atom)
(remove-1 (cdr remaining) result))
(t (remove-1 (cdr remaining)
(cons (first remaining)
(nreverse (remove-1 list '()))))