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

proper tail-recursion proposal

Here is a modified version of the proposal.  The requirement is now
specified without mentioning continuations or the space they take up.
The rationale has been marked as a rationale and now acknowledges
that alternatives exist and are not without their advantages.

                                           -Richard Kelsey

Section X.Y.

Implementations of Scheme are required to be {\em properly
tail-recursive}.  Procedure calls that occur in certain syntactic
contexts defined below are `tail calls'.  A Scheme implementation is
properly tail-recursive if it supports an unbounded number of pending
tail calls (a call is {\em pending} if the called procedure may still


Intuitively, no space is needed for a pending tail call because the
continuation that is used in the tail call has the same semantics as the
continuation to the procedure containing the call.  Although an improper
implementation might use a new continuation in the call, a return
to this new continuation would be followed immediately by a return
to the continuation passed to the procedure.  A properly tail-recursive
implementation returns to that continuation directly.

Proper tail-recursion allows iterative computations to be expressed
using ordinary procedure calls.  An alternative would be to have
one or more iterative primitive expressions (make DO a primitive
expression instead of a derived expression, for example).  Requiring
proper tail-recursion gives the programmer greater flexibility at the
cost of greater conceptual overhead (witness the length of this section)
and implementation complexity.


[The rest is unchanged, except for adding LET* and fixing the syntax
 of CASE.]