[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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.

Here are my notes about why I chose this approach:

 - I don't like calling the Scheme implementation "tail recursive".  Scheme
   implementations presumably contain portitions that are tail recursive 
   and other portions that are not.  Calling the whole implementation tail 
   recursive seems imprecise to me.

 - I don't like this being one big monolithic paragraph.  There are several
   concepts introduced, and I think they should be introduced one at a time.
   Once the terms are built up, I think making the requirement is ok.

 - I expect a firestorm of complaining over the use of the word `stack'.
   Maybe I'll be pleasantly surprised.  I prefer to use such metaphors because
   I think such abstractions give people a useful handhold when they are coming
   from other backgrounds.  I get jumped on a lot for using a stack metaphor
   when talking about Scheme because people apparently think I've forgotten
   that it's not a strict stack; personally, I think the people who are so 
   quick to jump on me have forgotten that even a metaphor that has a flaw can
   be a powerful way to reason and express even when not speaking rigoruously.
   The remark here is intended to allow someon whow is just barely reading
   along to confirm that something he may have strong knowledge of in another
   domain is in fact what is being discussed here.  To not offer that handhold
   seems to me to be impolite.

 - I'm not wedded to the term "tail call optimization".  I've heard it
   called "tail call elimination".  Another term could be made up.  But
   I would like to see a separate name for the concepts I've called
   "tail recursion" (which I assume people understand),
   "tail position" (which I assume is a subconcept of tail recursion we're
   giving a name to in this context but that has been learned elsewhere),
   and "tail call optimization" (which I assume is a name for an optimization
   not heretofore mentioned even though it may be familiar to many readers,
   and that we are basically just naming here).  These are all different
   things and need different names.