A new module for performing tail-call elimination

Alain Ketterlin alain at universite-de-strasbourg.fr.invalid
Thu Jul 16 13:23:47 CEST 2015

Antoon Pardon <antoon.pardon at rece.vub.ac.be> writes:

> On 07/13/2015 05:44 PM, Th. Baruchel wrote:
>> Hi, after having spent much time thinking about tail-call elimination
>> in Python (see for instance http://baruchel.github.io/blog/ ), I finally
>> decided to write a module for that. You may find it at:
>>   https://github.com/baruchel/tco
>> Tail-call elimination is done for tail-recursion as well as for
>> continuation-passing style (cps) in a consistent syntax for both usages.
>> Any tail-recursive function having the suitable format for being
>> embeddable in the Y combinator can be used here with no change at all
>> (with the main difference that tail-calls will be eliminated), but other
>> continuations can also be added
> Can you explain how you would do mutual recursive functions?
> Suppose I start with the following:
> def even(n):
>     True if n == 0 else odd(n - 1)
> def odd(n):
>     False if n == 0 else even(n - 1)
> How do I rewrite those with your module?

I'm not sure the module mentioned above has provision for that, but in
any case the Y combinator has a corresponding fixed-point combinator
called Y*. There is quite a bit of theory behind this, anybody
interested can google, e.g., "Y combinator mutual recursion", whose
first result is:


-- Alain.

More information about the Python-list mailing list