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

formalizing tail-call optimization

Richard's new wording that tries to avoid references to "space" still
has the same shortcomings that the original proposal had.

Here are four functions f1, f2, f3, and f4.  Of those four, when
invoked with an argument of '(), only the last is not allowed to run
out of resources:

(define f1 (lambda (x) (f1 (cons 'x x))))

(define f2 (lambda (x) (begin (f2 (cons 'x x)) x)))

(define f3 (lambda (x) (begin (f4 x) x)))

(define f4 (lambda (x) (f4 x)))

However, both f1 and f4 are what we would call "tail-recursive".  All
the current attempts at explaining Scheme's requirement for "proper"
tail-recursion aim at distinguishing between the failure modes of
examples f1 and f4.  This cannot be done if we don't explain the
behavior of cons and the liveness of variables.

Note that in some implementions there is no observable difference
between the failures of f1, f2, and f3.  The all just run out of
As long as the explanation in RnRS (n > 4) fails to explain these
issues _fully_, there is no point in explaining them at all.

And since there are such complete explanations around, I would prefer
to leave the wording of RnRS (n <= 4) and add a reference to the
relevant literature (e.g., Will Clinger's paper, Andrew Appel's work,
Bob Harper's work, ...).
Any additional incomplete explanation is nothing more than an
invitation to nit-pickers like me to take the whole proposal apart.