Possibly Pythonic Tail Call Optimization (TCO/TRE)

[Jussi Piitulainen]

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.