[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
Michael Sperber wrote:
>>>>>> "Pascal" == Pascal Costanza <firstname.lastname@example.org> 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.
> Pascal> three Common Lisp versions of an example of a collector I
> 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
> Pascal> because it is much simpler and direct than the others. For the
> Pascal> recursive version you even need to define a function. (Unless
> 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
> 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 Costanza University of Bonn
mailto:email@example.com Institute of Computer Science III
http://www.pascalcostanza.de Römerstr. 164, D-53117 Bonn (Germany)