It looks like it was for fun. The author has several repositories on Github holding Lisp interpreters in different languages. It might also be a learning technique: interpreters for higher order languages are good intermediate projects when learning new languages.
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.
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.
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.
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.)
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.
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.
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?
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.
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.
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) for details regarding the standard definition of "proper tail recursion" used in the Scheme spec and elsewhere.
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).
21 comments
[ 5.4 ms ] story [ 59.6 ms ] threadCouldn't we please base such things on scheme or clojure (for Lisp-1) or common lisp (for Lisp-2).
I thought those were exactly same thing.
It's plausible that a compiler might catch the tail recursion case but ignore non-recursive and co-recursive tail calls.
Consider:
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.
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.)
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.
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...
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.