Proper tail recursion

[Christopher T King]

On Tue, 6 Jul 2004, Thomas Bellman wrote:

> Duncan Booth <me at privacy.net> wrote:
> 
> > Just because a function looks recursive to you, doesn't mean it actually is 
> > recursive when it gets called.
> 
> > How do you propose to handle this?
> 
> > def foo(n):
> >     return foo(n-1)
> 
> > def baz(n):
> >     return 0
> 
> > bar = foo
> > foo = baz
> > bar(3)
> 
> 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().
> 
> 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.

What he said. :) I don't mean to optimize recursive functions into loops, 
but simply to replace normal calls at the end of functions with tail 
calls.

> 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.
> [snip]

I'm just guessing here (my knowledge of the internals isn't too great), 
but in the case of closures, isn't it okay to throw away the stack space, 
since any variables needed are kept in the function's func_closure 
attribute? To modify your example:

        def parrot(x):
            def spam(n):
                return n + y
            y = x*x
            return spam

        print parrot(3)(5)

This returns 28, as expected, and is (roughly) functionally no different 
from a tail-callified version of your parrot() function.

> > 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 don't need it that badly ;) -- it just would have made a neat 
generaliztion in my code, rather than special-casing a yield of 'None' to 
refer to the generator that yielded it.