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

proper tail recursion proposal, take 2




After the discussion on this list I have rewritten the rationale in
the proposed section on proper tail recursion, replacing the original
propaganda/apology with a nutshell version of the historical connection
between Scheme and proper tail recursion.  It is an obscure enough
concept that I would like there to be some explanation as to why it is
required.

Other than Matthias Blume's complaint that it is too weak to be
worth bothering with, are there any unresolved issues with the
non-rationale portion?
                               -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 active
tail calls (a call is {\em active} if the called procedure may still
return).

\begin{rationale}

Intuitively, no space is needed for an active 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 was one of the central ideas in Steele and
Sussman's original version of Scheme.  Their first Scheme interpreter
implemented both functions and actors.  Control flow was expressed using
actors, which differed from functions in that they passed their results
on to another actor instead of returning to a caller.  In the terminology
of this section, each actor finished with a tail call to another actor.

Steele and Sussman later observed that in their interpreter the code
for dealing with actors was identical to that for functions and thus
there was no need to include both in the language.

\end{rationale}

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)
  (let* ((I E) ...) E ... T)
  (letrec ((I E) ...) E ... T)

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

  (case E ((D D ...) E ... T) ...)
  (case E ((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.]