Implicit and explicit parallel programming in Haskell

Implicit and explicit parallel programming in Haskell

Mark P. Jones and Paul Hudak, Research Report YALEU/DCS/RR-982, Yale University, New Haven, Connecticut, USA, August 1993.


It has often been suggested that functional languages provide an excellent basis for programming parallel computer systems. This is largely a result of the lack of side effects which makes it possible to evaluate the subexpressions of a given term without any risk of interference.

On the other hand, the lack of side-effects has also been seen as one of the biggest weaknesses of functional languages since it rules out many features of traditional imperative languages such as state, I/O and exceptions. These ideas can be simulated in a functional language but the resulting programs are often unnatural and inefficient. On the bright side, recent work has shown how many of these ideas can be naturally incorporated into a functional language without compromising efficiency by expressing computations in terms of monads or continuations. Unfortunately, the ``single-threading'' implied by these techniques often destroys many opportunities for parallel computation.

In this paper, we describe a small extension to the Haskell I/O monad to allow a form of explicit high-level concurrency. It is a simple matter to incorporate these features in a sequential implementation, and genuine parallelism can be obtained on a parallel machine. In addition, the inclusion of constructs for explicit concurrency enhances the use of Haskell as an executable specification language, since some programs are most naturally described as a composition of parallel processes.

(Supported in part by ARPA, via a subcontract to Intermetrics, Inc.)

Available by http in pdf, PostScript, or gzipped dvi.