How does Software Transactional Memory (STM) work in Haskell? Provide an example.?

Software Transactional Memory (STM) is a concurrency control mechanism that simplifies concurrent programming by allowing multiple shared-memory transactions to be executed concurrently. In Haskell, STM is implemented as a monad (‘STM‘) with mutable references called Transactional Variables (‘TVar‘). The ‘TVar‘ values can be read and modified within an ‘STM‘ transaction.

STM allows multiple transactions to be composed easily without the need for locks, semaphores, or condition variables. The ‘STM‘ system ensures that transactions appear to have been executed atomically; if any conflicts are detected between transactions, the conflicting transactions will be retried.

Consider the following basic example of transferring money between two bank accounts, traditionally implemented with locks:

data Account = Account (MVar Int)

transfer :: Int -> Account -> Account -> IO ()
transfer amount from to = do
    modifyMVar_ (unAccount from) (return . subtract amount)
    modifyMVar_ (unAccount to) (return . (+ amount))

Here, the account has an integer balance, which is stored in an ‘MVar‘. The ‘transfer‘ function takes an integer amount and two accounts as arguments and modifies their balances using ‘modifyMVar_‘ that handles locks. This implementation could result in deadlocks.

Using STM, the implementation is simplified, and deadlock-free:

import Control.Concurrent.STM

data Account = Account (TVar Int)

transferSTM :: Int -> Account -> Account -> STM ()
transferSTM amount (Account from) (Account to) = do
    fromBalance <- readTVar from
    writeTVar from (fromBalance - amount)
    toBalance <- readTVar to
    writeTVar to (toBalance + amount)

transfer :: Int -> Account -> Account -> IO ()
transfer amount from to = atomically (transferSTM amount from to)

In the STM version, the ‘Account‘ holds a ‘TVar Int‘ instead of an ‘MVar Int‘. The ‘transferSTM‘ function is now within the ‘STM‘ monad context. Inside the ‘transferSTM‘ transaction, we read account balances using ‘readTVar‘, modify them, and write back the result using ‘writeTVar‘. Finally, the ‘transfer‘ function wraps the transaction with the ‘atomically‘ function to execute it.

Here’s a more detailed explanation of the main components of the STM library:

1. ‘TVar‘: Transactional variables are references to shared memory locations, with support for concurrent access.

2. ‘STM‘: The monad for STM transactions. ‘STM‘ actions can be composed using standard monadic operations, such as ‘>>=‘ and ‘return‘.

3. ‘atomically‘: This function takes an ‘STM‘ action and runs it as an atomic transaction.

4. ‘readTVar‘ and ‘writeTVar‘: These functions allow reading and writing ‘TVar‘ in transaction context. There are also combinators like ‘modifyTVar‘ and ‘modifyTVar’‘ that can be used to modify the value of a ‘TVar‘ directly.

5. ‘retry‘: When a transaction can’t continue due to other concurrent transactions, it can be retried by calling ‘retry‘. STM will roll back and re-execute the transaction when one of the accessed ‘TVar‘ changes.

6. ‘orElse‘: This function allows for composing alternative transactions. If a transaction calls ‘retry‘, it will try another alternative specified by ‘orElse‘.

Let’s extend the previous example with a conditional transfer, where the transaction only proceeds if the source account has sufficient balance:

transferIfEnough :: Int -> Account -> Account -> STM ()
transferIfEnough amount (Account from) (Account to) = do
    fromBalance <- readTVar from
    if fromBalance >= amount
        then do
            writeTVar from (fromBalance - amount)
            toBalance <- readTVar to
            writeTVar to (toBalance + amount)
        else retry

transfer :: Int -> Account -> Account -> IO ()
transfer amount from to = atomically (transferIfEnough amount from to)

Here, ‘transferIfEnough‘ checks if the source account has enough balance. If not, it will ‘retry‘ the transaction, and the STM system will re-execute it when the ‘from‘ account balance changes, ensuring a consistent atomic operation.