On Clojure's map and pmap functions

Let $f: A \to B$ be a function then mapping $f$ over $n$-tuples is the same as applying the product function $f^n$. The map function is one of the simplest types of product functions: the product of a function with itself. Consequently, map is embarrassingly parallel. Its parallelism is one of the main ingredients of modern parallel programming alongside the referential transparency that comes with functional programming languages.

If a programming language has referential transparency, then its components can be computed in any order and then combined afterwards to produce a common result. This is why functional programming languages are so good at modern parallel computing, and its a large part of why they have be seen to be getting greater traction in recent times. The parallelism of reduce is essentially in this category, because the combination of associativity and referential transparency allows you to freely determine your computation order.

The map function is distinguished by the fact that it is embarassingly parallel. This means that map can be decomposed into different independent computation tasks requiring no communication between one another until they are joined at the end. The fact that map is embarassingly parallel has already been put to good use in a number of parallel computing applications, such as MapReduce libraries like Apache Hadoop.

However, while the use of parallel mapping constructs is satisfactory that doesn't mean we should stop there. It is also desirable that we should have a general mathematical structure theorem for describing when functions can be given embarassingly parallel implementations. This will capture the categorical universal properties that make embarassing parallelism possible, without regard for representation details like the use of sequences. A truly abstract mathematical description should not make reference to representations.

If we have an embarrasingly parallel computation such as the application of the map function, then we can break it down into parts using threads or multiple computers. Then when the computations are done they can be combined to produce a common result. This is what the Clojure pmap does, as it uses the Java threading API to split up a computation into parts that can be run on as many processors as possible.

• The pmap function first gets the number of processors on the machine by using the static getRuntime method on java.lang.Runtime and then calling the virtual availableProcessors method on that to get the number of processors available on the JVM. The number of processors is used to determine how many threads to break the computation in to.
• Once the number of processors is determined the pmap function breaks up the computation of the map into separate threads using Clojure futures. These take a computation and run it on another thread without blocking, and then they cache the result so that it can be accessed later by dereferences.
• Finally, the computation of the parallel map is computed semi-lazily by using the lazy-sequence function. It computes an appropriate chunk of the sequence determined by the number of available processors but it doesn't compute everything unless required.

The implementation of an embarassingly parallel function like map will probably have to take a similar one to that played by Clojure's pmap: the computation will be broken up into threads handled by different processors. However, what makes this possible is a mathematical property shared not only by map but potentially by a number of other different types of functions. By understanding these structural properties, we can better understand the parallelisation of functional applications.

References:
Map (parallel pattern)