Item get () { atomic (n_items > 0) {... remove item ...}

}

 

The thread waits until the guard (n_items > 0) holds, before executing the block. But how could we take two consecutive items? We cannot call get(); get(), because another thread might perform an intervening get. We could try wrapping two calls to get in a nested atomic block, but the semantics of this are unclear unless the outer block checks there are two items in the buffer. This is a disaster for abstraction, because the client (who wants to get the two items) has to know about the internal details of the implementation. If several separate abstractions are involved, matters are even worse.

Thirdly, no previous transactional memory supports choice, exemplified by the select example mentioned earlier.

We tackle all three issues by presenting transactional memory in the context of the declarative language Concurrent Haskell, which we briefly review next.

2. 2. concurrent haskell

Concurrent Haskell²⁰ is an extension to Haskell 98, a pure, lazy, functional language. It provides explicitly forked threads, and abstractions for communicating between them. This naturally involves side effects and so, given the lazy evaluation strategy, it is necessary to be able to control exactly when they occur. The big breakthrough came from a mechanism called monads. ²¹

Here is the key idea: a value of type IO a is an I/O action that, when performed, may do some I/O before yielding a value of type a. For example, the functions putChar and getChar have types:

putChar :: Char -> IO () getChar :: IO Char

That is, putChar takes a Char and delivers an I/O action that, when performed, prints the character on the standard output; while getChar is an action that, when performed, reads a character from the console and delivers it as the result of the action. A complete program must define an I/O action called main; executing the program means performing that action. For example:

main :: IO () main = putChar ’x’

I/O actions can be glued together by a monadic bind combinator. This is normally used through some syntactic sugar, allowing a C-like syntax. Here, for example, is a complete program that reads a character and then prints it twice:

main = do {c <- getChar; putChar c; putChar c}

As well as performing external input/output, I/O actions include operations with side effects on mutable cells. A value of type IORef a is a mutable storage cell which can hold values of type a, and is manipulated (only) through the following interface:

newIORef :: a -> IO (IORef a) readIORef :: IORef a -> IO a writeIORef :: IORef a -> a -> IO ()

newIORef takes a value of type a and creates a mutable storage location holding that value. readIORef takes a reference to such a location and returns the value that it contains. writeIORef provides the corresponding update operation. Since these cells can only be created, read, and written using operations in the IO monad, there is a type-secure guarantee that ordinary functions are unaffected by state—for example, a pure function sin cannot read or write an IORef because sin has type Float -> Float.

Concurrent Haskell supports threads, each independently performing input/output. Threads are created using a function forkIO:

forkIO :: IO a -> IO ThreadId

forkIO takes an I/O action as its argument, spawns a fresh thread to perform that action, and immediately returns its thread identifier to the caller. For example, here is a program that forks a thread that prints ‘x’, while the main thread goes on to print ‘y’:

main = do {forkIO (print ’x’); print ’y’}

Peyton Jones provides a fuller introduction to concurrency, I/O, exceptions and cross-language interfacing (the “awkward squad” for pure, lazy, functional programming), ¹⁸ and Daume III provides a general online tutorial to Haskell. ⁶

3. comPosaBLe tRansactions

We are now ready to present the key ideas of the paper. Our starting point is this: a purely declarative language is a perfect setting for transactional memory, for two reasons. First, the type system explicitly separates computations which may have side effects from effect-free ones. As we shall see, it is easy to refine it so that transactions can perform memory effects but not irrevocable input/output effects. Second, reads from and writes to mutable cells are explicit, and relatively rare: most computation takes place in the purely functional world. These functional computations perform many, many memory operations—allocation, update of thunks, stack operations, and so on—but none of these need to be tracked by the STM, because they are pure and never need to be rolled back. Only the relatively rare explicit operations need be logged, so a software implementation is entirely appropriate.