Immutability changes everything

(written by lawrence krubner, however indented passages are often quotes). You can contact lawrence at: lawrence@krubner.com

(Acknowledgements:

I offer a huge “Thank you” to Natalie Sidner for the tremendous editing she did on the rough draft of this post. To the extent that this article is readable, it is thanks to her. Any mistakes are entirely my fault, and I probably added them after she was done editing. If you need to hire a good editor, contact Natalie Sidner at “nataliesidner at gmail dot com”.

Also, I thank Blanche Krubner for reviewing this work. As Mrs Krubner studied computer programming during the 1970s, I found it fascinating to get feedback from someone whose views of the discipline were shaped during a different era.)


This is part 4 of a 12 part series:

1.) Quincy’s Restaurant, a parable about concurrency

2.) Why I hate all articles about design patterns

3.) Clojure has mutable state

4.) Immutability changes everything

5.) Mutable iterators are the work of the Devil

6.) Get rid of all Dependency Injection

7.) Sick politics is the driving force of useless ceremony

8.) Functional programming is not the same as static data-type checking

Interlude

9.) Inheritance has nothing to do with objects

10.) Is there a syntax for immutability?

11.) Immutability enables concurrency

12.) Quincy’s Restaurant, the game


Immutability Changes Everything

This series exists to convince you that the Functional Paradigm is something you should look at. The Functional Paradigm leads to software that is conceptually much simpler than Object Oriented code, and it is safer. But our focus emphasizes immutability. Why is that?

Immutability is the starting point of the Functional Paradigm. Most of the other junk that Functionalists blabber about are nice to have (referential transparency, pure functions, pattern dispatch) but limiting mutability is what makes a system Functional. Put another way, if you have immutability, then you are already a long way toward being Functional, whereas if you have all the other stuff, but you don’t have immutability, then you’ve a confusing mess of a system.

Immutability is also the one aspect of the Functional Paradigm where you need support from the people who write the compiler (or virtual machine) for your language. You can write pure functions in any language. You can give yourself referential transparency just by writing pure functions. But immutability is difficult to get on your own.

Or rather, immutability is easy to get on your own, but you migt burn through all the memory on your machine. I could argue that PHP 4 was the most Functional script language ever created, since all values were copied during assignment. In PHP 4, this created a new object:

$existing_users = $users;

But it was too easy use up all of your memory. PHP 4 was not designed to be Functional, and it was incredibly wasteful with memory and other resources. (Starting with PHP 5, all object assignments in PHP are by reference.)

In almost any language, you can write immutable code by ensuring that all of your vars are CONSTANTs and that, when you want to mutate the value of the CONSTANT, you do so by creating a new CONSTANT. But, again, it really helps if the team working on your favorite language is willing to optimize the use of memory, and other resources, to help enable this style.

(Likewise, you can use any database as an immutable datastore, by only allowing writes and reads, but no deletes or updates. Then you have to write a great deal of code to be sure that you get the most recent version of a document (since there might be endless earlier versions of the same document). You can do this with MySql or PostgresSql or MongoDB, but it is easier when the database itself supports the style, as does Datomic.)

In theory, the Functional Paradigm can be implemented in any language. For instance, there is a website devoted to teaching people how to write Functional code in Java. The Functional paradigm is gaining ground even in languages that used to be famously loose, such as Javascript. Google has done a great job optimizing the V8 engine, and Facebook has encouraged Functional Javascript with their Immutable.js and React.js libraries. James Long summarizes the situation:

Immutable.js comes from Facebook and is one of the most popular implementations of immutable data structures. It’s the real deal; it implements fully persistent data structures from scratch using advanced things like tries to implement structural sharing. All updates return new values, but internally structures are shared to drastically reduce memory usage (and GC thrashing). This means that if you append to a vector with 1000 elements, it does not actually create a new vector 1001-elements long. Most likely, internally only a few small objects are allocated.

The advancements of structural sharing data structures, greatly helped with the groundbreaking work by Okasaki, has all but shattered the myth that immutable values are too slow for Real Apps. In fact, it’s surprising how many apps can be made faster with them. Apps which read and copy data structures heavily (to avoid being mutated from someone else) will easily benefit from immutable data structures (simply copying a large array once will diminish your performance wins from mutability).

