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

[Pascal Costanza <address@hidden>]

You seem to suggest that recursion is always the most "natural" solution 
but that's just not true. In many cases, an iteration expresses much 
more clearly the intention of a programmer. Here are three Common Lisp 
versions of an example of a collector I repeatedly need in a current 
project:

(loop for element in list
       do collect (car element))

(defun collect-elements (list)
   (unless list
     (cons (caar list) (collect-elements (cdr list)))))

(reduce 'cons list :key 'car :from-end t :initial-value nil)

I am strongly convinced that the first version is objectively the best 
because it is much simpler and direct than the others. For the recursive 
version you even need to define a function. (Unless you want to use a Y 
combinator instead, of course.)

I don't need a "fundamental rewrite" here to get efficient code, because 
the straightforward version already produces efficient code.


Pascal


Matthias Felleisen wrote:
> 
> 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 
> 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.
> 
> 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. 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.
> 
> -- Matthias
> 


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