Lisp in Dart 2.0(github.com)
github.com
Lisp in Dart 2.0
https://github.com/nukata/lisp-in-dart/blob/master/IMPLEMENTATION-NOTES.md
21 comments
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.
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.
If so, can a purely functional language require no more than one stack frame?
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).
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)
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.
(LLVM's first release was in 2003.)
[1] https://www.ecma-international.org/publications/files/ECMA-S...
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...
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.
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 + 1How 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.
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.)
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.
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.
Ah, you beat me to it! I was writing my comment and then forgot about the tab for a while.
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.
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)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:
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.
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.
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/1442...
I misused the term, yes: it should be "mutual recursion" not "corecursion", sorry.
I have only one question: what is the purpose of this stuff? Was it made to extend the possibilies of Dart?
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.
"A sort of subset of Emacs Lisp, but being Lisp-1 with lexical scoping"
Couldn't we please base such things on scheme or clojure (for Lisp-1) or common lisp (for Lisp-2).
Couldn'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.