"Tail call optimization, which also implies tail recursion optimization"
I thought those were exactly same thing.
I thought those were exactly same thing.
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) for details regarding the standard definition of "proper tail recursion" used in the Scheme spec and elsewhere.
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)
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-S...
def f(a):
return g(2*a)
def g(a):
return a + 1When 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.)
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.
def even(x):
return x == 0 or odd(abs(x)-1)
def odd(x):
return x == 1 or even(abs(x)-1)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)
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.