Hi, I am Saša Jurić, a software developer with 10+ years of professional experience in programming of web and desktop applications using Elixir, Erlang, Ruby, JavaScript, C# and C++. I'm also the author of the upcoming Elixir in Action book. In this blog you can read about Erlang and other programming related topics. You can subscribe to the feed, follow me on Twitter or fork me on GitHub.

Working with immutable data

| Comment on this post
In the next few articles I will talk about programming with immutable data, a very important property of functional programming languages. Using immutable data might seem scary to a typical OO programmer used to deal with data which can be modified in-place. After many years of C++/C#/Ruby based development, I certainly had difficulties getting used to this concept. However once accustomed, I found it brings many benefits over classical mutable data approach: it forces a cleaner, better structured code, and makes concurrent programming much easier.

This series especially targets classical OO developers, accustomed to standard mutable variables. You might find the topic interesting even if you don't plan on coding in a functional language such as Elixir or Erlang. Immutable structures can be implemented in other languages (like this one in Ruby) and can bring some benefits which are difficult to gain with mutable data.

The first article of this miniseries will be more theoretical, presenting the basic ideas, benefits and building blocks of immutable programming, while the future ones should contain more practical, code driven examples on how to manipulate complex data. As usual, I will talk from the Elixir/Erlang point of view, but most of the ideas presented can be implemented in most modern languages.


Basics

The general idea of immutable programing is that it is impossible to do an in-place modification of a variable. Instead we can call functions which transform current value and return the modified version:

new_data = transform(original_data)

The transform does not in any way changes the original data so after it is executed we have acces to both old and the new data. The transform is a side effect free function: the same input will always produce the same output.

A more specific example of how this works is illustrated by this Elixir snippet:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
defmodule Company do
  def new(name), do: {name, []}
  
  def add_employee({company_name, employees}, new_employee) do
    {company_name, [new_employee | employees]}
  end
end

company_1 = Company.new("Initech")
company_2 = Company.add_employee(company_1, "Peter Gibbons")
company_3 = Company.add_employee(company_2, "Michael Bolton")

The Company module defines transformation functions, and lines 9-11 illustrate how we can use them to create and modify the state without in-place mutations. With proper language support we won't need the intermediate variables. Instead we can somehow chain the calls together, feeding the output of the previous function as the argument of the next one. I plan to discuss this in the future articles, but here is the taste of how is this done in Elixir:

company = 
  Company.new("Initech") |>
  Company.add_employee("Peter Gibbons") |>
  Company.add_employee("Michael Bolton")

If appropriate data structures are chosen (with respect to the actual transformations), the two variables (old and new) will share as much memory as possible, with the rest being shallow copied. For example, if we modify the 3rd element of the Elixir list, the new list will hold a shallow copy of the first two elements, the third one will have the new value, and the rest of the list is completely shared. In the example above, when we call add_employee, the new company variable will completely share the data with the previous one, adding additional information (new employee data) to its own structure.

With appropriately selected data structures, the transformations should work reasonably fast (though not as fast as in place mutations, this is what we are trading off for some other benefits). In the example above, add_employee is an O(1) operation due to the characteristics of Erlang lists and the fact that we are pushing the new employee to the top of it.

How is this used in a long running program which must respond to outer interaction and represent the changing state using immutable data? The following pseudocode illustrates the idea:

forever do
  message = wait_for_external_input()
  new_state = transform(current_state, message)
  store_state(new_state)
end

A program waits for an external input such as user interaction, network message, message from another thread or process, change on a file system, etc. Based on that input and the current state, it computes the new state (without modifying the current one) and somehow stores it (so it can be retrieved when the next external input arrives).

