Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!feeds.phibee-telecom.net!newsfeed.xs4all.nl!newsfeed8.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
To: python-list@python.org
From: Terry Reedy <tjreedy@udel.edu>
Subject: Re: A new module for performing tail-call elimination
Date: Wed, 15 Jul 2015 17:19:49 -0400
References: <55a3dcd9$0$3024$426a34cc@news.free.fr> <55A6280C.3090602@rece.vub.ac.be>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:38.0) Gecko/20100101 Thunderbird/38.1.0
In-Reply-To: <55A6280C.3090602@rece.vub.ac.be>
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.549.1436995214.3674.python-list@python.org>
Lines: 60
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:93881

On 7/15/2015 5:29 AM, Antoon Pardon wrote:
> 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 will not answer for Baruchel's tco module.  However, combining the two 
bodies and following the general rule of replacing tail recursive calls 
with assignments inside a while loop gives us

def even(n):
     return not odd(n)

def odd(n):
     while True:
         if not n:
             return False
         else:
             n  -= 1
         if not n:
             return True
         else:
             n -= 1

# which passes this test

print(even(0) is True, odd(0) is False,
       even(1) is False, odd(1) is True,
       even(2) is True, odd(2) is False,
       even(5) is False, odd(5) is True,
       even(6) is True, odd(6) is False)

I believe that this pattern should work with any set of mutually 
recursive functions that always call each other in cyclic order.  A more 
elaborate version does not have this limitation.

-- 
Terry Jan Reedy