Composable Memory Transactions

This paper describes a technique for creating composable transactions, based in Haskell. It's an extremely elegant approach, for reasons which are completely unrelated to the fact that it's written in Haskell. Haskell merely allows them to give a static guarantee (via the type system) that the transaction system isn't perverted by the inclusion of non-transactional code.

You may think that "composable memory transactions" are not something that you have ever felt a need for, and therefore this paper is irrelevant to your life. However what the paper is really about is synchronization primitives for multithreaded code -- a topic that I have to deal with all the time. It just so happens that their proposed synchronization primitive has lots of other uses as well.

The authors point out that blocking within a transaction is not composable (due to the potential for deadlocks when other threads wait for locks that the transaction has already aquired), and that if you attempt to avoid blocking by introducing guards on transactions, then that also prevents composability. So instead of allowing blocking, they introduce a "retry" function which aborts the transaction and then schedules it for later execution. As an optimization, they put off rescheduling the transaction until at least one of the variables referenced before the retry has changed. In this way, they have the effect of blocking the calling thread, without locking the transactional store.

In the context of Haskell, the authors simply make retry into a function which returns a special value, which takes priority over any other values it is composed with. This is relatively elegant in the context of Monads, however I think the same effect could achieved in an imperative language by making retry throw a RetryException -- so the technique is not limited to functional programming. On the other hand, imperative languages make it so easy to modify global state that it may probably be difficult to apply the technique reliably to such languages.

(Via Lambda the Ultimate)