Re: requiring proper tail recursion

[William D Clinger <will@ccs.neu.edu>]

I would prefer to keep the discussion of tail-recursion in
Section 1.1 brief, because that section is after all a brief
overview of many different things, and just add "See section
X.Y." as a pointer to a fuller discussion.

As for section X.Y, I've edited John's edit of Richard's text
to reduce its overlap with the language of Section 1.1 and to
create a bit more separation between the formal content and the
vaguer intuition and rationale.  I have also made three
substantive changes:

  1.  For a COND clause of the form (E0 => E1), the implied call
      is in a tail context iff the entire COND expression is.
  2.  Top-level expressions are not counted as tail contexts.
  3.  EVAL is not required to evaluate its argument within a
      tail context; see below.

If you're wondering why top-level contexts should not be tail
contexts, remember that a Scheme program is defined as a sequence
of expressions, definitions, and syntax definitions, which are
supposed to be equivalent to a certain LET expression (see
Section 7.2).  Only the last expression or definition in a
program should be in a tail context, and that one exception (to
the general rule that top-level contexts are not tail contexts)
is not important enough to formalize.  Furthermore some
implementations, such as those that are based on an interactive
read/eval/print loop, might not be able to recognize the last
expression or definition of a program, and thus could not treat
it as a tail context.

EVAL is probably a bit more controversial.  It appears to me that
requiring EVAL to evaluate its argument within a tail context might
rule out implementations that implement a fully reflective tower of
interpreters.  It might also rule out implementations that must
perform some kind of context switch when transferring between native
and interpreted Scheme code; several existing implementations do
this, and have good reasons for doing this.  It is my understanding
that the R5RS description of EVAL was intended to be fairly easy for
all implementations to implement, which seems to be incompatible
with the Kelsey/Ramsdell proposal for requiring it to be
tail-recursive.

There is another difficulty with this definition of proper tail
recursion:  In some implementations, CALL-WITH-CURRENT-CONTINUATION
changes the representation of a continuation in ways that make it
occupy additional space.  Furthermore repeated uses of CALL/CC to
capture the same continuation might create multiple copies.  Both
kinds of implementation of CALL/CC are forbidden by the following
definition of proper tail recursion.  I am inclined to ignore this
problem, however, because CALL/CC is so seldom used that few people
would notice.  Furthermore it would probably be easier to change
implementations of CALL/CC to achieve proper tail recursion than
it would be to change the representations and invariants that, in
some implementations, make it difficult for EVAL to evaluate its
argument within a tail context.

Will

--------

Section X.Y.

Implementations of Scheme are required to be
{\em properly tail-recursive}.
This means that the continuation for a tail call, defined below,
must always be the same, in space efficiency as well as effect,
as the continuation that is passed to the procedure being called.
An implementation that allocates additional space for the
continuation, for example by pushing a stack frame, is not
properly tail-recursive.

Intuitively, no additional space is needed because the continuation
that is passed to the procedure must have the same semantics as the
continuation for the tail call:  Although an improper implementation
might pass a new continuation to the procedure, a return to this new
continuation would be followed immediately by a return to the
continuation for the tail call.  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.

* 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.  Implementations are allowed, but not required, to
recognize that some non-tail calls, such as the call to H below,
can be evaluated as though they were tail calls.

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

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.

[End of section X.Y.]