Re: requiring proper tail recursion

[hbaker@netcom.com (Henry G. Baker)]

> I accept Guy's definition as a fair re-casting of what I wrote,
> although I do lamentably have one philosophical quibble lingering:
> 
> Prior to the assertion that the tail call must be optimized / must not
> be pessimized, the choice to not do the thing Scheme does is value neutral.
> 
> It is only once you require that the language do the optimization /
> not do the pessimization that you find it very strongly important that
> implementations support this.

I don't completely understand why I was copied on this message, except
for perhaps my posting to comp.lang.scheme regarding the need for a
precise mathematical definition of 'tail-recursion' and
'tail-calling'.

There are at least two separate issues here.  One is how to define a
mathematical concept.  Another is how to deal with this concept in a
language standard.

Since I would hope that these concepts regarding tail-calling and
tail-recursion can be made mathematically precise, for the first
purpose I don't think that it is a matter of proper English wording,
since a precise mathematical definition can be put into logical form
-- if necessary -- and English should have nothing to do with it.

Regarding what to do about the Scheme standard, I would
suggest/recommend that this precise mathematical concept be put to use
to describe conforming/non-conforming implementations.  I have gone on
record elsewhere as decrying the use of English for programming
language standards, for exactly the same reasons why mathematicians in
the 20th century gave up on English for describing mathematics.  So I
won't reiterate that argument here.

Re iteration equivalent to tail-calling: This is _not_ true.  As
anyone who has tried to implement proper tail-calling in a
'stack-oriented' language already knows, 'while' loops _ain't good
enough_.  In C one reason is that you can only jump locally, whereas a
call allows you to make a call to a global entity -- that's why
Scheme2C doesn't work so well.

I have already been asked to put my $0.02 into the Java standard
requesting the ability to do tail-calling there.  However, the obvious
place to start looking for guidance is Scheme, and Scheme doesn't have
its act together on this issue yet.  So I don't think that anyone in
the Java community is going to listen until Scheme can say with more
authority what it is talking about.  Considering the mathematical
goals of some Scheme purists, I think that this inability to be
precise about the meaning of tail-calling should be embarrassing.

I have thrown down the gauntlet on this issue in my
Garbage-In/Garbage-Out column:

ftp://ftp.netcom.com/pub/hb/hbaker/sigplannotices/gigo-1997-03.html

The program snippets in this paper provide some counter-examples for
some hypotheses -- showing, e.g., that beta-reduction can in some
cases _kill_ the property of tail-calling.

(I don't consider the issue of debugging to be the controlling issue
here; debugging is for finding errors in programs, but it should never
keep you from writing a program in the first place -- that's the job
for type systems.)

-- 
Henry Baker
www/ftp directory URL:
ftp://ftp.netcom.com/pub/hb/hbaker/home.html