More so, in Neal Ford’s excellent book “Functional Thinking” he offers examples in Groovy, even though Groovy was initially influenced by Ruby, and both Groovy and Ruby initially celebrated a loose “mutate anything” style that is the opposite of Functional programming.

All the same, I think it is easier to work in the Functional style if you work in a language that actively promotes the Functional style. But if you’re in love with a highly mutable language like Javascript, you can still achieve a Functional style, so long as you commit to it.

Immutable objects are simple

If you want a slightly more formal argument for favoring immutability, consider that Joshua Bloch, in his well-regarded book “Effective Java“, lists “Minimize Mutability” as one of his 78 rules.

This is from page 75:

[He gives an example of a class that represents a complex number.]

    public final class Complex {
      private final double re;
      private final double im; 

      public Complex(double re, double im) {
        this.re = re;
        this.im = im;
      }

      // Accessors with no corresponding mutators

      public double realPart() { return re; }
      public double imaginaryPart() { return im; }

      public Complex add(Complex c) {
        return new Complex(re + c.re, im + c.im);
      }

      public Complex subtract(Complex c) {
        return new Complex(re - c.re, im - c.im);
      }

      public Complex multiply(Complex c) {
        return new Complex(re * c.re - im * c.im,
                           re * c.im + im * c.re,);
      }

      public Complex divide(Complex c) {
        double tmp = c.re * c.re + c.im * c.im;
        return new Complex((re * c.re + im * c.im) / tmp,
                           (im * c.re - re * c.im) /tmp);
      }

      // [more code in the book]

In addition to the standard Object methods, this class provides accessors for the real and imaginary parts and provides the four basic arithmetic operations: addition, subtraction, multiplication and division. Notice how the arithmetic operations create and return a new Complex instance, rather than modifying this instance. This pattern is used in most nontrivial immutable classes. This is known as the “functional” approach because methods return the result of applying a function to their operand without modifying it. Contrast this to the more common “procedural” or “imperative” approach in which methods apply a procedure to their operand, causing its state to change.

The functional approach may appear unnatural if you’re not familiar with it, but it enables immutability, which has many advantages. Immutable objects are simple. An immutable object can be in exactly one state, the state in which it was created. If you make sure that all constructors establish class invariants, then it is guaranteed that these invariants will remain true for all time, with no further effort on your part or on the part of the programmer who uses the class. Mutable objects, on the other hand, can have arbitrarily complex state spaces. If the documentation does not provide a precise description of the state transitions performed by mutator methods, it can be difficult or impossible to use a mutable class reliably.

Immutable objects are inherently thread-safe; they require no synchronization. They cannot be corrupted by multiple threads accessing them concurrently. This is far and away the easiest approach to achieving thread safety. In fact, no thread can ever observe any effect of another thread on an immutable object. Therefore, immutable objects can be shared freely. Immutable classes should take advantage of this by encouraging clients to reuse existing instances wherever possible.

…Immutable objects make great building blocks for other objects, whether mutable or immutable. It’s much easier to maintain the invariants of a complex object if you know that its component objects will not change underneath it. A special case of this principle is that immutable objects make great map keys and set elements: you don’t have to worry about their values changing once they’re in the map or set, which would destroy the map or set’s invariants.

Is the Functional style verbose?

Some people see code like this and complain that it is verbose:

user = store_session_key(user)
user = update_last_login(user)
user = update_permissions(user)

I am sympathetic to that complaint, but at least here you can guess what is going on. You see three functions being called, you can see the arguments to the functions, and you can see the return. More so, you can see that the return value of store_session_key is suppose to be the argument to update_last_login and that the return value from update_last_login is suppose to be the argument to update_permissions. That is important information.

I’ve known some developers who feel that the repetition in these three lines is a violation of DRY, but we should avoid applying DRY in such micro-circumstances. Truly, this would be one of those small optimizations that are the root of all evil. The concept of DRY (Don’t Repeat Yourself) should be applied at a much higher level.

Some of you may have read about my adventures at a startup last year. You will recall that I worked with a very junior Java programmer. Here is one of the functions that he wrote:

        public void extract() throws Exception{
                getTagMap(caseNERMap);
                getCaselessTagMap(caselessNERMap);
                extractNS(sentences);
                matchAllMoney(debrief);
                extractCelolotInformation();
                disambiguateEntities();
                singularizeLabels(celolotTagMap, customTagMap);
                mergeMaps();
                integrateDropDownInfo();
                findExplicitAssignments();
                getNumber("Amount");
                getNumber("Initial User Count");
                generateOppName();
                normalizeHashMap();
                convertToLabels();
        }

Generally, we should try to avoid writing code like this. Among other things, it is opaque. We can assume that each of these functions is modifying some variables that belong to the object that we are in, or perhaps they modify variables that exist in objects that this object currently holds a reference to.

Notice that this function has 8 arguments:

caseNERMap
caselessNERMap
sentences
debrief
celolotTagMap
customTagMap
“Amount”
“Initial User Count”

Or rather, it has zero arguments, but it is using 6 variables that exist somewhere outside of the function. Two arguments are hard-coded strings.

We could say “This function should have had 8 arguments.” (We could say that if we ignore the fact that this function should have probably been broken up into smaller functions, or arranged as a pipeline of closures, each with their own arguments.)

The “extract()” function is all about its side-effects. Roughly speaking, you can judge the quality of Java code by the number of functions that return void. The more you see “void”, the worse the quality.

There are a handful of circumstances where side-effects are justified, and those circumstances fall into roughly two categories:

1.) at startup when your app is first initialized

