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

[Pascal Costanza <address@hidden>]

Michael Sperber wrote:
>>>>>>"Pascal" == Pascal Costanza <costanza@iai.uni-bonn.de> writes:
> 
> 
> Pascal> Michael Sperber wrote:
> 
> Pascal> In Scheme you're relying on a very specialized feature of tail
> Pascal> calls to be sure that your code is efficient.
> 
> 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 :-)

I didn't have general tail recursion in mind but "proper tail recursion" 
as required by Scheme. This is a specialized feature because it is not 
widely found in other languages. It ensures space efficiency.

So I think my statement quoted above makes sense.

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

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

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

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

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

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

Or am I missing something?

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

(loop for i in list sum i)

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

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


Pascal

-- 
Pascal Costanza               University of Bonn
mailto:costanza@web.de        Institute of Computer Science III
http://www.pascalcostanza.de  Römerstr. 164, D-53117 Bonn (Germany)