override lazy val

Peregrinations of a developer in Scala land

Interlude: a simple type-level state machine

Sooner this year, Heiko Seeberger wrote a blog post about phantom types. As Heiko shows in his post, phantom types are an interesting technique to encode constraints on our code that are directly enforced by the compiler.

In this post, I present a slightly different technique that achieves the same goal, using shapeless’ records, and the underrated Dynamic mechanism of Scala.

We will implement a very simple state machine representing a door. Our door can have one of the three following states : Open, Closed or Locked. These states will be encoded as empty traits, very similar to the phantom types technique.

object Door {

  trait Open
  trait Closed
  trait Locked   

}

Then we need to express the possible transitions between the states of this door state machine. Since a transition involves two states, the following class should be enough to represent it :

class Transition[In, Out]

Now we’re equipped enough to define the possible transitions in our state machine. To do so, we’ll use a shapeless record :

"open"   ->> new Transition[Closed, Open]   ::
"close"  ->> new Transition[Open,   Closed] ::
"lock"   ->> new Transition[Closed, Locked] ::
"unlock" ->> new Transition[Locked, Closed] ::
HNil

But before going further with our implementation, let say a few words about records.

Records

Shapeless records are regular hlists but with each element’s type labelled with a singleton type (we discussed those here). These labelled hlist elements are called “fields”. We can create a field with the ->> operator that is defined in shapeless.syntax.singleton. On the left hand side of ->> we must use a singleton typeable value, i.e. a literal be it a String , a Symbol, a number literal etc.

Let see what happen when we create a field using ->>

scala> import shapeless.syntax.singleton._
import shapeless.syntax.singleton._

scala> "foo" ->> 42
res0: Int with shapeless.labelled.KeyTag[String("foo"),Int] = 42

As usual in shapeless land, we obtain a thing with a type way bigger than its value :). Lets decompose that big type in more palatable chunks. First, we see that it is a Int with ... meaning that a field built with ->> has a type compatible (but more specific) with that of the value we pass to the left hand side of ->>.

Then there is ... with KeyTag[String("foo"), Int]. It simply connects (or labels) the type of the value (here Int) with the singleton type of the label (here String("foo")).

In the end we get the value 42 but with the "foo" label attached to it at the type level.

Implementing the state machine

For our state machine implementation, we’re only realy interested in the type of the record that describes the possible transitions, because we want to check that a transition is possible completely at compile time. For that matter, we create a class whose purpose will be to carry the type of our record as a type parameter, along with a factory method to create instance of that class. While we’re at it, we add two other factory methods in the StateMachine companion object to ease the definition of initial state and transitions of our state machine.

class Definition[R <: HList]

object StateMachine {

  def initial[S] = new StateMachine[S]
  def definition[R <: HList](r: R) = new Definition[R]
  def transition[I, O] = new Transition[I, O]

}

Now we’re ready to fully describe our simple door state machine.

object Door {

  import StateMachine._
  import syntax.singleton._

  trait Open
  trait Closed
  trait Locked

  implicit val transitions  = definition(
    "open"   ->> transition[Closed, Open]   ::
    "close"  ->> transition[Open,   Closed] ::
    "lock"   ->> transition[Closed, Locked] ::
    "unlock" ->> transition[Locked, Closed] ::
    HNil
  )

  val init = initial[Open]

}

We still need to handle a “little” detail though : how do we make this door change between the possible states ?

Dynamic

There is a little known feature in the scala language, specified in SIP-17 that resembles the method_missing in Ruby. For brevity’s sake, I will not discuss it in great detail, but all you need to know is that it provides a way to call method that are not statically defined on some types.

The specification states that if a type extends the Dynamic trait, when we call a method that is not defined of this type, the compiler first tries to call one of the applyDynamic, applyDynamicNamed, selectDynamic or updateDynamic (depending on the attempted method call) before raising an error.

We’re only interested in selectDynamic here which is attempted when we call a non-existing method with no parameters. For example if we have

class Foo extends Dynamic {

    def selectDynamic(methodName: String) {
        println(s"You've just called $methodName !")
    }

}

Calling (new Foo).bar would print You've just called bar.

Implementing the state machine

We will use the Dynamic mechanism to implement our state machine transitions. The idea is to use the labels we’ve put on transitions in the definitions to create dynamic methods for available transitions from a given state. We need to implement selectDynamic so that init.close compiles (we’ve set the door open in the initial state) but init.open or init.lock don’t.

To do so, when our selectDynamic is call with a parameter xyz it must :

  • grab the state machine definition from the implicit scope
  • verify that there is a field in the definition record labelled with xyz
  • verify that this field contains a transition that goes from the current state to a state A
  • return a new state machine in the state A

This is what the following code implements

import shapeless.ops.record.Selector
import shapeless.Unpack2

class StateMachine[S] extends Dynamic {

  def selectDynamic[R <: HList, A, T](transition: Witness)
   (implicit d: Definition[R],
             select: Selector.Aux[R, transition.T, T],
             unpack: Unpack2[T, Transition, S, A]
   ): StateMachine[A] = new StateMachine[A]

}

Since the string passed to selectDynamic is fully known at compile time, we can safely convert it to the Witness of its singleton type.

Then we use Selector to search for a field labelled with this singleton type in the definition record.

If such field exists, we use Unpack2 to check that it is of type Transition[S, A], S being the current state of the state machine. We need Unpack2 to circumvent the infamous SI-2712 bug. Without that bug, we could have more simply written select: Selector.Aux[R, transition.T, Transition[S, A]]

In the end, we have a very concise door state machine, whose transition are completely checked at compile time. We can write

import Door._

init.close.lock.unlock.open.close

But not

init.open
init.close.close
init.close.lock.open
// etc ...

Conclusion

Using shapeless records and scala.Dynamic we were able to implement a very simple type-level state machine, with an extremely low runtime memory footprint (we only a reference to the empty Definition object).

We could go even further by checking at compile time that the definition record describes a deterministic state machine, that is a definition were from each state, there is at most one transition with the same label. This would made this post a bit too long though, but if you’re interested in such refinement, you can find an implementation in this gist.

comments powered by Disqus

About

Hi ! I'm Valentin Kasas and this is my programming blog.

I am a happy Scala user since 2012 and here is where I recount some of my wanderings in that vast landscape.

Follow @vil1