Why I dig Scala: Concurrency and the Dining Philosophers

I am occasionally asked what the big deal is about Scala. For me, to decide whether a programming language is worthwhile is dependent on two practical questions: does it aid comprehension, and does it reduce code. The two are not necessarily interchangeable. Terseness, after all, does nothing to aid comprehension. Scala scores points on both counts. It also has a sweet spot that I haven’t encountered elsewhere, that is that it lends itself to concurrent programming in a way which is easy to reason about, and therefore get right. It does this through a set of supporting language features that combined allows us to code at a higher level of abstraction: a leaning towards immutability, functional constructs (such as closures), as well as a familiar way to model a domain via object orientation.

Put together, it’s massively powerful. As it runs on the JVM you could code Scala concurrency the same way as Java, with the bog-standard tools such as wait/notify/notifyAll or the JDK 5+ concurrency libraries. You might get some shorter code, but it misses the point. Scala comes with an implementation of the Erlang-inspired actors model out of the box, which lets you deal with the problems of concurrency in a manner that is much easier to reason about. Actors aren’t a language construct, but a library that makes use the underlying platform (the JVM) and Scala’s language features to provide a much simpler mental model for us to deal with. Actors are “like” threads (not really, but close enough for a starting point) that send and receive messages to and from other actors. How does this aid comprehension? Synchronous and asynchronous messages are very simple to reason about, and IMHO much more straightforward than the Java concurrency libraries (compare the actors documentation to the Trains Book).

Consider the classic computer science concurrency problem, the Dining Philosophers. A number of philosophers sit down at a round table to do some eating and thinking. Each philosopher brings with him a single chopstick that he places on his right hand side. So you have X philosophers and X chopsticks. To eat, a philosopher must pick up the chopsticks on his left and right sides. Leaving aside hygiene issues, it’s a cool toy problem around resource contention. So, how would you do this in Scala? The mental leap to be made is that “everything is an actor”. Given a number of philosophers dining at a table, it’s quite nicely modelled if you think about both the philosophers and the table as actors that pass messages beteen each other. If you want to see the whole file (~150 lines), it’s available here.

Firstly the messages that we’re going to be passing around:

package net.jakubkorab.philosophers

import messages._
import scala.actors._
import scala.actors.Actor._
import scala.math._

package messages {
	class Chopstick(val position : Int)
	
	object Side extends Enumeration {
		type Side = Value
		val Left, Right = Value
		
		def randomSide() = { Side(floor(Side.values.size * random).intValue) }
		def otherSide(side : Side.Value) = { Side.values.find{_ != side}.get }
	}

	sealed abstract class Message

	abstract class TableMessage() extends Message
	case class AllFinished() extends TableMessage
	
	abstract class ChopstickResponse() extends TableMessage
	case class ChopstickAvailable(val chopstick : Chopstick) extends ChopstickResponse
	case class ChopstickUnavailable() extends ChopstickResponse 

	abstract class DinerMessage() extends Message
	case class RequestChopstick(val philosopher : Philosopher, val side : Side.Value) extends DinerMessage 
	case class ReplaceChopstick(val chopstick : Chopstick) extends DinerMessage 
	case class CouldNotEatAnotherBite(val guest : String) extends DinerMessage
}

Messages don’t actually need to be of any particular type, I just like thinking of that sort of thing in a hierarchy. All of the messages that I’ll pass around are subclasses of Message.

Now for our philosophers:

class Philosopher(val name : String, val wordsOfWisdom : String) extends Actor {
	var table : Actor = null
	var seatedAt : Int = -1
	
