ICFP 2009 - A Concurrent ML Library in Concurrent Haskell

A Concurrent ML Library in Concurrent Haskell

Avik Chaudhuri

The 14th ACM SIGPLAN International Conference on Functional Programming (ICFP 2009)
Edinburgh, Scotland, 31st August - 2nd September 2009

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 \emph{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 $\pi$-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 {\tt 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.

START Conference Manager (V2.56.8 - Rev. 748M)