Possibly Pythonic Tail Call Optimization (TCO/TRE)

Jussi Piitulainen jpiitula at ling.helsinki.fi
Mon Jul 13 13:22:19 CEST 2015


Ian Burnette writes:

> I've recently been playing around with Clojure, and I really like the
> way they've overcome the JVM not supporting TRE. The way Clojure
> solves this problem is to have a built in "recur" function that
> signals to the Clojure compiler to convert the code to a loop in the
> JVM. In python we could do something similar by having a recur(*args,
> **kwargs) function that removes its parent from the stack and then
> runs the parent function again with the given arguments. It would look
> something like this:

where I introduce some indentation:

>   def factorial(n, acc=1):
>      if n == 0:
>         return acc
>      else:
>         return recur(n-1, acc=(acc*n))
>                #signals to the interpreter to trigger TRE

That's oddly restricted to self-calls. To get the real thing, "recur"
should replace "return" - I'm tempted to spell it "recurn" - so the
definition would look like this:

def factorial(n, acc=1):
   if n == 0:
      return acc
   else:
      recur factorial(n-1, acc=(acc*n))

Probably it would still be syntactically restricted to calls - just
guessing what it would and would not be like to have this in Python:

def factorial(n, acc=1):
   recur ( acc if n == 0 else factorial(n-1, acc=(acc*n)) ) #error?

Something similar could be done inside lambda forms, again probably
restricted to calls in value position:

factorial = ( lambda n, acc=1 : #horror?
                ( acc if n == 0 else rec factorial(n-1, acc=(acc*n)) ))

But I don't think it's a way that's missing, I think it's a will. I know
you know this, and I agree with your point (in a paragraph that I'm not
quoting) that an explicit syntax for "eliminable" tail calls would be,
well, explicit :) so a user of such syntax should at least know why they
are not getting in their stack traces material that they have
specifically requested to not have in their stacks.


More information about the Python-list mailing list