tail recursion proposal

[Richard Kelsey <kelsey@research.nj.nec.com>]

This is a proposal for an expanded statement of the tail-recursion
requirement in R5RS.  It would be a new section.  The existing
statement, a paragraph in the section on semantics (section 1.1),
would remain.

It was written by John Ramsdell, Will Clinger, and myself following
the discussion on this list.

                                   -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 two conditions are met: the continuation
passed to a tail call is the same, in space efficiency as well as
effect, as the continuation that was passed to the procedure that
contains the tail call, and that same continuation must also be
passed to the procedure called from the tail call.
An implementation that allocates additional space for the
continuation to a tail call, for example by pushing a stack frame,
is not properly tail-recursive.

Intuitively, no additional space is needed 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 is important because it allows iterative
computations to be expressed efficiently, reliably, and portably
using ordinary procedure calls.

A {\em tail call} is a procedure call that occurs in a {\em tail
context}.  Tail contexts are defined inductively.  Note that a tail
context is always determined with respect to a particular lambda
expression.

* The last expression within the body of a lambda expression,
  shown as T below, occurs in a tail context.

        (lambda F E ... T)

* If one of the following expressions is in a tail context,
  then the subexpressions shown as T are in a tail context.

  (if E T T)
  (if E T)

  (let-syntax ((I Trans) ...) E ... T)
  (letrec-syntax ((I Trans) ...) E ... T)

  (begin E ... T)

  (let ((I E) ...) E ... T)
  (let I ((I E) ...) E ... T)
  (letrec ((I E) ...) E ... T)

  (cond (E E ... T) ...)
  (cond (E E ... T) ... (else E ... T))

  (case ((D D ...) E ... T) ...)
  (case ((D D ...) E ... T) ... (else E ... T))

  (and E ... T)
  (or E ... T)

  (do (DoC ...) (E E ... T) E ...)

  If a COND expression is in a tail context, and has a clause of
  the form (E0 => E1), then the (implied) call to the procedure
  that results from the evaluation of E1 is in a tail context.
  E1 itself is not in a tail context.

In the following example the only tail call is the call to F.
None of the calls to G or H are tail calls.  The reference to
X is in a tail context, but it is not a call and thus is not a
tail call.

   (lambda ()
     (if (g)
         (let ((x (h)))
           x)
         (and (g) (f))))

Note:  Implementations are allowed, but not required, to
recognize that some non-tail calls, such as the call to H
above, can be evaluated as though they were tail calls.
In the example above, the LET expression is equivalent to
a tail call to H unless some unexpected number of values
is returned to a continuation, in which case the effect is
explicitly unspecified and implementation-dependent.

Certain built-in procedures are also required to perform tail calls.
The first argument passed to APPLY and to
CALL-WITH-CURRENT-CONTINUATION, and the second argument passed to
CALL-WITH-VALUES, must be called via a tail call.
Similarly, EVAL must evaluate its argument as if it
were in tail position within the EVAL procedure.

[End of section X.Y.]