Tail recursion to while iteration in 2 easy steps

[Alain Ketterlin]

Terry Reedy <tjreedy at udel.edu> writes:

> On 10/4/2013 5:49 AM, Alain Ketterlin wrote:
>
>> I think allowing rebinding of function names is extremely strange,
>
> Steven already countered the 'is extremely strange' part by showing
> that such rebinding is common, generally useful, and only occasionally
> dodgy and a candidate for being blocked.

I was talking about rebinding a "function name", not about rebinding a
name to a function. Steve's message was pretty clear on this: iirc, his
first two cases were "binding a new name to an existing callable", the
last case (rebinding len) was in line with what I meant (except his code
"saved" the original function).

My example was: the code of "fact" contains a call to "fact", which is
not guaranteed to be bound to the function it appears in. And this
prevents any kind of optimization.

> I want to consider here what it would mean to concretely implement the
> abstract notion 'disallow rebinding of function names' and show what
> would be behind calling the idea 'not feasible'.

Again, I'm more concerned about the function than about the name.

And the fact that "disallow rebinding of function names" is not feasible
in Python is a design choice, not an essential characteristic of every
programming language.

That's fine. My point was: you can't at the same time have full
dynamicity *and* procedural optimizations (like tail call opt).
Everybody should be clear about the trade-off.

> 1. A 'name' is not a 'function name' unless the name is bound, at
> runtime, to a 'function'.
>
> 2. A 'function' in Python is not just one class but any callable
> object -- with with a __call__ methods. That comprises an unbounded
> set.

Right. Then when you do:

     def myfunc(...): ...

myfunc is bound to an callable object. In my example, I was doing the
equivalent to rebinding myfunc, losing the last reference to that piece
of code:

    myfunc = somethingelse

BTW, does the original callable object have a ref counter? Is it garbage
collected in that case? If not, would it be considered a bug?

> 3. Python does not mandate how namespaces are implemented. CPython
> uses both dicts and, for function local namespaces, internal C arrays.
> So 'names' in code can become either string keys for dicts or integer
> indexes for arrays.

Well, yes, but that's an implementation detail, no?

> 4. Rebinding can be explicit ('='), implicit ('import', 'class',
> def'), *or hidden* (globals('a') = 1; ob.__dict__('a') = 1). The
> hidden' methods are intentional as they are sometimes needed*.  In
> CPython, these forms remain different in the byte code, but it could
> be otherwise. The point is that is may or may not be possible for the
> interpreter to even recognize a 'rebinding' in order to apply any
> rebinding blocking rule.

Sure (that's exactly why I said it is easier to implement). If you were
to disallow rebinding of global function names, you would need a proper
notion of global scope and various categories of names, something almost
all compiled languages have.

> * There is no trick (that I know of) for hidden rebinding of function
> locals and nonlocals (short of using ctypes), but I am not sure that
> this is a language guarantee. However, I an sure that the absence is
> intentional.
>
>> even though it's easier to implement.
>
> No kidding.

(See above).

-- Alain.