Possibly Pythonic Tail Call Optimization (TCO/TRE)

[Terry Reedy]

On 7/14/2015 1:15 AM, Paul Rubin wrote:

>    def quicksort(array, start, end):
>       midp = partition(array, start, end)
>       if midp <= (start+end)//2:
>          quicksort(array, start, midp)
>          quicksort(array, midp+1, end)
>       else:
>          quicksort(array, midp+1, end)
>          quicksort(array, start, midp)
>
> I assume you know how quicksort and its partition step work.  The idea
> is you partition the array around the pivot element (midp is the index
> of that element), then recursively sort the two partitions, doing the
> smaller partition as a recursive call and the larger one as a tail call,
> so that you use O(log n) stack depth instead of potentially O(n).

Thank you for the example.  It I have ever seen how to minimize the max 
stack needed for first calls, I have forgotten.  First some comment:
1. There is no terminal condition, so the above will loop forever. The 
body should start with 'if not terminal(start, end):' where terminal is 
the actual expression.  I did not write it because it depends on whether 
'end' is the highest index or one past it.
2. There are no tail calls (call followed by return), so a tail-call 
optimizer will not optimize this.  A recur() function might be able to.
3. Mutation is anathema to functional programming, so a functional 
programmer would never write and version of this, at least not without 
holding his nose.

The tail-like calls in each branch can be avoided with assignment and 
gobacks.  In Python, we go-back with while loops. (IE, 'while' = 'label' 
+ 'if' + 'goto'.)  With minimal change to the above, we get (untested)

def quicksort(array, start, end):
     while not terminal(start, end):
         midp = partition(array, start, end)
         if midp <= (start+end) // 2:
             quicksort(array, start, midp)
             start = midp+1
         else:
             quicksort(array, midp+1, end)
             end = midp

I can understand that someone might prefer to break the symmetry of the 
paired calls by wrapping the second with recur() (assuming that such a 
function is sensibly feasible on *all* implementations).  In the other 
hand, I prefer the reduced-noise explicit assignment that highlights the 
one parameter that gets rebound.

-- 
Terry Jan Reedy