Are functional languages inherently more parallelizable than their OO or imperative cousins?

Question

I've been reading and thinking a fair bit about this. The buzz seems to be that in the multi-core future, functional languages will become more popular. I'm a relative noob to functional programming. My only exposure was academic, and nothing complicated enough to really put this class of language through its paces.

So, as I understand it, pure functions can be easily and transparently parallelized. This is a great feature, since it means no hassles with writing threading code. However, it doesn't appear to give much help with serial code.

Example:

fooN( ... (foo3(foo2(foo1(0)))))

Serial calls like this seem to be a common and sometimes unavoidable issue. To me these are at the root of why parallelization is so difficult. Some tasks simply are (or appear to be) highly serial. Does having a "functional mindset" allow you to better decompose some seemingly serial tasks? Do any existing functional languages offer transparent mechanisms for better parallelizing highly serial code? Finally, are functional languages inherently more parallelizable than OO or imperative languages, and why?

Answer 1

Functional languages are more parallelizable than imperative and OO languages because of pure functions. However, you're absolutely right, if you have these kinds of data dependencies, you can't parallelize it. The main value of functional programming is making the parallelism that is present in your code easier to spot and reason about because only data dependencies, not shared mutable state, can get in the way.

In fact, because most mere mortal programmers have difficulty working in purely functional languages, and because the Draconian policy of completely disallowing mutable state can be inefficient, there's been some buzz about the idea of allowing individual function bodies to be written imperatively, but disallowing side effects across functions. In other words, all functions that are to be parallelized would have to be pure. Then, you could have mutable state for local variables to make the code easier to write and more efficient, but still allow safe, easy automatic parallelization of calls to these pure functions. This is being explored in, for example, the 2.0 branch of the D language.

Answer 2

It is mainly about side effects. If the compiler knows that some pieces of the code has no side effects, it can optimize based on the code structure to run some of those in parallel.

Consider linq on C# / which is semi-functional:

var someValues = from c in someArray
                where // some  comparisson with no side effects
                select c;

You are specifying the intention of what you want to do, if the compiler knew each piece of the expression has no side effects, it could safely assign different parts of the array to process on different cores. Actually there is a .AsParalell that will be coming on parallel linq (plinq), that will enable just that. The issue comes in that it won't be able to enforce the no side effects bit (being on a language/framework that has no support for it), which can get really ugly if the developers aren't aware. Because of that, they made it explicit, but you can see that causing trouble along the way.