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

Re: proper tail-recursion proposal

I think it would be better to say "active tail calls" instead
of "pending tail calls".  To me, the word "pending" makes it
sound as though the call has not yet been made.

I also think that the second and third sentences of the second
paragraph of Kelsey's proposed revision of the rationale are not
technically correct.  The problem with

> An alternative would be to have
> one or more iterative primitive expressions (make DO a primitive
> expression instead of a derived expression, for example).

is that, given Scheme's historically important support for the
CPS idiom, making the iteration constructs primitive instead of
derived is not a true alternative, because not all CPS programs
can be translated into Scheme's iteration constructs, nor indeed
into any conventional set of iteration constructs.

There are two problems with

> Requiring
> proper tail-recursion gives the programmer greater flexibility at the
> cost of greater conceptual overhead (witness the length of this section)
> and implementation complexity.

The first is that proper tail recursion does not actually entail
additional implementation complexity.  This can be seen by comparing
the code for a properly tail recursive interpreter with that of an
improperly tail recursive interpreter, especially one that also
supports the primitive iteration constructs that would be required.

The second problem with the sentence above is that the only reason
for the greater conceptual overhead is that we are now trying to
say something about the space efficiency of procedure calls, of
which most language standards say nothing.

How many language standards bother to say that the space required
by procedure calls is bounded by that used in a conventional stack
implementation?  Do you really think this would be any easier to
state precisely, without appealing to implementation-specific data
structures, than Scheme's requirement for proper tail recursion?

The R5RS doesn't need to apologize for proper tail recursion.
It just needs to explain it.