Re: requiring proper tail recursion

[ramsdell@linus.mitre.org (John D. Ramsdell)]

I've edited Richard's text to define tail calls using contexts.
Please consider the enclosed specification.

John

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

Implementations of Scheme are required to be properly tail-recursive.
With a tail-recursive implementation, iteration can be expressed using
the ordinary procedure-call mechanics, so that special iteration
constructs are useful only as abbreviations.  Procedure-calls that
occur in a special context, called a tail context, are the ones used
to specify an iterative computation.  Procedure-calls that occur in a
tail context are called tail calls.  An implementation is
tail-recursive if the continuation passed to the procedure invoked
from every tail call is that which was passed to the enclosing
procedure.

A tail context is defined inductively.

* Top-level is a tail context.

* If a lambda expression occurs in any context, the subexpression
  labeled T is a tail context.

	(lambda F E ... T)

* If one of the following expressions occurs in a tail context,
  the subexpression labeled T is a tail context.

  (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 a tail context within the COND
  expression.  E1 itself is not in a tail context.

Using the above definition of tail contexts, 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 a tail context, 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 a tail context.  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)))

Note: The tail-recursion requirement exists because certain
implementation techniques 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.
Also note that in a particular tail-recursive implementation, other
procedure-calls may behave as tail calls, but programmers may only
rely on tail calls for iteration in all implementations of Scheme.

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

Comment:  The final sentence in the first paragraph, 

An implementation is tail-recursive if the continuation passed to the
procedure invoked from a tail call is that which was passed to the
enclosing procedure.

can only be used if we define the notion of a continuation.  I think
the sentence probably should be replaced, but I cannot think of a
replacement now.