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

*To*: rrrs-authors@martigny.ai.mit.edu*Subject*: Re: tail recursion (was Re: a (revised) draft of R5RS)*From*: ramsdell@linus.mitre.org (John D. Ramsdell)*Date*: 27 May 1997 06:35:00 -0400*Cc*: ramsdell@linus.mitre.org*In-Reply-To*: William D Clinger's message of Mon, 26 May 1997 18:38:17 -0500*References*: <ogt9113jk73.fsf@linus.mitre.org> <338A1EDB.5C99@ccs.neu.edu>

William D Clinger <will@ccs.neu.edu> writes: > This is the same as saying that > > > An implementation of Scheme is properly tail recursive > > if and only if for every Scheme program P and inputs D, > > the space required to execute P on D is O(N), where N > > is the space required by implementation X, > Acording to the R5RS, an implementation is tail recursive if syntactically recursive procedures can be used to describe iterative computations that execute in constant space. Will's requirement is different. It requires that Scheme implementations use space as would an implementation that includes tail-call elimination. Let's call implementations that meet Will's requirement tail-call aware. I don't believe that the report needs more formalism to explain precisely what it means for an implementation to be tail-call aware. All I would like to see is that we require that implementations are tail-call aware using informal language and justify this requirement by saying that it seems to allow the use of syntactically recursive procedures to describe iterative computations that execute in constant space. John

**Follow-Ups**:**Re: tail recursion (was Re: a (revised) draft of R5RS)***From:*Matthias Blume <blume@CS.Princeton.EDU>

**References**:**Re: a (revised) draft of R5RS***From:*ramsdell@linus.mitre.org (John D. Ramsdell)

**tail recursion (was Re: a (revised) draft of R5RS)***From:*William D Clinger <will@ccs.neu.edu>

- Prev by Date:
**tail recursion (was Re: a (revised) draft of R5RS)** - Next by Date:
**Re: tail recursion (was Re: a (revised) draft of R5RS)** - Prev by thread:
**tail recursion (was Re: a (revised) draft of R5RS)** - Next by thread:
**Re: tail recursion (was Re: a (revised) draft of R5RS)** - Index(es):