4 ms·
You can also optimize non-recursive tail calls: def add10(y: int) -> int: return y+10 def def add11(x: int) -> int: # won't get optimized
by uryga 8y ago
You can also optimize non-recursive tail calls:
def add10(y: int) -> int:
return y+10
def def add11(x: int) -> int:
# won't get optimized
return add10(x)+1
def add11_tail(x: int) -> int:
# should get optimized
return add10(x+1)
in `add11_tail` the call to `add10` is in the tail position, i.e. you can "forget" about `add11_tail`'s stack frame since it's not needed anymore. It's still needed in `add10`, because you start in `add11`, call `add10` and go back to to `add11` to add 1 to the result.
- ikfmpwdsoz 8y agoI was under the assumption that that was called sibling call optimization, and TCO referred exclusively to recursive calls. Was that just an LLVM-ism, or did I also get that wrong?
- mehrdadn 8y agoNope, if that's what LLVM says then they're wrong here. Tail call optimization has nothing inherently to do with recursion. Rather, "tail call" means that the call is the last (tail) thing the caller does. "Sibling call" doesn't really make a lot of sense to me either, since most calls are sibling calls, and most of them can't be optimized away like that. For reference, back in 2001, Microsoft's .NET CIL specs already had [1] a "tail call" prefix, described as follows: > Tail call prefix [indicates] that a method should relinquish its stack frame before executing a method call. (LLVM's first release was in 2003.) [1] https://www.ecma-international.org/publications/files/ECMA-ST-WITHDRAWN/ECMA-335,%201st%20edition,%20December%202001.pdf#page=93 https://www.ecma-international.org/publications/files/ECMA-S...
- dreamcompiler 8y agoTCO is a bigger concept than just recursion. Applying it to non-recursive tail calls makes code more efficient because it doesn't create a superfluous stack frame. But it's harder to debug because -- it doesn't create a superfluous stack frame.