I propose tail-call optimization to be added into CPython.

On 19 January 2014 08:52, Mark Lawrence wrote:

On 19/01/2014 07:39, musicdenotation@gmail.com wrote:

...

I propose tail-call optimization to be added into CPython.

Then implement it so everybody else can use it.

On a second though, it actually could be done, at the VM level. I am not a proponent, but after my second though I am from "-1" to "+0". I believe that anytime one have the sequence: 20 CALL_FUNCTION 1 23 RETURN_VALUE in byte code, the current stack frame could be discarded prior to making the function call. Looking from 10000 meters, it feels like it would not impact any other aspect of the language but for enabling automatically tail recursion calls. js -><-

-- My fellow Pythonistas, ask not what our language can do for you, ask what you can do for our language.

Mark Lawrence

_______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/

On Jan 19, 2014, at 18:57, "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

...

On 19 January 2014 09:54, Joao S. O. Bueno wrote:

...

On 19 January 2014 08:52, Mark Lawrence wrote:

...

On 19/01/2014 07:39, musicdenotation@gmail.com wrote:

I propose tail-call optimization to be added into CPython.

Then implement it so everybody else can use it.

On a second though, it actually could be done, at the VM level. I am not a proponent, but after my second though I am from "-1" to "+0".

I believe that anytime one have the sequence:

20 CALL_FUNCTION 1 23 RETURN_VALUE

in byte code, the current stack frame could be discarded prior to making the function call. Looking from 10000 meters, it feels like it would not impact any other aspect of the language but for enabling automatically tail recursion calls.

js -><-

...

-- My fellow Pythonistas, ask not what our language can do for you, ask what you can do for our language.

Mark Lawrence

_______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/

---

Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/ Actually, my original post is a response to his arguments.

On 20 January 2014 10:13, Terry Reedy wrote:

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.

As someone who is happy with the status quo, "return from" seems to me to be the only sensible way to incorporate it into the language. Direct analogy with yield from, clear semantics ... I like it. 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.

Consenting adults does make things nice and simple. I'm not proposing the following semantics, but I can think of an alternative that might be useful, but likely difficult (and costly) to implement, and difficult to explain. When code goes through a "return from", that frame is retained, but when a new frame for the same code object is created in the call stack, you *then* delete the calling frame. Hmm - actually, you could keep a structure (e.g. a dict) on the side mapping code objects to the most recent frame for that code object - that would make it reasonably cheap to do. Wouldn't get particularly large either since you'd only be recording frames that continued through a "return from". Tim Delaney

On 1/19/2014 8:15 PM, David Mertz wrote:

On Sun, Jan 19, 2014 at 3:13 PM, 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.

I was mostly disliking the idea of TCO during this discussion. However, the idiom of 'return from' seems sufficiently elegant and explicit--and has exactly the semantics you'd expect from 'yield from'--that I am actually +1 on that idea.

Being an explicit construct, it definitely becomes a case of "consenting adults" not of implicit magic. I.e. you are declaring right in the code that you don't expect to see a frame in a stack trace, which is fair enough. I mean, if you *really* wanted to you could muck around with 'sys._getframe(N).f_whatever' already which would give inaccurate tracebacks too. Probably there would be a way to removed frames from the stack even, using some such trick in current python.

Acting upon encountering a call-return bytecode pair has the following problems. 1. It is CPython specific and probably not portable to all implementations. Guido has cited this as a major block. 2. It must by optional, but how? 2A. A command line option is too broad. For some inputs, functions would return or crash depending on the option. Not good. Also, command line options do not work well when starting Python with icons. 2B. A future import would have a narrower scope but still might be too broad. It would also be an abuse because the 'future' would be a fake future that is partly now and partly never. 2C. A sys flag has the non-icon problems of a command line option. An explicit indicator in the function avoids most of these problems. The only one I am not sure about is other implementations, but with explicit system independent syntax, there is at least a chance. A developer can temporarily switch back to return (with small enough input) to get a full stack trace for exactly one function, just as one can temporarily add 'print' to get a 'loop trace' for exactly one loop. -- Terry Jan Reedy

