Solving the Santa Claus Problem in Erlang

Simon Peyton Jones has written an article about Software Transactional Memory in Haskell, to appear in a forthcoming book edited by Greg Wilson called "Beautiful code".

As someone who has been using (and teaching) Haskell since there was a Haskell 98 to use and teach, I have to say that I find Haskell a remarkably pleasant language to work in, and fully agree that it is easy to write beautiful code in Haskell. Simon Peyton Jones is an expert whose sandals I am unworthy to untie, but in this case, I am afraid that his code strikes me as, well, not at all beautiful.

He illustrates the use of Software Transactional Memory by solving the Santa Claus problem. The Santa Claus problem was reported by John A. Trono or St Michael's College, Vermont, in "A New Exercise in Concurrency", in ACM SIGCSE Bulletin, Volume 26, issue 3, pages 8-10, 1994.

Santa Claus sleeps in his shop up at the North Pole, and can only be wakened by either all nine reindeer being back from their year long vacation on the beaches of some tropical island in the South Pacific, or by some elves who are having some difficulties making the toys. One elf's problem is never serious enough to wake up Santa (otherwise he might never get any sleep), so, the elves visit Santa in a group of three. When three elves are having their problems solved, any other elves wishing to visit Santa must wait for those elves to return. If Santa wakes up to find three elves waiting at his shop's door, along with the last reindeer having come back form the tropics, Santa has decided that the elves can wait until after Christmas, because it is more important to get his sleigh ready as soon as possible. (It is assumed that the reindeer don't want to leave the tropics, and therefore they stay there until the last possible moment. They might not even come back, but since Santa is footing the bill for their year in paradise... This could also explain the quickness in their delivering of presents, since the reindeer can't wait to get back to where it is warm.) The penalty for the last reindeer to arrive is that it must get Santa while the others wait in a warming hut before being harnessed to the sleigh.

It is worth noting that the description of the Santa Claus problem in Peyton Jones's chapter is slightly different. For example, he does not model the last reindeer to arrive as doing anything different from the others. Trono provides a model answer in pseudo-C using counting semaphores, where the last worker of either kind to join a group is responsible for carrying out the activities of the group as a whole. I think we can agree that an algorithm involving no fewer than 10 semaphores is not an easy one to follow, so that finding a clean solution that doesn't require great inventive powers is an interesting exercise.

Here's the Haskell solution, Santa.hs. It takes 77 SLOC, by my count. It requires two new abstractions in addition to the Software Transactional Memory library: Groups and Gates. For an explanation, see the chapter.

Here's my Erlang solution, santa.erl. It takes 43 SLOC, by my count. The process architecture goes like this.

• There is a Santa process which waits for somebody to send along a group of reindeer {reindeer,[R1,...,R9]} or a group of elves {elves,[E1,E2,E3]}. Two nested receives are used: the outer one grabs a reindeer group no matter how many elves are waiting, while the inner one waits for anything to turn up. There can never be more than one reindeer group or three elf groups in Santa's mailbox. Santa doesn't know about any other processes; he can only talk to the reindeer or elves in a group because their pids are in the message he is sent, and after dealing with a group, he forgets them. After receiving a group, he writes a message, sends his own pid to each member, waits for them to respond (a 'barrier', if you will), and then loops around.
• Santa has two secretaries. Edna is the secretary who deals with elves. Whenever she has accumulated a group of three of them, she forwards the group to Santa. Robin is the secretary who deals with reindeer. Whenever she has accumulated a group of nine of them, she forwards the group to Santa. My 'secretaries' are very similar to Peyton Jones's 'groups', but were inspired by an old article of Dijkstra's. Since there are only 9 reindeer, there can be at most 9 messages in Robin's mailbox. Since there are 10 elves, there can be at most 10 messages in Edna's mailbox. Edna and Robin know Santa's pid but no others; they send stuff to him but he never sends anything back to them.
• Each elf is a process. It sends its pid to Edna, then waits for Santa to tell it to proceed, which he does by sending it his own pid. An elf then prints a message, and sends Santa (or whoever it was that told it to proceed) a {leave,self()} message to say it has finished. An elf has to know Edna's pid, but it doesn't know any others. There can be at most one message (Santa's signal to proceed) in its mailbox at any time. After finishing with Santa, it has a random delay.
• Each reindeer is just like an elf, except for knowing Robin's pid instead of Edna's pid, and writing 'Reindeer r delivering toys.' instead of 'Elf e meeting in the study.'

The Erlang solution involves no exotic control structures or data structures, just plain message passing. The only even slightly tricky thing is the nested receives to give reindeer priority over elves, and I owe that to a discussion of priority receives in the Erlang mailing list.

Beware! Good Erlang style insists that there should be a clean way to shut down a concurrent system like this. But there was no such shut down procedure in either the original problem specification or the Haskell version, so for the sake of a fair comparison, there isn't any in the Erlang code.