Re: [Python-ideas] Tail recursion elimination
MacroPy also has an implementation of TCO implemented using trampolining. It trades stack introspection for load-time-analysis, which could be a win or a loss depending on how you view things. ------------------------------ From: Ryan Sent: 1/18/2014 4:57 PM To: musicdenotation@gmail.com; Joao S. O. Bueno; python-ideas@python.org Subject: Re: [Python-ideas] Tail recursion elimination
I wrote one that uses decorators. How is that special syntax?
musicdenotation@gmail.com wrote:
On Jan 18, 2014, at 22:08, "Joao S. O. Bueno" jsbueno@python.org.br wrote:
You can use tail recursion elimination in Python as it is today.
I have seen many "implementations" of tail-call optimization, and their common problem is that they all require special syntax to work. I need a solution that is directly usable with Python's orrdinary *return*statement.
Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/
Now there's a new library I need to try!
Haoyi Li haoyi.sg@gmail.com wrote:
MacroPy also has an implementation of TCO implemented using trampolining. It trades stack introspection for load-time-analysis, which could be a win or a loss depending on how you view things.
From: Ryan Sent: 1/18/2014 4:57 PM To: musicdenotation@gmail.com; Joao S. O. Bueno; python-ideas@python.org Subject: Re: [Python-ideas] Tail recursion elimination
I wrote one that uses decorators. How is that special syntax?
musicdenotation@gmail.com wrote:
On Jan 18, 2014, at 22:08, "Joao S. O. Bueno" jsbueno@python.org.br wrote:
You can use tail recursion elimination in Python as it is today.
I have seen many "implementations" of tail-call optimization, and
their
common problem is that they all require special syntax to work. I
need a
solution that is directly usable with Python's orrdinary
*return*statement.
Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/
-- Sent from my Android phone with K-9 Mail. Please excuse my brevity.
I propose tail-call optimization to be added into CPython.
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 19 January 2014 08:52, Mark Lawrence breamoreboy@yahoo.co.uk 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/
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 jsbueno@python.org.br wrote:
On 19 January 2014 08:52, Mark Lawrence breamoreboy@yahoo.co.uk 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_VALUEin 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" jsbueno@python.org.br 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 jsbueno@python.org.br wrote:
On 19 January 2014 08:52, Mark Lawrence breamoreboy@yahoo.co.uk 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_VALUEin 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.
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.
On 20 January 2014 10:13, Terry Reedy tjreedy@udel.edu 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
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.
On Sun, Jan 19, 2014 at 3:13 PM, Terry Reedy tjreedy@udel.edu 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.
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
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 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.
On 20 Jan 2014 11:16, "David Mertz" mertz@gnosis.cx 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 tjreedy@udel.edu 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.
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
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/
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 ncoghlan@gmail.com
On 20 Jan 2014 11:16, "David Mertz" mertz@gnosis.cx 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 tjreedy@udel.edu 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.
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
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/
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.
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 greg.ewing@canterbury.ac.nz
Jonathan Slenders wrote:
@coroutinedef 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/
On Tue, Jan 21, 2014 at 07:46:12PM +1300, Greg Ewing wrote:
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.
If b() is a generator/iterator then the second example removes the frame associated fom a() from the stack while you iterate:
for x in a(): # one less frame on the stack at this point
Oscar
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 Tue, Jan 21, 2014 at 2:29 AM, spir denis.spir@gmail.com wrote:
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
To Python, the second one could be a tail call, but the first one isn't. It's really:
def perform (input): # a "action" data = prepare(input) process(data) return None
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.
def perform (input): # a "action" data = prepare(input) return from process(data) # now a tail call
ChrisA
On Jan 20, 2014, at 7:39, Chris Angelico rosuav@gmail.com 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 1/20/2014 10:29 AM, spir wrote:
I think tail call is very common
Yes, they are. That is why space-optimizing all tail calls, and destroying proper tracebacks for all tail calls, is gross over-kill. Saving space is only needed when recursion would make the stack space used grow without any particular bound. (Note that this is only an issue for practical implementations, not pure mathematics.)
The point of the 'tail call' proposal is to have the programmer explicitly say when space conservation is needed, instead of asking the interpreter to magically make that determination.
On 1/19/14 6:54 AM, Joao S. O. Bueno wrote:
On 19 January 2014 08:52, Mark Lawrence breamoreboy@yahoo.co.uk 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_VALUEin 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 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 01/19/2014 12:54 PM, Joao S. O. Bueno wrote:
On 19 January 2014 08:52, Mark Lawrence breamoreboy@yahoo.co.uk 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_VALUEin 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.
Denis
On 19 January 2014 12:27, spir denis.spir@gmail.com wrote:
On 01/19/2014 12:54 PM, Joao S. O. Bueno wrote:
On 19 January 2014 08:52, Mark Lawrence breamoreboy@yahoo.co.uk 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_VALUEin 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/
On 01/19/2014 04:12 PM, Joao S. O. Bueno wrote:
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)
All right, I did not rightly get your proposal.
Denis
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.
participants (17)
-
Andrew Barnert -
Chris Angelico -
David Mertz -
Greg Ewing -
Haoyi Li -
Joao S. O. Bueno -
Jonathan Slenders -
Mark Lawrence -
musicdenotation＠gmail.com -
Ned Batchelder -
Nick Coghlan -
Oscar Benjamin -
Ryan -
spir -
Stephen J. Turnbull -
Terry Reedy -
Tim Delaney