Re: formalizing tail-call optimization

[Matthias Blume <blume@CS.Princeton.EDU>]

From: Richard Kelsey <kelsey@research.nj.nec.com>
Subject: Re: formalizing tail-call optimization
Date: Fri, 9 Jan 1998 11:49:17 -0500

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

[Sorry.  I didn't bother to check and therefore worded that sentence
conservatively.]

> I suspect that you meant
> 
>    (define f3 (lambda (x) (begin (f3 x) x)))
>                                   **
> in which case (F3 '()) could also run out of space.

Yes, that was my intent.  Editing error...

>    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.

There is nothing "awful" about it. The point is that you didn't make
that explicit.  Or maybe you did, but such knowledge is useless
because you did not explain why f4 is NOT while f1 IS allowed to run
out of resources.  As a programmer, I am still left wondering what I
can rely on.

The proposed text provides a lower bound on the set of programs that
run out of space.  This information, while perhaps interesting to
some, is not useful to the programmer who wants to stay away from ALL
programs that run out of space.
In other words, the proposal only warns of functions like F2 and F3,
but is fails to also warn of F1.

The situation for the implementor is even worse.  How do I know that
F1 may but F4 may not run out of space?  What is it that distinguishes
the two?

You are correct in saying that what I want to see is some notion of
"safe for space".  And that's because the term "proper tail-recursion"
(or whatever) is meaningless without a notion of "safe for
space". That's all.

-Matthias