Re: tail recursion proposal

[Guy Steele - Sun Microsystems Labs <gls@livia.East.Sun.COM>]

   Date: Thu, 8 Jan 1998 23:25:15 GMT
   From: Jeff Dalton <jeff@aiai.ed.ac.uk>
   Subject: Re: tail recursion proposal
   To: Matthias Blume <blume@cs.princeton.edu>, kmp@harlequin.com
   Cc: rrrs-authors@martigny.ai.mit.edu
   
   > I don't think that "stack debugging" and such are very good at
   > justifying a lack of proper tail recursion.  If programs use loops
   > where they would otherwise use tail recursion, then "stack debugging"
   > won't find a stack to debug either.  
   
   If that's the kind of thinking that results in the tail recursion
   requirement, perhaps the entire issue needs to be reconsidered.  ^_^
   
   With optimized tail calls, ordinary tail calls, not used to
   implement any loop whatsoever, do not leave proper stack debugging
   information.  Loops are not the whole story.
   
   Moreover, Lisp implementations that do not optimize all tail recusions
   often handle a subset of cases (in particular, tail self-calls) that
   will suffice for straightforward loops.

Forgive me for jumping in at this particular message, Jeff;
I don't mean to pick on you personally, BUT...  I have to say that
I *still* disagree sharply with the notion that space-efficient
handling of tail-recursion is an "optimization" and with the notion
that always retaining "stack debugging information" is "proper".

To see why, imagine a programming language such as PASCAL or C that
has a GOTO statement.  I come along and complain that all the compilers
perform "goto optimization" and fail to retain "proper goto debugging
information".  What I want, of course, is for the system to keep a
complete running log of every goto transfer, remembering where it
came from, in case I want to trace back and figure out what happened.

Before anyone complains that this is absurd, consider these three points:

(a) There have been systems, some hardware-supported, that maintained
exactly such logs.  (However, as an engineering tradeoff, the log was
typically implemented as a circular buffer, so that only the last N jumps
were remembered.)  Notable examples of such systems are the PDP-10 systems
at MIT in the 1970's; the AI KA10 remembered the last jump, and the MC KL10,
if I recall correctly, could remember the last 16 jumps.  (Historical
note: the AI KA10 was the computer on which Scheme was first implemented.)
Moreover, such hardware assisted me several times in tracking down some
perverse bugs in the MacLisp runtime system.

(b) A goto is merely an impoverished function call---see various Scheme
papers from the 1970's (ahem!)---that cannot pass arguments; therefore,
as Sidney Marshall observed, you have to use side effects to make a useful
loop.  If you have goto, there is still a great need to have function calls;
but if you have function calls, then goto is merely syntactic sugar for
a special case.  (In some languages, goto can also be syntactic sugar
for a non-local exit, so we might have to say "if you have function calls
and call/cc, then goto is merely syntactic sugar".)

(c) The need to avoid saving arbitrarily large amounts of state during
a computation is, I think, undisputed.  The need to save some information,
judiciously, for debugging purposes, at least as an option, is, I think,
also undisputed.  But it ought to be an orthogonal option.  To insist
as a point of language design that "goto" be properly tail-recursive
but that "function call" NOT be properly tail-recursive is to conflate
two distinct concerns for no good reason; better to separate the concerns
and give the programmer more choices.

Therefore I strongly support the notion that the Scheme language definition
should require (or at least strongly advocate) that implementations not
accumulate unbounded state for a tail-recursive loop, exactly as we would
expect a C or PASCAL definition to require (or at least strongly advocate)
implementations not to accumulate unbounded state for a goto loop.
I also strongly support the notion that Scheme implementations should
provide debugging options that allow retention of various kinds of additional
debugging state when desired.

--Guy