6 ms·

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 simplific

by 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)
- art-w 11y ago
  Sure, finally breaks the tailcall syntax, just like it breaks the syntax rule "the function ends on a return". You are right that I haven't stated my motivation for arguing about tailcalls: - I really believe that tailcalls should be supported by Python. Recursion is too useful, and it's hard enough to teach without suffering the second class behaviour that Python currently offers. - A new syntax is harder to sell to programmers and the python team, because it says "tailcalls are not the norm". I claim that "return f()" is used way too much to justify the cost of writing explicitly "return from f()" for a free optimization. - A beginner doesn't need to know about tailcall to benefit from it, just like we don't teach them about the stack until they hit a stackoverflow. If you have two semantics with respect to stack release, it becomes harder to teach than if you choose only one (it triggers the question "why would you ever NOT write "return from" when you can?") You seem to disagree that tailcalls should be optimized everywhere possible, but I'm not sure if it's because you don't care about writing "return from" in general (and just want to enforce it when it's actually observable), or think that "return from" isn't always an optimization (but I'm really missing a counter-example?), or really believe that tailcalls makes the semantic of the stack harder because of things like "finally" (in which case I think we both suffer from a bias towards the stack-release semantic that we are used to.) If Python had tailcalls by default, would we have an argument for a "return after" syntax? I like static analysis. I just don't think tailcalls require a more explicit annotation than any other language feature: writing "return from collect()" in your example doesn't clarify your intent, it just triggers a warning when someone breaks the tailcall (but he can still break the stack complexity through other means.) You do have to state your global property somewhere: the local tailcall annotation allow you to prove it today, not guarantee its survival upon software evolution. And as a user of your library, my static analyser could benefit from a function annotation on your side, but it won't care about your usage of "return from".
  - beagle3 11y ago
    > You seem to disagree that tailcalls should be optimized everywhere possible I don't disagree, assuming there's a way to turn that off for debugging. I love it when things run faster and take less memory. I disagree that "there's already a syntax for tail call" (that can be relied upon if Python did TCE) because in Python there isn't. Therefore, even if Python had TCE, it would be brittle (a small change 50 lines away could make it into a non-tail call) and it would be bad style to rely on it as a programming mechanism. I've used common lisp with tailcalls. They work way better there than they would in Python, although there are still interaction problems with conditions/restarts/continuations/macros, mostly as invisible as they would be in Python. (Though, it's been something like 20 years, my memory is hazy). My claim can be summarized as follows: 1. TCO is nice and awesome. But it is an OPTIMIZATION, and shouldn't be a central language feature you rely on, unless it is easy to guarantee it happens. 2. If you want to rely on TCE as a general programming technique, you should be able to say "and if this thing isn't a tail call, don't compile" or "and if this thing isn't a tail call, give me a warning". 3. A "return from" in Python could be an excellent way to implement (2) for Python 4. I think a special form for Scheme that says "I rely on the following tail call being eliminated" would have been useful, as it is easy to shoot yourself in the foot relying on it while e.g. using macros - where something that looks like it is a simple call expands to a non-trivial expression. Luckily, in CL (and I assume in Scheme as well), you could do that at the library level with a relatively simple code walker. The Python Library-Level implementations that I've seen use a decorator to add the trampoline and need you to replace "return f(a,b,c)" with "raise TailCall(f, a, b, c)" (or something to that effect - you can get a much nicer syntax with some limitations). Ugly, inefficient, but available if you really need it.

by art-w 11y ago

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)

art-w 11y ago
Sure, finally breaks the tailcall syntax, just like it breaks the syntax rule "the function ends on a return". You are right that I haven't stated my motivation for arguing about tailcalls: - I really believe that tailcalls should be supported by Python. Recursion is too useful, and it's hard enough to teach without suffering the second class behaviour that Python currently offers. - A new syntax is harder to sell to programmers and the python team, because it says "tailcalls are not the norm". I claim that "return f()" is used way too much to justify the cost of writing explicitly "return from f()" for a free optimization. - A beginner doesn't need to know about tailcall to benefit from it, just like we don't teach them about the stack until they hit a stackoverflow. If you have two semantics with respect to stack release, it becomes harder to teach than if you choose only one (it triggers the question "why would you ever NOT write "return from" when you can?") You seem to disagree that tailcalls should be optimized everywhere possible, but I'm not sure if it's because you don't care about writing "return from" in general (and just want to enforce it when it's actually observable), or think that "return from" isn't always an optimization (but I'm really missing a counter-example?), or really believe that tailcalls makes the semantic of the stack harder because of things like "finally" (in which case I think we both suffer from a bias towards the stack-release semantic that we are used to.) If Python had tailcalls by default, would we have an argument for a "return after" syntax? I like static analysis. I just don't think tailcalls require a more explicit annotation than any other language feature: writing "return from collect()" in your example doesn't clarify your intent, it just triggers a warning when someone breaks the tailcall (but he can still break the stack complexity through other means.) You do have to state your global property somewhere: the local tailcall annotation allow you to prove it today, not guarantee its survival upon software evolution. And as a user of your library, my static analyser could benefit from a function annotation on your side, but it won't care about your usage of "return from".
- beagle3 11y ago
  > You seem to disagree that tailcalls should be optimized everywhere possible I don't disagree, assuming there's a way to turn that off for debugging. I love it when things run faster and take less memory. I disagree that "there's already a syntax for tail call" (that can be relied upon if Python did TCE) because in Python there isn't. Therefore, even if Python had TCE, it would be brittle (a small change 50 lines away could make it into a non-tail call) and it would be bad style to rely on it as a programming mechanism. I've used common lisp with tailcalls. They work way better there than they would in Python, although there are still interaction problems with conditions/restarts/continuations/macros, mostly as invisible as they would be in Python. (Though, it's been something like 20 years, my memory is hazy). My claim can be summarized as follows: 1. TCO is nice and awesome. But it is an OPTIMIZATION, and shouldn't be a central language feature you rely on, unless it is easy to guarantee it happens. 2. If you want to rely on TCE as a general programming technique, you should be able to say "and if this thing isn't a tail call, don't compile" or "and if this thing isn't a tail call, give me a warning". 3. A "return from" in Python could be an excellent way to implement (2) for Python 4. I think a special form for Scheme that says "I rely on the following tail call being eliminated" would have been useful, as it is easy to shoot yourself in the foot relying on it while e.g. using macros - where something that looks like it is a simple call expands to a non-trivial expression. Luckily, in CL (and I assume in Scheme as well), you could do that at the library level with a relatively simple code walker. The Python Library-Level implementations that I've seen use a decorator to add the trampoline and need you to replace "return f(a,b,c)" with "raise TailCall(f, a, b, c)" (or something to that effect - you can get a much nicer syntax with some limitations). Ugly, inefficient, but available if you really need it.