Re:What is tail call optimization (2008)?
by ww520 on Wednesday March 21, 2012 @06:17PM
(#3737049)
For a long time, I assumed the recursive tail call optimization was a really smart optimization done by the compiler to transform a normal recursive call into a tall call. I was trying to figure out how a compiler could do that.
Then later I learned that the optimization part is really done by human to transform the recursive call into a tail call. The "optimization" done by the compiler is relatively trivial in reusing the stack frame for the last function call.
Re:What is tail call optimization (2008)?
by pantaloons on Wednesday March 21, 2012 @05:31PM
(#3736801)
As always SICP has the answers[1], and helped me shift from a "production rule that transforms slow code to be faster" mindset towards a "implementation detail of the compiler that ensures it doesn't create unnecessary state" one. It's no more an optimization than explicitly not filling code with NOP's is.
Re:What is tail call optimization (2008)?
by jlongster on Wednesday March 21, 2012 @05:52PM
(#3736923)
SICP is such a great book. If anyone is interested in the last chapter, I just implemented the compiler which output the assembly code needed for explicit control evaluation.
Re:What is tail call optimization (2008)?
by tikhonj on Wednesday March 21, 2012 @05:27PM
(#3736777)
I think calling it an "optimization" is unfair. You don't call while loops that run in constant space an optimization, do you?
Without support for proper tail calls, a large range of otherwise valid recursive programs does not work. So, in a very real sense, supporting proper tail recursion changes the semantics of the language, letting you certain programs more easily.
Re:What is tail call optimization (2008)?
by lmkg on Wednesday March 21, 2012 @05:50PM
(#3736911)
I've always been a little bit uncomfortable with the line of reasoning that TCO is a semantics change. For any list of programs (and inputs) that would return with TCO but would otherwise fail with a memory error, there is some amount of memory additional memory you could add that would also cause the program to return. I don't normally consider buying RAM to change the semantics of my programming language. It certainly changes what's practical to do with constrained resources in a language, but the same could be said of most things that are considered "optimizations."
On the other hand, I do sympathize with the idea that TCO is somehow different that most optimizations. It potentially turns O(\inf) memory usage into O(1). If anything, it feels like an algorithmic optimization more than the implementation optimizations that compilers are generally limited to.
Re:What is tail call optimization (2008)?
by ryanpetrich on Wednesday March 21, 2012 @06:41PM
(#3737162)
On systems that have a limited stack size, it is a semantics change. Usually this is more limiting than memory or address space. Split stacks are one workaround, but can have a performance penalty of their own.
Re:What is tail call optimization (2008)?
by tikhonj on Wednesday March 21, 2012 @06:49PM
(#3737202)
This seems a little confusing--the tail call isn't really eliminated per se, it just behaves differently in terms of stack space. Semantically, it's still a call, just one that does not have any unnecessary additional overhead.
Re:What is tail call optimization (2008)?
by kylec on Wednesday March 21, 2012 @06:48PM
(#3737194)
Neat, that top answer is mine. And yes, it does borrow quite generously from the first chapter of SICP, which is the canonical source for that kind of info. Still, it's nice to see something I wrote coming up again. I'm glad it's helping people.
Then later I learned that the optimization part is really done by human to transform the recursive call into a tail call. The "optimization" done by the compiler is relatively trivial in reusing the stack frame for the last function call.
[1] http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-34.html
https://github.com/jlongster/outlet-machine
Without support for proper tail calls, a large range of otherwise valid recursive programs does not work. So, in a very real sense, supporting proper tail recursion changes the semantics of the language, letting you certain programs more easily.
On the other hand, I do sympathize with the idea that TCO is somehow different that most optimizations. It potentially turns O(\inf) memory usage into O(1). If anything, it feels like an algorithmic optimization more than the implementation optimizations that compilers are generally limited to.