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> You seem to suggest that recursion is always the most "natural"
 > Pascal> solution but that's just not true. In many cases, an iteration
 > Pascal> expresses much more clearly the intention of a programmer. 
Here are
 > Pascal> three Common Lisp versions of an example of a collector I 
repeatedly
 > Pascal> need in a current project:
 >
 > Pascal> (loop for element in list
 > Pascal>        do collect (car element))
 >
 > Pascal> [...]
 >
 > Pascal> I am strongly convinced that the first version is objectively 
the best
 > Pascal> because it is much simpler and direct than the others. For the
 > Pascal> recursive version you even need to define a function. (Unless 
you want
 > Pascal> to use a Y combinator instead, of course.)
 >
 > Pascal> I don't need a "fundamental rewrite" here to get efficient code,
 > Pascal> because the straightforward version already produces 
efficient code.
 >
 > It seem pretty far-fetched to me to call this code "straightforward"
 > or "direct":  You're relying on a very specialized feature of the CL
 > LOOP macro here to get your work done.


This doesn't prove anything. In Scheme you're relying on a very 
specialized feature of tail calls to be sure that your code is efficient.

In both cases, you have to know the languages well to get your work done 
to your satisfaction. In the Common Lisp case, I have at least three 
options to express my intent - one of them is straightforward, the other 
two are not.

 > The less you know about LOOP,
 > the harder it is to understand your code.  (How do I know, for
 > example, that your actually consing up the result, and not, say,
 > adding it up?)


...because you know. ;)

 > Matthias's point is that, while you can handle some special cases with
 > special constructs, as in this case, you can't cover all of them with
 > a finite number of constructs.


Why should it be important to cover all cases? When LOOP expressions get 
too complicated it's a good indication that your program design is 
broken. In other words, it's sufficient to cover the important cases. 
(The problem with a good design of a LOOP construct is to get a good 
sense what the important cases are.)

 > ... and, of course, I can't resist pointing out that iteration is a
 > special case of recursion.  So the terms you use are inappropriate.
 > Matthias is talking about *looping constructs*, not iteration.
 > Recursion is not always the most "natural" the solution---in the
 > spectrum you describe, it's always the *only* solution.


I disagree. Programming language design should not be purely based on 
the mathematical aesthetics of simplicity and generality. Programmer's 
convenience is also important.

To put it differently, it's important for what purposes your language is 
designed. If you want to mainly prove properties about languages then 
recursion is enough. If you want to be able to clearly express your 
intentions then it's not.

In my example, what I want is to collect the cars of all elements in a 
list. I simply don't care whether this is achieved by iteration, by 
recursion, or by sending a rocket to Mars and blowing it up. And the 
LOOP implementation explicitly tells me: "for all elements in the list, 
collect their cars." How can this be any clearer?

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)