| 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) |
To clarify: Yes, I believe that whichever stack release semantic is chosen (tailcall optimization or the current behaviour) triggers an understanding of its limitation. Languages that support tailcalls natively yield programmers that "see" tailcalls (so they don't think about it more than necessary), and non-tailcall support yield programmers that "see" stack allocation on recursion (but they don't think about the stack more than tailcall programmers do.)
Now, we both like the "default" behaviour that we have practised the most, because we really understand its limitation. When confronted with the other semantic, we can make it work, but it's slower to trigger our reflexes, and causes frustration:
A tailcall programmer forced to use a non tail-call language will have to "compile" his tail recursion into a loop. A non-tailcall programmer forced to use a tailcall language will gain free stack, but won't have to rewrite his algorithm.