Tail Recursion in Common Lisp ???

[David C. Plummer <DCP@QUABBIN.SCRC.Symbolics.COM>]

    Date: Thu, 17 Jul 1986  22:00 EDT
    From: STEVER%OZ.AI.MIT.EDU@XX.LCS.MIT.EDU

	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)
						   result))))))
		       (nreverse (remove-1 list '()))))

Try
	(defun remove (atom list)
	  (do ((rev-answer nil (if (eql (first remaining) atom)
				   rev-answer
				   (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.