Re: tail recursion proposal

[Jeff Dalton <jeff@aiai.ed.ac.uk>]

>    Date: Thu, 8 Jan 1998 23:25:15 GMT
>    From: Jeff Dalton <jeff@aiai.ed.ac.uk>
>
>    ...
>    
>    With optimized tail calls, ordinary tail calls, not used to
>    implement any loop whatsoever, do not leave proper stack debugging
>    information.  Loops are not the whole story.
>    
>    ...
> 
> Forgive me for jumping in at this particular message, Jeff;
> I don't mean to pick on you personally, BUT...  I have to say that
> I *still* disagree sharply with the notion that space-efficient
> handling of tail-recursion is an "optimization" and with the notion
> that always retaining "stack debugging information" is "proper".

Actually, I pretty much agree with what I take to be the main points
of your message.  For instance, your view of goto as an "impoverished
function call" seems fine to me, perhaps because I read those Scheme
papers from the 1970's back in the 1970's; and I agree that

  the Scheme language definition should require (or at least strongly
  advocate) that implementations not accumulate unbounded state for a
  tail-recursive loop.

But I also agree with KMP, and I thought "proper" was a game two could
play.  (More on this below.)

I would have stayed out of this if not for Matthias's somewhat
tendentious way of making his point about loops, which seemed to
be saying that there was no debugging issue at all, because
loops and proper tail recursion were alike in not leaving 
debugging information on a stack -- as if last call optimization
affected only cases that would be written as loops.

(I suppose an implementation might optimize tail calls only in
recursive cases, but some implementations will treat all tail
calls as parameterless gotos, we might say, and optimize them all.
I'm not sure which the RnRS intends to require, but either way
more cases are affected that would otherwise be written as loops.)

I have persisted in talking of "optimization", but because I think
that helps make it clear what I am talking about, not because I
think that's the best ways to express it in the report.

Anyway, I don't think anyone is arguing that Scheme should not
require space-efficient tail-recursion.

It seems to me that KMP has long held the view that there can be more
than one more or less equally good way for a programming language to
do things and that, while Scheme's way is a good way, it is not the
only good way.  That's a view I happen to agree with.  In any case,
the things KMP has said about tail recursion seem to me a natural
consequence of such a view.

> (c) The need to avoid saving arbitrarily large amounts of state during
> a computation is, I think, undisputed.  The need to save some information,
> judiciously, for debugging purposes, at least as an option, is, I think,
> also undisputed.  But it ought to be an orthogonal option.  To insist
> as a point of language design that "goto" be properly tail-recursive
> but that "function call" NOT be properly tail-recursive is to conflate
> two distinct concerns for no good reason; better to separate the concerns
> and give the programmer more choices.

But a language definition could not _require_ that either be
"properly tail recursive" (and since Scheme doesn't have goto one case
doesn't arise).  Eliminating the procedure call tail-recursion
requirement from the Scheme definition would be one way to allow
the concerns to be separately addressed.  And since that would 
allow a greater range of conforming Scheme implementations, it
would arguably increase programmer choice.  So this item seems
to cut both ways.

It might even be argued that requiring "proper tail recursion"
involves a confusion between language and implementation, and
even environment (for it says, in effect, that certain forms of
debugging support cannot be provided).  Those who think that something
significant follows from "debugging information" being "a programming
environment issue" might want to consider this.

By the way, I am somewhat saddened to find what seems to be a firmly
established presence in the Lisp world of the the idea that there are
fairly rigid language / environment (and / library) divisions that
ought to be respected, as if they did not represent only one
reasonable way of doing things and instead had something like the
force of natural law, as if, perhaps, God had established these
divisions at the creation and decreed that, on pain of humiliating
market failure, no language definition could fail to obey them.

It was not always thus.

-- jd