On April 22, 2009, Guido van Rossum wrote:
First, as one commenter remarked, TRE is incompatible with nice stack traces: when a tail recursion is eliminated, there's no stack frame left to use to print a traceback when something goes wrong later. This will confuse users who inadvertently wrote something recursive (the recursion isn't obvious in the stack trace printed), and makes debugging hard. Providing an option to disable TRE seems wrong to me: Python's default is and should always be to be maximally helpful for debugging.
What are "nice" stack traces? If you mean stack traces that record every function call then it is not nice and helpful at all given their length. Do loops have nice stack traces as you mean it? No. When something goes wrong in a loop, you don't get to see every iteration in the stack trace. You debug loops by examining the values of variables in the iteration it goes wrong. Likewise you debug a tail recursive function by examining the arguments that went into the function call that blows up. And if you don't want to turn on TRE by default, you can turn it off and offer an option to enable.
Second, the idea that TRE is merely an optimization, which each Python implementation can choose to implement or not, is wrong. Once tail recursion elimination exists, developers will start writing code that depends on it, and their code won't run on implementations that don't provide it: a typical Python implementation allows 1000 recursions, which is plenty for non-recursively written code and for code that recurses to traverse, for example, a typical parse tree, but not enough for a recursively written loop over a large list.
Yes, it is more of a language feature than an implementation feature. But once CPython implements it, I think other implementations will follow suit or Python developers will not write code that uses TRE just like JavaScript developers don't use Mozilla-specific extensions like let keyword.
Third, I don't believe in recursion as the basis of all programming. This is a fundamental belief of certain computer scientists, especially those who love Scheme and like to teach programming by starting with a "cons" cell and recursion. But to me, seeing recursion as the basis of everything else is just a nice theoretical approach to fundamental mathematics (turtles all the way down), not a day-to-day tool.
This isn't a valid argument. That something isn't fundamental is almost never an argument to leave it out. (Except for Scheme.)
Of course, none of this does anything to address my first three arguments. Is it really such a big deal to rewrite your function to use a loop? (After all TRE only addresses recursion that can easily be replaced by a loop. :-)
It isn't a big deal, yes. But why restrict programmers? Python is a multi-paradigm language anyway: you can write imperative or functional code with(out) object orientation. "There should be one – and only one – obvious way to do it"? You are misinterpreting it. It is about having only one obvious way to do things, but you have removed another obvious way to do certain things because certain problems are better expressed using recursion rather than looping (traversing a tree, for example). I think the most obvious way to do something is how it is defined. If there was really one way to do anything, there should be no for-loops, list comprehensions, or even object orientation at all in Python. Remember that recursion is either something lower- or higher-level than looping. And if you don't like abstractions over primitive concepts, you should be coding in machine code right now.
You can use tail recursion elimination in Python as it is today.
So, if you are needing that, just package this reference implementation in a module:-
http://metapython.blogspot.com.br/2010/11/tail-recursion-elimination-in-pyth...
js -><-
On 18 January 2014 12:52, musicdenotation@gmail.com wrote:
On April 22, 2009, Guido van Rossum wrote:
First, as one commenter remarked, TRE is incompatible with nice stack traces: when a tail recursion is eliminated, there's no stack frame left to use to print a traceback when something goes wrong later. This will confuse users who inadvertently wrote something recursive (the recursion isn't obvious in the stack trace printed), and makes debugging hard. Providing an option to disable TRE seems wrong to me: Python's default is and should always be to be maximally helpful for debugging.
What are "nice" stack traces? If you mean stack traces that record every function call then it is not nice and helpful at all given their length. Do loops have nice stack traces as you mean it? No. When something goes wrong in a loop, you don't get to see every iteration in the stack trace. You debug loops by examining the values of variables in the iteration it goes wrong. Likewise you debug a tail recursive function by examining the arguments that went into the function call that blows up. And if you don't want to turn on TRE by default, you can turn it off and offer an option to enable.
Second, the idea that TRE is merely an optimization, which each Python implementation can choose to implement or not, is wrong. Once tail recursion elimination exists, developers will start writing code that depends on it, and their code won't run on implementations that don't provide it: a typical Python implementation allows 1000 recursions, which is plenty for non-recursively written code and for code that recurses to traverse, for example, a typical parse tree, but not enough for a recursively written loop over a large list.
Yes, it is more of a language feature than an implementation feature. But once CPython implements it, I think other implementations will follow suit or Python developers will not write code that uses TRE just like JavaScript developers don't use Mozilla-specific extensions like let keyword.
Third, I don't believe in recursion as the basis of all programming. This is a fundamental belief of certain computer scientists, especially those who love Scheme and like to teach programming by starting with a "cons" cell and recursion. But to me, seeing recursion as the basis of everything else is just a nice theoretical approach to fundamental mathematics (turtles all the way down), not a day-to-day tool.
This isn't a valid argument. That something isn't fundamental is almost never an argument to leave it out. (Except for Scheme.)
Of course, none of this does anything to address my first three arguments. Is it really such a big deal to rewrite your function to use a loop? (After all TRE only addresses recursion that can easily be replaced by a loop. :-)
It isn't a big deal, yes. But why restrict programmers? Python is a multi-paradigm language anyway: you can write imperative or functional code with(out) object orientation. "There should be one – and only one – obvious way to do it"? You are misinterpreting it. It is about having only one obvious way to do things, but you have removed another obvious way to do certain things because certain problems are better expressed using recursion rather than looping (traversing a tree, for example). I think the most obvious way to do something is how it is defined. If there was really one way to do anything, there should be no for-loops, list comprehensions, or even object orientation at all in Python. Remember that recursion is either something lower- or higher-level than looping. And if you don't like abstractions over primitive concepts, you should be coding in machine code right now.
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 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.
On 18/01/2014 15:58, musicdenotation@gmail.com wrote:
On Jan 18, 2014, at 22:08, "Joao S. O. Bueno" <jsbueno@python.org.br mailto: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.
Then implement one and publish it so everybody else can use it.
musicdenotation@gmail.com, 18.01.2014 16:58:
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.
What do you need it for?
(and note that your answer might to be more suited for python-list than python-ideas, in which case you may reply over there)
Stefan
This one is. What are you taliking about?
On 18 January 2014 13:58, 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.
What are you talking about? This one is usable with ordinary returns. It just requires a decorator.
On 1/18/14 10:58 AM, musicdenotation@gmail.com wrote:
On Jan 18, 2014, at 22:08, "Joao S. O. Bueno" <jsbueno@python.org.br mailto: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.
You haven't explained why you need it.
--Ned.
Whether or not you really need it, adding it to Python is a fun challenge that's worth trying.
The first problem is that CPython makes a C function call for every Python function call, and C doesn't eliminate tail calls; the only way to do it manually is with longjmp. So, you probably want to add it to either Stackless or PyPy instead.
Second, detecting tail recursion to eliminate it is pretty hard, and you have to do a runtime check to detect that the function being called is already on the stack, which potentially slows down every function call. Fortunately, eliminating _all_ tail calls instead of just recursive ones is a lot easier in Python, and it's better in just about every way.
Third, eliminating tail calls means the aren't on the stack at runtime, which means there's no obvious way to display useful tracebacks. I don't think too many Python users would accept the tradeoff of giving up good tracebacks to enable certain kinds of non-pythonic code, but even if you don't solve this, you can always maintain a fork the same way that Stackless has been doing.
Meanwhile, it will be a lot easier to do this in steps: First add a tail statement that's like return except that its expression must be a Call; instead of compiling to a return bytecode it replaces the call_function* with a tail_function*, which you can initially fake by doing a call and return. Next, write a real implementation of tail_function* that jumps instead of calling and returning. Next, write a simple keyhole optimizer that converts any call_function* followed immediately by return into a tail_function*, which makes your custom syntax unnecessary, so you can revert it. Finally, solve the traceback problem in some way. (Maybe you could do something tricky here: Split the stack frame object into the bit needed for tracebacks and the bit needed for actual calling; tail call elimination takes care of the second one, and a different optimization to detect and run-compress loops takes care of the first one. Making that fast enough so that it doesn't slow down every call unacceptable probably means keeping around a dict mapping some kind of "position" record to frames.)
Sent from a random iPhone
On Jan 18, 2014, at 7:58, 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/
On Sat, Jan 18, 2014 at 10:29:46AM -0800, Andrew Barnert wrote:
Whether or not you really need it, adding it to Python is a fun challenge that's worth trying.
"Need" is a funny thing. There's nothing you can do with a for-loop that you can't do with a while-loop, but that doesn't mean we don't "need" for-loops. Certain algorithms and idioms are simply better written in terms of for-loops, and certain algorithms are simply better written in terms of recursion than looping.
You can go a long way without recursion, or only shallow recursion. In 15 years + of writing Python code, I've never been in a position that I couldn't solve a problem because of the lack of tail recursion. But every time I manually convert a recursive algorithm to an iterative one, I feel that I'm doing make-work, manually doing something which the compiler is much better at than I am, and the result is often less natural, or even awkward. (Trampolines? Ewww.)
Third, eliminating tail calls means the aren't on the stack at runtime, which means there's no obvious way to display useful tracebacks. I don't think too many Python users would accept the tradeoff of giving up good tracebacks to enable certain kinds of non-pythonic code,
What makes you say that it is "non-pythonic"? You seem to be assuming that *by definition* anything written recursively is non-pythonic. I do not subscribe to that view.
In fact, in some cases, I *would* willingly give up *non-useful* tracebacks for the ability to write more idiomatic code. Have you seen the typical recursive traceback? They're a great argument for "less is more". What normally happens is that you get a RuntimeError and the traceback blows away your xterm's buffer with hundreds of identical or near-identical lines. But even in the case where you didn't hit the recursion limit, the traceback is pretty much a picture of redundancy and noise:
py> a(7) Traceback (most recent call last): File "<stdin>", line 1, in <module> File "./rectest.py", line 2, in a return b(n-1) File "./rectest.py", line 5, in b return c(n-1) + a(n) File "./rectest.py", line 2, in a return b(n-1) File "./rectest.py", line 5, in b return c(n-1) + a(n) File "./rectest.py", line 2, in a return b(n-1) File "./rectest.py", line 5, in b return c(n-1) + a(n) File "./rectest.py", line 2, in a return b(n-1) File "./rectest.py", line 5, in b return c(n-1) + a(n) File "./rectest.py", line 2, in a return b(n-1) File "./rectest.py", line 5, in b return c(n-1) + a(n) File "./rectest.py", line 2, in a return b(n-1) File "./rectest.py", line 5, in b return c(n-1) + a(n) File "./rectest.py", line 9, in c return 1/n ZeroDivisionError: division by zero
The only thing that I care about is the very last line, that function c tries to divide by zero. The rest of the traceback is just noise, I don't even look at it.
Now, it's okay if you disagree, or if you can see something useful in the traceback other than the last entry. I'm not suggesting that TCE should be compulsary. I would be happy with a commandline switch to turn it on, or better still, a decorator to apply it to certain functions and not others. I expect that I'd have TCE turned off for debugging. But perhaps not -- it's not like Haskell and Scheme programmers are unable to debug their recursive code.
The point is that tracebacks are not sacrosanct, and, yes, I would like the choice between writing idiomatic recursive code and more extensive tracebacks. Trading off speed for convenience is perfectly Pythonic -- that's why we have the ability to write C extensions, is it not?
but even if you don't solve this, you can always maintain a fork the same way that Stackless has been doing.
Having to fork the entire compiler just to write a few functions in their most idiomatic, natural (recursive) form seems a bit extreme, wouldn't you say?
TCO (Tail Call Optimization) means that when TCO is in effect and a tail call "return f(<args>)" is executed, the current execution context (stack frame) is used for the call instead of allocating a new one. What is 'optimized' is space usage. The effect on time is not clear.
On 1/18/2014 7:45 PM, Steven D'Aprano wrote:
What makes you say that it is "non-pythonic"? You seem to be assuming that *by definition* anything written recursively is non-pythonic. I do not subscribe to that view.
Neither do I.
In fact, in some cases, I *would* willingly give up *non-useful* tracebacks for the ability to write more idiomatic code. The point is that tracebacks are not sacrosanct, and, yes, I would like the choice between writing idiomatic recursive code and more extensive tracebacks. Trading off speed for convenience is perfectly Pythonic -- that's why we have the ability to write C extensions, is it not?
Are you willing to do any of the work needed to make the option available, starting with a specification? If so, I have some ideas.
Having to fork the entire compiler just to write a few functions in their most idiomatic, natural (recursive) form seems a bit extreme, wouldn't you say?
A 'fork' could consist of a relatively small patch that could be uploaded to, for instance, PyPI. I would not be surprised if 100-200 lines might be enough.
On 19 January 2014 22:12, Terry Reedy tjreedy@udel.edu wrote:
TCO (Tail Call Optimization) means that when TCO is in effect and a tail call "return f(<args>)" is executed, the current execution context (stack frame) is used for the call instead of allocating a new one. What is 'optimized' is space usage. The effect on time is not clear.
On 1/18/2014 7:45 PM, Steven D'Aprano wrote:
What makes you say that it is "non-pythonic"? You seem to be assuming that *by definition* anything written recursively is non-pythonic. I do not subscribe to that view.
Neither do I.
Guido is on record as preferring iterative algorithms as more comprehensible for more people, and explicitly opposed to adding tail call optimisation. I tend to agree with him - functional programming works OK in the small (and pure functions are a fine tool for managing complexity), but to scale up in a way that fits people's brains, you need to start writing code that looks more like a cookbook.
If you want inspiration on how to design a language for typical human thought patterns, look to cookbooks, training guides and operator manuals, not mathematics.
Cheers, Nick.
On Jan 19, 2014, at 19:31, Nick Coghlan ncoghlan@gmail.com wrote:
On 19 January 2014 22:12, Terry Reedy tjreedy@udel.edu wrote: TCO (Tail Call Optimization) means that when TCO is in effect and a tail call "return f(<args>)" is executed, the current execution context (stack frame) is used for the call instead of allocating a new one. What is 'optimized' is space usage. The effect on time is not clear.
On 1/18/2014 7:45 PM, Steven D'Aprano wrote:
What makes you say that it is "non-pythonic"? You seem to be assuming that *by definition* anything written recursively is non-pythonic. I do not subscribe to that view.
Neither do I.
Guido is on record as preferring iterative algorithms as more comprehensible for more people, and explicitly opposed to adding tail call optimisation. I tend to agree with him - functional programming works OK in the small (and pure functions are a fine tool for managing complexity), but to scale up in a way that fits people's brains, you need to start writing code that looks more like a cookbook.
If you want inspiration on how to design a language for typical human thought patterns, look to cookbooks, training guides and operator manuals, not mathematics.
Nick
-- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia _______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/
See this: http://www.stanford.edu/class/cs242/readings/backus.pdf
It fits peoples' brains more because of familiarity, not "nature". While procedures in a guide (cookbook, user manual,...) are better written imperatively because of the way things are done (so are user interfaces), the behind-the-scenes algorithms have no single "intuitive" way to write that applies for all cases. They are written imperatively because of performance (and later, familiarity).
Poor support for functional programming + Global Interpreter Lock = Outdated language.
On 01/19/2014 11:32 PM, musicdenotation@gmail.com wrote:
It fits peoples' brains more because of familiarity, not "nature".
That people often use "intuitive" or "natural" instead of "famliar" or "usual" does not mean, logically, that there is no better intuitive or natural choice. That people misuse a term does not imply it has no proper meaning.
For instance, closed intervals are more intuitive or natural, obviously (but for some reason I don't know). If you ask someone to count from 1 to 9, you will probably be surprised to hear him/her start from 2 or stop after 8. If you are asked to choose a letter between c and g, you will probably be surprised to hear that 'c' or 'g' is no good choice.
[This does not mean that closed intervals are the right choice in programming, i'm just discuting the notions of intuitive or natural; this is related to the way we spontaneously think or understand. Programming may require unintuitive or unnatural design choices, for some other, independant reasons; dunno. For the matter, I think the right choice may be neither [i,j] closed nore [i,k[ half-closed intervals, but (i,n) ranges, where n is the number of items.]
About the case of recursivity, whether it may be intuitive or natural, I think (see some previous post) that is very, very hard to judge. It is so abstract, and obviously difficult to catch. It require understanding recurrence (remember difficulty of most people at school?) and then tuuning it inside out *in mind* like a sock ;-), to produce an algo running backwards, and still understanding that it will do the right thing (because in fact it computes forwards behind the stage, which is totally implicit, and again hard to get).
About optimisation of tail calls, I share Guido's "pronouncement". Mainly because these optimisable (backward) recursive algo are the ones one can easily express by a forward algo (using loops and/or corecursivity), if I understanding the issue well (which i'm not 100% sure, but I don't know any counter-example). The issue of stack traces and programmer feedback is just for me another reason (not decisive because such algos often require inserting debug prints anyway, to understand what actually happens and/or diagnose a bug).
Denis
On Mon, Jan 20, 2014 at 11:12 PM, spir denis.spir@gmail.com wrote:
For instance, closed intervals are more intuitive or natural, obviously (but for some reason I don't know). If you ask someone to count from 1 to 9, you will probably be surprised to hear him/her start from 2 or stop after 8. If you are asked to choose a letter between c and g, you will probably be surprised to hear that 'c' or 'g' is no good choice.
I'm not so sure about that. The half-open interval makes as much sense as the fully closed - all you have to do is interpret the indices as being *between* elements. Take, for example, Scripture verses. (Quotes taken from THE HOLY BIBLE, NEW INTERNATIONAL VERSION®, NIV® Copyright © 1973, 1978, 1984, 2011 by Biblica, Inc.® Used by permission. All rights reserved worldwide. Copyright notice included for license compliance. Note that I'm using bracketed numbers to indicate the beginnings of verses - in a printed Bible, these would normally be in superscript.)
John 14: [31] To the Jews who had believed him, Jesus said, “If you hold to my teaching, you are really my disciples. [32] Then you will know the truth, and the truth will set you free.” [33]
This passage is normally referred to as "John 14:31-32", but as you see, the verse marker [32] is in the middle of the quote. Using a half-open interval, this would start at "John 14:31" and end at "John 14:33". Half-open means: "Begin at the beginning, go on till you come to the end, then stop", as the King of Hearts instructed the White Rabbit.
It's easy to indicate the beginning of a chapter: your start reference is verse 1. Here's the beginning of the account of the creation of the world:
[1] In the beginning God created the heavens and the earth. [2] Now the earth was formless and empty, darkness was over the surface of the deep, and the Spirit of God was hovering over the waters. [3] And God said, “Let there be light,” and there was light. [4] God saw that the light was good, and he separated the light from the darkness. [5] God called the light “day,” and the darkness he called “night.” And there was evening, and there was morning—the first day. [6]
Common parlance: Genesis 1:1-5. Half-open: Genesis 1:1-6. Conclusion: Tie. No argument to be made for either side. But what if you're looking at the *end* of a chapter? Here are a few verses from later on in Genesis 1:
[29] Then God said, “I give you every seed-bearing plant on the face of the whole earth and every tree that has fruit with seed in it. They will be yours for food. [30] And to all the beasts of the earth and all the birds of the air and all the creatures that move on the ground—everything that has the breath of life in it—I give every green plant for food.” And it was so. [31] God saw all that he had made, and it was very good. And there was evening, and there was morning—the sixth day.
Common parlance: Genesis 1:29-31. Half-open: Genesis 1:29-2:1. It's much more obvious by the latter that this passage extends exactly to the end of the chapter.
Obviously it's way WAY too late to change the way Bible references are written, any more than Melway could renumber their maps all of a sudden. Massive case of lock-in and backward-incompatibility with existing code. But I put it to you that the half-open would make at least as much sense as the closed, in any situation where there are boundaries with contents between them.
Note, by the way, that I'm not looking at anything involving backward scanning or wider strides, both of which Python's slice notation supports. Neither of those is inherently real-world intuitive, so the exact semantics can be defined as whatever makes sense in code. (And there was some discussion a little while ago about exactly that.) I'm just looking at the very simple and common case of referencing a subset of consecutive elements from a much larger whole.
The closed interval makes more sense when the indices somehow *are* the values being retrieved. When you count from 1 to 9, you expect nine numbers: 1, 2, ..., 8, 9. When you list odd numbers from 1 to 9, you expect 1, 3, 5, 7, 9. But what if you're looking at a container train and numbering the twenty-foot-equivalent-units (TEU) that it has? A 40-foot container requires 2 TEU, a 60-foot container requires 3 TEU. A "reefer" (refridgerated container) might require an extra slot, or at least it might be a 56-footer and consume 3 TEU. One wagon might, if you're lucky, carry 5 TEU; numbering them 1 through 5 would be obvious, but numbering the boundaries between them as 0 through 5 is better at handling the multiple TEU containers. (Even more so when you look at double-stacked containers. An over-height 40-foot container could consume 2 TEU horizontally and 2 TEU vertically, and be put in slots (0,0)-(2,2). This is, in fact, exactly how a GTK2 Table layout works.) Both types of intervals have their places.
ChrisA
On 01/20/2014 02:09 PM, Chris Angelico wrote:
On Mon, Jan 20, 2014 at 11:12 PM, spir denis.spir@gmail.com wrote:
For instance, closed intervals are more intuitive or natural, obviously (but for some reason I don't know). If you ask someone to count from 1 to 9, you will probably be surprised to hear him/her start from 2 or stop after 8. If you are asked to choose a letter between c and g, you will probably be surprised to hear that 'c' or 'g' is no good choice.
I'm not so sure about that. The half-open interval makes as much sense as the fully closed - all you have to do is interpret the indices as being *between* elements. Take, for example, Scripture verses. (Quotes taken from THE HOLY BIBLE, NEW INTERNATIONAL VERSION®, NIV® Copyright © 1973, 1978, 1984, 2011 by Biblica, Inc.® Used by permission. All rights reserved worldwide. Copyright notice included for license compliance. Note that I'm using bracketed numbers to indicate the beginnings of verses - in a printed Bible, these would normally be in superscript.)
John 14: [31] To the Jews who had believed him, Jesus said, “If you hold to my teaching, you are really my disciples. [32] Then you will know the truth, and the truth will set you free.” [33]
This passage is normally referred to as "John 14:31-32", but as you see, the verse marker [32] is in the middle of the quote. Using a half-open interval, this would start at "John 14:31" and end at "John 14:33". Half-open means: "Begin at the beginning, go on till you come to the end, then stop", as the King of Hearts instructed the White Rabbit.
It's easy to indicate the beginning of a chapter: your start reference is verse 1. Here's the beginning of the account of the creation of the world:
[1] In the beginning God created the heavens and the earth. [2] Now the earth was formless and empty, darkness was over the surface of the deep, and the Spirit of God was hovering over the waters. [3] And God said, “Let there be light,” and there was light. [4] God saw that the light was good, and he separated the light from the darkness. [5] God called the light “day,” and the darkness he called “night.” And there was evening, and there was morning—the first day. [6]
Common parlance: Genesis 1:1-5. Half-open: Genesis 1:1-6. Conclusion: Tie. No argument to be made for either side. But what if you're looking at the *end* of a chapter? Here are a few verses from later on in Genesis 1:
[29] Then God said, “I give you every seed-bearing plant on the face of the whole earth and every tree that has fruit with seed in it. They will be yours for food. [30] And to all the beasts of the earth and all the birds of the air and all the creatures that move on the ground—everything that has the breath of life in it—I give every green plant for food.” And it was so. [31] God saw all that he had made, and it was very good. And there was evening, and there was morning—the sixth day.
Common parlance: Genesis 1:29-31. Half-open: Genesis 1:29-2:1. It's much more obvious by the latter that this passage extends exactly to the end of the chapter.
I do agree with your reasoning, it is indeed totally logical. However, it is not at all intuitive or natural (maybe tis is why Bible refs do not work your way ;-) dunno).
This is probably related to the issue of prog indices interpreted as ordinals [*] or offsets. Aparently, obviously in fact, people intuitively or naturally interpret them as ordinals; which breaks your logic or conflicts with it. Whether it's "much more obvious" (quoting you in the last parag above) is a also question of how you interpret indices: if they're ordinals for you, then Genesis 1:29-31 is perfectly clear on where the ref'ed passage stops.
[*] "ordinal" in the mathematical or linguistic sense, meaning a natural number holding the rank of an item in a sequence (not python's ord())
Obviously it's way WAY too late to change the way Bible references are written, any more than Melway could renumber their maps all of a sudden. Massive case of lock-in and backward-incompatibility with existing code. But I put it to you that the half-open would make at least as much sense as the closed, in any situation where there are boundaries with contents between them.
Note, by the way, that I'm not looking at anything involving backward scanning or wider strides, both of which Python's slice notation supports. Neither of those is inherently real-world intuitive, so the exact semantics can be defined as whatever makes sense in code. (And there was some discussion a little while ago about exactly that.) I'm just looking at the very simple and common case of referencing a subset of consecutive elements from a much larger whole.
The closed interval makes more sense when the indices somehow *are* the values being retrieved.
You are right; see also note below on the case where [i,k[ is actually advantageous by itself.
When you count from 1 to 9, you expect nine numbers: 1, 2, ..., 8, 9. When you list odd numbers from 1 to 9, you expect 1, 3, 5, 7, 9. But what if you're looking at a container train and numbering the twenty-foot-equivalent-units (TEU) that it has? A 40-foot container requires 2 TEU, a 60-foot container requires 3 TEU. A "reefer" (refridgerated container) might require an extra slot, or at least it might be a 56-footer and consume 3 TEU. One wagon might, if you're lucky, carry 5 TEU; numbering them 1 through 5 would be obvious, but numbering the boundaries between them as 0 through 5 is better at handling the multiple TEU containers. (Even more so when you look at double-stacked containers. An over-height 40-foot container could consume 2 TEU horizontally and 2 TEU vertically, and be put in slots (0,0)-(2,2). This is, in fact, exactly how a GTK2 Table layout works.) Both types of intervals have their places.
I also think there may be 2 kinds of notations for slices and such, one beeing [i,j] and the other maybe (i,n) where n is the number of items, rather than [i,k[ where k is the "post-last" or "past-the-end" index. Reasons to think on that path:
* since n is not an index, it avoids all thinking trouble and misinterpretations with k as opposed to j; in particular, it avoids the "intuitive conflict" evoked above
* n makes sense and is useful by itself (eg think at typical arrays {p,n} or slices/views {i,n}, or at algos for copy, compare, traversal, concat, map...)
* when [i,k[ works better than [i,j], most often it's because we have n (k=i+n) or need n (n=k-j), thus we avoid +1 or -1; this, rather than any worth of k by itself
* other cases where [i,k[ seems to work nicely is "self-feeding" in fact: we have & need [i,k[ just because the lang uses that, but the same would be true whatever the interval notation (eg the lang returns i,k from a builtin func searching something in a seq, and we then use it to get a subseq)
* the only advantage of k by itself, logically, I think, is when scanning a non-terminated token (eg a number): we must pass the last item (digit) to know the token is finished, thus end up holding i & k, not i & j; however, if we use (i,n) notation, it's easy enough to write (i,k-i), so no big deal, just as in the opposite case; and this situation is obviously, i guess, a little minority of uses of intervals [1]
Anyway, i think only practice of alternatives and talk among non-ideologically blinded programmers can tell us what's worth or not.
Denis
[1] However, from a semantic point of view, [i,k[ is problematic even in this very case where it seems nicer at first sight, because we don't need to type -1. Say we're scanning for a number and there is "1234567" in source: <-----> n 1234567 i jk We get i & k. If the lang uses [i,k[ intervals, then we just write it that way to get the right substring, and are pleased not to have to type -1. However, the "semantic truth" (if I may say) is that we stopped scanning *after* the last digit, and need to slice up to the *previous* character. This is not written in s[i,k]; where is the idea "up to the previous position" expressed in this notation? "Previous" translates to -1 in arithmetic or programming. For the notation to be semantically correct, it should say "-1" somewhere. And this is why closed intervals s[i,k-1] are superior, from the semantic perspective, even in this case, the very case where half-open intervals superficially look nicer. Half-open intervals do not say what they mean, so-to-say, they cheat ;-) (booh!)
A related point (semantics, thinking) is that, as far as i know, many programmers in langs using [i,k[ just do *not* think it. They just know from exp that it just works in most cases (reasons listed above) but do not think, for instance in this case along the lines: "all right, we stop after the last digit, thus need to slice up to the previous position, thus a half-open interval is right here". No, they seem to do it blindly like an automat. I asked other programmers about that when I noticed it was true by me (i use it blidly, don't know on a given case why/how it works unless I stop and *start* to think). I just prefer (to be) a programmer who thinks than a coding machine, but it's just me.
On Tue, Jan 21, 2014 at 1:29 AM, spir denis.spir@gmail.com wrote:
I also think there may be 2 kinds of notations for slices and such, one beeing [i,j] and the other maybe (i,n) where n is the number of items, rather than [i,k[ where k is the "post-last" or "past-the-end" index.
This is why REXX has the "DO... FOR" loop syntax. You can code a loop thus:
do i=1 to 5 /* 1, 2, 3, 4, 5 */
do i=1 to 5 by 2 /* 1, 3, 5 */
do i=1 by 2 for 6 /* 1, 3, 5, 7, 9, 11 */
The 'for N' criterion specifies the number of iterations to do, regardless of the stop position. (REXX doesn't have slice notation, so loops are the nearest equivalent.) It would be quite reasonable to create a slice-like object in Python, but I'm not sure how to put all of this functionality into syntax that's tight enough to be useful - nobody wants to write foo[slice(1,None,2,count=5)] !
ChrisA
+1 for the example you used.
On Mon, Jan 20, 2014 at 7:09 AM, Chris Angelico rosuav@gmail.com wrote:
On Mon, Jan 20, 2014 at 11:12 PM, spir denis.spir@gmail.com wrote:
For instance, closed intervals are more intuitive or natural, obviously
(but
for some reason I don't know). If you ask someone to count from 1 to 9,
you
will probably be surprised to hear him/her start from 2 or stop after 8.
If
you are asked to choose a letter between c and g, you will probably be surprised to hear that 'c' or 'g' is no good choice.
I'm not so sure about that. The half-open interval makes as much sense as the fully closed - all you have to do is interpret the indices as being *between* elements. Take, for example, Scripture verses. (Quotes taken from THE HOLY BIBLE, NEW INTERNATIONAL VERSION®, NIV® Copyright © 1973, 1978, 1984, 2011 by Biblica, Inc.® Used by permission. All rights reserved worldwide. Copyright notice included for license compliance. Note that I'm using bracketed numbers to indicate the beginnings of verses - in a printed Bible, these would normally be in superscript.)
John 14: [31] To the Jews who had believed him, Jesus said, “If you hold to my teaching, you are really my disciples. [32] Then you will know the truth, and the truth will set you free.” [33]
This passage is normally referred to as "John 14:31-32", but as you see, the verse marker [32] is in the middle of the quote. Using a half-open interval, this would start at "John 14:31" and end at "John 14:33". Half-open means: "Begin at the beginning, go on till you come to the end, then stop", as the King of Hearts instructed the White Rabbit.
It's easy to indicate the beginning of a chapter: your start reference is verse 1. Here's the beginning of the account of the creation of the world:
[1] In the beginning God created the heavens and the earth. [2] Now the earth was formless and empty, darkness was over the surface of the deep, and the Spirit of God was hovering over the waters. [3] And God said, “Let there be light,” and there was light. [4] God saw that the light was good, and he separated the light from the darkness. [5] God called the light “day,” and the darkness he called “night.” And there was evening, and there was morning—the first day. [6]
Common parlance: Genesis 1:1-5. Half-open: Genesis 1:1-6. Conclusion: Tie. No argument to be made for either side. But what if you're looking at the *end* of a chapter? Here are a few verses from later on in Genesis 1:
[29] Then God said, “I give you every seed-bearing plant on the face of the whole earth and every tree that has fruit with seed in it. They will be yours for food. [30] And to all the beasts of the earth and all the birds of the air and all the creatures that move on the ground—everything that has the breath of life in it—I give every green plant for food.” And it was so. [31] God saw all that he had made, and it was very good. And there was evening, and there was morning—the sixth day.
Common parlance: Genesis 1:29-31. Half-open: Genesis 1:29-2:1. It's much more obvious by the latter that this passage extends exactly to the end of the chapter.
Obviously it's way WAY too late to change the way Bible references are written, any more than Melway could renumber their maps all of a sudden. Massive case of lock-in and backward-incompatibility with existing code. But I put it to you that the half-open would make at least as much sense as the closed, in any situation where there are boundaries with contents between them.
Note, by the way, that I'm not looking at anything involving backward scanning or wider strides, both of which Python's slice notation supports. Neither of those is inherently real-world intuitive, so the exact semantics can be defined as whatever makes sense in code. (And there was some discussion a little while ago about exactly that.) I'm just looking at the very simple and common case of referencing a subset of consecutive elements from a much larger whole.
The closed interval makes more sense when the indices somehow *are* the values being retrieved. When you count from 1 to 9, you expect nine numbers: 1, 2, ..., 8, 9. When you list odd numbers from 1 to 9, you expect 1, 3, 5, 7, 9. But what if you're looking at a container train and numbering the twenty-foot-equivalent-units (TEU) that it has? A 40-foot container requires 2 TEU, a 60-foot container requires 3 TEU. A "reefer" (refridgerated container) might require an extra slot, or at least it might be a 56-footer and consume 3 TEU. One wagon might, if you're lucky, carry 5 TEU; numbering them 1 through 5 would be obvious, but numbering the boundaries between them as 0 through 5 is better at handling the multiple TEU containers. (Even more so when you look at double-stacked containers. An over-height 40-foot container could consume 2 TEU horizontally and 2 TEU vertically, and be put in slots (0,0)-(2,2). This is, in fact, exactly how a GTK2 Table layout works.) Both types of intervals have their places.
ChrisA _______________________________________________ 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 Mon, Jan 20, 2014 at 7:09 AM, Chris Angelico <rosuav@gmail.com mailto:rosuav@gmail.com> wrote:
Note, by the way, that I'm not looking at anything involving backward scanning
That would be for when you were reading your Bible text backwards, looking for hidden Satanic references.
If someone does that, they have more problems than one.
On Mon, Jan 20, 2014 at 10:56 PM, Greg Ewing greg.ewing@canterbury.ac.nzwrote:
On Mon, Jan 20, 2014 at 7:09 AM, Chris Angelico <rosuav@gmail.com <mailto:
rosuav@gmail.com>> wrote:
Note, by the way, that I'm not looking at anything involving backward scanningThat would be for when you were reading your Bible text backwards, looking for hidden Satanic references.
-- 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 Sun, Jan 19, 2014 at 10:31:06PM +1000, Nick Coghlan wrote:
Guido is on record as preferring iterative algorithms as more comprehensible for more people, and explicitly opposed to adding tail call optimisation.
Many people struggle with recursion. Many people struggle with couroutines, and asychronous programming, and Unicode. Some people never quite get the hang of object oriented programming. That doesn't imply that Python should only offer features which nobody struggles with. It would be a pretty bare language if that were the case :-)
I tend to agree with him - functional programming works OK in the small (and pure functions are a fine tool for managing complexity), but to scale up in a way that fits people's brains, you need to start writing code that looks more like a cookbook.
Python is not a pure functional language. Adding TCE won't make it one. If somebody wants to write their app in a pure functional manner, they're either not going to use Python at all, or they'll do it regardless of the lack of TCE and just grumble that Python is only suitable for "toy" applications.
But as a *component* of a larger "cookbook" style application, pure functions are great. And some functions are more naturally written in recursive style rather than iterative. I have no interest in writing my entire app as a pure-functional app (if I wanted to do that, I'd use Haskell). But I do have great interest in being able to write functions in the most natural way possible, and that sometimes means recursively, without having to compromise for performance.
If you want inspiration on how to design a language for typical human thought patterns, look to cookbooks, training guides and operator manuals, not mathematics.
And Python is a great example of that, but it's not really relevant to the idea of adding TCE. Or at least, its no more relevant than are people's grumbles that adding such things as closures and coroutines makes Python more complex and too advanced for "ordinary programmers".
Adding TCE need not affect Python as a language. People who like iteration will still write iterative functions. People who think like Java programmers will still write Java in Python, people who think like bash scriptors will still write bash in Python. The only addition is that people who think like Scheme programmers will have one less thing to complain about Python *wink*
Most programmers write for themselves, or for a small group. Arguing that Sue (who can think recursively) ought to write her code using an iterative algorithm because Tom and Jerry won't otherwise understand it is not a terribly strong argument when Tom and Jerry aren't in Sue's target audience.
On Sun, Jan 19, 2014 at 07:12:16AM -0500, Terry Reedy wrote:
Are you willing to do any of the work needed to make the option available, starting with a specification? If so, I have some ideas.
Given the amount of controversy over this, it would probably need a PEP. I might be able to start with a pre-PEP, time permitting, and see how that goes. (If those interminable bytes/unicode/2.8 threads on the Python-Dev list would start to die off, I might have more time to treat this seriously.)
Having to fork the entire compiler just to write a few functions in their most idiomatic, natural (recursive) form seems a bit extreme, wouldn't you say?
A 'fork' could consist of a relatively small patch that could be uploaded to, for instance, PyPI. I would not be surprised if 100-200 lines might be enough.
Lines of *C* though, right? Which means for anyone to use it, they would have to be willing to build Python from source, applying your patch, or the maintainer would have to volunteer to provide pre-built binaries. Neither of which is exactly a recipe for broad take-up.
On 1/19/2014 7:23 PM, Steven D'Aprano wrote:
On Sun, Jan 19, 2014 at 07:12:16AM -0500, Terry Reedy wrote:
Are you willing to do any of the work needed to make the option available, starting with a specification? If so, I have some ideas.
Since writing the above, I came across the 'return from' idea, which I think is the best so far, and better than any of the 'ideas' I was thinking of. See my 'return from' post.
Given the amount of controversy over this, it would probably need a PEP. I might be able to start with a pre-PEP, time permitting, and see how that goes. (If those interminable bytes/unicode/2.8 threads on the Python-Dev list would start to die off, I might have more time to treat this seriously.)
A 'fork' could consist of a relatively small patch that could be uploaded to, for instance, PyPI. I would not be surprised if 100-200 lines might be enough.
Lines of *C* though, right?
Yes.
Which means for anyone to use it, they would have to be willing to build Python from source, applying your patch, or the maintainer would have to volunteer to provide pre-built binaries.
A typical combination is source for *nix and a Windows installer.
Neither of which is exactly a recipe for broad take-up.
Use of macropy.experimental.tco would give some indication of the popularity of the idea. Without using it, I do not know how close it is.
A 'return from' patch could start by copying the code that recognizes 'yield from' and compiles it to a YIELD_FROM bytecode. (Or by looking at the part of the yield from patch that added the code.) Writing code to implement a RETURN_FROM bytecode, by modifying the RETURN_VALUE function, would be a separate step.
On 01/19/2014 01:45 AM, Steven D'Aprano wrote:
What makes you say that it is "non-pythonic"? You seem to be assuming that *by definition* anything written recursively is non-pythonic. I do not subscribe to that view.
It is certainly hard to judge the size of the field of "naturally" recursive algorithms. First it depends on applications or application domains, on thinking habits, on kinds of data structures... one is accustomed with. Second, there is much vagueness and ambiguity on the very term of recursion in programming. Recursion and recurrence just mean literally re-running, that is a cyclic, repetitive, looping, (re)iterative process.
The typical case used as example is factorial. fact(0) = 1 fact(n) = n * fact(n-1)
This is plain semantics. To get an *algorithm* to *compute* fact(n), one can interpret these semantics in 2 ways: * forward iteration: start with base case (0) then as long as we don't reach n compute the next factorial * backward iteration: start with n, then as long as we don't reach the base case compute the previous factorial Both are recursive, but in programming we call the second case a recursion, while the former is at times called corecursion (see wikipedia); corecursion is just equivalent to plain loops, since moving forward, and just as easy to understand. [Which is for the least strange, I'd happily swap the terms.] [And the actual computing process of backward iteration is actually forward, indeed, but this does not appear in code.]
Funnily enough (since sum is rarely used as example) the trivial case of sum can lead to a similar reasoning.
For quite a while I played with mostly functional languages, and as a consequence implemented many routines as "backward recursions" (ending with the base case), even when back to procedural programming, especially when dealing with tree-like or other linked data. I remember a case of a radix trie (see wikipedia) which I had a hard time getting right, actually a hard time *thinking*. Then by pure chance I stepped on an implementation of tries in python, using "forward recursion", which was trivial to understand. I translated the logic to my C trie, very happily. This radically changed my view on "naturally" recursive algorithms. That tries (and other linked data when implemented the functional way) are *self-similar* (see wikipedia) data structures, that thus corresponding algorithms too are "naturally" self-similar, does not imply that *backward* recursion is the natural / simple / easy way.
(Now, I do agree that def fact (n): return 1 if n<2 else n * fact(n-1) is very ok: simple and easy enough... once one gets the very principle of backward recursion, meaning thinking recurrence so-to-say inside out.)
Denis
From: Steven D'Aprano steve@pearwood.info
Sent: Saturday, January 18, 2014 4:45 PM
On Sat, Jan 18, 2014 at 10:29:46AM -0800, Andrew Barnert wrote:
Whether or not you really need it, adding it to Python is a fun challenge that's worth trying.
"Need" is a funny thing.
Which I why I made that point. It's not a completely objective question, and it may be hard for the OP (or you, or anyone else) to convince anyone that he "needs" it even though he does (or, more importantly, convince people that _they_ need it). If so, he doesn't have to let that stop him from writing and sharing an implementation. It may turn out that, once people have a chance to play with it, that will convince everyone better than any abstract argument he could make. If not, at least he's had fun, learned about CPython internals, and, most importantly, produced a fork that he can maintain as long as he thinks he needs it. Depending on your time and resources, that may not be worth doing, but that's the same decision as any other development project; there's nothing actually stopping anyone from doing it if it's worth their while, so anyone who wants this should consider whether it's worth their while to do it.
You can go a long way without recursion, or only shallow recursion. In 15 years + of writing Python code, I've never been in a position that I couldn't solve a problem because of the lack of tail recursion. But every time I manually convert a recursive algorithm to an iterative one, I feel that I'm doing make-work, manually doing something which the compiler is much better at than I am, and the result is often less natural, or even awkward. (Trampolines? Ewww.)
But the same is true for converting a naive recursive algorithm to tail-recursive. It's unpleasant make-work, just like converting it to iteration. In a language like Common Lisp, it's about the same amount of work, but the tail-recursive version often ends up looking more natural. In a language like Python, where we typically deal in iterables rather than recursive data structures, I believe it would often be _more_ work rather than the same amount, and end up looking a lot less natural rather than more. I'm sure there would be exceptions, but I suspect they would be rare.
Third, eliminating tail calls means the aren't on the stack at runtime, which means there's no obvious way to display useful tracebacks. I don't think too many Python users would accept the tradeoff of giving up good tracebacks to enable certain kinds of non-pythonic code,
What makes you say that it is "non-pythonic"? You seem to be assuming that *by definition* anything written recursively is non-pythonic.
Not at all. There's plenty of code that's naturally recursive even in Python—and much of that code is written recursively today. For a good example, see os.walk.
However, the main driver for TCE is the ability to write looping constructs recursively, which is not possible without it (unless the thing you're looping over is guaranteed not to be too big). Look at any tutorial on tail recursion; it's always recursing over a cons list or something similar. And looping that way in Python will almost always be non-pythonic, because you will have to drive the iterable manually. Again, there are surely exceptions, but I doubt they'd be very common.
In fact, in some cases, I *would* willingly give up *non-useful*
tracebacks for the ability to write more idiomatic code. Have you seen the typical recursive traceback?
But if you eliminate tail calls, you're not just eliminating recursive tracebacks; you're eliminating every stack frame that ends in a tail call. Which includes a huge number of useful frames.
If you restrict it to _only_ eliminating recursive tail calls, then it goes from something that can be done at compile time (as I showed in my previous email) to something that has to be done at runtime, making every function call slower. And it doesn't work with mutual or indirect recursion (unless you want to walk the whole stack to see if the function being called exists higher up—which makes it even slower, and also gets us back to eliminating useful tracebacks).
py> a(7) Traceback (most recent call last): File "<stdin>", line 1, in <module> File "./rectest.py", line 2, in a return b(n-1) File "./rectest.py", line 5, in b return c(n-1) + a(n) File "./rectest.py", line 2, in a return b(n-1) File "./rectest.py", line 5, in b return c(n-1) + a(n) File "./rectest.py", line 2, in a return b(n-1) File "./rectest.py", line 5, in b return c(n-1) + a(n) File "./rectest.py", line 2, in a return b(n-1) File "./rectest.py", line 5, in b return c(n-1) + a(n) File "./rectest.py", line 2, in a return b(n-1) File "./rectest.py", line 5, in b return c(n-1) + a(n) File "./rectest.py", line 2, in a return b(n-1) File "./rectest.py", line 5, in b return c(n-1) + a(n) File "./rectest.py", line 9, in c return 1/n ZeroDivisionError: division by zero
The only thing that I care about is the very last line, that function c tries to divide by zero. The rest of the traceback is just noise, I don't even look at it.
Your example is not actually tail-recursive.
I'm guessing you know this, and decided that having something that blows up fast just to have an example of a recursive traceback was more important than having an example that also fits into the rest of the discussion—which is perfectly reasonable.
But it's still worth calling that out, because at least half the blog posts out there that say "Python sucks because it doesn't have TCE" prove Python's suckiness by showing a non-tail-recursive algorithm that would blow up exactly the same way in Scheme as in Python.
Now, it's okay if you disagree, or if you can see something useful in
the traceback other than the last entry.
Sure. Unless that line in b is the only place in your code that ever calls c, I think it would be useful to know how we got to c and why n is 0. If that isn't useful, than _no_ tracebacks are ever useful, not just recursive ones.
I'm not suggesting that TCE should be compulsary. I would be happy with a commandline switch to turn it on, or better still, a decorator to apply it to certain functions and not others. I expect that I'd have TCE turned off for debugging.
But the primary reason people want TCE is to be able to write functions that otherwise wouldn't run. Nobody asks for TCE because they're concerned about 2KB wasted on stack traces in their shallow algorithm; they ask for it because their deep algorithm fails with a recursion error. So, turning it off to debug it means turning off the ability to reproduce the error you're trying to debug.
but even if you don't solve this, you can always
maintain a fork the same way that Stackless has been doing.
Having to fork the entire compiler just to write a few functions in their most idiomatic, natural (recursive) form seems a bit extreme, wouldn't you say?
Not necessarily.
The whole reason Stackless exists is to be able to write some algorithms in a natural way that wasn't possible with mainline CPython. At least early on, it looked at least plausible that Stackless would eventually be merged into the main core, although that turned out not to happen. There are some core language changes that were inspired by Stackless. Someone (Ralf Schmidt, I think?) was able to extract some of Stackless's functionality into a module that works with CPython, which is very cool. But even without any of that, people were able to use Stackless when they wanted to write code that required its features. That's surely better than not being able to write it, period.
And a TCE fork could go the same way. It might get merged into the core one day, or it might inspire some changes in the core, or it might turn out to be possible to extract the key functionality into a module for CPython—but even if none of that happens, you, and others, can still use your fork when you want to.
If you prefer to call it a patch or a branch or something else instead of a fork, that's fine, but it's basically the same amount of work either way, and there's nothing stopping anyone who wants it from doing it.
On Sun, Jan 19, 2014 at 12:01:00PM -0800, Andrew Barnert wrote:
From: Steven D'Aprano steve@pearwood.info
[...]
In fact, in some cases, I *would* willingly give up *non-useful* tracebacks for the ability to write more idiomatic code. Have you seen the typical recursive traceback?
But if you eliminate tail calls, you're not just eliminating recursive tracebacks; you're eliminating every stack frame that ends in a tail call. Which includes a huge number of useful frames.
If you restrict it to _only_ eliminating recursive tail calls, then it goes from something that can be done at compile time (as I showed in my previous email) to something that has to be done at runtime, making every function call slower. And it doesn't work with mutual or indirect recursion (unless you want to walk the whole stack to see if the function being called exists higher up—which makes it even slower, and also gets us back to eliminating useful tracebacks).
But if TCE becomes opt-in, say by the proposed "return from" syntax, then you can keep your cake and eat it too. I can decide at *edit* time, "this function should have TCE enabled", and leave the rest of my code to have the "normal" behaviour.
If the choice was "TCE everywhere" versus "TCE nowhere", I would choose nowhere too. But it need not be that choice.
py> a(7) Traceback (most recent call last): File "<stdin>", line 1, in <module> File "./rectest.py", line 2, in a return b(n-1) File "./rectest.py", line 5, in b return c(n-1) + a(n)
[...]
File "./rectest.py", line 9, in c return 1/n ZeroDivisionError: division by zero
The only thing that I care about is the very last line, that function c tries to divide by zero. The rest of the traceback is just noise, I don't even look at it.
Your example is not actually tail-recursive.
I'm guessing you know this, and decided that having something that blows up fast just to have an example of a recursive traceback was more important than having an example that also fits into the rest of the discussion—which is perfectly reasonable.
Yes, you got me. It was throw away code, which I've since thrown away, but if I recall correctly one of the three functions was tail-recursive. I was more concerned with making the rhetorical point that sometimes the only part of the traceback you care about is the bit that actually fails, at which point the rest of the traceback is noise and you might choose to prefer performance over a more detailed traceback.
But it's still worth calling that out, because at least half the blog posts out there that say "Python sucks because it doesn't have TCE" prove Python's suckiness by showing a non-tail-recursive algorithm that would blow up exactly the same way in Scheme as in Python.
I work with one of those guys :-(
I'm not suggesting that TCE should be compulsary. I would be happy with a commandline switch to turn it on, or better still, a decorator to apply it to certain functions and not others. I expect that I'd have TCE turned off for debugging.
But the primary reason people want TCE is to be able to write functions that otherwise wouldn't run. Nobody asks for TCE because they're concerned about 2KB wasted on stack traces in their shallow algorithm; they ask for it because their deep algorithm fails with a recursion error. So, turning it off to debug it means turning off the ability to reproduce the error you're trying to debug.
You seem to be assuming that bugs in deep algorithms only manifest themselves in sufficiently deep data sets that turning TCE off will cause a recursion error before the true bug manifests, thus masking the bug you care about by mere lack of resources.
I don't believe that is the case for all bugs, or even a majority. If it is true for some bugs -- of course it will be -- then a solution is to add enough temporary debugging code (e.g. logging, or even just good ol' print) to see enough of what is going on that you can identify the bug, stacktrace or no stacktrace. Chances are you would have to write some temporary debugging code regardless of whether the algorithm was iterative or recursive, TCE or no TCE.
On Jan 19, 2014, at 17:49, Steven D'Aprano steve@pearwood.info wrote:
But if TCE becomes opt-in, say by the proposed "return from" syntax, then you can keep your cake and eat it too. I can decide at *edit* time, "this function should have TCE enabled", and leave the rest of my code to have the "normal" behaviour.
My first post on the subject suggested adding a new keyword (I think I used "tailcall", borrowed from Guido's post) to do explicit tail calls, and only building TCE as an automatic optimization on top of it (which I'm pretty sure could be done with a trivial peephole optimizer rule) if you still need it after that. So obviously, I agree with this.
And yes, "return from" is definitely better than "tailcall"--readable and understandable, no new keyword, etc.
And I still think this would be a fun project even though I don't think I would ever use it. I tried effectively this same design against Stackless 2.6 a few years ago, but it sometimes leaked, and would crash whenever a C function called a Python function that tail called, and I ran out of free time to debug any further. The point is, this isn't a massive impossible project; many of the people insisting they want it are probably capable of writing it, even if they've never tried hacking on the interpreter. (The grammar is a huge pain the first time, however...)
Andrew Barnert, 18.01.2014 19:29:
The first problem is that CPython makes a C function call for every Python function call, and C doesn't eliminate tail calls; the only way to do it manually is with longjmp
Many C compilers actually fold tail recursion into loops. However, that has nothing to do with an *interpreter* that happens to be written in C not eliminating tail recursion. There is no technical reason you couldn't do TRE in CPython at the *interpreter* level. And this has nothing to do with longjmp.
Stefan
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/
On 1/18/2014 9:52 AM, musicdenotation@gmail.com wrote:
A few notes first:
1) A tail call is a 'top level' call in a return statement. return f(*args, **kwds) A directly recursive call, where f refers to the function with the return statement, is a special case.
2) Whether a tail call is directly recursive cannot be determined, in Python, at compile time merely by looking at the function definition. If 'f' is the definition name of the function, an assumption can be made, but doing so is a semantic change in the language.
3). 'Tail recursion elimination' has two quite different meanings.
3a. Compile the (in Python, assumed to be) directly recursive function as if it had been written with a while loop. This is typically done in languages that do not expose while loops. This eliminates the function call overhead as well as stack growth. This does nothing for indirect recursion through intermediate function calls.
3b. At runtime, make the call but reuse the current stack frame. This is easily done (at least in CPython) for all tail calls. But doing so for all tail calls will make stack traces pretty useless, as tail calls are rather common. Determining whether the call is recursive, to limit stack reuse, takes extra work. Either choice only eliminates stack growth.
Comments on some of you responses to a *subset* of TRE issues.
On April 22, 2009, Guido van Rossum wrote:
First, <the stack trace issue>
...
Do [while/for] loops have nice stack traces as you mean it?
No, if you want a complete trace, you must add a print statement inside the loop. Looping with tail recursion gives you the complete trace for free.
Second, <what is fundamental>
... What is fundamental, besides alternation, is the ability to express an unbounded amount of repetition, with variation, in a small finite amount of code. I call this computational induction, in analogy to mathematical induction. The alternative implemenations include recursion and explicit while/for loops. There are also the combinator and fixed point approaches.
<writing repetition with explicit loops>
I think the most obvious way to do something is how it is /defined/.
Most recursive definitions are naturally written with body recursion rather than tail recursion. A simple example (without input checking) is the factorial function.
def fact(n): if n: return fact(n-1) * n else: return 1
To get TRE, one must re-write in tail-recursive form. (Python default arguments actually make this easier than in most languages.)
def fact(N, n=1, result=1): if n<N: return fact(n+1, result*(n+1) else: return result
I have intentionally written the tail form so it calculates intermediate results in the same order, making no assumption that the reduction operator is either cummutative or associative. Once the work of converting to tail form is done, conversion to while form is trivial and easier than the conversion from body to tail recursion.
def fact(N): n, result = 1, 1 while n < N: n, result = n+1, result*(n+1)
But in fact, Python has another alternative, for loops.
def fact(N): result = 1 for n in range(2, N): result = result * n return result
For loops are the proper way to write most collection processing that one could write with tail recursion, as it makes use of Python's iterator protocol.
def sum(iterable): sum = 0 for n in iterable: sum = sum + n return sum
To write that with either recursion or while, one must call iter() and next() and catch StopIteration oneself. Try it (I have) and see if you really think it more natural. Lisp/scheme get away with recursion for collection processing because there is only one collection type and clever pattern-matching syntax to deconstruct an instance to get one element at a time. I personally consider the efficiency of for loops, for both programmer and computer, to be a major reason to not bother with TRE.
On 01/19/2014 12:09 AM, Terry Reedy wrote:
I share all your views except for the following, which in my view is incomplete:
- A tail call is a 'top level' call in a return statement. return f(*args, **kwds)
A directly recursive call, where f refers to the function with the return statement, is a special case.
This is also true for "actions" (rather than proper functions, which purpose is to compute a new piece of data). It's actually rather common (also in C ;-). There is no data procuct. (see PS)
Denis
PS: An example may be an "action" writing out list items which calls, or rather delegates to, another action that writes additional items preceded by a separator.
def write_items (stream, l): n = len(l) if n == 0: stream.write('\n') return
stream.write(str(l[0])) if n == 1 : return
write_other_items(stream, l, n) # tail call
def write_other_items (stream, l, n): for i in range(1,n): stream.write(" ") stream.write(str(l[i])) stream.write('\n')
from sys import stdout l = [] write_items(stdout, l) l = [1] write_items(stdout, l) l = [1,2,3] write_items(stdout, l)
-
Andrew Barnert -
Chris Angelico -
Greg Ewing -
Joao S. O. Bueno -
Mark Lawrence -
musicdenotation＠gmail.com -
Ned Batchelder -
Nick Coghlan -
Ryan -
Ryan Gonzalez
-
spir -
Stefan Behnel -
Steven D'Aprano -
Terry Reedy