[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
requiring proper tail recursion
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
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
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.