5 ms·

What is tail call optimization (2008)?

36 points by wicknicks 15y ago

tikhonj 15y ago
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.
- lmkg 15y ago
  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.
  - ryanpetrich 15y ago
    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.
    - deleted 15y ago
      [deleted]
- pwpwp 15y ago
  I prefer tail-call elimination.
  - tikhonj 15y ago
    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.
  - ataranto 15y ago
    Sounds painful.
pantaloons 15y ago
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. [1] http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-34.html http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-34.html
- jlongster 15y ago
  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. https://github.com/jlongster/outlet-machine https://github.com/jlongster/outlet-machine
ww520 15y ago
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.
- Drbble 15y ago
  http://www.owlnet.rice.edu/~comp210/96spring/Labs/lab09.html http://www.owlnet.rice.edu/~comp210/96spring/Labs/lab09.html (search for ""omatic".) The author seems to use automatic" to mean "mindless human", though, not "mindful computer"
kylec 15y ago
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.
cygx 15y ago
Shameless advertisement: A new answer for those of us preferring imperative languages: http://stackoverflow.com/a/9814654/48015 http://stackoverflow.com/a/9814654/48015

36 points by wicknicks 15y ago

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.

lmkg 15y ago
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.
- ryanpetrich 15y ago
  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.
  - deleted 15y ago
    [deleted]
pwpwp 15y ago
I prefer tail-call elimination.
- tikhonj 15y ago
  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.
- ataranto 15y ago
  Sounds painful.

pantaloons 15y ago

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. [1] http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-34.html http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-34.html

jlongster 15y ago
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. https://github.com/jlongster/outlet-machine https://github.com/jlongster/outlet-machine

ww520 15y ago

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.

Drbble 15y ago
http://www.owlnet.rice.edu/~comp210/96spring/Labs/lab09.html http://www.owlnet.rice.edu/~comp210/96spring/Labs/lab09.html (search for ""omatic".) The author seems to use automatic" to mean "mindless human", though, not "mindful computer"

kylec 15y ago

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.

cygx 15y ago

Shameless advertisement: A new answer for those of us preferring imperative languages: http://stackoverflow.com/a/9814654/48015 http://stackoverflow.com/a/9814654/48015