Parallel Functional Languages (idea)

Functional programming languages have several key features that make them attractive for use in parallel computing, such as the absence of deadlock and race conditions. Because of the side-effect free nature of purely functional languages, they possess a certain inherent parallelism. Take for example a function:

f(g(x), h(x))

In normal imperative languages, h(x) and g(x) may change the values of non-locals, or change the value of x itself, making the order of evaluation important. However, in a purely functional language, once a variable is bound, it's value never changes. Thus, h(x) and g(x) can be computed in parallel, and the result of the operation will remain the same regardless of the order of their execution.

Many functional languages also take advantage of parallelism through the use of skeletons, which map certain patterns of computation with a template for parallelization. For example, most functional languages have a map construct that allows for applying a function over every element of a list, returning another list:

map(square, {1, 2, 3, ... 10})

In this case, the first parameter the function map takes is square which is a function that returns the square of a number. The second parameter is a list of numbers each element of which will be squared. The return value is then {1, 4, 9, ... 100}. Clearly, the map function can be implemented in parallel by the compiler. A function composed of multiple map calls can be associated with a pipelined template.

The data parallelism in the map function can be thought of as similar to vector operations in High Performance Fortran, but the functional equivalent can be more powerful, as arbitrary functions can be applied.

The side-effect free nature of functional languages also have other advantages, such as allowing for easy analysis of dependencies, since communication between processes only exist in the functional parameters; and deadlock freedom, since there can be no contention for access to a sahred variable.

Thus, "sequential" functional languages in themselves have implicit or semi-implicit parallelism. However, there are several functional languages designed for parallelism, such as Sisal, and pH. Many parallel functional languages allow for explicit control of parallelism using directives.