Beautiful Code [272]
Using a well-known example allows you to directly compare my solution with well-described solutions in other languages. In particular, Trono's paper gives a semaphore-based solution that is partially correct. Ben-Ari gives a solution in Ada95 and in Ada.[§§§] Benton gives a solution in Polyphonic C#.[||||||]
[§§§] Nick Benton, "Jingle bells: Solving the Santa Claus problem in Polyphonic C#," Technical report, Microsoft Research, 2003.
[||||||] Mordechai Ben-Ari, "How to solve the Santa Claus problem," Concurrency: Practice and Experience, Vol. 10, No. 6, pp. 485–496, 1998.
24.3.1. Reindeer and Elves
The basic idea of the STM Haskell implementation is this. Santa makes one "Group" for the elves and one for the reindeer. Each elf (or reindeer) tries to join its Group. If it succeeds, it gets two "Gates" in return. The first Gate allows Santa to control when the elf can enter the study and also lets Santa know when they are all inside. Similarly, the second Gate controls the elves leaving the study. Santa, for his part, waits for either of his two Groups to be ready, and then uses that Group's Gates to marshal his helpers (elves or reindeer) through their task. Thus the helpers spend their lives in an infinite loop: try to join a group, move through the gates under Santa's control, and then delay for a random interval before trying to join a group again.
Rendering this informal description in Haskell gives the following code for an elf:[###]
[###] I have given this function a suffix 1 because it deals with only one iteration of the elf, whereas in reality the elves rejoin the fun when they are done with their task. We will define elf in the section "The Main Program."
elf1 :: Group -> Int -> IO ( )
elf1 group elf_id = do { (in_gate, out_gate) <- joinGroup group
; passGate in_gate
; meetInStudy elf_id
; passGate out_gate }
The elf is passed its Group and an Int that specifies its elfin identity. This identity is used only in the call to meetInStudy, which simply prints out a message to say what is happening:[****]
[****] The function putStr is a library function that calls hPutStr stdout.
meetInStudy :: Int -> IO ( )
meetInStudy id = putStr ("Elf " ++ show id ++ " meeting in the study\n")
The elf calls joinGroup to join its group and passGate to pass through each of the gates:
joinGroup :: Group -> IO (Gate, Gate)
passGate :: Gate -> IO ( )
The code for reindeer is identical, except that reindeer deliver toys rather than meet in the study:
deliverToys :: Int -> IO ( )
deliverToys id = putStr ("Reindeer " ++ show id ++ " delivering toys\n")
Because IO actions are first-class, we can abstract over the common pattern, like this:
helper1 :: Group -> IO () -> IO ( )
helper1 group do_task = do { (in_gate, out_gate) <- joinGroup group
; passGate in_gate
; do_task
; passGate out_gate }
The second argument of helper1 is an IO action that is the helper's task, which the helper performs between the two passGate calls. Now we can specialize helper1 to be either an elf or a reindeer:
elf1, reindeer1 :: Group -> Int -> IO ( )
elf1 gp id = helper1 gp (meetInStudy id)
reindeer1 gp id = helper1 gp (deliverToys id)
24.3.2. Gates and Groups
The first abstraction is a Gate, which supports the following interface:
newGate :: Int -> STM Gate
passGate :: Gate -> IO ( )
operateGate :: Gate -> IO ( )
A Gate has a fixed capacity, n, which we specify when we make a new Gate, and a mutable remaining capacity. This remaining capacity is decremented whenever a helper calls passGate to go through the gate; if the remaining capacity is zero, passGate blocks. A Gate is created with zero remaining capacity, so that no helpers can pass through it. Santa opens the gate with operateGate, which sets its remaining capacity back to n.
Here, then, is a possible