Re: tail recursion proposal

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

From: Jeff Dalton <jeff@aiai.ed.ac.uk>
Subject: Re: tail recursion proposal
Date: Thu, 8 Jan 1998 23:25:15 GMT

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

The issue should be reconsidered as follows: Either make space
requirements transparent throughout the language or drop the "proper
tail recursiveness" requirement.  But that has been said before by
other people, too.

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

Here is how one should look at the problem:

There are two ways of running the code of a function: 1. by an
"ordinary" function call that will leave plenty of stack debugging
information in many not-so-highly-optimizing implementations, and
2. by a GOTO to the beginning of the function.  The second method
leaves no stack debugging information around.

These two cases are easily distinguishable by syntactic inspection of
the program.  Most of the new proposal defines this syntactic
distinction.  Most programmers already had a good intuitive
understanding of it anyway.

Sure, tail-call elimination covers more cases than simple loops.  But
that does not mean that it is harder to understand.  Loops are indeed
not the whole issue, and that is exactly the point.  Tail-call
optimization not only turns programs back into loops that could have
easily been coded as loops in the first place -- it also can effectively
turn programs into loops where one would be hard-pressed to code them
as syntactic loops. (Just think of tail-calls to functions that were
passed in as parameters or that were fetched from data-structures.)

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

But such techniques do not work for non-straightforward loops, and
those can be interesting and important as well.

-Matthias