WORKING WITH IMMUTABLE DATA

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:

  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 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. 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.

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.

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:

  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 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:

# 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 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:

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 do 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 (like 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

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.

* * *

Since Elixir is often wrongfully labeled as OO language, I would like to stress that the programming style used in these examples is in no way Elixir specific. Erlang itself supports polymorphic dispatches via a lesser known feature called "tuple modules", which allows us to couple code with data. Although somewhat controversial, the feature is still here, and we can exploit it to make the code more readable.

Before starting, let me give you a slight preview of what will we be able to accomplish:

Company.new(name: "Foo")
  .add_employee(Employee.new(name: "alice",  salary: 340.00))
    .add_employee(Employee.new(name: "bob", salary: 120.00))

Although the code looks very OO-ish, no in-place mutation of a variable takes place. Instead, each function call creates a new intermediate variable which holds the modified version, which shares as much data as possible with the old version (assuming appropriate data structures are used).

Basic manipulation

The basic unit of code organization in Elixir is a module, a simple collection of functions.

On top of this, drawing from the power of its macro system, Elixir provides struct, which are nothing more than modules. structures are mainly meant to be used as pure structures which group data together. However, since they are essentially modules, we can extend them with our own functions which, when defined in a particular way, can simulate something akin to OO methods:

defmodule Company 
do

  defstruct name: "", employees: []
  
  def new x
  do 
    %Company{name: x}
  end

  def add c , x
  do 
    %Company{name: c.name, employees: [x | c.employees]} 
  end

end

We start off by defining a structure and its fields. Then a function add is defined. The code of the function is fairly simple: it push new employee to the top of the list. This is an immutable way of modifying things: instead of an in-place mutation, we return a modified version.

The primary benefit of OO style is the elegant use of the dot (.) operator which allows us to chain multiple statements without using intermediate variables. To mimic this in pure functional style, we can use the pipeline operator (|> ) which feeds the result of the previous function to the next call as the first argument. So the call

    something |> fun1(a,b) |> fun2(c,d)

is in compile time transformed into

    fun2(fun1(something, a, b), c, d)

This makes it easy to chain function calls, much like in OO approach, but without the need for runtime dispatch.

    
   Company.new("Initech") 
|> Company.add("Peter Gibbons") 
|> Company.add("Michael Bolton") 
|> IO.inspect

Last lines demonstrate how we can use the Company structure. First we create a new instance, then we can use it to call add "method", and print the final result.

Notice that the pipeline operator feeds the previous result as the first argument.

Manipulating complex data

Due to similarities between pipeline and OO chaining, it is fairly straightforward to convert OO code to the FP version:

file "Company.ex":

defmodule Company 
do

  @moduledoc """
  some info about module Company
  """

  defstruct name: nil, employees: Map.new 


  @doc """ 
  some words abt method 'create' 
  """ 
  def create(name) 
  do 
    %Company{name: name , employees: Map.new}
  end


  @doc """ 
      some words abt method 'insert' 
  """ 
  def insert(c , x)
  do
    %Company{ name: c.name , 
              employees: Map.put(c.employees ,
                                 x.id , 
                                 %{name: x.name , salary: x.salary})
            }
  end
 
 
  @doc """ 
  some words abt method 'extract'
  """ 
  def extract(c , id), do: Map.get(c.employees , id)

end

file "Employee.ex":

defmodule Employee
do

  @doc """ 
  some words abt function 'new' 
  """ 
  def new(id , name , salary) , do: %{id: id , name: name , salary: salary}

end

And script file "Doit.exs":

x1 = Employee.new(1 , "alice" , 123.45)
x2 = Employee.new(2 , "bob" , 987.65)

y = Company.create("foo") |> Company.insert(x1) |> Company.insert(x2)

IO.inspect Company.extract(y , 2).name
IO.inspect Company.extract(y , 1).salary

Whenever we call the Company module function from the outside, we have to explicitly reference the module. This is the obvious consequence of not using polymorphic dispatch: the code will be a bit polluted with duplicated module references. It is not as huge problem as it might initially seem. Usually, a chain of multiple calls of functions from a single module, could be moved to that module as a distinct function. Once inside the module, we can omit the module prefix when calling functions.

$> ls
Company.ex  Doit.exs  Employee.ex
$> elixirc Company.ex Employee.ex 
$> ls
Company.ex  Doit.exs  Elixir.Company.beam  Elixir.Employee.beam  Employee.ex
$> elixir Doit.exs 
"bob"
123.45

Protocols

By abandoning OO styled syntax, we also lose polymorphic nature of our code: the function which gets invoked is now determined in compile time. When you do need a polymorphism, i.e. a run-time decision of which function to call, there are two standard ways of doing it.

The basic Erlang way of doing run-time polymorphism is to use multi-clause functions and pattern matching.

Each clause represents a specific implementation which will be invoked depending on the actual values of arguments. The problem with this technique is that it is not flexible. If a new type must be supported, definition of the polymorphic function must be extended with an appropriate clause. This means that all variants must reside in one module.

Furthermore, the problem becomes harder to solve if for some reason you can't modify the module. In such situations, you must add another layer of indirection (essentially another multi-clause function) in front of it, which is somewhat clumsy.

To overcome this, Elixir introduces protocols , a construct somewhat similar to OO interfaces.

A protocol is essentially an abstract module, where functions are declared, but not implemented. The generic piece of code uses the protocol , while clients provide implementations for their own types.

By implementing the protocol , you get the benefit of reusing the generic code, without modifying it. However, comparing to OO interfaces, protocols are again based on pure functions and do not rely on data + behavior coupling.

The main benefit of protocols is that new implementations can be freely provided and are not required to reside in one place in code.