6 ms·

"Tail call optimization, which also implies tail recursion optimization" I thought those were exactly same thing.

chc4 8y ago
Tail call optimization is returning the result of any function, with tail recursion being the specific case where it's the same function. I think I've seen some languages where they special-case recursion by doing a code transformation, but would stack overflow if you called anything else instead.
- patrec 8y ago
  I don't think this is strictly correct. The below is (mutually) tail recursive: def even(x): return x == 0 or odd(abs(x)-1) def odd(x): return x == 1 or even(abs(x)-1)
  - codebje 8y ago
    That's co-recursion, rather than strict recursion. It's plausible that a compiler might catch the tail recursion case but ignore non-recursive and co-recursive tail calls. Consider: def even(x, useless, arguments); return x == 0 or odd(abs(x) - 1) def odd(x): return x == 1 or even(abs(x) - 1, 6, 9) There are two more formal parameters to even(), which means the stack frame when calling even from odd() includes two more actual parameters. If the compiler follows the usual stack management approach of having the caller allocate and release space for actual parameters, this means the caller has to be aware that the stack space for odd's actual parameters is larger than the size needed for its formal parameters. If odd() is tail calling odd(), there's no difference in actual parameter space, and so the caller can be ignorant of it. It's a minor enough difference that any compiler implementing TCO should handle it anyway (just keep track of the maximum parameter size required in a function's tail call tree, and have the caller allocate and free enough space, or have the cleanup of actual parameters performed by callee) but big enough that a toy or experimental compiler, or one in which TCO is being slowly added, might just do the simple case only.
    - patrec 8y ago
      Do you have a source where co-recursion is used to describe mutual recursion as above? I'm under the impression it refers to a different concept, see e.g. https://softwareengineering.stackexchange.com/questions/144274 https://softwareengineering.stackexchange.com/questions/1442...
      - codebje 8y ago
        I misused the term, yes: it should be "mutual recursion" not "corecursion", sorry.
patrec 8y ago
In a language with guranteed tail call optimization, the below consumes no stack, although there's no recursion. def f(a): return g(2*a) def g(a): return a + 1
- uryga 8y ago
  Ah, you beat me to it! I was writing my comment and then forgot about the tab for a while.
- cwzwarich 8y ago
  How does your definition distinguish between stack space used for call frames and stack space used for storage of temporaries? It's not possible to capture the difference without an asymptotic property, which wouldn't matter in this case because there's a constant number of function calls.
  - codebje 8y ago
    There's no difference. When you exit a function, you must clean up local stack allocations. It doesn't matter if you exit with a return or a jump. It doesn't matter where you jump. If you leave the stack with temporary allocations in place, they'll leak space. (A compiler pipeline may, at some point, observe that releasing stack space, jumping, then claiming the same amount of stack space could be optimised to just a jump, but it may equally observe that releasing, jumping, and claiming a different amount could be optimised to either releasing or claiming the difference, then jumping, too - there's still no difference between recursive, co-recursive, and non-recursive tail calls.)
  - dreamcompiler 8y ago
    If function A tail-jumps to function B and B exits with a Return instruction (rather than another JMP) then B's Return cleans up A's stack frame automatically. It doesn't have to care that the current frame actually belongs to A rather than B. If A has local variables, the compiler will insert an instruction to increment the SP before the final JMP, which cleans up the space for the locals. [This requires stack frames to push local variables after pushing the return address (if any), but that's easy to arrange.] The point is that the compiler can make the TCO decision statically just by inspecting the function in question. Dynamic analysis of who-calls- who is not necessary.
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 ago
  I 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 ago
    Nope, 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 ago
    TCO 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.
cwzwarich 8y ago
There are three distinct concepts that are often conflated: 1) The syntactic construct of a tail call. 2) Abstract space efficiency properties that guarantee asymptotic space usage of programs using tail calls. 3) The implementation techniques used to guarantee 2). Even though the implementation techniques of 3) apply to all calls, the space efficiency properties in 2) are asymptotic and thus are only meaningful when applied to programs with unbounded recursive function invocations. Applying the techniques of 3) only to function calls that might potentially be involved in a recursive chain would still satisfy any of the standard definitions of 2). See Will Clinger's paper Proper Tail Recursion and Space Efficiency (https://dl.acm.org/citation.cfm?id=277719 https://dl.acm.org/citation.cfm?id=277719) for details regarding the standard definition of "proper tail recursion" used in the Scheme spec and elsewhere.
- iuoershg 8y ago
  If so, can a purely functional language require no more than one stack frame?
  - nailuj 8y ago
    It depends on what you mean by purely functional, the lambda calculus certainly doesn't require stack frames. Even better, you can implement any programming language without a stack. Stack frames are only a convenience feature for programmers after all (well, and many architectures probably do some hardware optimizations when using the stack related registers for stack things).

