Tail recursion to while iteration in 2 easy steps

[MRAB]

On 07/10/2013 18:57, Antoon Pardon wrote:
> Op 07-10-13 19:15, Alain Ketterlin schreef:
>>> 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.
>
> Your wrong. Full dynamics is not in contradiction with tail call
> optimisation. Scheme has already done it for years. You can rebind
> names to other functions in scheme and scheme still has working tail
> call optimisatiosn.
>
Consider this code:

def fact(n, acc=1):
    if n <= 1:
        return acc
    return fact(n-1, n*acc)

It compiles to this:

 >>> dis.dis(fact)
   2           0 LOAD_FAST                0 (n)
               3 LOAD_CONST               1 (1)
               6 COMPARE_OP               1 (<=)
               9 POP_JUMP_IF_FALSE       16

   3          12 LOAD_FAST                1 (acc)
              15 RETURN_VALUE

   4     >>   16 LOAD_GLOBAL              0 (fact)
              19 LOAD_FAST                0 (n)
              22 LOAD_CONST               1 (1)
              25 BINARY_SUBTRACT
              26 LOAD_FAST                0 (n)
              29 LOAD_FAST                1 (acc)
              32 BINARY_MULTIPLY
              33 CALL_FUNCTION            2 (2 positional, 0 keyword pair)
              36 RETURN_VALUE

I think that CALL_FUNCTION immediately followed by RETURN_VALUE could
be tail-call optimised by dropping the caller's stack frame provided
that (like in this case) the callee doesn't refer to any name in the
callers stack frame (nonlocal).

You could also consider replacing the caller's stack frame with a
smaller pseudo-frame, perhaps compressing multiple pseudo-frames or
repeated sequences of pseudo-frames into a single pseudo-frame, so that
it could still generate the same traceback as before (or an compressed
traceback like what was discussed on python-ideas in the threads
"Compressing excepthook output" and "Idea: Compressing the stack on the
fly").