Interesting. I very much like the "return from" syntax. It's explicit and consistent enough with "yield from". When using coroutines, it currently also happens that at some points you have a choice to drop certain frames from the stack. Take for instance the following: @coroutine def a(): result = yield from b() # 'b' is another coroutine return result or often written as: @coroutine def a(): return (yield from b()) You could write it as: def a(): return b() In the last example, you delegate to another coroutine, removing 'a' from the stack. (see this discussion: https://groups.google.com/forum/#!topic/python-tulip/5xW44wh5Krs ) 2014/1/20 Nick Coghlan

On 20 Jan 2014 11:16, "David Mertz" wrote:

...

I was mostly disliking the idea of TCO during this discussion. However,

the idiom of 'return from' seems sufficiently elegant and explicit--and has exactly the semantics you'd expect from 'yield from'--that I am actually +1 on that idea.

I agree that a PEP for "return from" would be interesting. It also gives debuggers something to latch on to in order to handle the new scenario (just as they needed some adjustment to handle "yield from").

"return from" could also be explicitly disallowed in try blocks and with statements (since those inherently conflict with the idea of reusing the current frame for a different call).

By keeping a list of references to the ellided calls (perhaps using counts for more efficient handling of recursive calls), you could even partially reconstruct the missing parts of the traceback.

...

Being an explicit construct, it definitely becomes a case of "consenting adults" not of implicit magic. I.e. you are declaring right in the code that you don't expect to see a frame in a stack trace, which is fair enough. I mean, if you *really* wanted to you could muck around with 'sys._getframe(N).f_whatever' already which would give inaccurate tracebacks too. Probably there would be a way to removed frames from the stack even, using some such trick in current python.

Yep, we do that (from C) in importlib to try to reduce the infrastructure noise in the tracebacks shown to users.

Cheers, Nick.

...

On Sun, Jan 19, 2014 at 3:13 PM, Terry Reedy wrote:

...

Proposal (mostly not mine): add 'return from f(args)', in analogy with

...

...

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

...

...

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

...

...

水逝云飞 then suggested 'return from'. My only contribution is to point out

...

...

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

'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. the feature 'opt-in' on a function by function basis. though?" the analogy with the new, and initially strange, 'yield from'. 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

_______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/

-- Keeping medicines from the bloodstreams of the sick; food from the bellies of the hungry; books from the hands of the uneducated; technology from the underdeveloped; and putting advocates of freedom in prisons. Intellectual property is to the 21st century what the slave trade was to the 16th.

_______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/

_______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/

No I didn't. Those examples that I wrote are equivalent, except that the second will miss a frame on the stack. 2014/1/21 Greg Ewing

Jonathan Slenders wrote:

@coroutine

...

def a(): return (yield from b())

You could write it as:

def a(): return b()

I'm guessing you mean

def a(): return from b()

but that wouldn't be a coroutine, because it doesn't contain a 'yield' anywhere.

-- Greg

_______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/

I think tail call is very common. Consider following examples: def perform (input): # a "action" data = prepare(input) process(data) # tail call def result (input): # a "function" properly speaking data = prepare(input) return process(data) # tail call def case1 (input): if cond(input): <deal with common case in place> return deal_with_special_case() # tail call def case2 (input): if cond(input): <deal with special case in place> return deal_with_common_case() # tail call def perform_cases (input): if cond1(input): case1(input) # tail call elif cond2(input): case2(input) # tail call elif cond3(input): case3(input) # tail call def result_cases (input): if cond1(input): return case1(input) # tail call elif cond2(input): return case2(input) # tail call elif cond3(input): return case3(input) # tail call There are probably many more typical *schemas* of common tail call use cases. It is in any case very frequent, of pretty various usage, and not specific to functional or functional-like programming. Instead, we all use tail calls constantly, without even thinking at it, just like we constantly make prose ;-). [1] My point of view is not that tail call is a special (maybe very minoritary) kind of call, but that there are 2 kinds of calls maybe of equal importance: * delegation: another proc is passed the responsability of performing a task, or achieving the rest of it (tail call) * assistance: another proc is used to assist in a main task, still controlled and assumed by the main proc (sub call) I guess there are 2 main situations of delegation: / tail calls * the main proc sorts out cases and delegates in some or all cases * the main proc prepares the task and a delegate achieves it which may be mixed. (I may miss some, for sure.) "return from" may well do the job, but entertains imo wrong views about tail calls. Maybe "pass" would do the job better. When a delegate f performs an action (action, examples 'perform' & 'perform_cases' & 'case*' above), it can be interpreted as "pass the responsability of the task to f", or just "pass by f". When a delegate f computes a result (function, examples 'result' & 'result_cases' above) it can interpreted as "pass f's result back to the caller". (There is a similar ambiguity with "return", actually also matching semantic ambiguity.) denis [1] Allusion to https://en.wikipedia.org/wiki/Le_Bourgeois_gentilhomme

