why tail recursion matters and why Java isn't it, was Re: lisp performance was Re: problems with lisp

[Matthias Felleisen <address@hidden>]

On Tuesday, September 2, 2003, at 05:54 PM, Ken Anderson wrote:

 > I don't believe you need a fundamental rewrite in Lisp any more often 
then you do
 > in another language.

> Generally, write your Lisp (or any other language really) in a clear 
> straight forward manner.  When you have a performance problem, use a 
> profiler to find out where it is.  Don't guess, not even if you're an 
> expert.  The 80/20 rule means you have to address performance, but 
> most of the code can ignore it.

Ken,  with all due respect, this is not right. Unless your functional 
or object-oriented
language (including Python) doesn't impose uniform tail-call 
optimizations (TCO),
you can't get away without a fundamental rewrite.

What truly bothers me is that pl researchers and ll workers just don't 
get this
insight. There are two kinds of traversals for data (including natural 
number):
  - those that follow the structure
     (that's the essence of OOP dispatch, to call methods only;
     loops are *not* OOP per se, though you can fit them in via 
iterators;
     for the contrary, see Java)
  - those that generate new data before they recur.
There is nothing else.

For the first, you can add 127,341 looping constructs because you 
believe
your programmer-clients won't understand recursion. But you will never 
cover
all cases. You will only do so if your language has TCO and you can
use your goto-with-parameters (aka tail calls) to match the 
gotos-in-data
(aka references).  You will always have to squeeze your program 
structure
into some unnatural looping structure to get decent performance for the 
first
time around.

-- Matthias