4. Active procedure calls

Implementations of Scheme must be properly tail-recursive. Procedure calls that occur in certain syntactic contexts called tail contexts 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 regular returns as well as returns through 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. This allows the execution of an iterative computation in constant space, even if the iterative computation is described by a syntactically recursive procedure. Thus with a properly tail-recursive implementation, iteration can be expressed using the ordinary procedure-call mechanics, so that special iteration constructs are useful only as syntactic sugar.

A formal definition of proper tail recursion can be found in Clinger98.

4.1. 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.

Implementations of Scheme should also support a practically unbounded number of active calls which are not tail calls. The number of active non-tail calls should be bounded only by the amount of storage space available to the program. Any other behaviour is implementation-specified; however, implementations which do not support unbounded numbers of active non-tail calls should raise an exception with condition type &implementation-restriction upon an attempt to activate a non-tail call which breaks the implementation’s limit.

RationaleThe need to support unbounded numbers of non-tail calls is related to the requirement for safety . Consider the following implementation of a simplified version of the map procedure :Without a guarantee that practically unbounded numbers of non-tail calls may be active at any one time, it is unsafe to call this procedure on a list ls of any particular length, because a list longer than the number of allowed active non-tail calls would not behave in the expected way.

4.2. Description

The tail contexts in which tail calls occur are defined inductively. In general, any body or sequence of expressions has its final expression in a tail context if the body or sequence of expressions itself is part of the syntax of a syntactic form which itself is used in a tail context. This report usually notes when final expressions are in tail contexts, and always notes explicitly when final expressions are not required to be in a tail context. Implementations which provide libraries with additional syntactic forms in addition to those defined in this report must also document any case in which a body or sequence of expressions which forms part of a syntactic form is never in tail context, even if the syntactic form as a whole is in a tail context.

Certain built-in procedures must also 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. Implementations which provide libraries with additional procedures whose final result is the unmodified result of calling some other procedure given as an argument should document whether the arguments to those procedures are tail-called or not.