A new module for performing tail-call elimination

[Terry Reedy]

On 7/17/2015 4:55 PM, Marko Rauhamaa wrote:
> Terry Reedy <tjreedy at 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