Cheap (But Functional) Threads

William L. Harrison and Adam Procter. Accepted for publication in Higher-Order and Symbolic Computation.

Abstract. This article demonstrates how a powerful and expressive abstraction from concurrency theory plays a dual rôle as a programming tool for concurrent applications and as a foundation for their verification. This abstraction—monads of resumptions expressed using monad transformers—is cheap: it is easy to understand, easy to implement, and easy to reason about. We illustrate the expressiveness of the resumption monad with the construction of an exemplary multitasking operating system kernel with process forking, preemption, message passing, and synchronization constructs in the pure functional programming language Haskell.