Re: proper tail recursion proposal, take 2

[Matthias Blume <blume@zenbu.CS.Princeton.EDU>]

From: Richard Kelsey <kelsey@research.nj.nec.com>
Subject: proper tail recursion proposal, take 2
Date: Wed, 14 Jan 1998 17:39:17 -0500

> Other than Matthias Blume's complaint that it is too weak to be
> worth bothering with, are there any unresolved issues with the
> non-rationale portion?

Despite the danger of repeating myself, let me explain one more time
why it is not worth bothering with...

> ...  A Scheme implementation is
> properly tail-recursive if it supports an unbounded number of active
> tail calls (a call is {\em active} if the called procedure may still
> return).

Suppose we had already properly defined what "active" means (and thus
answered Kent's complaint), it is still completely undefined which
programs are allowed to run out of resources and which ones are not.

The problem is that not all programs that would lead to an unbounded
number of active tail calls can also be executed in finite space.
Clearly, we do not expect the unbounded number of active tail calls in
the following program to successfully execute in most implementations:

    (define grow (lambda (x) (grow (cons 'x x))))

Now, after we acknowledge that there are some programs that have an
unbounded number of active tail calls and still are allowed to run out
of space, to fulfil the "properly tail recursiveness" requirement, is
it then enough if there exist _some_ programs (perhaps not even more
than one) that fulfill the "unbounded number of active tail calls"
definition and which do not run out of space?  If so, let's say that
program is (up to \alpha-renaming) the following:

     (define loop (lambda () (loop)))

Is it ok if the compiler recognizes this directly and produces a tight
loop just here?

I think we all agree that this would not be ok, that it would be
silly. But the "definition" above does not say at all what we really
want.  That's why I call the proposed "strengthening" of the wording
useless -- it is no more precise than what we had before.  And even
before we all knew intuitively what we wanted.  Please, don't waste
document space on words with no meaning!

-Matthias