Proper Tail Recursion

[Moved here from ProperTailCall -- although in fact "proper tail call" is a more accurate name.]

Standard-compliant implementations of the SchemeLanguage are required to support "proper TailRecursion", i.e. they have to support an unbounded number of active TailCall?s.

See William D. Clinger's paper, Proper tail recursion and space efficiency (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.4500) for a more formal definition.

Quoting:

: Proper tail recursion is not the same as ad hoc TailCallOptimization in stack-based languages. Proper tail recursion often precludes stack allocation of variables, but yields a well-defined asymptotic space complexity that can be relied upon by portable programs.
: The essence of proper tail recursion is that a procedure can return by performing a tail call to any procedure, including itself.
: A tail call does not cause an immediate return, but passes the responsibility for returning from the procedure that performs the tail call to the procedure it is calling. In other words, the activation of a procedure extends from the time that it is called to the time that it performs either a return or a tail call.

Quoting R5RS (see RevisedReportOnAlgorithmicLanguageScheme):

Intuitively, no space is needed for an active tail call because the continuation (see ContinuationExplanation and ContinuationPassingStyle) 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 GuySteele and GeraldSussman's original version of Scheme. Their first Scheme interpreter implemented both functions and actors (see ActorsModel). 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.

Version 5.0 introduced ProperTailCalls to the LuaLanguage.

ColorForth has TailCallOptimization, and as with Scheme encourages using ProperTailRecursion to implement loops.

CategoryLanguageFeature CategoryScheme