A concurrency monad based on constructor primitives: or, being first-class is not enough

Abstract

A monad is presented which is suitable for writing concurrent programs in a purely functional programming language. In contrast to, for instance, the IO monad [Launchbury, Peyton Jones 94], the primitives added to the functional language are not represented as built-in functions operating on the monad, but rather by Perry-style constructors [Perry 90] of a distinguished algebraic data type. Therefore, monadic expressions representing concurrent computations are not only first-class objects of the language; in addition, they may even be decomposed. A number of examples show that decomposability of concurrent code is crucial for the purely functional construction of more powerful concurrency abstractions like rendezvous, remote procedure call, and critical regions from the primitives. The paper argues that this technique helps to remedy a recurrent dilemma in the design of concurrent programming languages, namely, how to keep the language small, coherent, and rigorously defined, yet to provide the programmer with all the communication constructs required. It is suggested that functional languages are not only capable of describing concurrent programs, but that in terms.