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

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

Alan wants to know what's bothering Ramsdell.

Alan Bawden <Alan@lcs.mit.edu> writes:

> I cannot find anything in the draft of R5RS I have that defines "properly
> tail recursive" in this way or, for that matter, in any other way.  

(1) Making a requirement without defining the meaning of the
requirement bothers me.

(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,
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.

Let me propose that we substitute the following paragraph for the
paragraph that begins with the sentence: "Implementations are required
to be properly tail recursive."  (page 3, par. 5)

The Scheme programming language uses syntactically recursive
procedures of a special form to express iterative computations that
execute in constant space.  Implementations are required to
distinguish between two kinds of call sites within a procedure.  A
tail call in a procedure is a call that returns its result to
the caller of the procedure.  Implementations are required to arrange
it so that every tail call returns directly to the procedure's
caller.  As a result, loops can be implemented using tail calls.

By the way, the term "properly tail recursive" and any of its
variations are not in the index.