A new module for performing tail-call elimination

[Chris Angelico]

On Thu, Jul 16, 2015 at 11:35 PM, Antoon Pardon
<antoon.pardon at rece.vub.ac.be> wrote:
> 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.

That's not an algorithmic change, though. That's just a mechanical
change, and a poorly-written one. My point was that I have yet to see
anything that demands TCO and can't be algorithmically improved. The
best so far has been a quicksort that uses TCO to guarantee a maximum
on stack usage.

ChrisA