The first time I used Go to solve the particular puzzle I’d like to discuss in this post, I though I was doing something wrong because the solution is so concise.

Secton 3.7 of the Little Book of Semaphores presents the following puzzle:

Imagine that goroutines represent ballroom dancers and that two kinds of dancers, leaders and followers, wait in two queues before entering the dance floor. When a leader arrives, it checks to see if there is a follower waiting. If so, they can both proceed. Otherwise it waits. Similarly, when a follower arrives, it checks for a leader and either proceeds or waits, accordingly. Write code for leaders and followers that enforces these constraints.

In Go this is as simple as having a channel where one set of goroutines write to and another set of goroutines read from:

type Signal struct{}

func leader(queue chan <- Signal}) {
	queue <- Signal{}
	// dance
}

func follower(queue <- chan Signal) {
	<-queue
	// dance
}

Here the channel is not used for communicating between the leader and the follower, but just to make sure that a leader waits for a follower before proceeding. When sending a signal over the queue channel, the leader blocks until there’s a follower that reads it from the channel. This meets the requirements, but it’s boring in the sense that we didn’t really gain anything as it’s just a bunch of goroutines with delayed execution. The puzzle is extended in the following way:

Each leader can dance concurrently with only one follower, and vice versa. In other words, you got to dance with the one that brought you.

That’s more interesting! Put in the previous terms, the writer and the reader get paired, which in Go is still easy to do:

func leader(queue chan<- chan DanceStep) {
	ch := make(chan DanceStep)
	queue <- ch
	// dance
	close(ch)
}

func follower(queue <-chan chan DanceStep) {
	ch := <-queue
	// dance
}

(complete code here)

The externally provided channel is used to send and receive another channel, which in turn is used to communicate between the leader and the follower.

Strictly speaking, this is not what TLBOS is asking for, as I have interpreted the “dance concurrently” bit in the puzzle as “work in lockstep with each other”. What the puzzle is actually asking for is that one leader and one follower dance before any other leaders or followers do. If you think about it, that’s what you get from channels without doing anything else.

Consider this:

func leader(queue chan <- DanceStep) {
	// compute information for one "DanceStep" here
	myDanceStep := DanceStep{}

	// send information to one follower
	queue <- myDanceStep

	// and dance!
	// ...
}

func follower(queue <- chan DanceStep) {
	// receive information for one "DanceStep" from one leader
	myDanceStep := <-queue

	// and dance!
	// ...
}

Here the leader computes some data and waits for one follower to show up, while other leaders are doing the same; one follower shows up, picks the data from one leader, and both that particular leader and that particular follower dance (get unblocked and proceed with the rest of the function).

On the other hand, in my extended version, the leader and the follower go one step further, and they share memory by communicating with each other. This is already doing more than what TLBOS proposes with not only less code, but less complicated code as well.

Thanks for reading, and as usual, comments and questions are welcomed!