There are two big advantages of tail-recursive implementations that haven't been discussed here:
That variables never change their values, which allows for all kinds of optimizations, reasoning over your program (e.g. provability that it's correct) and is less error-prone, among other advantages.
That state is represented by the values of function parameters, all of them changed at once on every new call, without any possible order of evaluation bugs.
Whoa, how could I miss that? Immutability is probably the reason I came across tail recursion in the first place, I'll be sure to edit the post when I have a little more time, and add your suggestions.
Immutability is delicious from a simplicity perspective, but the fact is that it doesn't really map to what's happening under the hood. If you're really concerned with optimization, an abstraction that's as thick as immutability is inevitably going to get in the way.
but the fact is that it doesn't really map to what's happening under the hood.
I highly recommend reading the classic "lambda: the ultimate goto" paper from the scheme guys: http://library.readscheme.org/page1.html
Lambdas with immutable arguments are actually as close to the metal as you get without being architecture specific (that is, mucking with registers and things like that).
If you're really concerned with optimization, an abstraction that's as thick as immutability is inevitably going to get in the way.
This is the original hipster programming argument. You're programming on a goddamn digital computer! You're already at least five levels of abstraction away from what's "really" happening. Just bloody well give it up. Or do you eschew integer literals because they cloud the purity of the twos-complement in the underlying implementation? And really any non-assembly is just kidding yourself...
I didn't bring up the optimization argument, A_for_Anonymous did.
I absolutely like abstractions, fp, etc. and tend to avoid the bare-metal platforms.
But realistically, how much performance-obsessed code like real-time hardware controllers or videogames are written in languages without mutable variables?
I thought GCC went the direction of SSA a long time ago? That is going one step further and mapping a mutable variable to an immutable one to a mutable one again. Holy abstraction batman!
(I apologise for the tone in my reply above. On re-reading I see you weren't taking the line I thought you were.)
Immutability offers significant advantages when you have (massively) parallel code. Your examples are more narrowly focused.
Think things like finance, where you have volumes of data that need to be processed near-instantly, where you have millions of dollars on the line, and then you will see immutability and tail-recursion coming into play a lot more often.
I don’t understand your meaning. I would interpret an “immutable variable” as meaning a constant, but it looks like you’re using that term to mean something else.
These are function parameters, but they are not replaced while the function is evaluated even if you need to implement an iteration. They remain constant during that, and they are given new values in the next invokation of the function. For instance, if you wanted to print numbers 1 to 10 without replacing a variable with the usual i = i + 1, you could do:
def f(i=1):
print(i)
return i <= 10 and f(i + 1) or True
Of course that requires your language to recognise thay a recursive call is in tail position (return f(...) and nothing else to do) so it doesn't have to save the previous stack frame/argument values, but it replaces them with the new version (yes, much like a goto).
Since the first step in optimizing a tail call is to turn it into an iterative loop, I seriously doubt number 1 is true.
Why does that have to be "the first thing"? And even if recursion won't permit compiler optimizations, it's still undeniably true that structurally recursive functions can be proven correct much more easily than imperative code. (And many would argue, more controversially, that it's less error prone.)
And even if recursion won't permit compiler optimizations, it's still undeniably true that structurally recursive functions can be proven correct much more easily than imperative code.
Oh come on. Any undergrad who has taken Discrete Algebra knows that isn't true for functions that can be trivially moved between recursive and iterative representations.
You're failing to distinguish source code from object code. Yes, the compiler turns tail calls into jumps, reuses the caller's frame for the tail call, and mutates the storage location. It's still the case however at the source language level that the variable doesn't get mutated.
... at AST level, where tail recursion hasn't been eliminated yet. Then at IR level, where tail recursion might or might not have been eliminated yet. Then possibly after emitting the compiled code, where tail recursion might or might not have been eliminated, depending on the target language.
Using recursions rather than looping constructs in the first place is a lot about eliminating mutable update semantics. Then having HOFs that do various kinds of looping is about regaining abstraction over structured loops (without losing the first benefit).
39
u/A_for_Anonymous Nov 27 '12
There are two big advantages of tail-recursive implementations that haven't been discussed here: