Proper tail recursion

[Duncan Booth]

Thomas Bellman <bellman at lysator.liu.se> wrote in
news:ccekq2$8kp$1 at news.island.liu.se: 

> Instead of doing tail recursion elimination, one could implement
> general tail call optimization.  It shouldn't be too difficult to
> make the compiler recognize tail calls, i.e
> 
>      return spam(params)
> 
> outside any try statement.  It could then generate the byte code
> TAIL_CALL instead of CALL_FUNCTION.  TAIL_CALL would throw away
> the current stack frame before calling spam().
> 

That ought to be doable. The main disadvantages I can see are that stack 
backtraces will be incomplete (which could be confusing), and unbounded 
recursion won't be caught (which may or may not matter).

> This doesn't give you the performance improvement of not making a
> function call, but at least it makes a tail recursive function
> run in constant space.
> 
> Of course, some care needs to be taken to ensure that the current
> stack frame isn't thrown away if the called function is a local
> function accessing the namespace of the calling function.  I.e,
> in the case
> 
>      def parrot(x):
>          def spam(n):
>           return n + y
>          y = x*x
>          return spam(5)
> 
> the call to 'return spam(5)' must make sure that 'y' is
> accessible to spam().

No it doesn't. References to 'y' in parrot are handled indirectly by 
storing the value in a cell object. The stack frame only holds a reference 
to the cell object. So long as the cell still has another reference the 
value remains valid.

>> However, I don't believe there is at present any easy way to get hold
>> of the current executing function or generator object.
> 
> Raising and catching an exception, and digging through the
> traceback object might give you enough information to do
> that.  But it's not very pretty, and I'm not sure that it
> is portable between C-Python, Jython, PyPy, Psyco, and any
> other Python compiler/interpreter.
> 
I'm pretty sure that there is nothing useful in the traceback object. You 
can find out which instruction was executing, but this doesn't help in 
identifying the function since several functions could share the same code 
(an active generator being an obvious example where this happens).