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:

http://stackoverflow.com/questions/4899113/fixed-point-combinator-for-mutually-recursive-functions

-- Alain.


More information about the Python-list mailing list