[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

tail calls [was: Vanishing MrEd]



Greg Pettyjohn wrote:

> Shriram once said in an email, that tail call optimization was "the most
> profound advancement in compiler technology"
> --- or something to that affect. (Please forgive, if I've misquoted, if it's
> important, I can dig and find the original mail.) 

I claim I'm being profoundly misquoted (-:.  Let me elaborate.

What I had tried to convey to Greg was that I thought Scheme's design
had a certain "just so" flavor to it.  Two things, in particular, mesh
together delectably: closures and tail calls.  Either one without the
other would be much less effective.  Closures permit programmers to
bundle up computations, and tail calls allow a seamless transition
between computations, so they often work very closely together.

While people make a bug fuss about continuations and somewhat less of
one about closures, they often overlook the operation that makes these
bits hang together, which is the tail call.  As evidence, I bet if you
looked at survey-of-programming-language texts, few will even mention
tail calls, and even fewer will explain why it matters (beyond the
obvious, namely a means to implement loops).

I was also trying to explain to Greg why the tail *call* was
critical.  Too often people settle for tail recursion, or even assume
this is the important special case.  In fact, I don't think tail
recursion is very interesting at all.  Many times I'm happier writing
simple tail recursion with a special-purpose looping construct.  The
interprocedural tail call is the one I can't do without.  

When people sell tail calls through tail recursion (presumably because
they figure the average C/Java programmer will grasp this example more
easily), they get a response like, "Hey, I've used loops and never
missed this -- who needs it?"  The battle is lost before it has even
been joined.  I therefore think it's important that, if you're going
to try selling tail calls to someone from a loop-based programming
community, you should avoid bringing tail straight-recursion up at
all, or at least until the very end.  Otherwise you give one more
person who knew nothing about this topic at all the impression that
they understand it and are right to denigrate it.  (Arguably, the way
it's been presented to them, they *are* right to denigrate it.)

>						    I can explain to people
> how the simpler version works --- i.e. how a simple tail call is replaced
> with a goto and hence avoids using extra stack opperations. Can someone
> explain why this is so profound?

It's not the underlying semantics that is profound: it's the
programming styles that it engenders, *especially* in the context of
Scheme (or any other language with lexical closures).

Shriram