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

Groups > comp.lang.python > #94042

Re: A new module for performing tail-call elimination

Show all headers | View raw

On 7/17/2015 4:55 PM, Marko Rauhamaa wrote:
> Terry Reedy <tjreedy@udel.edu>:
>
>> On 7/16/2015 3:45 PM, Marko Rauhamaa wrote:
>>> Nobody seemed to notice that I just posted a fairly typical tail call
>>> function:
>>
>> Because non-recursive tail calls are completely normal.
>
> I don't know how recursion makes a difference

There are two extremely important differences:
1. Direct recursion calls the function that contains the call.  This is 
what allows replacement of tail recursion with a loop within the same 
function.
2. Almost all problems with stack overflow are due to recursion, whether 
at the tail or within the body of a code block. Such problems are nearly 
always with linear recursion (one recursive call per call until the base 
case).  Problems with branching recursion (multiple recursive calls per 
call) are rare except for very deep trees and  graphs.

> but that one did happen to be recursive.

Not directly, as needed for loop conversion.

class X:  # omitted from original but needed below
     def setvalue(self, keyseq, value, offset=0):
         ...
         child.setvalue(keyseq, value, offset + 1)

child.setvalue is a new callable bound method object, call it 'bm', that 
is different from the setvalue function. This tail call is not a tail 
recursive call. The standard conversion of adding a while loop and 
replacing the tail call with the assignment in the call, in this case 
'offset = offset+1' will not work.

> It could easily have been replaced with a while loop

Given the equality stated below, then yes.
child.setvalue(*args) == bm(*args) calls (in 3.x)
     bm.__func__(bm.__self__, *args)
If type(child) == type(self) == X, then bm.func == X.setvalue
and the indirect call is the same as
     X.setvalue(child, keyseq, value, offset + 1)
making the bound method call indirectly recursive.
If we replace the bound method call in setvalue with the call to 
setvalue itself, then we have a tail recursive call and can do the 
standard replacement to get:

class X
     def setvalue(self, keyseq, value, offset=0):
         while True:
             ...
             # child.setvalue(keyseq, value, offset + 1)
             offset += 1
             self = child

If children are not always instances of type(self), as when a tree has 
separate Node and Leaf classes, then recursive calls to Node instances 
must be separated from non-recursive Leaf calls before replacing the 
recursive calls.

Having a good reason to rebind the first parameter within methods, as 
above, is a good reason to not hide it (as some have proposed).

> but there were good aesthetic reasons to leave it recursive.

Once one learns that looping and recursive calls are two ways of doing 
the same thing -- repeatedly executing a block of code with altered 
inputs, then the aesthetic reasons are purely aesthetic.

I personally would probably initially write and test setvalue with 
recursion.  If I were releasing it for others to use in production code 
(where aesthetics no longer break ties between equivalent correct 
implementations), I would do the conversion to avoid possible stack 
overflows.  For cases like this, where only some parameters are rebound, 
I might leave the original tail call in a comment as documentation, as I 
did above.

-- 
Terry Jan Reedy

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