[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: requiring proper tail recursion
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