Are purely functional data structures always lock-free?

Question

I've seen this claimed in several places, including on SO: https://stackoverflow.com/a/20467457/243238, https://stackoverflow.com/a/4400389/243238. I get the point that locks are not needed to modify the data but you end up with multiple versions of it after concurrent modifications. That doesn't seem very useful in practice. I've tried to describe this with a simple scenario below:

Let's say we have 2 threads A and B. They are both modifying a purely functional dictionary D. They don't need locks at this point because the data is immutable so they output new dictionaries DA and DB. Now my question is how do you reconcile DA and DB so that later operations can see a single view of the data?

EDIT: The answers are suggesting to use a merge function over DA and DB. I don't see how that solves the problem since there could be another thread C which runs concurrently with the merge operation. The claim is that purely functional data structures are lock-free but using a merge function sounds more like eventual consistency which is a different thing.

Answer 1

Good observation. But this just means that parallelism in the presence of a "global state" is difficult or impossible, regardless of the programming language.

In impure languages, this is just less obvious. You may think that you can get away with locking, synchronization and all the highly complex code around it.

Whereas in pure languages, you have n pure state transformers and cannot but realize that if you apply them in pareallel to some initial state S0 you end up with so many states S1, S2, S3 ... Sn

Now, the purity just guarantees that the parallel transformations of S0 do not interfere with each other in any way. It doesn't solve your program design issues, such as what that state means, if it is maybe too coarse, or too fine grained and if you can compute an end result form various transformed states.

Answer 2

The point with functional data structures is atomicity. In your scenario, DA and DB are guaranteed to be consistent, how to merge them into a consistent value depends on your application (functional programming will not solve ALL your problems for you). This is still however more than what you get in imperative paradigm where DA and DB depend on how the threads are sequenced.

Answer 3

In general there are a lot of ways to do it. In practice, you may want to ensure that either DA or DB is canonical. If that cannot be done then there should be a merge process

Thread A/B: 

da  <- readSharedMemory at D
da' <- modifyDict da
mergeSharedMemory da'

where mergeSharedMemory is capable of combining two dictionaries with a similar history in a consistent fashion. Generally, these kinds of structures are well-studied in the database literature as CRDTs—"convergent replicated data types" and "commutative replicated data types". The INRIA Paper has a great deal of detail about this.

Answer 4

Purely functional data structures are the easiest way to make lock-free mutable data structures. Given an arbitrary purely functional data structure T, you can define a lock-free mutable data structure newtype U = U (IORef T). Given an arbitrary function f :: T -> (T, a), you can write

mf :: U -> IO a
mf (U ref) = atomicModifyIORef' ref f

Why, then, is there a whole literature of fancy techniques for making lock-free data structures? Because not all data structures can be implemented efficiently enough in a purely functional way. Any operation that takes too long will slow all the threads down and lead to a backlog of updates.

Answer 5

You create a third function taking DA and DB that produces DAB.