Re: tail recursion proposal

[Sidney Marshall <marshall@wrc.xerox.com>]

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
give programmers flexibility about expression, not to trade one form
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 
that did not fill the reader's head with Scheme-centric propaganda.

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
|  consciously made design trade-off.  Proper tail-recursion has
|  traditionally been important in Scheme because it allows iterative
|  computations to be expressed using ordinary procedure calls with a
|  space efficiency that is portably reliable.  Also, sufficient
|  techniques are believed to exist so that it is usually possible for
|  an implementation to compensate heuristically for the would-be loss
|  of debugging power.