What does it mean to store the state? The simplest approach is to assign a value to a global variable. Since in most mutable languages assigning a value doesn't modifies the old value this won't break the immutability principle (closures might complicate the matter but I won't go into such deep details).
Erlang and Elixir offer more sophisticated solutions such as infinite tail recursion, where a loop is a function which calls itself passing the new state as the argument (if you haven't read it, refer to my article on actors which explains this in more details). Alternatively, an in memory mutable key-value store called ETS can be used.


Benefits

The key benefits of this approach are data consistency, improved code quality and easier concurrent programming.

Data consistency

Since transformation does not change the data (it only returns a modified version), it can be considered as an atomic operation. If it fails somewhere in the middle, it will not leave a mess inside the current state. We can capitalize on this by slightly altering the pseudo code presented earlier:

1
2
3
4
5
6
7
forever do
  message = wait_for_external_input()
  new_state = transform(current_state, message)
  store_state(new_state)
catch
  store_state(current_state)
end

If an invalid message somehow causes an unhandled exception, we can simply continue the execution using the current state (line 6) which is in no way corrupted by the transformation. Think of this as an in memory atomicity: either complete transformation will happen, or nothing will change.

The transformation may still introduce side effects, if it communicates with external entities e.g. by sending messages to other threads or system processes, storing to database or file system, or issuing network requests. Functions with side effects are also called impure functions. To retain consistency, it is best to completely separate impure operations from the state transformations, first calling the pure state transformation and afterwards executing the side effect tasks:

forever do
  message = wait_for_external_input()
  new_state = transform(current_state, message)
  execute_impure_tasks(new_state)
  store_state(new_state)
catch
  store_state(current_state)
end

If the state transformation breaks, no side effects will be introduced and consistency is kept completely. For the impure tasks, we have to either ensure it executes atomically (e.g. by using database transactions) or live with the fact they will not always succeed and develop our system accordingly.


Improved code quality

When an impure transformation causes no side effects, it is easy to reason about the code, and understand what it does and what it simply cannot do. Consider the following two function calls:

# retrieves employee, doesn't modify anything
employee = company.employee(name: "Peter Gibbons")

# retrieves employee, returns modified company
{employee, new_company} = company.employee(name: "Michael Bolton")

The first call retrieves the employee and produces no side effects. We can be 100% positive nothing else is modified.

The second call, however, additionally returns the company, which is a clear indication it does some additional work (e.g. internally caches the employee so the next retrieval works faster).

Another important benefit is the promotion of well factored code. Working with immutables forces you to divide your code into many small functions. Although not immutable specific, here it is more or less the only way to develop maintainable code. Since the code will be factored into many small functions with clean inputs and outputs, which produce no other side effects and do not rely on any global data, it will bring improved reusability and the code will be easier to test.

Easier concurrent programming

With the help of immutables we can write concurrent, multi threaded programs almost without any need for classical synchronization techniques such as locks, semaphores and mutexes:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
# main thread
forever do
  message = wait_for_external_input()
  new_state = transform(current_state, message)
  notify_parallel_thread(new_state) # requires synchronization
  store_state(new_state)
end


# parallel thread
forever do
  message = wait_for_message_from_main_thread() # requires synchronization
  do_something(message)
end

The code above presents two threads of execution. The main one again runs the infinite loop which processes external inputs and modifies the state. In line 5, the main thread somehow notifies the parallel thread that it has some new work for it. Upon receiving that notification (line 12) the parallel thread will do something with the data it received.

Consequently, we need some kind of messaging system to communicate between threads (Erlang has it built in, and I have seen libraries available for other languages, or you can always hand code it yourself) and this messaging system will indeed require some synchronization, since both parties, the sender and the receiver, modify the shared communication channel.

However, the data transformations run in parallel, without any need for synchronization. The transformation of the main thread (line 4) can run simultaneously to the computation of the parallel thread (line 13), even if both functions work on exactly the same data residing in the same memory location. This works because neither transform of the main thread nor do_something of the parallel thread can modify the data.

So the data transformations, which we expect to be complex operations (otherwise why parallelize them?), can run completely in parallel, without any need for acquiring the lock, waiting for another thread to finish, or blocking another thread. Not only does this significantly simplifies the code, and reduces deadlock possibility (it can still happen, but far less often), but it also promotes the true parallelism, since the need for synchronization is minimal. I should note that in Erlang, this benefit is not relevant, since the data is never shared between two processes anyway (it is deep copied instead).


Building blocks

The basic idea behind immutable data is not very complicated and can be implemented in many mutable based languages. In addition to primitive types (ints, floats, booleans, ...), we need two complex structures: one to hold together small fixed number of elements (something akin to records), and another one to store arbitrary large, dynamically changed collections. Of course, both of these structures must be implemented as immutables: each modifier method may not modify any existing variable, but instead must create the new instance which represents the modified version of the structure.

To implement fixed size records, Erlang and Elixir use tuples. Tuples have instant read time and O(N) modify time (N being the size of tuple). When we modify a tuple, a new one is always constructed, with modified values in place of original ones, and unchanged values shallow copied. Since tuples usually hold a small number of fixed elements, the updates should be fast enough. In an OO language tuples can be implemented using a class which exposes only public readonly properties (which may return only immutables) and modifier methods, which return new instance.

Arbitrary sized collections are usually implemented with cons, a singly linked list where each element holds a value and a pointer to the rest of the list. When using cons, pushing a new element at the top of the list, and reading the head of the list are O(1) operations. All other operations such as random data access, updates or deletes are O(N). If we update an Mth element of an N sized list, the first M-1 elements will be shallow copied, than the modified element comes, and the rest of the list is completely shared.

All other complex structures such as binary tree, hash, stack, queue or set, can be implemented on top of tuples and cons (lists). For example, in Erlang, a balanced binary tree is implemented as a recursive tuple and gives an O(log2N) performance for both reads and writes. Erlang dictionary, on the other side, uses both tuples and lists, nesting them to divide the data in buckets.

In a language which deals strictly with immutables, there are no classical loops (since a variable cannot be modified). Instead such languages have strong support for recursion, transforming the tail recursion calls to pure jump instructions. Often a support for pattern matching exists, allowing us to write functions consisting of multiple clauses, of which only one will execute depending on the values of input arguments. Here's the example of recursive list iteration in Elixir:

def each([]), do: :ok # empty list
def each([head | tail]) do
  IO.inspect head
  each(tail)
end

Notice how two clauses of function exist, one for empty and another for non empty list.

If the recursive code is too verbose, we can use helper functions to make the code seem more imperative. For example, in Elixir, the function Enum.filter can be called to get all even numbers from the list:

Enum.filter(
  [1, 2, 3, 4, 5], 
  fn(x) -> rem(x, 2) == 0 end
)

This is an example of a so called higher order function, which is a fancy name for a function that takes another function as an argument, or returns a function (or both). In this case Enum.filter takes the list and a filter function which is invoked for each element of the list. The result is another list holding all elements for which the filter function returned true.
Although the fact is hidden, Enum.filter is internally still based on a recursion, as there are no alternatives in an immutable based language.

If you try to emulate immutables in a mutable based language you will have the commodity to use typical loops (lik for and while) which use local mutable variables. I advise avoiding this approach whenever possible. Many modern mutable based languages, such as Ruby, provide high order enumerable functions which can reduce the amount of mutables in a program.


Downsides

As I mentioned earlier, immutable updates will generally be slower than the mutable ones. After all, we are constructing a new variable instead of modifying the existing memory location and in addition shallow copy some elements. However, this should usually not present a problem, since the real performance cost most often lies in the computational part (e.g. transforming the data) or in I/O operations.

Since every modifications returns a new value, the garbage collector will have to deal with a large amount of short lived variables. If the language is immutable based, the GC is probably specifically fine tuned for such situations. For other environments it is best to research and test. I would expect the generational collectors to work fine, since they expect many short lived variables but I don't have any real experience or data to back this up.

The final downside (actually a benefit) is that you can't resort to fast hacks. If you deal with immutables. Forget about quick fixes where a global variable is set in one place and read in another one. Data can only be propagated via function arguments or return values, so you are forced to incorporate your special cases in your conceptual model, which is a good thing because it again promotes cleaner, easier to maintain code.

Wrapping up

If you have endured this far, hopefully you are a bit intrigued in exploring the world of immutable programming. I tried to reduce the boring theory to a bare minimum, which we can use to do something more interesting. Next time I will discuss how to deal with a more complex immutable data.

On a completely unrelated note for all Erlang programmers:  I'll be attending this year's Erlang User Conference, so if you happen to be there and are interested in a live discussion about Erlang, Elixir or anything else, let me know. I am looking forward to finally meeting Erlang programmers in person :-)

Post a Comment