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.
I prefer tail-call elimination.
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.
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.