[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: requiring proper tail recursion
While rereading Will's edit of the tail recursion requirement, I found
it hard to decide exactly what was meant by a tail context. Let me
suggest we drop the language referring to tail contexts and instead
identify tail calls using the related idea of tail expressions defined
below.
John
Procedure calls that are also \emph{tail expressions} are \emph{tail
calls.} Tail expressions are defined inductively.
* The last expression within the body of a lambda expression,
shown as T below, is a tail expression.
(lambda F E ... T)
* If one of the following expressions is a tail expression,
then the subexpressions shown as T are tail expressions.
(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 a tail expression, and has a clause of
the form (E0 => E1), then the (implied) call to the procedure
that results from the evaluation of E1 is a tail expression.
E1 itself is not a tail expression.
* If a procedure call is a tail expression, it is a tail call.