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

[Peter Seibel <address@hidden>]

Matthias Felleisen <matthias@ccs.neu.edu> writes:

> 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.

Assuming you wrote it recursively. Which, from what you write below I
guess you *do* assume. But as I tried to point out to Russ originally,
if you don't start with recursion it doesn't require a fundamental (or
any) rewrite to end up with a non-recursive solution.

> 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.

There aren't loops? That's sort of a strong statement--it seems clear
to me that a statement that strong is likely only true in certain
contexts. Can you explain in what context you mean that? Or am I
misunderstanding you in some more fundamental way?

> 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.

I must not be understanding you. What cases aren't covered by any of
the basic looping constructs provided by languages that don't provide
TCO? (E.g. DO in Common Lisp, while in Java, or, for that matter,
backward branches in assembly?)

> 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.

What's unnatural about looping? If I find certain algorithms easier to
think of in terms of a loop (do this, do that, then go back to the
beginning unless I'm done) what does that mean? That I'm a programming
illiterate? That I'm *really* thinking in terms of recursion but don't
know it because I've somehow trained my brain to unnaturally translate
my Platonic recursive ideas into an "iterative" form before they reach
my consciousness?

-Peter

-- 
Peter Seibel                                      peter@javamonkey.com

         Lisp is the red pill. -- John Fraser, comp.lang.lisp