tail recursion

[harrison@sp21.csrd.uiuc.edu (Luddy Harrison)]

>> Would Scheme without garbage collection be Scheme?  Would Scheme
>> without tail-recursion elimination be Scheme?  These questions
>> are identical.

I am a bit perplexed that people are responding to my question about
the meaning of proper tail-recursion by defending the requirement that
Scheme implementations be properly tail-recursive.  First, I am not an
author of the Scheme proposal, and therefore even if I wanted the
requirement lifted (I do not), it should make little difference.  Bert
stated my interest exactly: I want a test that I can apply to
novel implementations that will tell me unambiguously whether they are
properly tail-recursive.

If I understand the responses so far, two characterizations of proper
tail-recursion have been forwarded.  One presents an interpreter M0,
and declares that an implementation is properly tail-recursive if it
requires O(kX) storage, where X is the requirement of M0 on a program
and k is a function only of the implementation.

The second definition is a characterization not of tail-recursion per
se, but of infinite looping: it requires that if a state recurs along
a tail-recursive control-flow path, that the program must loop
infintely (that is, it must not exhaust the memory).  The objective of
this definition is to "force" proper tail-recursion in the general
case by requiring it of this special case.

-Luddy