Sealgram

Immutability and Purity

People often point that immutability and purity makes writing parallel code easier, but I think the magnitude of this change is not grasped by people that did not try it on practice. As an example, this is a snippet of Haskell code that calls "someSlowFunction" a few times, with the parameters taken from a list:

input = [a, list, of', data, to, handle]
foo [] = []
foo (i:ii) = let
       x = someSlowFunction i
       y = foo ii
       in x:y

Now, this is a version of the same code, with the "someSlowFunction" calls parallelized over as many workers as wanted (if it's compiled by GHC, you'll get a command line switch for that):

input = [a, list, of', data, to, handle]
foo [] = []
foo (i:ii) = let
       x = someSlowFunction i
       y = foo ii
       in x `par` y `seq` x:y

There are libraries for available for when even that par-seq syntax gets too complex, but that is an usual case. That's what is possible when computation is done with immutable data and pure functions. In pure code over immutable values, parallelism can be fully automated. Yet, this approach of manually adding it, by a simple mark at the code seems to bring the best performance on practice, so that many languages are adopting it.

Anyway, this code marking isn't exclusive of Haskell. Even imperative languages are adopting it. Yet, those languages are viable only for very simple parallelism cases, since lack of compile-time checked purity and immutability creates a special kind of stealthy bugs, that can silently corrupt data over the usually long computations.

For concurrency everything is different. First, execution sequencing can not be abstracted away. Some times the ordering of the code is on the problem specification. Also, it makes no sense to make pure code concurrent - its entire point is reordering IO.

Yet, immutability is also a big boost for concurrency. Immutable data is completely free from synchronization problems. By making immutable the default, 99% of the data just stop being a problem and programmers can focus on the 1% (or, often, less) that are are required to mutate. And, since concurrency is the main use case for mutable data, most of Haskell mutable primitives come already bundled with synchronization control, for extra convenience.

Immutability and purity will also make bugs easier to find, and performance easier to reason about. Added to that, they are a great filter for code quality. But since there are no easy metrics for those, an article just can not convince anybody that didn't experience those. Besides, fully exploiting those take some learning - one just does not experience any of that on the first try.

So, let's just stay with parallelism and concurrency. Two extremely important problems for computing today. For those, your life will be much, much easier if your pure code is segregated from the impure, and your values are immutable by default. And even easier if the compiler helps you enforcing that.

Monads for Marking Purity

There are several ways of marking code pure to checking at compile time.

The naivest of all approaches is simply marking the declaration of every function with side effects. The syntax could look like:

io int f(int param1, int param2, int param3)

This works. One creates a basic set of IO functions already marked at the standard library, and rejects any unmarked function that calls a marked one.

But this naive form creates an independent type system just for functions, that add complexity to the language, and will not play well with having functions as first class entities, as arguments or return values from other functions. Yet, this system is simple to use and reason about.

Alternatively, one can pass IO around as a value. This way, impure functions have an extra argument of some IO type, and only impure functions have a value around to pass at it. Would look like this:

int f(io i, int param1, int param2, int param3)

This approach plays very well with functions as first class entities and high order programming. It also does not require any specialized type system. But it increases the code complexity, and does not play well with immutability. [1]

For solving that, monads were created. Any type system that allows high order types would include let the first declaration be expressed at the same type system as the values. Syntax, thus would look exactly like the first example:

io int f(int param1, int param2, int param3)

In Haskell, instead of pseudo-code:

-- Optional type declaration:
f :: Int -> Int -> Int -> IO Int
-- The function body
f param1 param2 param3 =

Except, this time "IO Int" is a plain type, allowed everywhere. But notice that this "IO" type has a special meaning - it means functions must always be evaluated, and in the same order as they appear on the code. Well, monads are just a generalization of this meaning.

Since monads are expressed by the same type system of values, high order functions can simply take monadic functions as parameters, the same way they can take pure functions:

-- Gets a value, a list of functions to apply it,
-- returns a list of values.
f :: Int -> [Int -> Int] -> [Int]

-- Gets a value, a list of IO functions to apply it,
-- returns a list of values.
f :: Int -> [Int -> IO Int] -> IO [Int]

Or, in other words, monadic IO gives you the best of both approaches, and none of the problems.

Monads for Immutability

For immutability the case is less clear, but not less strong. Most real word problems just need data to change from a moment to the other. In principle, this is no problem for immutable data, one just creates new data as the computation evolves, and lets old data forgotten, to be retired by the garbage collector. That is:

let
d0 = initialData
(x, d1) = somethingThatTransformsData d0
d2 = otherThingThatTransformsData d1
d3 = yetAnotherThing d2
-- And so on...

Does not look too bad, but it is. First, all those functions must explicitly return the next data, thus all those functions will be more complex than they need to be. A couple of lines of code here, a couple there, and suddenly your code is hard to change, because hundreds of lines spread into several files must be updated together.

Then, there are many possible organizations for that code, all equivalent, but all incompatible. For example, when a function does not change the data, should it return a new version anyway? And when it must return some other value, in what order is the tuple constructed? Remembering those permutations is a real load.

Finally, code like that is full of opportunities for simple typos to insert hard to debug, and even hard to detect bugs. Exactly the opposite of what one expects from a strictly typed language.

Haskell has many monads that deal exclusively with state. The general idea is that they let state keeping on the bind function, and just export the suitable accessors for reading and writing, however it makes sense. It has 4 general purpose state keeping monads:

• Reader, that broadcasts an immutable state to functions,
• Writer, that collects immutable state from functions,
• State, that manages mutable state between functions (solving the example above),
• RWS, that acts as Reader, Writer and State, for three different kinds of state.

On the State monad, the above code would look like:

do
       put initialData
       x <- somethingThatTransformsData
       otherThingThatTransformsData
       yetAnotherThing
       -- And so on...

All the possible variance goes away, all those variables disappear. There is even a library called "lens" that will make state reading and writing almost equal to reading and writing state on an object in a traditional OOP language, but keeps everything immutable.