Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #93923

Re: A new module for performing tail-call elimination

From Alain Ketterlin <alain@universite-de-strasbourg.fr.invalid>
Newsgroups comp.lang.python
Subject Re: A new module for performing tail-call elimination
Date 2015-07-16 13:23 +0200
Organization Université de Strasbourg
Message-ID <87egk8qrb0.fsf@universite-de-strasbourg.fr.invalid> (permalink)
References <55a3dcd9$0$3024$426a34cc@news.free.fr> <mailman.532.1436952589.3674.python-list@python.org>

Show all headers | View raw

Antoon Pardon <antoon.pardon@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.

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

A new module for performing tail-call elimination "Th. Baruchel" <baruchel@no.spam.gmx.dot.com> - 2015-07-13 15:44 +0000
  Re: A new module for performing tail-call elimination Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-15 11:29 +0200
    Re: A new module for performing tail-call elimination Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-07-16 18:07 +1000
      Re: A new module for performing tail-call elimination Robin Becker <robin@reportlab.com> - 2015-07-16 10:13 +0100
      Re: A new module for performing tail-call elimination Robin Becker <robin@reportlab.com> - 2015-07-16 10:28 +0100
        Re: A new module for performing tail-call elimination Marko Rauhamaa <marko@pacujo.net> - 2015-07-16 12:56 +0300
      Re: A new module for performing tail-call elimination Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-16 12:41 +0200
        Re: A new module for performing tail-call elimination Steven D'Aprano <steve@pearwood.info> - 2015-07-17 04:58 +1000
          Re: A new module for performing tail-call elimination Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-17 11:00 +0200
      Re: A new module for performing tail-call elimination Chris Angelico <rosuav@gmail.com> - 2015-07-16 21:11 +1000
      Re: A new module for performing tail-call elimination Jeremy Sanders <jeremy@jeremysanders.net> - 2015-07-16 13:29 +0200
      Re: A new module for performing tail-call elimination Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-16 15:35 +0200
      Re: A new module for performing tail-call elimination Chris Angelico <rosuav@gmail.com> - 2015-07-16 23:47 +1000
        Re: A new module for performing tail-call elimination Paul Rubin <no.email@nospam.invalid> - 2015-07-17 20:06 -0700
      Re: A new module for performing tail-call elimination Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-16 16:21 +0200
      Re: A new module for performing tail-call elimination Chris Angelico <rosuav@gmail.com> - 2015-07-17 00:27 +1000
      Re: A new module for performing tail-call elimination Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-16 17:14 +0200
      Re: A new module for performing tail-call elimination Ian Kelly <ian.g.kelly@gmail.com> - 2015-07-16 10:17 -0600
      Re: A new module for performing tail-call elimination Ethan Furman <ethan@stoneleaf.us> - 2015-07-16 10:54 -0700
      Re: A new module for performing tail-call elimination Ethan Furman <ethan@stoneleaf.us> - 2015-07-16 11:02 -0700
      Re: A new module for performing tail-call elimination Terry Reedy <tjreedy@udel.edu> - 2015-07-16 15:45 -0400
      Re: A new module for performing tail-call elimination Ethan Furman <ethan@stoneleaf.us> - 2015-07-16 12:58 -0700
      Re: A new module for performing tail-call elimination Robin Becker <robin@reportlab.com> - 2015-07-17 09:57 +0100
    Re: A new module for performing tail-call elimination Alain Ketterlin <alain@universite-de-strasbourg.fr.invalid> - 2015-07-16 13:23 +0200
  Re: A new module for performing tail-call elimination Terry Reedy <tjreedy@udel.edu> - 2015-07-15 17:19 -0400
  Re: A new module for performing tail-call elimination Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-16 09:45 +0200
  Re: A new module for performing tail-call elimination Terry Reedy <tjreedy@udel.edu> - 2015-07-16 15:34 -0400
    Re: A new module for performing tail-call elimination Marko Rauhamaa <marko@pacujo.net> - 2015-07-16 22:45 +0300
      Re: A new module for performing tail-call elimination Terry Reedy <tjreedy@udel.edu> - 2015-07-17 15:47 -0400
        Re: A new module for performing tail-call elimination Marko Rauhamaa <marko@pacujo.net> - 2015-07-17 23:55 +0300
          Re: A new module for performing tail-call elimination Terry Reedy <tjreedy@udel.edu> - 2015-07-17 20:40 -0400
            Re: A new module for performing tail-call elimination Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-07-19 10:39 +1200
          Re: A new module for performing tail-call elimination Chris Angelico <rosuav@gmail.com> - 2015-07-18 10:47 +1000
          Re: A new module for performing tail-call elimination Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-07-19 10:39 +1200
      Re: A new module for performing tail-call elimination Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-07-19 10:39 +1200
        Re: A new module for performing tail-call elimination Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-07-19 01:09 +0100
        Re: A new module for performing tail-call elimination MRAB <python@mrabarnett.plus.com> - 2015-07-19 01:19 +0100
        Re: A new module for performing tail-call elimination Marko Rauhamaa <marko@pacujo.net> - 2015-07-19 09:29 +0300
  Re: A new module for performing tail-call elimination Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-17 10:06 +0200

csiph-web