Re:Will It Optimize?
by samth on Friday September 16, 2011 @09:33AM
(#3004364)
The comment about tail calls is wrong -- it's not an optimization, it's a guarantee about semantics of your program. Not optimizing tail calls is like making array dereference run in linear time instead of constant: it changes the programs you can write.
[ Parent
| on HN ]
Irrespective of how it changes the semantics of (mostly functional) languages that rely on it for iteration, tail calling is also an optimization in languages that don't need to rely on it for this, and it is not wrong to describe it as such.
There are two things here: an optimization, and a semantics guarantee. Obviously, if your language provides the guarantee, then implementing it correctly isn't just an optimization. But the original article claims that the transformation proves that proper tail calling is "just an optimization", which it doesn't prove at all. It's still an important semantic guarantee which increases the expressiveness of a language. This is true regardless of whether it is the only means of expressing iteration in a language.
Re:Will It Optimize?
by ridiculous_fish on Friday September 16, 2011 @04:32PM
(#3006190)
What the factorial example proves is that the set of recursive functions that can run in constant space is larger than just tail-recursive functions.
You're right to say that TCO guarantees increase the expressiveness of a language. If we could provide the same guarantees for an even larger class of recursive functions, it stands to reason our expressiveness would increase even further!
Re:Will It Optimize?
by lukesandberg on Friday September 16, 2011 @11:31AM
(#3004825)
In a language that requires TCO then you are right, it's not about optimization it's about correctness. In a language (like c) that has no such semantics it is 'just' an optimization. In scheme however it is a correctness issue.