A new module for performing tail-call elimination
rosuav at gmail.com
Thu Jul 16 15:47:59 CEST 2015
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)
> 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.
More information about the Python-list