tail recursion (was Re: a (revised) draft of R5RS)

[Kent Pitman <kmp@harlequin.com>]

   References: <27May1997.152105.Alan@LCS.MIT.EDU>
   X-Fingerprint: E4 3B C3 07 C8 2E 2C 82  3E CD EC 4D 86 09 8B B8
   X-Url: http://www.cs.princeton.edu/~blume/
   Content-Transfer-Encoding: 7bit
   Date: Tue, 27 May 1997 16:26:50 -0400
   From: Matthias Blume <blume@CS.Princeton.EDU>


   From: Alan Bawden <Alan@lcs.mit.edu>
   Subject: tail recursion (was Re: a (revised) draft of R5RS)
   Date: Tue, 27 May 1997 16:04:21 -0400

   > (Matthias Blume sent a number of examples asking, for each one, if the call
   > to `f' should be tail recursive.  As far as I can see, the answer in each
   > case is "yes, of course".  I suppose an implementor can be forgiven for
   > missing any one of them, but I would expect him or her to fix the problem
   > once it was pointed out.)

   I would prefer to make things _very_ explicit, because there are a few
   tricky cases. For example:

      (call-with-input-file file f)

   Intuitively the call to f will not be tail-recursive,

I don't agree.  Of course the call will be tail recursive.  FROM ITS
POINT OF CALL, which is not the caller of CALL-WITH-INPUT-FILE.  An
intermediate stack frame (if you'll pardon my abuse of the term, which
I still like as a metaphor even in continuation-land) is pushed but
not between call-with-input-file and its caller (at least, not
intially :-), and not between f and its caller (well, not its
intentional caller--of course, since tail calls get removed, it will
of necessity run immediately up against the new frame, but not because
of not having tail called).  In principle, this is a potential problem
with any function that takes a thunk as an argument since there can be
arbitrary computation before the thunk is called (provided function
semantics isn't violated).  This has nothing to do with the
specificity of tail recursion--it has to do with the specificity of
the function call-with-input-file, and the fact that its definition
admits multiple and computationally quite different modes of
implementation.

The surprise, if there is one, comes from each user's expectation that
unwind-protect will work in some way they have probably come to expect
for that implementation, only to find that not every implementation
agrees on what that oh-so-obvious way is.  The surprise, if there is
one, I think mostly only turns up in an attempt to port since most
single-implementation-only users either have it clear in their heads
that the purpose of call-with-input-file is to do a non-tailcall or to
do a tail-call, and probably none realizes that this is a place where
the language has said "this function may or may not due a tailcall,
with far reaching bizarrely different results".

Yes, yes, the language does say it's undefined and anyone who reads it as
being defined is just confused, but I daresay that's most users, each of
whom is now doubt oblivious to the underlying issue and will defend to the
death the uniqueness of his own implementation's way of handling it.

~~~~~~~~~

For myself, I agree with what I perceive to be Alan's position: That
this thing doesn't have to be specified formally, as long as it's
clear.  BUT that the word really does pop out of nowhere and requires
some auxiliary text to really understand by someone who isn't part of
the `in club' and is merely "an intelligent reader unaware of the
issue but otherwise capable of understanding it".  A little bit more
English would seem sufficient to me.  Let someone (Will, for example)
publish an auxiliary paper we can reference to clarify the
significance if it becomes a matter of more concern than that...