[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: requiring proper tail recursion




I agree with John Ramsdell that the statement of the tail
recursion requirement should make it easy to determine whether
any particular call is actually required to be tail-recursive.
The earlier proposals boil down to `all calls that can be done
tail-recursively must be done tail-recursively'.  The difficulty
is that this depends on implementation details.  Are any procedures
in-lined?  Is any beta-substitution performed at compile time?
What matters isn't which calls can be tail-recursive, but which
calls must be.

As an alternative, here is an exanded version of John's syntax-based
specification.
                                          -Richard

----------------

Tail Calls

If E1 is a subexpression of E2 such that once the flow of control has
reached E1 the only remaining observable actions or effects of E2 are
those of E1, E1 is said to be in {\em tail position} within E2.
A procedure call that is in tail position within the body of a procedure
is said to be a {\em tail call}.

Scheme implementations are required to detect tail calls and to ensure
that the continuation passed to the invoked procedure is that which was
passed to the enclosing procedure.

Note: This requirement exists because certain implementation
techiques used for other languages, such as pushing a frame on a
stack for all calls, whether tail calls or not, make it difficult
to predict the behavior of loops expressed using recursion.

For the purposes of this requirement, the locations of tail-position
subexpressions within Scheme expressions are those labelled T in the
following grammar: (this grammar includes only those expressions that
have subexpressions in tail position):

  (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 CoCl ...)
  (cond CoCl ... (else E ... T))
     CoCl ::= (E E ... T)

  (case CaCl ...)
  (case CaCl ... (else E ... T))
     CaCl ::= ((D D ...) E ... T)

  (and E ... T)
  (or E ... T)

  (do (DoC ...) (E E ... T) E ...)

If a COND expression has a clause of the form (E0 => E1) then the
(implied) application of E1 is in tail position within the COND
expression.  E1 itself is not in tail position.

If an application has a LAMBDA expression as the procedure then an
expression that is in tail position with respect to the body of the
LAMBDA expression is in tail position with respect to the application.

  ((lambda F E ... T) E ...)

These are the only subexpressions which implementations are required
to treat as in tail position.

Tail position is a transitive property: if E1 is in tail position
within E2, and E2 is in tail position within E3, then E1 is in tail
position within E3.

  (if (begin E E)
      (cond (E => (lambda (I) E T))
            (else E T))
      (or E E T))

The second E in the BEGIN is in tail position with respect to that
BEGIN but not with respect to the COND.

Note: The tail positions shown above for the derived forms are
consistent with the results of applying transitivity to the macro
definitions in appendix \ref{derivedmacros}.

Using the above definition of tail position, in the following code
only the call to F is a tail call; none of the calls to G are tail
calls.  The reference to X is in tail position, but it is not a call
and thus not a tail call.

  (lambda ()
    (if (g)
        (let ((x (g)))
          x)
        (and (g) (f))))

Implementations are also required to have certain built-in procedures
invoke one of their arguments using a tail call: the first argument of
APPLY and CALL-WITH-CURRENT-CONTINUATION, and the second argument of
CALL-WITH-VALUES.  Similarly, EVAL must evaluate its argument as if it
were in tail position.  As an example, the following expression should
loop endlessly:

    (let ((exp '(lambda (exp)
                  (eval `(apply ,exp '(,exp))
                        (scheme-report-environment 5)))))
      (eval `(,exp ',exp)
            (scheme-report-environment 5)))