Beautiful Code [271]
retry :: STM a
Here is a modified version of withdraw that blocks if the balance would go negative:
limitedWithdraw :: Account -> Int -> STM ( )
limitedWithdraw acc amount
= do { bal <- readTVar acc
; if amount > 0 && amount > bal
then retry
else writeTVar acc (bal - amount) }
The semantics of retry are simple: if a retry action is performed, the current transaction is abandoned and retried at some later time. It would be correct to retry the transaction immediately, but it would also be inefficient: the state of the account will probably be unchanged, so the transaction will again hit the retry. An efficient implementation would instead block the thread until some other thread writes to acc. How does the implementation know to wait on acc? Because the transaction reads acc on the way to the retry, and that fact is conveniently recorded in the transaction log.
The conditional in limitedWithdraw has a very common pattern: check that a Boolean condition is satisfied and, if not, retry. This pattern is easy to abstract as a function, check:
check :: Bool -> STM ( )
check True = return ( )
check False = retry
Now, we can use check to re-express limitedWithdraw a little more neatly:
limitedWithdraw :: Account -> Int -> STM ( )
limitedWithdraw acc amount
= do { bal <- readTVar acc
; check (amount <= 0 || amount <= bal)
; writeTVar acc (bal - amount) }
We now turn our attention to choice. Suppose you want to withdraw money from account A if it has enough money, but if not then withdraw it from account B? For that, we need the ability to choose an alternative action if the first one retries. To support choice, STM Haskell has one further primitive action, called orElse, whose type is:
orElse :: STM a -> STM a -> STM a
Like atomically, orElse takes actions as its arguments, and glues them together to make a bigger action. Its semantics are as follows. The action (orElse a1 a2) first performs a1. If a1 retries (i.e., calls retry), it tries a2 instead. If a2 also retries, the whole action retries. It may be easier to see how orElse is used:
limitedWithdraw2 :: Account -> Account -> Int -> STM ( )
-- (limitedWithdraw2 acc1 acc2 amt) withdraws amt from acc1,
-- if acc1 has enough money, otherwise from acc2.
-- If neither has enough, it retries.
limitedWithdraw2 acc1 acc2 amt
= orElse (limitedWithdraw acc1 amt) (limitedWithdraw acc2 amt)
Because the result of orElse is itself an STM action, you can feed it to another call to orElse and so choose among an arbitrary number of alternatives.
24.2.5. Summary of Basic STM Operations
In this section, I have introduced all the key transactional memory operations supported by STM Haskell. They are summarized in Table 24-1. This table includes one operation that has not so far arisen: newTVar is the way in which you can create new TVar cells, and we will use it in the following section.
Table 24-1. The key operations of STM Haskell
Operation Type signature
atomically STM a -> IO a
retry STM a
orElse STM a -> STM a -> STM a
newTVar a -> STM (TVar a)
readTVar TVar a -> STM a
writeTVar TVar a -> a -> STM ( )
Beautiful Concurrency > The Santa Claus Problem
24.3. The Santa Claus Problem
I want to show you a complete, runnable concurrent program using STM. A well-known example is the so-called Santa Claus problem,[] originally attributed to Trono:[]
[] My choice was influenced by the fact that I am writing these words on December 22.
[] J. A. Trono, "A new exercise in concurrency," SIGCSE Bulletin, Vol. 26, pp. 8–10, 1994.
Santa repeatedly sleeps until wakened by either all of his nine reindeer, back from their holidays, or by a group of three of his ten elves. If awakened by the reindeer, he harnesses each of them to his sleigh, delivers toys with them and finally unharnesses them (allowing them to go off on holiday). If awakened by a group of elves, he shows each of the group into his study,