read


read
or learn more

No Stinking Mutants

Jul 12, 2011

In the quest for programming nirvana developers are constantly trying to reduce complexities in their code. One source of confusion and complexity is mutation. This post is about the different faces of mutation and state change, and the ways that Clojure helps to alleviate the complexities surrounding them. This is not a comprehensive treatise by any means, but hopefully it serves as a survey.

disclosure: this was a rejected submission to PragPub’s Special Clojure issue (which was excellent BTW), so it’s much longer than I would have liked for my blog, and probably much more formal than I normally write.

A surfeit of mutation

The Java programming language allows one to create classes with publicly accessible fields:

package gfx;

public class ThreeDee {
    public double x;
    public double y;
    public double z;
}

This level of promiscuity in a Java class definition allows any other piece of code to directly manipulate the instance fields:

ThreeDee p = new ThreeDee();
p.x = 0.0;
p.y = 1.0;
p.z = 2.0;

Almost every Java book written will discourage public class fields in the name of tight-coupling and instead promote the use of getters and setters. From the perspective of mutation complexities however, there is very little difference between one and the other. The tangled web of mutation still exists.

web of confusion

While this example is extreme, Java’s model for mutation leads to a tightly coupled web of mutation that can make programs difficult to reason about, test, and change. There are better alternatives to this web of insanity, as I will discuss next.

Package local mutation

A more constrained model of mutation is one bounded by package access. Observe the following class definition:

package gfx;

public class ThreeDee {
    double x;
    double y;
    double z;
}

The class ThreeDee now limits access to its fields to only the classes within the gfx package. This is less of a problem for coupling because the assumption is such that you have more control over the code in a given package and can therefore adjust accordingly should the fields in ThreeDee change. However, while the web of mutation has been shrunk, it is still complex within the gfx package itself.

pkg web of confusion

While certainly not a widespread phenomenon, you will on occasion encounter package-level mutable fields in Java source in the wild.

Class local mutation

Every Java book (and most OO books in general — for good reason IMO) written will espouse the virtues of data hiding encapsulation. This practice is useful not only in hiding implementation details, but also to hide mutation. For example, Google’s Guava library provides an ImmutableList class that implements an immutable implementation of the classic list data-structure. An example usage is as below:

import com.google.common.collect.ImmutableList;

ImmutableList lst = ImmutableList.of("servo", "joel", "crow");
System.out.println("lst is " + lst.toString());

System.out.println("REVERSING!");
lst.reverse();

System.out.println("lst is now " + lst.toString());

When running the code above, you’ll notice the following printed:

lst is [servo, joel, crow]
REVERSING!
lst is [servo, joel, crow]    

The ImmutableList class lives by its namesake and does not provide a mutable interface, in fact if you try to call the mutable bits of the java.util.List interface a java.lang.UnsupportedOperationException is thrown.

lst.remove(0);
// java.lang.UnsupportedOperationException

The Guava library is designed to provide clean immutable collections1 for use in Java programs. However, that’s not to say that mutation isn’t there. Instead, the mutable bits are cleverly hidden away inside of the Guava classes. In the case of ImmutableList there is a plain-old Java array holding the elements of the list hidden away from grubby little mutants.

Limiting mutation at the class boundary is a fairly nice way to develop Java classes, especially those requiring concurrent execution. That is, if a class is immutable from an external API perspective and its internals are thread-safe, then instances can be shared freely across thread boundaries.

class web of confusion

However, there is still a problem. That is, Google’s Guava library is an amazing piece of programming, but it’s advantages can only be realized within the context of a system-wide convention for immutability. In other words, Java will not enforce immutability as a language feature — the onus is on us to enforce our own best-practices.

I don’t know about you, but I’ve found programming conventions and best-practices difficult to observe completely when left to my own devices.

This is where Clojure enters the fray.

Single points of mutation

Clojure is a programming language in the Lisp family of languages that eschews promiscuous mutation. The core libraries and data structures are geared toward immutability by default. In fact, Clojure’s data-structures provide most of the same functionality as Guava, except in Clojure these features are exposed and enforced at the language level. Therefore, the problem of an adherence to convention is simplified vastly. However, let’s be realistic; sometimes mutation is needed. In the case where mutation really does seem like a good fit for any given problem at hand, Clojure provides multiple solutions.

Reference types

Recall the image denoting the aforementioned web of mutation:

web of confusion

Clojure’s model of mutation attempts to simplify the model from the chaos above by distilling the points of mutation into as few points of evil as possible; preferably one:

single point

