Tail recursion

Noodle can now do limited tail call optimization. Only the tail recursion case is optimized in this way. That is, when a function calls itself and immediately returns the result of that call, Noodle can transform the bytecode so that the new function call doesn't take up any extra stack space. The initial function's stack space is no longer needed, once the arguments to the function call are computed, so there's no reason to keep it there. This is accomplished by transforming the function call into a series of assignments, one for each input variable, and simply jumping to the top of the function again.

The most difficult part of this is not the transformation- it's determining under which cases those steps are actually valid. When the tail-recursive call uses keyword arguments or varargs (*) or kwargs (**), for example, it's trickier to come up with valid bytecode to correctly reinitialize the function. Default arguments cause another problem, since a code object has no way of knowing which default arguments are attached to it in a containing function object.

So the current requirements for taking advantage of Noodle's tail call optimization are thus:

• Tail call must be at the end of the function, in addition to being in a tail position (this restriction is expected to go away at some point)


• Tail call must be to the current function, by the same name


• Tail call must give arguments for all positional parameters and all default parameters, in order, and must not give any keyword arguments, varargs, or kwargs.

When you're writing a recursive function, these restrictions should in general be rather simple to get around.

I don't expect Noodle will be able to support any further tail call optimization, since Python bytecode is currently incapable of jumping between code objects. Jumping can only be done to elsewhere in the current code object.