Re: tail recursion (was Re: a (revised) draft of R5RS)

[ramsdell@linus.mitre.org (John D. Ramsdell)]

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