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

[Matthias Felleisen <address@hidden>]

On Wednesday, September 3, 2003, at 01:11 AM, Peter Seibel wrote:

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

To understand how program design truly works, you need to go "pure".

Consider OOP. All you get when you compute are objects:
  - you can create them
  - you can send messages to them.
That's it. The messages can carry along data, which means you can send
objects along. I don't see loop in there. I do see recursion 
everywhere, however,
because an object can send a message to an object of the same class. 
Indeed,
if you want to represent anything of arbitrary size, you need to define 
the class
hierarchy in a recursive manner. That's particularly true for natural 
numbers.

So now you can ask, where do loops come in? What kind of message is a 
loop?
Do you ever write
   someArrayObject.loop_over_all(...)
I do but these kind of loops are iterators like map, for-each, andmap, 
filter, reduce,
etcetc. And they are great. But these loops are abstractions over 
recursion.

Now imagine a complex class hierarchy. If you have TCO, you get looping 
behavior
along a spine for free in the "natural" (this is a well-defined term 
here) program design.

But if you don't have TCO, you need to stand on your head and look for 
some way to
squeeze your problem into one of the three looping constructs that the 
language
provides.

-- Matthias