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

Re: requiring proper tail recursion



Jim Blandy wrote:
> If H returns multiple values, (let ((x (h))) x) is not equivalent to
> (h), as the last sentence implies, is it?

Good point!

On the other hand, the fact that (LET ((X (H))) X) can be evaluated
as if it were (H) does not imply that those two expressions are
equivalent.  See below.

I agree that the R5RS shouldn't have to point out opportunities
for optimization, and that this particular example may be too
obscure or politically incorrect.

On the third hand, I recall that this entire business about adding
some kind of definition of proper tail recursion to the R5RS came
about because Jeffrey Mark Siskind feared that the legality of
certain optimizations might not be sufficiently obvious given the
absence of a definition within the R4RS, and I think this is a
fairly good example of a legal optimization whose legality is not
entirely obvious.

See below my revision of Blandy's suggested rewording for this
example.

Will

--------

    In the following example the only tail call is the call to F.
    None of the calls to G or H are tail calls.  The reference to
    X is in a tail context, but it is not a call and thus is not a
    tail call.

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

    Note:  Implementations are allowed, but not required, to
    recognize that some non-tail calls, such as the call to H
    above, can be evaluated as though they were tail calls.
    In the example above, the LET expression is equivalent to
    a tail call to H unless some unexpected number of values
    is returned to a continuation, in which case the effect is
    explicitly unspecified and implementation-dependent.