[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.