requiring proper tail recursion

[William D Clinger <will@ccs.neu.edu>]

The Scheme standards should be clear concerning what is
required of implementations and can be relied upon by
programmers.  The existing standards require proper tail
recursion without defining it; that was ok so long as
well-informed readers of the documents knew what was meant
or could learn what was meant by consulting sources that
were referenced by the standards.

The role of the standard is to provide enough technical
guidance so that men and women of good will can base their
discussion on technical issues.  It does not need to be so
airtight as to rule out perverse interpretations.

No standard can be phrased so tightly as to eliminate all
possible perverse interpretations of it.  Ultimately an
implementor's freedom to interpret the standard perversely
is constrained by his/her users, and the users' freedom to
interpret perversely is constrained by their choice of
available implementations.

So I think the real problem is to define proper tail recursion
in a way that will make the concept comprehensible to a larger
audience.  There are three main approaches:

  1.  Define proper tail recursion as passing the same
      continuation for a syntactically tail-recursive call
      that was passed to the procedure corresponding to the
      innermost lambda expression within whose body the call
      appears.
  2.  Define proper tail recursion in terms of the asymptotic
      space used by continuations.
  3.  Define proper tail recursion using a more general notion
      of safe-for-space, relying on the fact that any
      implementation that is safe-for-space must also, in the
      large, be properly tail recursive in senses #1 and #2.