Parallel functional programming has a relatively long history. Burge was one of the first to suggest the basic technique of evaluating function arguments in parallel, with the possibility of functions absorbing unevaluated arguments and perhaps also exploiting speculative evaluation [22]. Berkling also considered the application of functional languages to parallel processing [17].
Due to the absence of side-effects in a purely functional program, it is relatively easy to partition programs so that sub-programs can be executed in parallel: any computation which is needed to produce the result of the program may be run as a separate task. There may, however, be implicit control- and data- dependencies between parallel tasks, which will limit parallelism to a greater or lesser extent.
Higher-order functions (functions which act on functions) can also introduce program-specific control structures, which may be exploited by suitable parallel implementations, such as those for algorithmic skeletons (Section 3.2).
Here is a classic divide-and-conquer program, a variant on the naive
Fibonacci program. Since the two recursive calls to nfib are
independent, they can each be executed in parallel. If this is done
naively, then the number of tasks created is the same as the result of
the program. This is an exponentially large number ().
nfib n = if n <= 1 then 1
else 1 + nfib(n-1) + nfib(n-2)