2.) when your app outputs or stores its result

Regarding #1, we will later talk about the ongoing debate that Functional programmers have had about Dependency Injection.

There are several things we can do to improve the “extract()” function, but one of the most basic is transform it into a pure function, where the state being modified is handed in, and we can see it being altered. That might seem verbose, but we should be willing to pay that price so as to achieve code that can be read. Again, Joshua Bloch gave an excellent example.

When we do write a function that updates the value of a var outside of the function, then that update should be the sole outcome of the function. Updating multiple external vars is probably a mistake, and more so, having no idea what outside vars are being updated is seriously opaque code. In the fucntion I just linked to, I give an example where I am updating an external var, but at least you can see, inside my function, which var I’m updating.

Pipelines or multiple changes to a local binding

Commonly, we will have a data structure and we will want to push it through multiple transformations. We can do this a few ways, and some of the choice depends on how much transparency we want about the code, and also how we want to handle error-checking.
In Clojure, when I use Enlive to generate HTML fragements, I have written code such as this, which looks a lot like code you will find in other languages:

(defn tma-link-to-this-item-if-it-is-a-file [template request]
  {:pre [
         (vector? template)
         (map? request)
         ]
   :post [(vector? %)]}
    (let [item (first (controller/fetch "get-current-item" request))
          template (enlive/transform template
                                     [:#tma-link-to-this-item-if-it-is-a-file :a]
                                     (enlive/content (str "Download: " (:file-name item))))
          template (enlive/transform template
                                     [:#tma-link-to-this-item-if-it-is-a-file :a]
                                     (enlive/set-attr :href (str "/processed/" (:file-name item))))]
    template))

In these lines you can see that the local var “template” appears both on the left and the right:

          template (enlive/transform template
                                     [:#tma-link-to-this-item-if-it-is-a-file :a]
                                     (enlive/content (str "Download: " (:file-name item))))
          template (enlive/transform template
                                     [:#tma-link-to-this-item-if-it-is-a-file :a]
                                     (enlive/set-attr :href (str "/processed/" (:file-name item))))

That is, I give “template” to the Enlive function “transform” and I get back a new template, and then I give that new template to to the Enlive function “transform” again, and make yet another transformation. This is similar to the Java code we saw up above, where making a change means getting back a new object, rather than the old object mutated.

      public Complex add(Complex c) {
        return new Complex(re + c.re, im + c.im);
      }

Clojure offers a few other ways to handle this, including the “threading” macro, so I could have written:

(-> template
       (enlive/transform
                        [:#tma-link-to-this-item-if-it-is-a-file :a]
                        (enlive/content (str "Download: " (:file-name item))))
       (enlive/transform
                        [:#tma-link-to-this-item-if-it-is-a-file :a]
                        (enlive/set-attr :href (str "/processed/" (:file-name item)))))

This is idiomatic Clojure, although beginners often have trouble reading this.

In the next post, we look at an especially the horrors of mutable iterators.

Source