Software bugs aren't inevitable

Jerzy Karczmarczuk karczma at
Fri Sep 16 12:04:11 CEST 2005

Terry Reedy cites:
> "Mike Meyer" who fights with:
>>>While that's true, one of the reasons Guido has historically rejected
>>>this optimization is because there are plenty of recursive algorithms
>>>not amenable to tail-call optimization.

>>Since the BDFL is *not* known for doing even mildly silly things when
>>it comes to Python's design and implementation, I suspect there's more
>>to the story than that.
> Yes.  The reason Guido rejected tail-call optimization the last time it was 
> suggested is because it is semanticly incorrect for Python.  Python's name 
> bindings are dynamic, not static, and the optimization (and the discussion 
> here) assumes static bindings.  In Python, runtime recursiveness (defined 
> as a function *object* calling itself directly or indirectly), is 
> dynamically determined.  You cannot tell whether a function object will act 
> recursive or not just by looking at its code body.  


The question is to optimize the TAIL CALLS, not just the recursivity.
Mind you, Scheme has also a dynamical name binding, yet it does this
optimization. This is for me more a question of policy than of
semantics [with the *true* meaning of the word "semantics"].

The situation is a bit different in, say, Prolog, where the tail calls
cannot - typically - be optimized for *serious* reasons, the indeterminism.
Prolog has to keep/stack the choice points in recursive generators.
In Python not so.

Now I began to scratch my head. I will have to translate some Prolog
algorithms to Python generators...

Jerzy Karczmarczuk

More information about the Python-list mailing list