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.

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.