Possibly Pythonic Tail Call Optimization (TCO/TRE)

Chris Angelico rosuav at gmail.com
Mon Jul 13 16:05:41 CEST 2015


On Mon, Jul 13, 2015 at 11:55 PM, Antoon Pardon
<antoon.pardon at rece.vub.ac.be> wrote:
> On 07/13/2015 02:34 PM, Chris Angelico wrote:
>>
>>>> Warping your code around a recursive solution
>>>> to make it into a perfect tail call usually means making it look a lot
>>>> less impressive; for instance,
>>> And sometimes your problem is very easily solved by a number of functions
>>> that tail call each other but in python you will need to warp your code
>>> around an iterative solution, in order to avoid the stack limit.
>> Example, please? In all my Python programming, I've never hit the
>> stack limit outside of deliberate playing around (or accidental
>> infinite recursion, which means it's doing its job).
>
> I have had to process text coming from a network connection. The data
> was mosly unstructered text with some lines that could be used as markers
> to proceed through some kind of state machine that indicated how the
> following lines needed to be processed. That was easiest written by having
> a function for each "state" that would process the next lines until
> a marker line was encountered and then call the function corresponding
> with the next state. However since a connection could stay active for
> days, sooner or later a stack limit would occur if done the natural
> recursive way.

I'm not sure why the transition to another state has to be recursive.
With most network protocols, you'll end up returning to some kind of
"base state" - maybe there's a header line that says that you're
entering some new mode, which strongly suggests a subroutine call, but
then at the end of that mode, you would return to the normal position
of looking for another header. Alternatively, if the only way you know
you're at the end of one mode is by discovering the beginning of the
next, it's common to be able to have a single primary loop that
dispatches lines appropriately - when it gets the next header, it
sends the entire previous block to its appropriate function, and then
carries on looking for lines of text.

Maybe this is something where previous experience makes you more
comfortable with a particular style, which will mean that functional
idioms will never feel more comfortable to me than iterative ones do,
and vice versa for you. If that's the case, then I'll stick with
Python and Pike, and you can happily use Lisp and Haskell, and neither
of us need be a problem to the other. But honestly, I'm not seeing
anything that requires infinite recursion in your description. And
I've worked with a lot of networking protocols in my time.

>>> It seems warping your code is only seen as a problem when going in the
>>> functional direction. Going into the iterative direction may take all
>>> the warping that is needed, without comment.
>> That's because I've never seen code that warps more for iteration than
>> it does for programming in general. Again, example please?
>
> And since when is your experience the measure stick for what other people
> encounter as problems?

That's why I said "example please?". My experience has not a single
time come across this. If you want to make an assertion that iterative
code requires equivalent warping to tail-recursive code, I want to see
an example of it. Is that difficult?

ChrisA


More information about the Python-list mailing list