[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Tail Recursion in Common Lisp ???
- To: STEVER%OZ.AI.MIT.EDU@XX.LCS.MIT.EDU, Bernard S. Greenberg <BSG@STONY-BROOK.SCRC.Symbolics.COM>
- Subject: Tail Recursion in Common Lisp ???
- From: David C. Plummer <DCP@QUABBIN.SCRC.Symbolics.COM>
- Date: Thu, 17 Jul 86 22:38 EDT
- Cc: Common-Lisp@SU-AI.ARPA
- In-reply-to: <STEVER.12223534508.BABYL@MIT-OZ>
Date: Thu, 17 Jul 1986 22:00 EDT
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.
There are some implementations that will drop out if they are forced to
implement tail recursion. The standard argument revolves around
programming environments and debugger information.
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 '()))))
(defun remove (atom list)
(do ((rev-answer nil (if (eql (first remaining) atom)
(cons (first remaining) rev-answer)))
(remaining list (cdr remaining)))
((endp remaining) (nreverse rev-answer))))
Somebody made the claim the other day, I think on this list, that if you
had tail recursion you can do away with the "syntactic sugar" of
iteration constructs. I'll claim that is somewhat bogus. The iteration
constructs express an idea. They express iteration. Syntactic sugar
embodies ideas and provides abstractions. Also, the iteration
constructs can easily macroexpand into tail recursive calls if that's
the way you want to implement them.