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

[Michael Sperber <address@hidden>]

>>>>> "Pascal" == Pascal Costanza <costanza@iai.uni-bonn.de> writes:

Pascal> Michael Sperber wrote:
>> Tail recursion is a pretty fundamental semantic property, and it sure
>> isn't about "efficiency."  (And, as such, it's anything but
>> specialized.)  I'll leave it to Shriram to yell at you some more :-)

Pascal> I didn't have general tail recursion in mind but "proper tail
Pascal> recursion" as required by Scheme.

So did I.  Sorry for omitting the "proper."

Pascal> This is a specialized feature because it is not widely found
Pascal> in other languages. It ensures space efficiency.

It ensures expressibility, and once again, it's a fundamental property
of the semantics.  Scheme just gives that property its due.  The fact
that most other programming languages don't have proper tail recursion
is a mistake.

Pascal> Why should it be important to cover all cases? 
>> Because you may not be able to write the program you need if you
>> don't.

Pascal> Such a reasoning would rule out all program analysis tools because
Pascal> there is a very important class of program properties that you
Pascal> provably cannot express. Still, program analysis tools are being
Pascal> written, and they are useful.

I don't see what this had to do with anything.  Where does program
analysis come in all of a sudden?

Pascal> The same holds for iteration: You may not be able to cover important
Pascal> cases, but this doesn't mean that you shouldn't include them for the
Pascal> cases you _can_ cover.

So ... ermh ... yes.  I never said any different.  Neither did Matthias.

Pascal> Note that I don't argue for reclacing recursion by iteration. That
Pascal> would be stupid.

One again, iteration is a special case of recursion.  In a lot of
cases, replacing (non-iterative) recursion by iteration makes perfect sense.

Pascal> I disagree. Programming language design should not be purely based on
Pascal> the mathematical aesthetics of simplicity and generality. Programmer's
Pascal> convenience is also important.
>> This isn't anything to agree or disagree on: It's a fact.  Exposing
>> iteration in a form that doesn't utilize explicit calls (looping
>> forms, that is) is a different matter.  You need to adjust your use of
>> terminology.

Pascal> I don't get this. I think that loop expressions makes programming more
Pascal> convenient, so in my view these things are clearly related.

You are just not reading what Matthias and I are writing.  You're
talking about "convenience," while Matthias and I are talking about
principles and terminology.  You're using the terminology in a wrong way.

Pascal> In my example, what I want is to collect the cars of all elements in a
Pascal> list. I simply don't care whether this is achieved by iteration, by
Pascal> recursion, or by sending a rocket to Mars and blowing it up. And the
Pascal> LOOP implementation explicitly tells me: "for all elements in the
Pascal> list, collect their cars." How can this be any clearer?
>> By explaining what you mean by "collect."  And by writing down the
>> order of the collection.  Try writing down solutions where the
>> accumulating operation isn't cons, but, say +, and, or -.  This should
>> be a matter of simple replacement, right?

Pascal> (loop for i in list sum i)

Pascal> (loop for i in list sum (- i))

Pascal> However, (apply '+ list) or (apply '- list) are more appropriate in
Pascal> this regard. (In the case of - you get different results, but this is
Pascal> because of the way - is defined.)

So what about AND?

And how do you know this has the same associativity behavior?

-- 
Cheers =8-} Mike
Friede, Völkerverständigung und überhaupt blabla