Re: requiring proper tail recursion

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

   Date: Mon, 2 Jun 97 14:31:50 -0700
   From: Morry Katz <katz@quilty.Stanford.EDU>
   To: will@ccs.neu.edu
   Cc: 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
   ...
   
   I find this paragraph difficult to read.  As such, I feel that those
   who are less knowledgable will find it opaque.   Might I suggest
   something like the following?  the second sentence is still too
   unwieldy for a final product, but I think the following version is a
   little easier to understand.
   
        Implementations of Scheme are required to be properly
        tail-recursive.  Any procedure applications appearing in another
        procedure having the property that whatever value is returned by
        the applied procedure will in turn be returned by the procedure in
        which the application appears is said to be in a tail position.
        The important feature of procedure applications in tail position
        is that the stack frame for the calling procedure is unneeded once
        the call has been made.  An implementation is said to be properly
        tail-recursive if it in effect arranges for the result of a
        tail position call to be returned directly to the continuation
        that was passed to the procedure that contains the tail position
        call, instead of being returned to the calling procedure.
        Proper tail-recursion allows iteration to be efficiently
        expressed using ordinary procedure-call mechanics.  Special
        iteration  constructs become useful only as syntactic sugar.
        
Unfortunately, the second sentence is not merely unwieldy, but wrong.
That the value returned be the same is too strong a condition for
requiring tail-recursion.

--Guy