Re: requiring proper tail recursion

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

I have a new suggestion for the tail recursion requirement, but first
a question about this one:

Guy Steele - Sun Microsystems Labs <gls@livia.East.Sun.COM> writes:
...
> I like it, but would be inclined to go at it from a slightly different point
> of view:
> 
>   When a procedure p1 is to be called from a point within the definition of
>   a procedure p2 that has been called with continuation k, and when the only
>   observable actions or effects of p2 that remain to be accomplished after
>   execution of p1 is to yield control directly to k, passing it exactly the
>   value(s) yielded by p1, then the point of call of p1 is said to be a
>   <I>tail position</I> within p2, continuation k itself should be used as the
>   continuation of p1, and the call to p1 is said to be a <I>tail call</I>.
...
>   Implementations of Scheme are required to reliably detect function calls
>   from a tail position....

Consider the Scheme procedure FOO:

(define (foo x y)
  (if (goo? x y)
      (bar x y)
      (let ((z (baz x y)))
        z)))

The call to BAR is certainly a tail call, but what about BAZ?  Can one
observe the binding and dereferencing of variable Z?

I suggest we approach stating the tail recursion requirement from the
perspective of a programmer.  Think about lexical scoping.  A static
analysis is all that is required to associate bindings with variable
references, but what is more important is this task is easily done by
a programmer.  I believe a very simple static analysis of a program
should be all that is needed to identify tail calls in a Scheme
procedure.

Here is the current abstract syntax of Scheme:

E := K | I | (E E*) 
   | (lambda (I*) E* E) (lambda (I* . I) E* E) | (lambda I E* E)
   | (if E E E) | (if E E) | (set! I E)

Now consider another version of the abstract syntax of Scheme with a
new nonterminal T, which is also the start symbol:

T := K | I | (E E*) 
   | (lambda (I*) E* T) (lambda (I* . I) E* T) | (lambda I E* T)
   | (if E T T) | (if E T) | (set! I E)

E := K | I | (E E*) 
   | (lambda (I*) E* T) (lambda (I* . I) E* T) | (lambda I E* T)
   | (if E E E) | (if E E) | (set! I E)

Label combinations produced by the T production as tail calls.  Even
in the face of macros, I believe the identification of tail calls
using this kind of static analysis is easy to do.  Notice that every
tail call identified with this procedure is a tail call in the sense
of Guy Steele's definition.

John