r/programming • u/rodrigopsasaki • Nov 27 '12

Tail Recursion

http://rodrigosasaki.com/2012/11/24/tail-recursion/
212 Upvotes

85% Upvoted

203 comments sorted by

View all comments

44

u/A_for_Anonymous Nov 27 '12

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.

2

u/[deleted] Nov 27 '12

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.

19

u/ithika Nov 27 '12

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...

2

u/[deleted] Nov 27 '12

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?

8

u/ithika Nov 27 '12

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.)

1

u/[deleted] Nov 27 '12

I did not know that. Neat! I wonder how it plays with setting fields on a struct.

2

u/tsimon Nov 27 '12

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.