Concurrent Haskell

Concurrent HaskellextendsHaskell 98with explicitconcurrency.Its two main underlying concepts are:

• A primitive typeMVar αimplementing a bounded/single-placeasynchronous channel,which is either empty or holds a value of typeα.
• The ability to spawn a concurrentthreadvia theforkIOprimitive.

Built atop this is a collection of useful concurrency and synchronisation abstractionssuch asunbounded channels,semaphoresand sample variables.

Haskell threads have very low overhead: creation, context-switching and scheduling are all internal to the Haskell runtime. These Haskell-level threads are mapped onto a configurable number of OS-level threads, usually one perprocessor core.

Software Transactional Memory

Thesoftware transactional memory(STM) extensiontoGHCreuses the process forking primitives of Concurrent Haskell. STM however:

• avoidsMVars in favour ofTVars.
• introduces theretryandorElseprimitives, allowing alternativeatomic actionsto becomposedtogether.

STM monad

The STMmonadis an implementation of software transactional memory in Haskell. It is implemented in GHC, and allows for mutable variables to be modified intransactions.

Traditional approach

Consider a banking application as an example, and a transaction in it—the transfer function, which takes money from one account, and puts it into another account. In the IO monad, this might look like:

typeAccount=IORefInteger

transfer::Integer->Account->Account->IO()
transferamountfromto=do
fromVal<-readIOReffrom-- (A)
toVal<-readIORefto
writeIOReffrom(fromVal-amount)
writeIORefto(toVal+amount)

This causes problems in concurrent situations where multiple transfers might be taking place on thesameaccount at thesametime. If there were two transfers transferring money from accountfrom,and both calls to transfer ran line(A)before either of them had written their new values, it is possible that money would be put into the other two accounts, with only one of the amounts being transferred being removed from accountfrom,thus creating arace condition.This would leave the banking application in an inconsistent state.

A traditional solution to such a problem is locking. For instance, locks can be placed around modifications to an account to ensure that credits and debits occur atomically. In Haskell, locking is accomplished with MVars:

typeAccount=MVarInteger

credit::Integer->Account->IO()
creditamountaccount=do
current<-takeMVaraccount
putMVaraccount(current+amount)

debit::Integer->Account->IO()
debitamountaccount=do
current<-takeMVaraccount
putMVaraccount(current-amount)

Using such procedures will ensure that money will never be lost or gained due to improper interleaving of reads and writes to any individual account. However, if one tries to compose them together to create a procedure like transfer:

transfer::Integer->Account->Account->IO()
transferamountfromto=do
debitamountfrom
creditamountto

a race condition still exists: the first account may be debited, then execution of the thread may be suspended, leaving the accounts as a whole in an inconsistent state. Thus, additional locks must be added to ensure correctness of composite operations, and in the worst case, one might need to simply lock all accounts regardless of how many are used in a given operation.

Atomic transactions

To avoid this, one can use the STM monad, which allows one to write atomic transactions. This means that all operations inside the transaction fully complete, without any other threads modifying the variables that our transaction is using, or it fails, and the state is rolled back to where it was before the transaction was begun. In short, atomic transactions either complete fully, or it is as if they were never run at all. The lock-based code above translates in a relatively straightforward way:

typeAccount=TVarInteger

credit::Integer->Account->STM()
creditamountaccount=do
current<-readTVaraccount
writeTVaraccount(current+amount)

debit::Integer->Account->STM()
debitamountaccount=do
current<-readTVaraccount
writeTVaraccount(current-amount)

transfer::Integer->Account->Account->STM()
transferamountfromto=do
debitamountfrom
creditamountto

The return types ofSTM ()may be taken to indicate that we are composing scripts for transactions. When the time comes to actually execute such a transaction, a functionatomically:: STM a -> IO ais used. The above implementation will make sure that no other transactions interfere with the variables it is using (from and to) while it is executing, allowing the developer to be sure that race conditions like that above are not encountered. More improvements can be made to make sure that some other "business logic"is maintained in the system, i.e. that the transaction should not try to take money from an account until there is enough money in it:

transfer::Integer->Account->Account->STM()
transferamountfromto=do
fromVal<-readTVarfrom
if(fromVal-amount)>=0
thendo
debitamountfrom
creditamountto
elseretry

Here theretryfunction has been used, which will roll back a transaction, and try it again. Retrying in STM is smart in that it won't try to run the transaction again until one of the variables it references during the transaction has been modified by some other transactional code. This makes the STM monad quite efficient.

An example program using the transfer function might look like this:

moduleMainwhere

importControl.Concurrent(forkIO)
importControl.Concurrent.STM
importControl.Monad(forever)
importSystem.Exit(exitSuccess)

typeAccount=TVarInteger

main=do
bob<-newAccount10000
jill<-newAccount4000
repeatIO2000$forkIO$atomically$transfer1bobjill
forever$do
bobBalance<-atomically$readTVarbob
jillBalance<-atomically$readTVarjill
putStrLn("Bob's balance:"++showbobBalance++",Jill's balance:"++showjillBalance)
ifbobBalance==8000
thenexitSuccess
elseputStrLn"Trying again."

repeatIO::Integer->IOa->IOa
repeatIO1m=m
repeatIOnm=m>>repeatIO(n-1)m

newAccount::Integer->IOAccount
newAccountamount=newTVarIOamount

transfer::Integer->Account->Account->STM()
transferamountfromto=do
fromVal<-readTVarfrom
if(fromVal-amount)>=0
thendo
debitamountfrom
creditamountto
elseretry

credit::Integer->Account->STM()
creditamountaccount=do
current<-readTVaraccount
writeTVaraccount(current+amount)

debit::Integer->Account->STM()
debitamountaccount=do
current<-readTVaraccount
writeTVaraccount(current-amount)

which should print out "Bob's balance: 8000, Jill's balance: 6000". Here theatomicallyfunction has been used to run STM actions in the IO monad.