Software bugs aren't inevitable
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
Terry J. Reedy
More information about the Python-list