[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: requiring proper tail recursion
From: Kent Pitman <kmp@harlequin.com>
Date: Mon, 2 Jun 97 18:14:23 EDT
To: katz@cs.stanford.edu
Cc: will@ccs.neu.edu, 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
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.
I like it, but would be inclined to go at it from a slightly different point
of view:
When a procedure p1 is to be called from a point within the definition of
a procedure p2 that has been called with continuation k, and when the only
observable actions or effects of p2 that remain to be accomplished after
execution of p1 is to yield control directly to k, passing it exactly the
value(s) yielded by p1, then the point of call of p1 is said to be a
<I>tail position</I> within p2, continuation k itself should be used as the
continuation of p1, and the call to p1 is said to be a <I>tail call</I>.
The effective substitution of some other continuation k2 for the continuation k
in the call to p1 is called <I>tail call pessimization</I>. This is
an extremely detrimental pessimization because it effectively prevents
the use of tail calls to implement iteration, a widely used and
well-loved programming idiom in the Scheme language. Tail call
pessimization will cause an iteration so programmed to accumulate
unnecessary continuations; informally, they will unnecessarily ``consume stack''.
Implementations of Scheme are required to reliably detect function calls
from a tail position and to avoid tail call pessimization.
--Guy