[Haskell-cafe] Lock-Free Data Structures using STMs in Haskell

Pete Kazmier pete-expires-20080608 at kazmier.com
Wed Apr 9 09:50:27 EDT 2008

I recently read the STM paper on lock-free data structures [1] which I
found very informative in my quest to learn how to use STM.  However,
there are a few things I do not fully understand and was hoping
someone might be able to explain further.

In the STM version of the ArrayBlockingQueue, the following type is

  data ArrayBlockingQueueSTM e = ArrayBlockingQueueSTM {
    shead :: TVar Int,
    stail :: TVar Int,
    sused :: TVar Int,
    slen :: Int,
    sa :: Array Int (TVar e)

It's unclear to me why the Array's elements must be wrapped in TVars.
Why aren't the TVars on shead, stail, and sused sufficient?  Here is
the only function that reads from the queue:

  readHeadElementSTM :: ArrayBlockingQueueSTM e
                        -> Bool -> Bool -> STM (Maybe e)
  readHeadElementSTM abq remove block
    = do u <- readTVar (sused abq)
         if u == 0
            then if block
                    then retry
                    else return Nothing
            else do h <- readTVar (ihead abq)
                 let tv = sa abq ! h
                 -- Why are the array elements wrapped in TVars?
                 e <- readTVar tv
                 if remove
                    then do
                      let len = slen abq
                      let newh = h `mod` len
                      writeTVar (shead abq) $! newh
                      writeTVar (sused abq) $! (u-1)
                    else return ()
                 return (Just e)

It is not immediately obvious to me why the elements need to be
wrapped in TVars.  Could someone help elaborate?

The other question is in regards to section 2 where STM is
introduced.  The authors define the following:

  decT :: TVar Int -> IO ()
  decT v = atomically (do x <- readTVar v
                          if x == 0
                             then retry
                             else return ()
                          writeTVar v (x-1))

And then go on to show how easy it is to compose STM types with this

  decPair v1 v1 :: TVar Int -> TVar Int -> IO ()
  decPair v1 v2 = atomically (decT v1 `orElse` decT v2)

Will this actually compile?  I was under the impression that 'orElse'
could only combine STM types, not IO () types.  

Thank you,

[1] Anthony Discolo, Tim Harris, Simon Marlow, Simon Peyton Jones, and
Satnam Singh. Lock-free data structures using STMs in Haskell. In
Eighth International Symposium on Functional and Logic Programming
(FLOPS.06), April 2006.

More information about the Haskell-Cafe mailing list