Re: proper tail recursion proposal, take 2

[Richard Kelsey <kelsey@research.nj.nec.com>]

   References: <199801142239.RAA21110@kima.nj.nec.com>
   Date: Wed, 14 Jan 1998 21:53:25 -0500
   From: Matthias Blume <blume@zenbu.CS.Princeton.EDU>

   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.

Don't worry, you aren't repeating yourself.  In a message
sent last Friday you wrote

 The proposed text provides a lower bound on the set of
 programs that run out of space.

which is certainly not `completely undefined'.

   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.

You are correct.  There are lots of ways to run out of space.
You can use too many cons cells.  Integers can get too large.
You can write too many characters to a file.

You are also correct that the proper tail recursion requirement
addresses only one of these.  Your point of view seems to be that
unless we address *all* of them there is no point in addressing any.

Your earlier suggestion that we adopt some definition of
safe-for-space doesn't help, by your measure, because they also
leave gaps.  Do they say how big a file you can write?  How many
non-tail-recursive active calls are allowed?

I agree whole-heartedly that we could do better than just requiring
proper tail recursion.   But whatever measure of space we adopt, proper
tail recursion will be a part of it.  What's the harm in going one
step at a time?  Especially as we don't know how to go all the way?

                                    -Richard Kelsey