[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

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 

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


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)