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

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

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 
  - 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 
     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 
your programmer-clients won't understand recursion. But you will never 
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 
(aka references).  You will always have to squeeze your program 
into some unnatural looping structure to get decent performance for the 
time around.

-- Matthias