A Concurrent ML Library in Concurrent Haskell

Avik Chaudhuri

Abstract
In Concurrent ML, synchronization abstractions can be defined and passed as values, much like functions in ML. This mechanism admits a powerful, modular style of concurrent programming, called higher-order concurrent programming. Unfortunately, it is not clear whether this style of programming is possible in languages such as Concurrent Haskell, that support only first-order message passing. Indeed, the implementation of synchronization abstractions in Concurrent ML relies on fairly low-level, language-specific details.

In this paper we show, constructively, that synchronization abstractions can be supported in a language that supports only first-order message passing. Specifically, we implement a library that makes Concurrent ML-style programming possible in Concurrent Haskell. We begin with a core, formal implementation of synchronization abstractions in the π-calculus. Then, we extend this implementation to encode all of Concurrent ML's concurrency primitives (and more!) in Concurrent Haskell.

Our implementation is surprisingly efficient, even without possible optimizations. Preliminary experiments suggest that our library can consistently outperform OCaml's standard library of Concurrent ML-style primitives.

At the heart of our implementation is a new distributed synchronization protocol that we prove correct. Unlike several previous translations of synchronization abstractions in concurrent languages, we remain faithful to the standard semantics for Concurrent ML's concurrency primitives. For example, we retain the symmetry of choose, which can express selective communication. As a corollary, we establish that implementing selective communication on distributed machines is no harder than implementing first-order message passing on such machines.

PDF

BibTeX
@inproceedings{cmllch-C09,
    author = {Avik Chaudhuri},
    title = {A Concurrent ML Library in Concurrent Haskell},
    booktitle = {Proceedings of the 14th ACM
                 International Conference on Functional Programming (ICFP'09)},
    year = {2009},
    pages = {269--280},
    publisher = {ACM}
}

Code
 Download Haskell
 An implementation of Concurrent ML events in Haskell
 An extended implementation with guarded communication

The extended implementation is also available with documentation off HackageDB, at Control.Concurrent.CML in the module hierarchy.
The source code can be downloaded as a Cabal source package kindly maintained by Benjamin Franksen. See also http://code.haskell.org/cml/.

Evaluation
 Benchmarks
    in Haskell (compiled using ghc 6.8.1)
    in OCaml (compiled using ocamlopt 3.10.2)

A longer version of this paper, containing proofs and other details, is available as an arXiv e-print.