Path: csiph.com!optima2.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!1.eu.feeder.erje.net!eternal-september.org!feeder.eternal-september.org!mx02.eternal-september.org!.POSTED!not-for-mail
From: Jussi Piitulainen <jpiitula@ling.helsinki.fi>
Newsgroups: comp.lang.python
Subject: Re: Possibly Pythonic Tail Call Optimization (TCO/TRE)
Date: Mon, 13 Jul 2015 14:22:19 +0300
Organization: A noiseless patient Spider
Lines: 48
Message-ID: <lf5twt8mhec.fsf@ling.helsinki.fi>
References: <mailman.460.1436783918.3674.python-list@python.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: mx02.eternal-september.org; posting-host="305c68510616a2e7ac08bcd2ff1598bd"; logging-data="4246"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19ThMSxEOgXfzEe1kG6y1lzsFJPXaWWiHQ="
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.1 (gnu/linux)
Cancel-Lock: sha1:NO+BGUxtGui2CHe1cyXWPwR2/6Q= sha1:oBr9BoBqrZmn0wfmUrcdIlzZsA4=
Xref: csiph.com comp.lang.python:93751

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.