4 ms·

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(

by 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.

by 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.