Tail recursion

[Glenn Moloney <glenn@physics.unimelb.edu.au>]

Hi all,

I know most people have seen this, but just so everyone has a concrete
understanding of where Scheme is required to be tail recursive, I've
included the "Proper Tail Recursion" section of the R5RS info pages
(see also http://ftp-swiss.ai.mit.edu/~jaffer/r5rs_5.html#SEC23). I
assme this is a more detailed spec of what is also required, though
not spelled out in R4RS.

					cheers,
					glenn.

Proper tail recursion
=====================

Implementations of Scheme are required to be *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 *active* if the called procedure may still
return. Note that this includes calls that may be returned from either
by the current continuation or by continuations captured earlier by
`call-with-current-continuation' that are later invoked. In the
absence of captured continuations, calls could return at most once and
the active calls would be those that had not yet returned. A formal
definition of proper tail recursion can be found in
   [propertailrecursion: William Clinger. Proper Tail Recursion and Space
    Efficiency. To appear in Proceedings of the 1998 ACM Conference on
    Programming Language Design and Implementation, June 1998.]

     *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 passed 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.


A *tail call* is a procedure call that occurs in a *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 <tail expression> below, occurs in a tail context.

     (lambda <formals>
       <definition>* <expression>* <tail expression>)

   * If one of the following expressions is in a tail context, then the
     subexpressions shown as <tail expression> are in a tail context.
     These were derived from rules in the grammar given in chapter
     *Note Formal syntax and semantics:: by replacing some occurrences
     of <expression> with <tail expression>.  Only those rules that
     contain tail contexts are shown here.

     (if <expression> <tail expression> <tail expression>)
     (if <expression> <tail expression>)
     
     (cond <cond clause>+)
     (cond <cond clause>* (else <tail sequence>))
     
     (case <expression>
       <case clause>+)
     (case <expression>
       <case clause>*
       (else <tail sequence>))
     
     (and <expression>* <tail expression>)
     (or <expression>* <tail expression>)
     
     (let (<binding spec>*) <tail body>)
     (let <variable> (<binding spec>*) <tail body>)
     (let* (<binding spec>*) <tail body>)
     (letrec (<binding spec>*) <tail body>)
     
     (let-syntax (<syntax spec>*) <tail body>)
     (letrec-syntax (<syntax spec>*) <tail body>)
     
     (begin <tail sequence>)
     
     (do (<iteration spec>*)
         (<test> <tail sequence>)
       <expression>*)
     
     where
     
     <cond clause> --> (<test> <tail sequence>)
     <case clause> --> ((<datum>*) <tail sequence>)
     
     <tail body> --> <definition>* <tail sequence>
     <tail sequence> --> <expression>* <tail expression>

   * If a `cond' expression is in a tail context, and has a clause of
     the form `(<expression1> => <expression2>)' then the (implied)
     call to the procedure that results from the evaluation of
     <expression2> is in a tail context.  <expression2> itself is not
     in a tail context.

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.

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 could be compiled as a tail call to
     `h'. (The possibility of `h' returning an unexpected number of
     values can be ignored, because in that case the effect of the
     `let' is explicitly unspecified and implementation-dependent.)