A Poor Man’s Concurrency Monad
📜 Abstract
Without adding any primitives to the language, we define a concurrency monad transformer in Haskell. This allows us to add a limited form of concurrency to any existing monad. The atomic actions of the new monad are lifted actions of the underlying monad. Some extra operations, such as fork, to initiate new processes, are provided. We discuss the implementation, and use some examples to illustrate the usefulness of this construction.
✨ Summary
The paper develops a concurrency monad transformer, written entirely within Haskell and parameterized over an arbitrary underlying monad. Its central idea is to represent computations in continuation-passing style, so that a computation can be suspended by retaining its continuation and resumed later.
The transformer introduces an Action datatype with three cases: an atomic underlying-monad computation, a fork of two processes, and termination. A round-robin interpreter maintains a list of active processes, executes one atomic action at a time, places its continuation at the end of the process list, and expands forks into additional processes. Consequently, lifted operations from the underlying monad become atomic with respect to the simulated scheduler.
The construction is demonstrated with several examples. A writer monad produces interleaved output from concurrently running processes; changing the granularity of the lifted write operation changes the possible interleavings. The same mechanism can merge an infinite list of infinite lists by assigning each component list to a process. The paper also shows how mutable state can be lifted into the concurrent setting, including an MVar-like abstraction whose reads may block until a value becomes available.
The approach is intentionally limited: it simulates concurrency through cooperative interleaving rather than implementing real preemptive parallelism. An atomic action that does not terminate can prevent the entire computation from progressing, and the simple blocking implementation for shared variables uses inefficient busy-waiting. The paper reports that the technique was also applied to extend the TkGofer graphical system.
The supplied scan contains a first-page header referring to “January 1993,” but the journal record identifies the published article as a May 1999 paper in the Journal of Functional Programming. Cambridge’s bibliographic record reports 50 Crossref citations and lists later work concerning concurrent Haskell debugging, lightweight GHC concurrency primitives, Lwt, and Scala Actors among the citing publications. (doi.org) The paper has also been used directly as teaching material in a University of Pennsylvania course on Haskell concurrency, where it serves as the basis for constructing a simple concurrent monad. (seas.upenn.edu)