Clojure offers a set of reference types that provide a mutation model centered on singular points of mutation. References types can be viewed as containers for values — where values are things that cannot be changed like the number 9 or the immutable vector [1 2 3]. Clojure therefore allows mutation only at the boundary of the reference type under very specific semantic constraints. The precise mutation semantics of each reference type are beyond the scope of this article,2 but common among each is that the mutation occurs as the result of a function call given the reference type’s current value.

Atoms

The simplest of Clojure’s mutable reference types is the Atom. Simply put, the Atom implements thread-safe compare-and-swap logic for mutation.

(def TIME (atom 0))

The Atom TIME when created will hold the value 0. To get at the value inside Clojure provides a dereferencing function deref (note, the symbol ;=> denotes a function return value):

(deref TIME)
;=> 0

All of Clojure’s reference types adhere to a simple interface for retrieving their value using deref (or the syntactic @ operator, that does the same thing). To update the value in the Atom TIME Clojure uses the swap! function that itself takes the Atom and a update function that will be used to calculate a new value from the current value:

(swap! TIME inc)

@TIME
;=> 1

You can also pass arguments to the update function (where applicable):

(swap! TIME + 100)

@TIME
;=> 101

Internal to the swap! function, the preceding will be executed as such:

  1. Get the current value of TIME from the Atom
  2. Calculate (+ <current value> 100)
  3. Check if the value in the Atom is the same as before
  4. If it is, then set the new value to the calculated value
  5. Else Retry from step 1

Pretty simple no? It is when provided as a language-level feature, but to implement compare-and-swap correct and efficient in the context of a large codebase is a decidedly more complex task.

As mentioned, Atoms are but one mutable reference type provided by Clojure. I encourage you to explore the other offerings available: Refs, Vars, and Agents.

Function local mutation

You can also restrict mutation to occur only within the confines of a single function.3 Observe a naive implementation of zencat that uses an internal array to build the return vector:

(defn zencat2 [x y]
  (let [sz-x (count x)
        sz-y (count y)
        ary (make-array Object (+ sz-x sz-y))]
    (dotimes [i sz-x] 
      (aset ary i (nth x i)))
    (dotimes [i sz-y] 
      (aset ary (+ i sz-x) (nth y i)))
    (vec ary)))

Aside from being highly inefficient, the function zencat2 is filled to the brim with mutation. However, the mutable array ary never escapes the scope of the zencat2 function. Instead, it is converted to an instance of Clojure’s immutable vector. There will come a time when you may need to implement an algorithm that requires mutation either for speed or the sake of clarity. That’s OK, Clojure will help you to hide the necessary mutations in a lovely veneer.

Immutable locals

The function zencat2 used a mutable array instance to build a longer sequence from the concatenation of two other sequences. This fact gave the illusion of mutable locals, but in reality locals in Clojure are immutable by default. This fact can be daunting if you come from a language where mutation runs rampant. The natural question that arises when one realizes the fact of immutable locals is, “how do you keep local state?” As it turns out, the answer has already been revealed in the implementation of zencat. That is, in languages like Clojure and Erlang (to name only two) that do not have mutable function locals, the way to “change” the values of locals is through recursion. In the case of zencat, the value of the loop locals src and ret are changed to their new values on each invocation of the recur (implementing tail-recursion) statement. Therefore, it is possible, and in most cases preferable, to eliminate mutability entirely in Clojure. Observe the following:

(defn zencat3 [x y] 
   (if (seq y) 
      (recur (conj x (first y))
             (next y))
      x))

The implementation of zencat3 contains not a single mutation! The manipulation of immutable data-structures is really Clojure’s strong points, and in fact is highly optimized to support such manipulations as idiomatic. The majority of the Clojure code that you will find in the wild will look similar to zencat3, but there is still unneeded complexity in its implementation because as we know, recursion is a low-level operation.

Point-free

While the surface area of mutation has been eliminated with the implementation of zencat3, there is still complexity in that you need to reason through the different values that x and y take as the recursive invocations execute. What if you could eliminate x and y completely? As it turns out, you can. Functional programming fosters another style referred to as “point free” style. In a nutshell, point-free refers to the act of composing existing functions in such a way that their arguments are never explicitly listed. An implementation of zencat4 using point-free style would work as follows:

(def zencat4 (comp vec concat))

The comp function is a highly useful tool for composing functions in a point-free style. Simply put, comp returns a function that is the composition of the functions vec and concat. In other words, comp effectively returns the following:

(fn [x y] 
  (vec (concat x y)))

