Re: proper tail-recursion proposal

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

   Date: Fri, 09 Jan 1998 09:18:18 -0500
   From: William D Clinger <will@ccs.neu.edu>
   References: <199801091049.FAA03524@kima.nj.nec.com>

   I think it would be better to say "active tail calls" instead
   of "pending tail calls".  To me, the word "pending" makes it
   sound as though the call has not yet been made.

Right.  "Active" is much better.

   I also think that the second and third sentences of the second
   paragraph of Kelsey's proposed revision of the rationale are not
   technically correct.  The problem with

   > An alternative would be to have
   > one or more iterative primitive expressions (make DO a primitive
   > expression instead of a derived expression, for example).

   is that, given Scheme's historically important support for the
   CPS idiom, making the iteration constructs primitive instead of
   derived is not a true alternative, because not all CPS programs
   can be translated into Scheme's iteration constructs, nor indeed
   into any conventional set of iteration constructs.

Making iteration constructs primitive is a true alternative for
language designers.  Doing so is less expressive.  For example,
it makes using using a CPS idiom harder.  The original Scheme
authors chose to go with proper tail recursion instead.

The rationale was not meant to explain why we don't switch back to
primitive iteration constructs now, but to explain why the original
designers didn't choose them in the first place (I'm guessing of
course; they might have gone with proper tail recursion simply
because it is a clever idea).

   There are two problems with

   > Requiring
   > proper tail-recursion gives the programmer greater flexibility at the
   > cost of greater conceptual overhead (witness the length of this section)
   > and implementation complexity.

   The first is that proper tail recursion does not actually entail
   additional implementation complexity.  This can be seen by comparing
   the code for a properly tail recursive interpreter with that of an
   improperly tail recursive interpreter, especially one that also
   supports the primitive iteration constructs that would be required.

Yes, if the only thing that is important is proper tail
recursion.  In the Scheme implementations I am aware of there
is additional code and complexity to implement proper
tail-recursion in conjunction with other features.

   The second problem with the sentence above is that the only reason
   for the greater conceptual overhead is that we are now trying to
   say something about the space efficiency of procedure calls, of
   which most language standards say nothing.

The reason we are working so hard to say something about the
space efficiency of procedure calls is that we use them to
express iteration.  If we used some other construct for iteration
we would care a lot less about proper tail recursion.

   The R5RS doesn't need to apologize for proper tail recursion.
   It just needs to explain it.

Comparing it to widely-used alternatives is not an apology.

                               -Richard Kelsey