Editing Software transactional memory (section)

== Composable operations ==
In 2005, Tim Harris, [[Simon Marlow]], [[Simon Peyton Jones]], and [[Maurice Herlihy]] described an STM system built on [[Concurrent Haskell]] that enables arbitrary [[Linearizability|atomic operations]] to be composed into larger atomic operations, a useful concept impossible with lock-based programming. To quote the authors:

<blockquote>
Perhaps the most fundamental objection [...] is that ''lock-based programs do not compose'': correct fragments may fail when combined. For example, consider a hash table with thread-safe insert and delete operations. Now suppose that we want to delete one item A from table t1, and insert it into table t2; but the intermediate state (in which neither table contains the item) must not be visible to other threads. Unless the implementor of the hash table anticipates this need, there is simply no way to satisfy this requirement. [...] In short, operations that are individually correct (insert, delete) cannot be composed into larger correct operations.<br/>
&mdash;Tim Harris et al., "Composable Memory Transactions", Section 2: Background, pg.2<ref name="cmt">{{Cite book |last1=Harris |first1=T. |last2=Marlow |first2=S. |author2-link=Simon Marlow |last3=Peyton Jones |first3=S. |author3-link=Simon Peyton Jones |last4=Herlihy |first4=M. |author4-link=Maurice Herlihy |year=2005 |doi=10.1145/1065944.1065952 |chapter=Composable memory transactions |title=Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming - PPoPP '05 |pages=48 |chapter-url=https://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/2005-ppopp-composable.pdf |isbn=1595930809 |s2cid=53245159}}</ref>
</blockquote>

With STM, this problem is simple to solve: simply wrapping two operations in a transaction makes the combined operation atomic. The only sticking point is that it is unclear to the caller, who is unaware of the implementation details of the component methods, when it should attempt to re-execute the transaction if it fails. In response, the authors proposed a <code>retry</code> command which uses the transaction log generated by the failed transaction to determine which memory cells it read, and automatically retries the transaction when one of these cells is modified, based on the logic that the transaction will not behave differently until at least one such value is changed.

The authors also proposed a mechanism for composition of ''alternatives'', the <code>orElse</code> function. It runs one transaction and, if that transaction does a ''retry'', runs a second one. If both retry, it tries them both again as soon as a relevant change is made.{{Clarify|date=July 2011}} This facility, comparable to features such as the Portable Operating System Interface ([[POSIX]]) networking <code>select()</code> call, allows the caller to wait on any one of a number of events simultaneously. It also simplifies programming interfaces, for example by providing a simple mechanism to convert between blocking and nonblocking operations.

This scheme has been implemented in the [[Glasgow Haskell Compiler]].