However, rather than cluttering the implementation of zencat4 with references to locals x and y, we can read the point-free implementation as; make a vector out of the concatenation of the arguments to zencat4. Point-free style is not always the best approach, but in some cases it can truly provide elegant solutions, and from my perspective represents the functional programming ideal:

  • Build independent, generalized, state-free functions
  • Plug them together via composition

This approach also works from the consumer’s perspective. Whereas, for any desired function Z composed of functions A . B, one can understand Z simply by first understanding B, followed by A.4 Point-free style is the capstone realization of true reusability, but it only works well when a programming language provides powerful abstractions — a separate topic for another day.

Clojure has it all

We’ve travelled a twisty passage through the different manifestations of mutation. Starting with a wide-open mutation strategy and ending on implementation strategy without a mutation in sight, nor even a local spied. Clojure is an opinionated language with regards to mutation, but as we saw, its idioms allow for a wide range of mutation styles. While it would be beautiful and pure to disallow mutation in any of its forms, Clojure is a practical language and therefore provides the tools for mutation should requirements dictate the need for them. The title of this post is provocative (and evocative for others) in the spirit of fun. Neither myself, nor does the Clojure ideal deny the need for mutability. Clojure provides support for a wide spectrum of options for mutation, it’s up to us to use its offerings wisely.

:F


  1. I highly recommend reading the source code of the Guava library. It and Clojure’s own immutable data structure implementations are masterful. Another high-quality codebase is Functional Java

  2. Unfortunately I need to punt on a deeper examination of how each of Clojure’s reference types simplify mutation through uniform interfaces, change as the application of a pure function, validators, and transactions. Such a topic would warrant a multi-post series IMO. 

  3. Clojure’s reference types are not a panacea for the complexities in designing concurrent systems. One should be mindful of designing concurrent systems, and in fact, the simplest threaded model is composed of a single thread. Clojure provides a feature called transients that provide a way to perform (potentially) faster data structure operations by using underlying mutable strategies that assume that the mutation occurs in a single thread only. The interface for transient manipulation looks very similar to that of the normal structure functions, as seen in my zencat gist. The zencat function builds a transient return vector that is the concatenation of two vectors x and y provided as arguments. While not precisely in the same category as the other mutation patterns discussed, transients deserve some consideration nonetheless. 

  4. Tony Morris espouses the virtues of composability more elegantly when discussing scalaz. The context is different, but the spirit is the same. 

6 Comments, Comment or Ping

  1. Great article!

    Only one minor nit to pick. It seems to me that you are implying (perhaps unintentionally) that Clojure’s reference types help with the “tangled web of mutation.”

    I think Clojure’s reference types are more about the insanity of multi-threaded programming. Using reference types you are better able to reason about correctness, but you can still create a tangled web of mutation.

    Do you agree that tangled webs of mutation are orthogonal to reasoning about multi-threaded correctness, or am I off base?

    Paul

  2. Ben Ellis

    @Paul

    I think you’re on to something. You could use a reference (or an atom, or, on a single thread, a var) and make code that is just as full of mutation and misery as the diagrams given above. You would just be fighting against the language design as you did it.

    Clojure’s preference for immutable data is its most advantageous aspect for avoiding confusing mutable state. References, vars, and atoms are ways of dealing with mutable state when you need something mutable.

    References give you mutable state, and safe multithreaded that allows (via transaction) to enforce invariants on multiple, related bits of mutable state.

  3. @Paul

    That is more than a minor nitpick as it’s definitely a glaring hole in the article. That is, I could have (and should have) gone into some discussion about minimizing the mutation, change as the application of a pure function, validators, and transactions, but I didn’t. Unfortunately for now I will punt (see my notes for punting) and just say, “this is an article for another day” since it probably warrants its own treatment. :F

  4. I guess what I was getting at was that the tangled web of mutation is more a function of encapsulation and coupling, whereas the reference types attack the problem of concurrency.

    You can have a concurrently safe, well reasoned program that still inappropriately touches mutable data in lots of different namespaces (i.e. the “tangled web of mutation”).

  5. Hi, Fogus,

    Your article was biased and inconsistent, hence poor.

    Despite saying that, “The title of the post is … in the spirit of fun,” your repeated straw-manning was fit only for the school-yard.

    Your repeated mentioning of, “Mutation insanity,” made your point manfully strongly, but collapsed with the embarrassing admission, “Neither myself, nor does the Clojure ideal deny the need for mutability.”

    Can you see how skewed your article is?

  6. @Shmoo

    I thought it was rather balanced — the joke’s on me I suppose.

Reply to “No Stinking Mutants”