[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: daniel@mojave.stanford.edu, rrrs-authors*Subject*: tail recursion*From*: harrison@sp21.csrd.uiuc.edu (Luddy Harrison)*Date*: Tue, 24 Apr 90 11:44:51 CDT*In-Reply-To*: Daniel Weise's message of Tue, 24 Apr 90 09:20:30 PDT <9004241620.AA07188@mojave.Stanford.EDU>

>> 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

**References**:**tail recursion***From:*daniel@mojave.stanford.edu (Daniel Weise)

- Prev by Date:
**tail recursion** - Next by Date:
**Re: tail recursion** - Prev by thread:
**tail recursion** - Next by thread:
**Re: tail recursion** - Index(es):