Proper tail recursion

[Thomas Bellman]

Duncan Booth <me at privacy.net> wrote:

> Christopher T King <squirrel at WPI.EDU> wrote in 
> news:Pine.LNX.4.44.0407060839230.18699-100000 at ccc4.wpi.edu:

>> Is it feasable, and/or desirable to have Python optimize tail-recursive 
>> calls, similar to Scheme and gcc -O2? i.e. effectively compile this:

> 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.

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().  That might need a runtime check in many
cases.  (In the common case of there being no local functions at
all in the caller, it can be determined statically, of course.)
Hmm, there is an attribute 'func_closure' on function objects,
that at a quick glance seems to be None if it doesn't access the
surrounding namespace.


> 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.


-- 
Thomas Bellman,   Lysator Computer Club,   Linköping University,  Sweden
"The one who says it cannot be done should    ! bellman @ lysator.liu.se
 never interrupt the one who is doing it."    ! Make Love -- Nicht Wahr!