[Python-ideas] A Continuations Compromise in Python

[Antoine Pitrou]

Hello again,

Steven D'Aprano <steve at ...> writes:
> 
> But surely that's the point of removing tail-recursion? Each function 
> call has overhead, and by reducing the number of function calls, you 
> reduce the amount of overhead.

Well, it's not that obvious. Tail call optimization does not totally remove
function calls, it replaces them with a slightly lighter kind of control
transfer. It would not save the cost of setting up a new frame object (the
function you transfer control to probably has differing constants and local
variables), of passing parameters around (Python's rich function call
conventions cost some CPU time) and various other bookkeeping.

So, TCO would make the cost of the tail call slightly lighter (how much exactly
is unknown), but it won't *suppress* it like e.g. inlining would do.

> I've seen tail-call optimization 
> described as programatically converting a tail-call recursive function 
> into an equivalent iterative function. I've also seen it referring to a 
> process of minimizing the depth of the function call stack while still 
> making the same number of function calls.

The former sentence is the formulation in theoretical (algorithmic) terms.
The latter sentence is how I believe it gets implemented in practice.
Basically, at the assembler level, you replace a "CALL + RETURN" sequence with a
single "JUMP" instruction. But that JUMP instruction still must do all the work
of setting up parameters, initializing a new frame etc. It's not anything like a
lightweight intra-function JUMP.

> Even the people on 
> various blog sites saying it's "easy" are actually saying that a 
> solution which is either fragile, or slow, or both, is easy, and that 
> shouldn't surprise anyone.

Well, in the sentence you were responding to I was talking about optimizing
recursive calls in Python *without* introducing TCO. ;)

Regards

Antoine.