	private var timesLeftToEat = 3
	override def act() = {
		while (timesLeftToEat > 0) {
			think()
			val side = Side.randomSide // pick a chopstick to use first 
			say("Requesting chopstick 1 on " + side)
			table !? (1000, RequestChopstick(this, side)) match { 
				case Some(ChopstickAvailable(chopstick1 : Chopstick)) => {
					pause() // put in a delay so we can see actors switching
					val otherSide = Side.otherSide(side) // request the other
					say("Requesting chopstick 2 on " + otherSide)
					table !? (100, RequestChopstick(this, otherSide)) match {
						case Some(ChopstickAvailable(chopstick2 : Chopstick)) => {
								eat() 
								pause()
								table ! ReplaceChopstick(chopstick1) // return chopsticks
								pause()
								table ! ReplaceChopstick(chopstick2)
							}
						case Some(ChopstickUnavailable()) => { 
							say("No " + otherSide + " chopstick"); 
							table ! ReplaceChopstick(chopstick1); 
						}
						case None => { say("None"); table ! ReplaceChopstick(chopstick1) }
					}
				}
				case Some(ChopstickUnavailable()) => { say("No " + side + " chopstick") } // no luck getting a chopstick
				case None => say("None")
			}
		}
		react {
			case AllFinished => { say(wordsOfWisdom); exit }
		}
	}
	
	private def think() = { say("Hmm"); pause() }
	private def eat() = { 
		say("Nom nom"); 
		timesLeftToEat -= 1
		if (timesLeftToEat == 0) {
			table ! CouldNotEatAnotherBite(name)
		}
	}
	private def say(s : String) = { println(name + ": " + s) }
	private def pause() = { Thread.sleep(ceil(random * 1000).intValue) }
}
object Philosopher {
	def apply(name : String, wordsOfWisdom : String) = new Philosopher(name, wordsOfWisdom)
}

As I said, it’s pretty straightforward if you think of an actor as a Thread. Think of act() as the equivalent of Runnable#run(). Philosophers will be instantiated with a name and some words of wisdom they’ll come up with. Once they’re sat at a table, they’ll receive an instance of table for them to communicate with and a place where they’re sitting. Messages are sent either asynchronously to the table using the ! method, or synchronously using !? (in which case the number that follows is a timeout). The syntax may be unfamiliar, but I think it reads pretty easily even to those unfamiliar with Scala. I won’t go through it in detail. A philosopher sends a chopstick request to the table and gets a response, either that a chopstick is available, or that it’s unavailable. Pretty straightforward.

So, now the table.

class Table(val philosophers : Set[Philosopher]) extends Actor {
	if (philosophers.size < 2) throw new IllegalArgumentException("At least 2 philosophers must dine together")
	var chopsticks = new Array[Chopstick](philosophers.size)
	var location = 0
	philosophers.foreach { philosopher => 
		chopsticks(location) = new Chopstick(location)  // lay the cutlery
		philosopher.seatedAt = location
		location += 1
	}
	var guestsEating = philosophers.size
	
	override def act() = {
		println("Starting the meal")
		philosophers.foreach { philosopher => philosopher.table = self; philosopher.start  } // let's go
		while (true) {
			receive {
				case RequestChopstick(philosopher : Philosopher, side : Side.Value) => giveChopstickIfAvailable(philosopher, side)
				case ReplaceChopstick(chopstick : Chopstick) => replaceChopstick(chopstick)
				case CouldNotEatAnotherBite(guest : String) => guestFinished(guest)
			}
		}
	}
	
	private def giveChopstickIfAvailable(philosopher : Philosopher, side : Side.Value) = {
		var index = if (side == Side.Right) philosopher.seatedAt else philosopher.seatedAt - 1 
		if (index < 0) { index = philosophers.size - 1 } // get the one on the end of the array
		
		val chopstick = chopsticks(index)
		if (chopstick == null) {
			println("No chopstick available at " + index)
			sender ! ChopstickUnavailable() // sender, not philosopher!
		} else {
			chopsticks(index) = null
			sender ! ChopstickAvailable(chopstick)
		}
	}
	
	private def replaceChopstick(chopstick : Chopstick) = {
		chopsticks(chopstick.position) = chopstick
	}
	
	private def guestFinished(guest : String ) = {
		println(guest + " is done")
		guestsEating -= 1
		if (guestsEating == 0) { 
			philosophers.foreach {_ ! AllFinished}
			println("All done")
			exit
		}
	}
}

