The Problem with Immutability

There's been so many articles touting the benefits of functional programming lately.  Read just a few and one theme immediately emerges: no side effects is good.  With immutability there's no side effects, and with no side effects life becomes a lot easier.  Programs are easier to write, compose, debug and you get concurrency for "free".  While all this may be true, I feel there needs to be a little balance on the subject lest some people start to think functional programming is a silver bullet. 

We live in an imperative world where there's state and things are mutable.    This fact alone hints as to why functional programming cannot be the end all solution.  I/O is the classic example of where imperative operations are required.  For example, Haskell, a functional language, has these things called monads to do I/O.  Michael Scott writes in Programming Language Pragmatics,

Monads...acknowledge that the physical world is imperative, and that a language that needs to interact with the physical world in nontrivial ways must include imperative features.

I also recall a recent article with Joe Armstrong on state and mutability in Erlang that came to the same obvious conclusion: state and side effects are necessary, we just need to confine them so the rest of the program is not polluted.

Beyond this inherent issue of modeling the imperative physical world, there are just some things that are more imperative in nature, like counting and updating.  Destructive updating assignments may clog the von Neumann tube, but immutability creates a lot of garbage.  The need for destructive updates leads to the so-called trivial update problem.  How can we efficiently handle updates without creating new copies of the entire data structure.  In imperative languages it's very easy to do map.remove("myKey") but in a functional language you have to call a function passing in the current immutable map and getting back a new immutable map with one entry removed. 

There are two ways to deal with this.  One is to hope your compiler can optimize.  If the compiler can verify that the old map is never used after the function returns instead of creating a new copy of the map the compiler can just do the update imperatively, in-place.  Apparently there's this Sisal compiler that was shown to eliminate 99-100% of all copy operations.  And that was back in 1992.  Then again, that was very geared toward numerical calculations, so I'm not sure how things would translate to your run of the mill web app.

Another approach is to make your data structures smarter.  Smarter is probably the wrong word.  The key is to recognize the difference between imperative and functional data structures.  In imperative languages data structures are ephemeral, existing as-is, without a history.  Think of all the data structures we use everyday in Java: HashSet, HashMap, ArrayList.  They're all ephemeral.  Functional languages, because of immutability, have automatically persistent data structures.  Adding two elements to an initially empty list means you have three versions of the list: (), (e1), (e1 e2).  In the imperative world you just have a single list of three elements.

The problem is how to achieve persistence with O(1) additional space and O(1) slowdown.  Good news is really smart guys like Sleator, Tarjan and Okasaki have laid the foundation for efficient persistent data structures.  I know Rich Hickey's Clojure has persistent data structures base on Okasaki's work with some modifications to get around just the amortized guarantees.  A lot of the work around persistent data structures is around amortized running times, but Clojure has these "persistent vectors" so the time is guaranteed for certain data structures.  While much progress has been made in this area ephemeral data structures still have quite a head start.

As someone who's basically programmed in Java all his career I find all this very functional stuff very fascinating.  No doubt about functional programming's many pros, but it's also good to be aware of the cons.  I remember when Java faced much criticism because creating objects was expensive, but those criticism have largely subsided.  The Java language hasn't really changed, the bad programs we (I) write definitely haven't changed--it's just that the JVM has gotten a lot better at resource management.  So is functional programming at a similar stage, where all that's needed is improvements in compiler optimization and better functional data structures?  Or are we already there and I'm not just aware of it? 

Comments

[Tony Morris]

You have missed the point completely. "We live in an imperative world where there's state and things are mutable." This statement is wildly untrue true and sets the premise for the remainder of your error.

Second, monads have nothing to with I/O. You use monads in your favourite programming language, whether you know that or not.

Java has a couple of monads: the semi-colon and the throws keyword. C has the semi-colon, C# has monad comprehensions (LINQ). Whether you're aware of this or not is the important point. What is not important is whether or not you are using monads (since you are -- get used to it).

Although Java is perhaps the most impractical language on the planet, you would at least benefit from understanding some of its fundamental underpinnings should you be forced to use it. This is why I am compelled to point out that you have made an error, and not just a little one.

It would help for you to understand what this "monad" word means to prevent future error.

I am happy to teach you in your favourite language if you like, but like I said, it is not a very practical language and so presents unnecessary barriers. I hope this helps.

[tinou]

hi tony,

thanks for the comments. my blog is a flushing ground for random thoughts, so during this flushing process it wouldn't surprise me at all if everything i said is completely wrong.

can you expand on a couple of the things you said. the world is stateful/mutable seems so apparent to me, but maybe i have a different (incorrect?) understanding of what state means. last month i was listening to a conversation with gilad bracha and he said this regarding regarding functional vs. imperative:

"[people] don't know how to break it [problems] down into functions and their perception of it is stateful; it often is. i mean i'm looking at you right now, and i know it's not really you any more, it's a new you that just got reconstituted. but most people have this idea that it really is you. memory is important. so throwing out state makes life a lot simpler but very often creates a problem in modeling things. and if you really, really understand something you can usually throw away the state but it is often very hard. you need to have both, but you need to be close to functional as you can."

that's what i meant when i said the world is imperative and has state and is mutable.

the monad thing. i mentioned monad only to put micahel scott's quote in context. i'll defer to you on exactly what monads are, since i for sure don't know the complete story on monads, except that everytime i read about IO I see monads. maybe that'll be my next blog: WTF is a monad?!?

[Mentics]

Regarding the immutable world. I found this thought interesting: the world is not imperative, but it is reactive. I was reading about functional reactive programming, and that seems to get closer to modeling the real world since it sets up the "physics" of a program declaratively. How things interact. And then you say go, and your application "just works" because the interactivity/dataflow is defined.