Software bugs aren't inevitable

Terry Reedy tjreedy at
Fri Sep 16 08:12:17 CEST 2005

"Mike Meyer" <mwm at> wrote in message 
news:863bo5j0br.fsf at
> aahz at (Aahz) writes:
>> 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.
> That seems amazingly silly. Sort of like refusing to hoist function
> definitions because not all function definitions can be hoisted. Or
> choose your favorite "sometimes-I-can-sometimes-I-can't" 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.  Trivial examples:

def f(): return f() # looks recursive
g = f
def f(): return 1 # now the function formerly named f and now g is not

def f(): return g() # looks not recursive
g = f # now it is

Someone, I believe Raymond H., wrote and posted and maybe added to the 
Cookbook a CPython-specific bytecode hack to change 'load global named 'f' 
(or whatever) to 'load  constant <function object f>' to eliminate the 
dynamic name lookup.  This could be written as a decorator if it is not 

Terry J. Reedy

More information about the Python-list mailing list