# Re: tail recursion proposal

```Some more thoughts on tail-call optimization:

Scheme requires tail-call optimization because it doesn't have gotos.
Without gotos it is impossible to iterate along a list etc. without
consuming stack space on each iteration. The only other option would be to
use call/cc but the result would be too heavyweight and somewhat opaque.
The following (unchecked) code illustrates this:

Common lisp (expands to a (go label)):

(defun accumulate (lst)
(for i in lst sum i))

or

(defun accumulate (lst)
(prog ((l lst)
(sum 0))
loop
(if (null l)
(return sum))
(setq sum (+ (car l) sum))
(setq l (cdr l))
(go loop)))

Scheme (tail recursive):

(define (accumulate lst)
(let loop ((l lst)
(sum 0))
(if (null? l)
sum
(loop (cdr l) (+ (car l) sum)))))

Scheme (using call/cc for goto)

(define (accumulate lst)
(let ((l lst)
(sum 0))
(let ((k (call/cc (lambda (k1) k1))))
(if (null? l)
sum
(begin (set! sum (+ (car l) sum))
(set! l (cdr l))
(k k))))))

On the other hand contrast the following code:

Lisp:

(for i to 10 collect #'(lambda () i))

or

(do ((i 0 (+ i 1))
(lst nil (cons #'(lambda () i) lst)))
((= i 10) (nreverse lst)))

with scheme:

(let loop ((i 0)
(lst '()))
(if (= i 10)
(reverse lst)
(loop (+ i 1) (cons (lambda () i) lst))))

or

(do ((i 0 (+ i 1))
(lst '() (cons (lambda () i) lst)))
((= i 10) (reverse lst)))

In the lisp case a loop variable is rebound causing the returned list of
functions all to return the same value. The scheme examples generate new
names at each iteration and these examples return a list of functions each
returning a different value.

The point to all this is that lisp almost always requires one to
side-effect variables to write constant-space loops while scheme allows one
to write constant-space loops without side-effects if there is tail-call
optimization. "set!" is not as essential when writing scheme programs.

I don't know whether or not any of these points need to be brought up in
the discussion of tail call optimization.

--Sidney Marshall

At 01:01 PM 1/8/98 PST, Kent Pitman wrote:
I frequently run across Scheme refugees who are confused by an
expectation that all programming languages will support tail recursion
as Scheme does.  Indeed, it's a common source of programming error for
Common Lisp users who used to be Scheme people and who are often
unable to express themselves iteratively using a "loop" notation, and
so end up blowing out of stack space.  (Always ironic, to me, because
I thought the original point of the tail recursion exercise was to
of dogma for another...  I would feel more sympathetic toward them if
they knew what a loop was and were just grumbling about the expressive
inconvenience, but they often look at me with a stare like there is
something dirty or unhealthy or even just plain unknown about "loop"
constructs.)  Anyway, I trace the cause of this inflexibility on their
part partly to the fact that I think S&ICP and its followers apparently
spend too little time on the "alternatives" part, but I trace THAT, in
turn, to this part of the Scheme spec which simply and without explanation
requires a certain behavior.

Now that we're going to spend time explaining things a little, I take
some specific issue with the following paragraph, which I consider
central to the issue.  It appears to express a universal truth instead
of a design trade-off.  And that, I think, is a shame.

|  Proper tail-recursion is important because it allows iterative
|  computations to be expressed efficiently, reliably, and portably
|  using ordinary procedure calls.

I think the design trade-off is certainly one made by Scheme but it is
not the only legitimate such choice, and I would prefer to see wording

I also think the funny little list of adverbs here is odd in that they
really wants to be combining, not modifying expressed in a free-standing
way.  There is nothing inherently "unreliable" or "unportable" about the
expression of a procedure in this way.  What is unreliable or unportable
is only the space-efficiency.  The minimal fix to this paragraph's complaint
is:

|  Proper tail-recursion is important in Scheme because it allows
|  iterative computations to be expressed using ordinary procedure
|  calls with a space efficiency that is portably reliable.

But I would prefer more elaborated text, such as:

|  The requirement to support proper tail recursion implicitly thwarts
|  some techniques for ``stack debugging'', since if an error occurs,
|  the chain of active continuations will have lost information about
|  how the computation reached the present state.  This was a