The role of the table is to manage the resources, in this case the chopsticks. Calling start() on an actor is analogous to Thread#start().

And now, to kick it all off, let’s stick some philosophers on a table. I have chosen the Greco-Roman Stoics for their easy going approach to life, but any school of thought will do. Chinese philosophers may have been more appropriate to the cutlery. My example, my choice.

object PhilosophersLauncher {
	def main(args : Array[String]) = {
		val table = new Table(
			Set(Philosopher("Seneca the Younger", "The point is, not how long you live, but how nobly you live."),
				Philosopher("Epictetus", "Freedom is secured not by the fulfilling of men's desires, but by the removal of desire." ),
				Philosopher("Marcus Aurelius", "Everything is right for me, which is right for you, O Universe."),
				Philosopher("Zeno of Citium", "Shit happens.")) // one of his lesser known ones
			).start 
	}
}

So, does it work?

Starting the meal
Seneca the Younger: Hmm
Epictetus: Hmm
Marcus Aurelius: Hmm
Seneca the Younger: Requesting chopstick 1 on Right
Marcus Aurelius: Requesting chopstick 1 on Right
Epictetus: Requesting chopstick 1 on Right
Marcus Aurelius: Requesting chopstick 2 on Left
No chopstick available at 1
Marcus Aurelius: No Left chopstick
Marcus Aurelius: Hmm
Epictetus: Requesting chopstick 2 on Left
No chopstick available at 0
Epictetus: No Left chopstick
Epictetus: Hmm
Marcus Aurelius: Requesting chopstick 1 on Left
Seneca the Younger: Requesting chopstick 2 on Left
Seneca the Younger: Nom nom
Marcus Aurelius: Requesting chopstick 2 on Right
Marcus Aurelius: Nom nom
Epictetus: Requesting chopstick 1 on Left
No chopstick available at 0
Epictetus: No Left chopstick
Epictetus: Hmm
...
Epictetus: Requesting chopstick 1 on Left
Zeno of Citium: Requesting chopstick 1 on Left
Epictetus: Requesting chopstick 2 on Right
Epictetus: Nom nom
Epictetus is done
Zeno of Citium: Requesting chopstick 2 on Right
Zeno of Citium: Nom nom
Zeno of Citium: Hmm
Zeno of Citium: Requesting chopstick 1 on Right
Zeno of Citium: Requesting chopstick 2 on Left
Zeno of Citium: Nom nom
Zeno of Citium is done
All done
Marcus Aurelius: Everything is right for me, which is right for you, O Universe.
Epictetus: Freedom is secured not by the fulfilling of men's desires, but by the removal of desire.
Seneca the Younger: The point is, not how long you live, but how nobly you live.
Zeno of Citium: Shit happens.

Yup. I think it’s pretty easy to make sense of all this. You can easily reason about what happens when, just by drawing a sequence diagram. Consider the backdown strategy when a philosopher can’t get hold of a chopstick:

Zeto->Table: RequestChopstick(Left)
activate Table
Table-->Zeto: ChopstickAvailable(C0)
deactivate Table

Epictetus->Table: RequestChopstick(Left)
activate Table
Table-->Epictetus: ChopstickAvailable(C1)
deactivate Table

Zeto->Table: RequestChopstick(Right)
activate Table
Table-->Zeto: ChopstickUnavailable()
deactivate Table
Zeto->Table: ReplaceChopstick(C0)

note over Zeto: Sleeps for a bit before trying again

Epictetus->Table: RequestChopstick(Right)
activate Table
Table-->Epictetus: ChopstickAvailable(C0)
deactivate Table
Epictetus->Epictetus: Eat
Epictetus->Table: ReplaceChopstick(C1)
Epictetus->Table: ReplaceChopstick(C0)

So, actors are cool, and in Scala they are easy to reason about due to the syntax and ability to mix in OO concepts. For a comparison, check out the equivalent in Java using semaphores. The Scala version is far less code and much easier to comprehend. And if you think that’s cool, check out Akka.