What is it about functional programming that makes it inherently adapted to parallel execution?

Question

I've been reading over and over that functional languages are ideal (or at least very often useful) for parallelism. Why is this? What core concepts and paradigms are typically employed and which specific problems do they solve?

On an abstract level, for example, I can see how immutability might be useful in preventing race conditions or other problems stemming from resource competition, but I can't put it any more specifically than that. Please note, however, that my question is broader in scope than just immutability -- a good answer will provide examples of several relevant concepts.

Answer 1

The main reason is that referential transparency (and even more so laziness) abstracts over the execution order. This makes it trivial to parallelize evaluation.

For example, if both a, b, and || are referentially transparent, then it doesn't matter if in

a || b

a gets evaluated first, b gets evaluated first, or b doesn't get evaluated at all (because a was evaluated to true).

In

a || a

it doesn't matter if a gets evaluated once or twice (or, heck, even 5 times … which wouldn't make sense, but doesn't matter nonetheless).

So, if it doesn't matter in which order they are evaluated and it doesn't matter whether they are evaluated needlessly, then you can simply evaluate every sub-expression in parallel. So, we could evaluate a and b in parallel, and then, || could wait for either one of the two threads to finish, look what it returned, and if it returned true, it could even cancel the other one and immediately return true.

Every sub-expression can be evaluated in parallel. Trivially.

Note, however, that this is not a magic bullet. Some experimental early versions of GHC did this, and it was a disaster: there was just too much potential parallelism. Even a simple program could spawn hundreds, thousands, millions of threads and for the overwhelming majority of sub-expressions spawning the thread takes much longer than just evaluating the expression in the first place. With so many threads, context switching time completely dominates any useful computation.

You could say that functional programming turns the problem on its head: typically, the problem is how to break apart a serial program into just the right size of parallel "chunks", whereas with functional programming, the problem is how to group together parallel sub-programs into serial "chunks".

The way GHC does it today is that you can manually annotate two subexpressions to be evaluated in parallel. This is actually similar to how you would do it in an imperative language as well, by putting the two expressions into separate threads. But there is an important difference: adding this annotation can never change the result of the program! It can make it faster, it can make it slower, it can make it use more memory, but it cannot change its result. This makes it way easier to experiment with parallelism to find just the right amount of parallelism and the right size of chunks.

Answer 2

Lets first look at why procedural programming is so bad at concurrent threads.

With a concurrent programming model, you are writing sequential instructions that (by default) expect to be run in isolation. When you introduce multiple threads, you need to explicitly control access to prevent concurrent access to a shared variable when those changes may affect each other. This is difficult programming to get right, and in testing, it is impossible to prove that it has been done safely. At best, you can only confirm that on this test run, no observable issues occurred.

In functional programming, the problem is different. There is no shared data. There is no concurrent access to the same variable. Indeed, you can only set a variable once, there are no "for loops", there are just blocks of code that when executed with a given set of values will always perform the same outcome. This makes testing both predictable and a good indicator of correctness.

The problem the developer has to solve in functional programming is how to design the solution minimising common state. When the design problem requires high levels of concurrency and minimal shared state, functional implementations are a very effective strategy.

Answer 3

Minimised shared state

What is it about functional programming that makes it inherently adapted to parallel execution?

The pure nature of the functions (referential transparency), i.e. having no side effects, leads to fewer shared objects and hence less shared state.

A simple example is;

double CircleCircumference(double radius)
{
  return 2 * 3.14 * radius; // constants for illustration
}

The output is solely dependent on the input, there is no state that is included; in contrast to a function such as GetNextStep(); where the output is dependent on what the current step is (typically held as a data member of an object).

It is the shared state that needs access to be controlled via mutexes and locks. Having stronger guarantees about shared state allows for better parallel optimisations and better parallel composition.

---

Referential Transparency and pure expressions

More detail on what referential transparency is can be found here on Programmers.SE.

[It] means that you can replace any expression in the program with the result of evaluating that expression (or vice versa) without changing the meaning of the program. Jörg W Mittag

Which in turn allows pure expressions that are used to construct pure functions - functions that evaluate to the same result given the same input arguments. Each expression can thus be evaluated in parallel.

Answer 4

Pure functional code is thread-safe by default.

That, by itself, is already a huge win. In other programming languages, designing blocks of code that are completely thread-safe can be really, really challenging. But a pure functional language forces you to make everything thread-safe, except in the few places where you explicitly do something that's not thread-safe. You could say that in imperative code, being thread-safe is explicit [and hence typically rare], whereas in pure functional code, thread-unsafe is explicit [and hence typically rare].

In an imperative language, most of the problem is how to add enough locking to prevent weird data races, but not too much to kill performance or provoke random deadlocks. In a pure functional language, most of the time such considerations are moot. The problem now is "only" figuring out how to divide the work up evenly.

At one extreme, you have a tiny number of parallel tasks which don't use all available cores. At the other extreme, you have billions of tiny tasks which introduce so much overhead that everything slows to a crawl. Of course, trying to figure out "how much work" a particular function call does is often very difficult indeed.

All of these problems exist in imperative code as well; it's just that the imperative programmers are usually too busy wrestling with just trying to make the thing work at all to worry about delicate fine-tuning of task sizes.

Answer 5

The hardest part of writing parallel code is to stop one thread from reading data that is being updated by anther thread.

A common solution to this is to use immutable objects, so that once an object is created it is never updated. But in real life data has to be change, therefore “persistence” data is used, where every update returns a new object – this can be make efficient by careful choose of data structures.

As functional programming does not allow any side effects, “persistence objects” are normally used when doing functional programming. So the pain a functional programmer is forced to take due to the lack of side effects, leads to a solution that works well for parallel programming.

An additional benefit being that functional language systems check that you are keeping to the rules, and have lots of tools to help you do so.