tail recursion

[gls@Think.COM (Guy Steele)]

   Date: Tue, 24 Apr 90 16:10:40 BST
   From: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSFnet-Relay.AC.UK>

   > Then I define an implementation to be properly tail-recursive if,
   >    for every program state P,
   >       if continued execution eventually causes state P to recur,
   >          and every non-tail-recursive evaluation begun since
   >              the first occurrence of state P has completed
   >              before the second occurrence of state P
   >       then state P will recur indefinitely many times without
   > 	 running out of resources

   What about cases where some storage is allocated that isn't part of
   the evaluation of the recursion itself?  (Reversing a list with an
   accumulating parameter, say.)  What about loops that take input from
   the user?  That is, when states don't recur, the definition doesn't
   impose any restrictions at all on how the calls involved are
   implemented.

That is correct.  This property is quite intentional.  I believe that
there is very little else one can say about tail-recursion without
dragging in the question of representations of the data structures.

I don't have a good way to compare unequal states for their relative
memory consumption.  One might think, for example, that if two
states are the same except for one list of NIL's, then the state
with the longer list ought to consume more memory; but it just isn't
so.  Consider various data-compression techniques such as CDR-coding;
do we wish to rule them out by imposing a monotonicity requirement
on storage consumption?

Without a way to compare unequal states, I can discuss tail-recursion
only in terms of equal states.  I agree that it is strange to define
tail-recursion, a property we wish to exploit in writing certain
interesting programs, as if solely in terms of the behavior of
UNinteresting programs.

Please, can anyone either refute or improve upon my definition?

   It also seems to require garbage collection.

Yes, it probably does.  That is an interesting point, but maybe
that is essential.  Tail-recursive programs simply aren't allowed
to build up increasing state, whether "on the stack" or "in the heap"
(and in the presence of call/cc, what's the difference, after all?).

--Guy