Miker

17th level Hacker

Python Tail Call

This is pretty interesting, a tail call optimization decorator for Python. It doesn’t work for a lot of cases.. like these ones:

@tail_call_optimized
def even( n ):
  if n == 0:
    return True
  else:
    return odd( n - 1 )

@tail_call_optimized
def odd( n ):
  if n == 0:
    return False
  else:
    return even( n - 1 )

@tail_call_optimized
def countto( n ):
  if n == 0:
    return 0
  else:
    return 1 + countto( n - 1 )

print odd( 31 )
print countto( 31 )

It forced me to actually take a look at decorators in Python to figure out what was going on and why they failed though. The basic flow of the “throw an exception and catch it at a higher level” idea is easy to follow. However what it’s doing when it catches that exception at a higher level is pulling the input arguments up to the higher level and reevaluating with the new arg set, and I’m not even sure what exactly it’s doing in the case of mutual recursion, and seems to stick to only one of the functions.

This one works for mutually recursive calls, but I haven’t dug into it yet. Looks interesting though. However it doesn’t work when the return value feeds back into the recusion:

@trampolined
def countto( n ):
  if n == 0:
    return 0
  else:
    return 1 + countto( n - 1 )

print countto( 3030 )

The stack overflows when I try that. The scheme implementations don’t have a problem with it however:

;1> (define countto (lambda (x) (if (= x 0) 0 (+ 1 (countto (- x 1))))))

#;2> (countto 30000)
30000

Still, interesting stuff to dig at.