chc4 8y ago

Tail call optimization is returning the result of any function, with tail recursion being the specific case where it's the same function. I think I've seen some languages where they special-case recursion by doing a code transformation, but would stack overflow if you called anything else instead.

patrec 8y ago
I don't think this is strictly correct. The below is (mutually) tail recursive: def even(x): return x == 0 or odd(abs(x)-1) def odd(x): return x == 1 or even(abs(x)-1)
- codebje 8y ago
  That's co-recursion, rather than strict recursion. It's plausible that a compiler might catch the tail recursion case but ignore non-recursive and co-recursive tail calls. Consider: def even(x, useless, arguments); return x == 0 or odd(abs(x) - 1) def odd(x): return x == 1 or even(abs(x) - 1, 6, 9) There are two more formal parameters to even(), which means the stack frame when calling even from odd() includes two more actual parameters. If the compiler follows the usual stack management approach of having the caller allocate and release space for actual parameters, this means the caller has to be aware that the stack space for odd's actual parameters is larger than the size needed for its formal parameters. If odd() is tail calling odd(), there's no difference in actual parameter space, and so the caller can be ignorant of it. It's a minor enough difference that any compiler implementing TCO should handle it anyway (just keep track of the maximum parameter size required in a function's tail call tree, and have the caller allocate and free enough space, or have the cleanup of actual parameters performed by callee) but big enough that a toy or experimental compiler, or one in which TCO is being slowly added, might just do the simple case only.
  - patrec 8y ago
    Do you have a source where co-recursion is used to describe mutual recursion as above? I'm under the impression it refers to a different concept, see e.g. https://softwareengineering.stackexchange.com/questions/144274 https://softwareengineering.stackexchange.com/questions/1442...
    - codebje 8y ago
      I misused the term, yes: it should be "mutual recursion" not "corecursion", sorry.

patrec 8y ago

In a language with guranteed tail call optimization, the below consumes no stack, although there's no recursion. def f(a): return g(2*a) def g(a): return a + 1

uryga 8y ago
Ah, you beat me to it! I was writing my comment and then forgot about the tab for a while.
cwzwarich 8y ago
How does your definition distinguish between stack space used for call frames and stack space used for storage of temporaries? It's not possible to capture the difference without an asymptotic property, which wouldn't matter in this case because there's a constant number of function calls.
- codebje 8y ago
  There's no difference. When you exit a function, you must clean up local stack allocations. It doesn't matter if you exit with a return or a jump. It doesn't matter where you jump. If you leave the stack with temporary allocations in place, they'll leak space. (A compiler pipeline may, at some point, observe that releasing stack space, jumping, then claiming the same amount of stack space could be optimised to just a jump, but it may equally observe that releasing, jumping, and claiming a different amount could be optimised to either releasing or claiming the difference, then jumping, too - there's still no difference between recursive, co-recursive, and non-recursive tail calls.)
- dreamcompiler 8y ago
  If function A tail-jumps to function B and B exits with a Return instruction (rather than another JMP) then B's Return cleans up A's stack frame automatically. It doesn't have to care that the current frame actually belongs to A rather than B. If A has local variables, the compiler will insert an instruction to increment the SP before the final JMP, which cleans up the space for the locals. [This requires stack frames to push local variables after pushing the return address (if any), but that's easy to arrange.] The point is that the compiler can make the TCO decision statically just by inspecting the function in question. Dynamic analysis of who-calls- who is not necessary.

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 ago
I 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 ago
  Nope, 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 ago
  TCO 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.

cwzwarich 8y ago

There are three distinct concepts that are often conflated: 1) The syntactic construct of a tail call. 2) Abstract space efficiency properties that guarantee asymptotic space usage of programs using tail calls. 3) The implementation techniques used to guarantee 2). Even though the implementation techniques of 3) apply to all calls, the space efficiency properties in 2) are asymptotic and thus are only meaningful when applied to programs with unbounded recursive function invocations. Applying the techniques of 3) only to function calls that might potentially be involved in a recursive chain would still satisfy any of the standard definitions of 2). See Will Clinger's paper Proper Tail Recursion and Space Efficiency (https://dl.acm.org/citation.cfm?id=277719 https://dl.acm.org/citation.cfm?id=277719) for details regarding the standard definition of "proper tail recursion" used in the Scheme spec and elsewhere.

iuoershg 8y ago
If so, can a purely functional language require no more than one stack frame?
- nailuj 8y ago
  It depends on what you mean by purely functional, the lambda calculus certainly doesn't require stack frames. Even better, you can implement any programming language without a stack. Stack frames are only a convenience feature for programmers after all (well, and many architectures probably do some hardware optimizations when using the stack related registers for stack things).