A new module for performing tail-call elimination

Chris Angelico rosuav at gmail.com
Thu Jul 16 13:11:16 CEST 2015


On Thu, Jul 16, 2015 at 8:41 PM, Antoon Pardon
<antoon.pardon at rece.vub.ac.be> wrote:
>> Fixing the obvious mistake (failing to return anything) leads to the next
>> mistake. When all you have is a hammer, everything looks like a nail.
>>
>> def even(n):
>>     return n%2 == 0
>>
>> def odd(n):
>>     return n%2 != 0
>>
>>
>> are faster, easier to understand, and don't turn into an infinite loop if
>> you pass a negative integer.
>
> Nice of you to illustrate how being pedantic about something, can
> make a response useless with regard to the intended original question.
>
> Sure your implementation for solving this particular problem is better
> if the purpose is to actually solve this problem. But it is useless as
> an illustration for the question I'm asking, which was about how to
> use a particular module.

Once again, tail call optimization is used as a way to make something
more efficient that shouldn't need to be done at all.

"Bubble sort takes too long when I give it 1000 elements. How can I
make it faster?"

Before looking at code improvements or language improvements, it's
crucial to do algorithmic improvements. The recursive even() and odd()
functions are O(n), the modulo ones are O(1). Bubble sort is simply a
terrible way to sort long lists. Time spent optimizing bubble sort is
time utterly and totally wasted, because you'll get more benefit by
switching to quicksort, insertion sort, or a hybrid like Timsort. Time
spent eliminating tail call stack frames is equally useless if a small
algorithmic change can eliminate the recursion altogether.

That's why we need examples that *can't* be trivially reimplemented
some other way.

Unless, of course, *all* TCO examples, even real-world ones, could be
trivially reimplemented some other way, a theory which is gaining
currency...

ChrisA


More information about the Python-list mailing list