Barry Margolin <barmar@bbnplanet.com> wrote:
+---------------
| >You can't effectively use continuation-passing style without
| >having tail recursion.
|
| Aye, there's the rub. I don't think most humans programmers use CPS
| directly.
+---------------
Not in the bulk of one's coding, no, but occasionally I find myself
quite naturally writing CPS code when I'm coding some sort of finite-state
machine (e.g., a lexical analyzer, a communications protocol, etc.).
When you consider that a tail call is really a "goto, with arguments",
a number of opportunities arise to employ it usefully. That is, the
fact that you can pass arguments with the goto partially negates the
disadvantage of the spaghetti-coding that gotos would otherwise encourage.
Or to say it another way: Dijkstra said that gotos were harmful; Wulf
asserted that mutable variables were exactly equivalent in harm to gotos
if you wrap a loop around the mutations; I now claim that for *either*
to harm you you really need both! Gotos hurt because you can get somewhere
with your global (or at least, shared-scope) variables set in who *knows*
what kind of shape; mutable variables (especially global ones) IN THE
PRESENCE OF LOOPS (iteration) have an isomorphic problem.
But by using goto-with-argument and *omitting* the shared-scope mutable
variables, the transfer of control is intimately tied to each change in
value bound to a lexical appearance of a variable. [Yes, I just realized
that I'm, rather awkwardly, describing functional programming, but I seem
to have come at it from an odd (to me) angle, and perhaps that angle might
be helpful to someone else as well...]
Finally, to circle back 'round again to the topic of "interative" versus
"tail recursive", the classic iterative solutions require mutable variables,
while the tail-recursive solutions don't *mutate* anything, they simply
create *new* bindings of the same names with the new values. For anyone who
has ever written a generational copying garbage collector, the difference
can be extremely significant! [For those not familiar, the key phrase is
"maintaining the remembered set" of objects in older generations which
point to newer generations...]
So, yes, there *are* (possibly rare) cases where the tail-recursive style
can be *more* efficient than the apparently-equivalent iterative style.
-Rob
[p.s. Apologies in advance: Back from sabbatical 11/2/98, but
until then email will still get a "vacation" bounce message...]
-----
Rob Warnock, 8L-855 rpw3@sgi.com
Applied Networking http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673
2011 N. Shoreline Blvd. FAX: 650-964-0811
Mountain View, CA 94043 PP-ASEL-IA