[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: tail recursion proposal
I frequently run across Scheme refugees who are confused by an
expectation that all programming languages will support tail recursion
as Scheme does. Indeed, it's a common source of programming error for
Common Lisp users who used to be Scheme people and who are often
unable to express themselves iteratively using a "loop" notation, and
so end up blowing out of stack space. (Always ironic, to me, because
I thought the original point of the tail recursion exercise was to
give programmers flexibility about expression, not to trade one form
of dogma for another... I would feel more sympathetic toward them if
they knew what a loop was and were just grumbling about the expressive
inconvenience, but they often look at me with a stare like there is
something dirty or unhealthy or even just plain unknown about "loop"
constructs.) Anyway, I trace the cause of this inflexibility on their
part partly to the fact that I think S&ICP and its followers apparently
spend too little time on the "alternatives" part, but I trace THAT, in
turn, to this part of the Scheme spec which simply and without explanation
requires a certain behavior.
Now that we're going to spend time explaining things a little, I take
some specific issue with the following paragraph, which I consider
central to the issue. It appears to express a universal truth instead
of a design trade-off. And that, I think, is a shame.
| Proper tail-recursion is important because it allows iterative
| computations to be expressed efficiently, reliably, and portably
| using ordinary procedure calls.
I think the design trade-off is certainly one made by Scheme but it is
not the only legitimate such choice, and I would prefer to see wording
that did not fill the reader's head with Scheme-centric propaganda.
I also think the funny little list of adverbs here is odd in that they
really wants to be combining, not modifying expressed in a free-standing
way. There is nothing inherently "unreliable" or "unportable" about the
expression of a procedure in this way. What is unreliable or unportable
is only the space-efficiency. The minimal fix to this paragraph's complaint
| Proper tail-recursion is important in Scheme because it allows
| iterative computations to be expressed using ordinary procedure
| calls with a space efficiency that is portably reliable.
But I would prefer more elaborated text, such as:
| The requirement to support proper tail recursion implicitly thwarts
| some techniques for ``stack debugging'', since if an error occurs,
| the chain of active continuations will have lost information about
| how the computation reached the present state. This was a
| consciously made design trade-off. Proper tail-recursion has
| traditionally been important in Scheme because it allows iterative
| computations to be expressed using ordinary procedure calls with a
| space efficiency that is portably reliable. Also, sufficient
| techniques are believed to exist so that it is usually possible for
| an implementation to compensate heuristically for the would-be loss
| of debugging power.