Re: formalizing tail-call optimization

[Richard Kelsey <kelsey@research.nj.nec.com>]

   Date: Fri, 09 Jan 1998 11:08:31 -0500
   From: Matthias Blume <blume@CS.Princeton.EDU>

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

[`Tries'?  A quick check shows that, except for the rationale,
  I was 100% successful in avoiding references to "space".]

The change was not meant to address your concerns, but to
avoid using the unspecified notions of continuations, their
size, and when two are `the same'.

   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.

That certainly isn't my aim.  My intent, as far as these four
functions is concerned, is to require that implementations allow
(F3 '()) and (F4 '()) to execute without running out of space and
to allow them to run out of space (or something) on the other two.

I suspect that you meant

   (define f3 (lambda (x) (begin (f3 x) x)))
                                  **
in which case (F3 '()) could also run out of space.

   [...]

   Any additional incomplete explanation is nothing more than an
   invitation to nit-pickers like me to take the whole proposal apart.

What is so awful about making it explicit that F4 not be
allowed to run out of space?  What problems will this cause?
So far you haven't picked an nits at all, you have simply
stated that the proposed section does not require that
implementations be `safe for space'.  Fine.  That was not
the intent.
                          -Richard Kelsey