[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> 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
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
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
> 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
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 Costanza University of Bonn
mailto:email@example.com Institute of Computer Science III
http://www.pascalcostanza.de Römerstr. 164, D-53117 Bonn (Germany)