[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
tail recursion
>> 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