Re: requiring proper tail recursion

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

   From: Kent Pitman <kmp@harlequin.com>
   Date: Mon, 2 Jun 97 18:14:23 EDT
   To: katz@cs.stanford.edu
   Cc: will@ccs.neu.edu, rrrs-authors@martigny.ai.mit.edu, hbaker@netcom.com,        
jgm@cs.cornell.edu, matthias@cs.rice.edu, shriram@cs.rice.edu,        will@ccs.neu.edu
   Subject: requiring proper tail recursion
   
   Here's my go at the same, building from Katz's rewording with other 
   major changes (explained below):
   
     When a procedure p1 with continuation k1 is to be called from a point
     within the definition of a procedure p2 with continuation k2,
     and when the only observable actions or effects that remain to be
     accomplished upon return to k1 is to yield values and control directly to k2,
     then the point of call of p1 is said to be a <I>tail position</I> within p2,
     because the continuation k2 can be correctly substituted for k1 as the
     continuation of p1, and the call to p1 is said to be a <I>tail call</I>.
   
     The effective substitution of the continuation k2 for the continuation
     k1 prior to the call to p1 is called <I>tail call optimization</I>.  This is
     an important optimization because it means that only continuations
     where there is a semantically important action still remaining to be
     done upon return will be remembered.  In particular, tail recursive 
     function calls which effectively implement iteration will not accumulate
     unnecessary continuations if tail call optimization is reliably used;
     informally, they will not ``consume stack''.
   
     Implementations of Scheme are required to reliably detect function calls
     from a tail position and to perform tail call optimization.

I like it, but would be inclined to go at it from a slightly different point
of view:

  When a procedure p1 is to be called from a point within the definition of
  a procedure p2 that has been called with continuation k, and when the only
  observable actions or effects of p2 that remain to be accomplished after
  execution of p1 is to yield control directly to k, passing it exactly the
  value(s) yielded by p1, then the point of call of p1 is said to be a
  <I>tail position</I> within p2, continuation k itself should be used as the
  continuation of p1, and the call to p1 is said to be a <I>tail call</I>.

  The effective substitution of some other continuation k2 for the continuation k
  in the call to p1 is called <I>tail call pessimization</I>.  This is
  an extremely detrimental pessimization because it effectively prevents
  the use of tail calls to implement iteration, a widely used and
  well-loved programming idiom in the Scheme language.  Tail call
  pessimization will cause an iteration so programmed to accumulate
  unnecessary continuations; informally, they will unnecessarily ``consume stack''.

  Implementations of Scheme are required to reliably detect function calls
  from a tail position and to avoid tail call pessimization.
  
--Guy