On Jan 20, 2014, at 7:39, Chris Angelico wrote:

If process() happens to return None, then it becomes a tail call, but since Python has no way of knowing if this will be the case, it can't optimize anything away. (Conversely, if the interpreter knew that perform()'s return value was going to be ignored, the same optimization could be made, but it can't assume that either.)

But if 'return from' syntax is added, I don't think it'll be much of an issue to put explicit return statements in functions where you know it'll always be None.

This is a great argument for not just the idea of the explicit syntax, but also the "return from" name. I hadn't thought about the fact that (non-functional-style) code often ignores a None return value and then returns None, which automatic TCO can't handle, but explicit can. And in that case, "return from" expresses exactly the right thing, just as it does in the recursive case.

On 19 January 2014 08:52, Mark Lawrence wrote:

...

On 19/01/2014 07:39, musicdenotation@gmail.com wrote:

...

I propose tail-call optimization to be added into CPython.

Then implement it so everybody else can use it. On a second though, it actually could be done, at the VM level. I am not a proponent, but after my second though I am from "-1" to "+0".

I believe that anytime one have the sequence:

20 CALL_FUNCTION 1 23 RETURN_VALUE

in byte code, the current stack frame could be discarded prior to making the function call. Looking from 10000 meters, it feels like it would not impact any other aspect of the language but for enabling automatically tail recursion calls. A big confusion here is between "tail recursion calls" and "tail calls". This change would eliminate all tail calls, so that if f() ended by calling g(), then g would reuse the stack frame of f. If g raises an exception, the stack trace would have no evidence of f in it. This is what people mean about unusable stack traces. And don't forget

On 1/19/14 6:54 AM, Joao S. O. Bueno wrote: that the stack is inspectable at runtime, so we aren't only talking about the visible stack trace produced on error, but the result of inspect.stack() etc, also. Sure, if you eliminate only *recursive* tail calls, then the resulting stack traces aren't so bad, because you can do bookkeeping so that the 1000 recursive calls to the same function are represented by one frame with an annotation of 1000 on it somewhere. But how do you make it work your above code work only for recursive calls? And what about mutually recursive calls? Aren't those important too? So we have two choices: the relatively easy job of eliminating all tail calls, which will throw away information we value, or the unsolved problem of how to eliminate recursive tail calls. --Ned.

js -><-

...

-- My fellow Pythonistas, ask not what our language can do for you, ask what you can do for our language.

Mark Lawrence

_______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/

_______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/

On 19 January 2014 12:27, spir wrote:

On 01/19/2014 12:54 PM, Joao S. O. Bueno wrote:

...

On 19 January 2014 08:52, Mark Lawrence wrote:

...

On 19/01/2014 07:39, musicdenotation@gmail.com wrote:

...

I propose tail-call optimization to be added into CPython.

Then implement it so everybody else can use it.

On a second though, it actually could be done, at the VM level. I am not a proponent, but after my second though I am from "-1" to "+0".

I believe that anytime one have the sequence:

20 CALL_FUNCTION 1 23 RETURN_VALUE

in byte code, the current stack frame could be discarded prior to making the function call. Looking from 10000 meters, it feels like it would not impact any other aspect of the language but for enabling automatically tail recursion calls.

You also need to adjust frame size, possibly even its structure (dunno, depends on implementation details of python's "calling convention" so to say), to get a right space (and disposition) for the callee's input variables.

Not in this suggestion - I did not propose re-using the frame, as seens to be the case around the calls, just because of that: these frames in Python seen to be tied to the code object within it. My suggestion is simply to discard the current frame before building the frame for the call. (Maybe adding some logging information on this next frame so that the stack trace could be complete) js -><-

Denis

_______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/

Joao S. O. Bueno writes:

My suggestion is simply to discard the current frame before building the frame for the call. (Maybe adding some logging information on this next frame so that the stack trace could be complete)

That way lies madness. The logging information needs to be stored somewhere. If it's to be "complete", it may as well be in ... wait for it ... a stack frame.