9 ms·

But tailcalls already have a syntax: return f(a, b, c) # tailcall on f return f(g(b)) # tailcall on f return f(a, b, c) + 0 # tail call on + The

by art-w 11y ago

But tailcalls already have a syntax: return f(a, b, c) # tailcall on f return f(g(b)) # tailcall on f return f(a, b, c) + 0 # tail call on + The last function to be called before a return is tailcall. That's it. Nothing more. It doesn't matter that the return "expression" can be more complex, only the last call is concerned. It's a simple rule. Now, regarding your concern for the static analysis of stack allocation: This is not a feature you have for any other aspect of the language... you have no way of specifying your expected memory consumption. But you do have your experience, you know the traps, you have learned the patterns to look for. Sure, the annotation could be used by a static linter, but builtin static analysis is not a feature in Python. Why should tailcalls be a syntaxic exception? (Note: tail recursion is a special case of tail calls! The annotation you are thinking about would be more interesting as a function annotation, as you really don't want to track each of your recursive returns to state your global expectation.) What you are asking for is common for new language features: You want a red flag, something that highlight the semantic prominently, so that you don't forget and are forced to think about something you aren't used to. Please have a look at your python code: how many returns end with a call to a function? Are you going to decorate each of them with "tailreturn"? It's really a free optimization, your program will run faster and consume less memory once it is there. (Is Python even specifying that its implementation should use a stack?)

beagle3 11y ago
My problem is that given the following examples, only 3 can be eliminated even though there's no visible marker: return f(a,b,c) return f(a,b,c) or False try: return f(a,b,c) finally: os.remove(tempfilename) return [north,south,west,east][dir]() return a[0] In the presence of try (also with, and perhaps a few others I can't think of right now) even the examples you gave cannot be TCEd. Personally, I consider broken a language in which enclosing a construct with "try: .... finally: pass" to switch between constant memory and endless memory requirements. That is already true for scheme in a way. Guido's refusal to break python in this sense is wholly supported by me, even if that's not his reason to refuse. And "return from" suggested by another poster is the perfect pythonic syntax for such a thing. And I definitely thing it is a property of the specific call site, NOT the entire function, whether it should be checked for tailness. Decorators are the wrong solution here.
- art-w 11y ago
  What's so invisible about your examples? I agree that an optimizing interpreter makes the situation harder to analyse, because we can't remember every simplification it handles. Without it, the tailcalls are very explicit. Previously, you argued that Python semantics makes it very clear that all costs are visible. This seems to be against any rewrite rule, as the visible cost ("or False", "+ 0", "finally: pass") suddenly disappear. You are using your own rebuttal as an argument to make tailcalls look harder to analyse! They are not. > And I definitely thing it is a property of the specific call site, NOT the entire function, whether it should be checked for tailness. Decorators are the wrong solution here. As a caller of a function, the property you care about is "does it consumes a fixed amount of stack?". As the writer of this function, that's the thing that matters in the end: Sure, that means checking each tail calls, but you really want the global guarantee that you didn't forgot one. The local explicit annotation becomes redundant.
  - beagle3 11y ago
    You wrote earlier: > But tailcalls already have a syntax: > > return f(a, b, c) # tailcall on f However, this tail call cannot be eliminated in the context of a try: or with: scope. Ergo, it is NOT tail call syntax. Using it does not guarantee that the tail call can be eliminated: def write_list_to_file(file, list): "Looks weird, but it has reason to do this based on overall system architecture" try: item = list[0] list[0] = None file.write(item) return write_list_to_file(file, list[1:]) finally: list[0] = item Despite being compatible with your "tailcall syntax", this is not actually a tailcall. Ergo: no tailcall syntax. Proponents of tail calls almost always ignore a very simple practical consideration: If you rely on a tail call being eliminated and it isn't, then your program becomes incorrect, in the sense that it goes from needing constant memory to needing infinite memory. I simply cannot fathom what argument one might have against an annotation "this tail call must be eliminated for this program to be correct" that can easily be verified by the compiler (is the compiled call site CALL instruction followed by a RET opcode? if so, it's a tail call. If not, it's not!). Not doing so means that an enclosing context can change the meaning of the (recursive equivalent to) "while 1:" to "for x in range(MEMORY): ...; raise OutOfMemoryException();" based on compiler optimization capability. > You are using your own rebuttal as an argument to make tailcalls look harder to analyse! They are not. No, I claim that they are extremely easy to analyze for a compiler; They are not as easy for a reader (with/try context 50 lines away converts a tail call into a non tail call. You have to both be aware of the context and of this possibility - or you will be unwittingly replacing a while loop with a limited for loop). If you claim that it is easy to analyze for a reader, then you are not considering Python's original and still significant audience: non programmers. > As a caller of a function, the property you care about is "does it consumes a fixed amount of stack?". Yes, you do. And as a caller of a function, you don't see or control its attributes in any way, so that isn't an argument for or against decorators. > As the writer of this function, that's the thing that matters in the end: Sure, that means checking each tail calls, but you really want the global guarantee that you didn't forgot one. The local explicit annotation becomes redundant. You have two wrong assumptions here: 1) That if all returns are tail calls, then constant stack use is guaranteed. 2) That I actually want every return to be a tail call Neither of these are necessary. Therefore, while such a decorator may be useful for your style, it does not make a local explicit annotation redundant. Consider a very sparse tree data structure with n nodes, and 0-500 children for every node, but with only log(n) of the nodes having more than one child. (It arises in practice e.g. when building a suffix array on some kinds of inputs; The Patricia tree is an optimization of this). Computing on this structure can be done as follows, assuming some special case for 2-children nodes: def collect(node, acc): if node.count_children() == 0: return acc + node.value if node.count_children() == 1: return collect(node.get_child(0), acc + node.value) # this is key to memory use if node.count_chilren() == 2: return acc + PAIR_START + collect(node.get_child(0), 0) + collect(node.get_child(1), 0) + PAIR_END acc = acc + MULTI_START for child in node.get_children(): acc = acc + collect(child, 0) acc = acc + MULTI_END return acc Now, the key collect() call determines overall memory use; if there's TCE, it will be overall O(log n). If there isn't, it will be O(n). If you add a try: finally: (with actual code, not finally:pass) it will become O(n) regardless. The example is realistic, although somewhat contrived to be compact. If your argument isn't "well, you don't need new syntax and help from the compiler if you just pay attention and remember not to use with/try if you ever need guaranteed tail calls", then please state it more clearly because I haven't understood it. And if that's your argument, then I think it is technically right but practically wrong (in the same sense that saying "python is useless, you can do everything in assembly" is technically right and practically wrong)
