A new module for performing tail-call elimination

[Antoon Pardon]

On 07/16/2015 01:11 PM, Chris Angelico wrote:
> 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.

Once again, the intend of the example is ignored. The question was
not about how tail call optimization could be done on this specific
example. The question was about how it could be done generally and
this example was just used as a vehicle to get the question more
easily explained.
 

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

But that is not a similar question. A similar question would have been
if someone would have trouble with making comparing items somehow
parametric is his function. So he writes a bubblesort to illustrate
that he somehow wants to specify on call time how items get compared.

And what happens is that lots of people start critisizing the bubble sort
and ignore the actual question, even though the question was not about
bubble sort. Bubble sort was just used as a vehicle to easily explain
the question. 

> Before looking at code improvements or language improvements, it's
> crucial to do algorithmic improvements.

But we were not looking at code improvements here. We were looking
at how to use a particular module. 

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

Which are all beside the point. The intent of the even and odd functions
was not to actually use them in production, but as a vehicle to ask someone
on how to use his module. For anyone in this context to seize upon the
particular implementation of those functions, is just making it clear
he completly missed the specific intend and used these examples to get
on his high horse.

>  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 depends on the purpose. When the purpose is to learn something, it
may be usefull to spend time on code unfit for production, because such
code is often more comprehensible than code for which tco would be actually
useful. So here you are critisizing code meant to learn something, because
it isn't useful.

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

These functions were not intented to provide such an example. I also
think that was rather clear. So critisizing them because they are not
is just disingenuous.

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

Of course they could be rather trivially reimplemented. They would
also become rather ugly and less easy to comprehend.

Here is one way to do the odd, even example.

def even(n):
    return odd_even('even', n)

def odd(n):
    return odd_even('odd', n)

def odd_even(fn, n):
    while fn is not None:
        if fn == 'even':
            fn, n = (None, True) if n == 0 else ('odd', n - 1)
        elif fn == 'odd':
            fn, n = (None, False) if n == 0 else ('even', n - 1)
        else:
            raise ValueError("Unknown state: %s" % fn)
    return n

Any collection of functions that tail calls each other can rather
trivially be turned into a state machine like the above. You can
just paste in the code of the individual functions and replace
the return call combo's with an assignment indicating which 'function'
is to be 'called' next and its arguments.
    
-- 
Antoon Pardon