To: python-list@python.org
From: Terry Reedy <tjreedy@udel.edu>
Subject: Re: Possibly Pythonic Tail Call Optimization (TCO/TRE)
Date: Tue, 14 Jul 2015 20:23:27 -0400
References: <CAD+URuj-4e62-9hvpiLsrBP1M6kXRyZhZ6XyL01gWWnDoShvNg@mail.gmail.com> <CAPTjJmrnd2cdA75ROZUKsJfYMdYUXkxRbEN50UE_-r0Jg=c5nQ@mail.gmail.com> <55A3A853.4040006@rece.vub.ac.be> <CAPTjJmr92j+2DDPsZxynoHyZTTCpc-48cWCVrx_fT3dA0j_Osg@mail.gmail.com> <55A3C366.6060602@rece.vub.ac.be> <mailman.468.1436796350.3674.python-list@python.org> <87fv4r1fre.fsf@jester.gateway.sonic.net>
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: <87fv4r1fre.fsf@jester.gateway.sonic.net>
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.518.1436919834.3674.python-list@python.org>
Lines: 52
NNTP-Posting-Host: 2001:888:2000:d::a6
Path: csiph.com!usenet.pasdenom.info!news.stben.net!border1.nntp.ams1.giganews.com!nntp.giganews.com!newsfeed.xs4all.nl!newsfeed8.news.xs4all.nl!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Xref: csiph.com comp.lang.python:93838

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