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].
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.
(lambda <formals> <definition>* <expression>* <tail expression>)
(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>
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 toh
above, can be evaluated as though they were tail calls. In the example above, thelet
expression could be compiled as a tail call toh
. (The possibility ofh
returning an unexpected number of values can be ignored, because in that case the effect of thelet
is explicitly unspecified and implementation-dependent.)