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

[Guy Steele - Sun Microsystems Labs <gls@livia.East.Sun.COM>]

   To: rrrs-authors@martigny.ai.mit.edu
   Subject: Re: tail recursion (was Re: a (revised) draft of R5RS)

Just to beat my previous message to death:
   
   (1) Making a requirement without defining the meaning of the
   requirement bothers me.

Agreed!

   (2) Given the lack of any definition about tail recursion, the only
   way one can say an implementation meets this requirement is to show
   that the consequences described follow from the implementation
   decisions.  In that sense, the definition of a tail recursive
   implementation I gave follows from the lack of anything else more
   definite.  This bothers me.
   
   (3) What really bothers me is that we fail to give readers any hint
   that implementations must distinguish between two kinds of call sites,

Not two kinds of call sites, but two kinds of evaluation contexts:
those that create new continuations and those that do not.  (And we have
to talk about the nature of the continuations that are created.)
   
   and that implementations are to treat tail calls specially.  It's not
   that there are syntactically recursive procedures that can be used to
   describe iterative computations that execute in constant space on this
   machine.  The point is that programmers can rely on the fact that
   loops can be implemented with syntactically recursive procedures of a
   particular form: loops are built out of procedures with tail calls.

Loops can be implemented with code from which it can be inferred on
purely syntactic grounds that there is no net accumulation of continuations
dependent in size on the number of iterations.

--Guy