Papers and presentations about transactional memory in Haskell


Beautiful concurrency

Simon Peyton Jones. This is a chapter for the book "Beautiful code", edited by Greg Wilson, O'Reilly 2007. Abstract The free lunch is over. We have grown used to the idea that our programs will go faster when we buy a next-generation processor, but that time has passed. While that next-generation chip will have more CPUs, each individual CPU will be no faster than the previous year's model. If we want our program to run faster, we must learn to write parallel programs.

Parallel programs execute in a non-deterministic way, so they are hard to test, and bugs can be almost impossible to reproduce. If we want to write parallel programs that work reliably, we must pay particular attention to beauty. Sadly, parallel program are often less beautiful than their sequential cousins; in particular they are, as we shall see, less modular.

In this chapter I describe Software Transactional Memory (STM), a promising new approach to programming shared-memory parallel processors. Although still in its infancy, STM seems to support modular programs in a way that current technology does not. By the time we are done, I hope you will be as enthusiastic as I am about STM. It is not a solution to every problem, but it is a beautiful and inspiring attack on the daunting ramparts of concurrency.


Composable memory transactions

Tim Harris, Simon Marlow, Simon Peyton Jones, and Maurice Herlihy. ACM Conference on Principles and Practice of Parallel Programming 2005 (PPoPP'05). Abstract. Writing concurrent programs is notoriously difficult, and is of increasing practical importance. A particular source of concern is that even correctly-implemented concurrency abstractions cannot be composed together to form larger abstractions. In this paper we present a new concurrency model, based on transactional memory, that offers far richer composition. All the usual benefits of transactional memory are present (e.g. freedom from deadlock), but in addition we describe new modular forms of blocking and choice that have been inaccessible in earlier work. We've updated the original "Composable memory transactions" paper by fixing a couple of typos in the semantics. More importantly, it also includes an Appendix that describes a more consistent semantics for exceptions; this is what we propose to implement in GHC 6.6.

Lock -Free Data Structures using STMs in Haskell

Anthony Discolo, Tim Harris, Simon Marlow, Simon Peyton Jones, and Satnam Singh. Eighth International Symposium on Functional and Logic Programming, April 2006 (FLOPS'06). Abstract. This paper explores the feasibility of re-expressing concurrent algorithms with explicit locks in terms of lock free code written using Haskell's implementation of Software Transactional Memory (STM). Preliminary experimental results are presented which show that for multi-processor systems the simpler lock free implementations offer competitive or superior performance when compared to their corresponding the lock based implementations.

Transactional memory with data invariants

Tim Harris and Simon Peyton Jones. First ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing (TRANSACT'06), 11 June 2006, Ottawa, Canada. Abstract. This paper introduces a mechanism for asserting invariants that are maintained by a program that uses atomic memory transactions. The idea is simple: a programmer writes check E where E is an expression that should be preserved by every atomic update for the remainder of the program's execution. We have extended STM Haskell to dynamically evaluate check statements atomically with the user's updates: the result is that we can identify precisely which update is the first one to break an invariant.