Path: csiph.com!optima2.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!1.eu.feeder.erje.net!newsfeed.xs4all.nl!newsfeed8.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <55A7B309.8080903@rece.vub.ac.be>
References: <55a3dcd9$0$3024$426a34cc@news.free.fr> <mailman.532.1436952589.3674.python-list@python.org> <55a76628$0$2846$c3e8da3$76491128@news.astraweb.com> <55A78A42.4090506@rece.vub.ac.be> <CAPTjJmr4TJuMpgPm_cuMo_eM-xuNfgyLbTFvqA36mFvpNxQ1UA@mail.gmail.com> <55A7B309.8080903@rece.vub.ac.be>
Date: Thu, 16 Jul 2015 23:47:59 +1000
Subject: Re: A new module for performing tail-call elimination
From: Chris Angelico <rosuav@gmail.com>
Cc: "python-list@python.org" <python-list@python.org>
Content-Type: text/plain; charset=UTF-8
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.582.1437054482.3674.python-list@python.org>
Lines: 36
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:93927

On Thu, Jul 16, 2015 at 11:35 PM, Antoon Pardon
<antoon.pardon@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