[Python-ideas] return from (was Re: Tail recursion elimination)

[Terry Reedy]

Proposal (mostly not mine): add 'return from f(args)', in analogy with 
'yield from iterator', to return a value to the caller from an execution 
frame running f(args) (and either reuse or delete the frame that ran 
'return from'). The function name 'f' would not have to match the name 
of the function being compiled, this would actually be TCO, even if it 
were nearly always used for recursive tail calls. That does mean that is 
would work for mutually tail recursive functions.

On 1/19/2014 6:57 AM, Joao S. O. Bueno wrote:
> OTOH, since we are at it, we'd better check
> 2009 BDLF's opinion on the subject:
>
> http://neopythonic.blogspot.com.br/2009/04/tail-recursion-elimination.html

I read throught the comments and near the very end, in July 2013, Dan 
LaMotte said... '''
Definitely seems to be complicated/impossible to determine a function is 
tail recursion 'compliant' statically in python, however, what if it 
were an 'opt in' feature that uses a different 'return' keyword?

     def f(n):
     if n > 0:
     tailcall f(n - 1)
     return 0
'''
In additional paragraphs, he noted, among other things, that this makes 
the feature 'opt-in' on a function by function basis.

Guido replied "Dan: your proposal has the redeeming quality of clearly 
being a language feature rather than a possible optimization. I don't 
really expect there to be enough demand to actually add this to the 
language though. Maybe you can use macropy to play around with the idea 
though?"

水逝云飞 then suggested 'return from'. My only contribution is to point 
out the analogy with the new, and initially strange, 'yield from'.

Guido seems to have said that if a) someone tries out the idea with 
macropy, and b) someone demonstrates enough demand, he might consider 
adding such a feature. So this seems to me the best option to pursue to 
get something into CPython. I also think it is the best proposal so far.

As for a), I have not looked as macropy, but:
On 1/19/2014 4:33 PM, Haoyi Li wrote:> MacroPy's @tco decorator is about 
as easy as you could ask for. 'pip
 > install macropy', 'from macropy.experimental.tco import macros, tco' 
 > is about as easy as you could ask for. Works for arbitrary tail-calls 
 > too, not just tail recursion.

That leaves b) for those of you who want the feature.

Any PEP should admit that the feature might be abused. Someone might write
   return from len(composite)
Unless return from refuses to delete the frame making a call to a C 
function, the effect would be to save a trivial O(1) space as the cost 
of deleting the most important line of a stack trace should len() raise. 
But I think this falls under the 'consenting adults' principle. A 
proposed doc should make it clear that the intended use is to make 
deeply recursive or mutually recursive functions run and not to replace 
all tail calls.

-- 
Terry Jan Reedy