Software bugs aren't inevitable

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


"Mike Meyer" <mwm at mired.org> wrote in message 
news:863bo5j0br.fsf at bhuda.mired.org...
> aahz at pythoncraft.com (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 
now.

Terry J. Reedy






More information about the Python-list mailing list