Path: csiph.com!usenet.pasdenom.info!news.redatomik.org!newsfeed.xs4all.nl!newsfeed8.news.xs4all.nl!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <CAD+URuj-4e62-9hvpiLsrBP1M6kXRyZhZ6XyL01gWWnDoShvNg@mail.gmail.com>
References: <CAD+URuj-4e62-9hvpiLsrBP1M6kXRyZhZ6XyL01gWWnDoShvNg@mail.gmail.com>
Date: Mon, 13 Jul 2015 21:28:15 +1000
Subject: Re: Possibly Pythonic Tail Call Optimization (TCO/TRE)
From: Chris Angelico <rosuav@gmail.com>
Cc: "python-list@python.org" <python-list@python.org>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.461.1436786904.3674.python-list@python.org>
Lines: 64
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:93752

On Sun, Jul 12, 2015 at 8:20 AM, Ian Burnette <ian.burnette@gmail.com> wrot=
e:
>
> 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 p=
roblem is to have a built in "recur" function that signals to the Clojure c=
ompiler to convert the code to a loop in the JVM. In python we could do som=
ething similar by having a recur(*args, **kwargs) function that removes its=
 parent from the stack and then runs the parent function again with the giv=
en arguments. It would look something like this:
>
> def factorial(n, acc=3D1):
>     if n =3D=3D 0:
>         return acc
>     else:
>         return recur(n-1, acc=3D(acc*n)) #signals to the interpreter to t=
rigger TRE
> # Doesn't overflow the stack!
>
> factorial(30000)
>
>
> I've also created a plugin that mocks this behavior using the try/except =
looping method that others have utilized to implement TCO into python. Of c=
ourse, my plugin still requires a decorator and the overhead of transmittin=
g information through an exception. Implementing recur with interpreter sup=
port should lead to much better performance.
>

When a function is purely tail-recursive like this, it's trivial to
convert it at the source code level:

def factorial(n):
    acc =3D 1
    while n > 0:
        acc *=3D n
        n -=3D 1
    return acc

The cases that _can't_ be converted this trivially are the ones that
usually can't be converted automatically either - the best case I can
think of is tree traversal, where one of the calls could be tail-call
optimized:

def traverse(node, func):
    if node.left: traverse(node.left, func)
    func(node)
    if node.right: return recur(node.right, func)

(By the way, what happens if you call recur() without returning its result?=
)

It still needs stack space for all the left calls, so it's not really
benefiting that much from TCO. Where does the advantage show up? Why
is it worth writing your code recursively, only to have it be
implemented iteratively? Warping your code around a recursive solution
to make it into a perfect tail call usually means making it look a lot
less impressive; for instance, the 'acc' parameter in your above code
has no meaning outside of transforming the recursion into tail
recursion.

https://xkcd.com/1270/

ChrisA