Re:Tail Recursion
by sdevlin on Tuesday November 27, 2012 @12:22PM
(#4837710)
Decent explanation, but I have a couple quibbles.
First, the term "tail recursion" is overly narrow. This transformation should apply to all tail calls, not just recursive ones. This is useful, for example, in families of mutually recursive functions.
Second, this transformation is not really an optimization, as it changes the behavior of some programs (by preventing stack overflow or memory allocation errors). It's a documented feature of languages (or specific implementations of languages) that users rely on to write programs in a particular style.
I prefer the term "tail call elimination" to describe these transformations.
Re:Tail Recursion
by kvb on Tuesday November 27, 2012 @12:50PM
(#4837753)
Of course, some languages only support elimination of tail calls when they're recursive. I believe that Scala suffers from this (since the JVM doesn't support tail call elimination).
Re:Tail Recursion
by kvb on Tuesday November 27, 2012 @01:32PM
(#4838020)
It would be possible to do this, but as you note it would potentially be annoying in practice. "tailcall" is a reserved (but unused) word in F#, so the compiler could be extended to issue an error if the user prefixed a non-tail call with that word. This "opt in" approach would presumably be less invasive while allowing people to indicate cases where the semantics are actually important to them. Having said that, as far as I'm aware there are no current plans to implement such a feature (and I haven't seen users clamoring for it, either).
First, the term "tail recursion" is overly narrow. This transformation should apply to all tail calls, not just recursive ones. This is useful, for example, in families of mutually recursive functions.
Second, this transformation is not really an optimization, as it changes the behavior of some programs (by preventing stack overflow or memory allocation errors). It's a documented feature of languages (or specific implementations of languages) that users rely on to write programs in a particular style.
I prefer the term "tail call elimination" to describe these transformations.
This makes me wonder if Visual Studio's F# mode could help detect common errors, e.g. highlight recursive calls not made in tail position.
On the other hand, this could get annoying as such calls are often not a real problem in practice.
http://learnyousomeerlang.com/recursion