beagle3 11y ago
P.s: python has (or at least had) "static" analysis of the kind w.r.t exceptions and generators when they didn't mix well. And python's call stack is sort-of visible through tracebacks, frames, and stuff like that.

by art-w 11y ago

beagle3 11y ago

My problem is that given the following examples, only 3 can be eliminated even though there's no visible marker: return f(a,b,c) return f(a,b,c) or False try: return f(a,b,c) finally: os.remove(tempfilename) return [north,south,west,east][dir]() return a[0] In the presence of try (also with, and perhaps a few others I can't think of right now) even the examples you gave cannot be TCEd. Personally, I consider broken a language in which enclosing a construct with "try: .... finally: pass" to switch between constant memory and endless memory requirements. That is already true for scheme in a way. Guido's refusal to break python in this sense is wholly supported by me, even if that's not his reason to refuse. And "return from" suggested by another poster is the perfect pythonic syntax for such a thing. And I definitely thing it is a property of the specific call site, NOT the entire function, whether it should be checked for tailness. Decorators are the wrong solution here.

art-w 11y ago
What's so invisible about your examples? I agree that an optimizing interpreter makes the situation harder to analyse, because we can't remember every simplification it handles. Without it, the tailcalls are very explicit. Previously, you argued that Python semantics makes it very clear that all costs are visible. This seems to be against any rewrite rule, as the visible cost ("or False", "+ 0", "finally: pass") suddenly disappear. You are using your own rebuttal as an argument to make tailcalls look harder to analyse! They are not. > And I definitely thing it is a property of the specific call site, NOT the entire function, whether it should be checked for tailness. Decorators are the wrong solution here. As a caller of a function, the property you care about is "does it consumes a fixed amount of stack?". As the writer of this function, that's the thing that matters in the end: Sure, that means checking each tail calls, but you really want the global guarantee that you didn't forgot one. The local explicit annotation becomes redundant.
- beagle3 11y ago
  You wrote earlier: > But tailcalls already have a syntax: > > return f(a, b, c) # tailcall on f However, this tail call cannot be eliminated in the context of a try: or with: scope. Ergo, it is NOT tail call syntax. Using it does not guarantee that the tail call can be eliminated: def write_list_to_file(file, list): "Looks weird, but it has reason to do this based on overall system architecture" try: item = list[0] list[0] = None file.write(item) return write_list_to_file(file, list[1:]) finally: list[0] = item Despite being compatible with your "tailcall syntax", this is not actually a tailcall. Ergo: no tailcall syntax. Proponents of tail calls almost always ignore a very simple practical consideration: If you rely on a tail call being eliminated and it isn't, then your program becomes incorrect, in the sense that it goes from needing constant memory to needing infinite memory. I simply cannot fathom what argument one might have against an annotation "this tail call must be eliminated for this program to be correct" that can easily be verified by the compiler (is the compiled call site CALL instruction followed by a RET opcode? if so, it's a tail call. If not, it's not!). Not doing so means that an enclosing context can change the meaning of the (recursive equivalent to) "while 1:" to "for x in range(MEMORY): ...; raise OutOfMemoryException();" based on compiler optimization capability. > You are using your own rebuttal as an argument to make tailcalls look harder to analyse! They are not. No, I claim that they are extremely easy to analyze for a compiler; They are not as easy for a reader (with/try context 50 lines away converts a tail call into a non tail call. You have to both be aware of the context and of this possibility - or you will be unwittingly replacing a while loop with a limited for loop). If you claim that it is easy to analyze for a reader, then you are not considering Python's original and still significant audience: non programmers. > As a caller of a function, the property you care about is "does it consumes a fixed amount of stack?". Yes, you do. And as a caller of a function, you don't see or control its attributes in any way, so that isn't an argument for or against decorators. > As the writer of this function, that's the thing that matters in the end: Sure, that means checking each tail calls, but you really want the global guarantee that you didn't forgot one. The local explicit annotation becomes redundant. You have two wrong assumptions here: 1) That if all returns are tail calls, then constant stack use is guaranteed. 2) That I actually want every return to be a tail call Neither of these are necessary. Therefore, while such a decorator may be useful for your style, it does not make a local explicit annotation redundant. Consider a very sparse tree data structure with n nodes, and 0-500 children for every node, but with only log(n) of the nodes having more than one child. (It arises in practice e.g. when building a suffix array on some kinds of inputs; The Patricia tree is an optimization of this). Computing on this structure can be done as follows, assuming some special case for 2-children nodes: def collect(node, acc): if node.count_children() == 0: return acc + node.value if node.count_children() == 1: return collect(node.get_child(0), acc + node.value) # this is key to memory use if node.count_chilren() == 2: return acc + PAIR_START + collect(node.get_child(0), 0) + collect(node.get_child(1), 0) + PAIR_END acc = acc + MULTI_START for child in node.get_children(): acc = acc + collect(child, 0) acc = acc + MULTI_END return acc Now, the key collect() call determines overall memory use; if there's TCE, it will be overall O(log n). If there isn't, it will be O(n). If you add a try: finally: (with actual code, not finally:pass) it will become O(n) regardless. The example is realistic, although somewhat contrived to be compact. If your argument isn't "well, you don't need new syntax and help from the compiler if you just pay attention and remember not to use with/try if you ever need guaranteed tail calls", then please state it more clearly because I haven't understood it. And if that's your argument, then I think it is technically right but practically wrong (in the same sense that saying "python is useless, you can do everything in assembly" is technically right and practically wrong)

beagle3 11y ago

P.s: python has (or at least had) "static" analysis of the kind w.r.t exceptions and generators when they didn't mix well. And python's call stack is sort-of visible through tracebacks, frames, and stuff like that.