Builder Pattern in Scala with Phantom Types

Analyzing and creating Design Patterns using Functional Programming concepts for your own good.

There are many things I’ve been willing to write about this past few months. I figured some talk about Design Patterns combining OOP and FP would be a really great place to start.

In this post we will explore a variation of the Builder Pattern commonly known from the GoF book using some Functional Programming abstractions and patterns. As you might guess, FP additions will result in cleaner, more declarative and expressive code, with one major benefit from the original solution: The code will not even compile unless the object is correctly built.

It’s far beyond the scope of this post to discuss the several advantages that compile-time type checking offers, but we can simplify it a little bit just by saying that we rather have code failing in compile time than in production.

Caveats of the Builder Pattern

Let’s see an example of what we just discussed. Consider we are modeling a system that provides food recipes for a restaurant. For the sake of simplicity in the scope of this post we can just say that Food is a combination of ingredients:

case class Food(ingredients: Seq[String])

Yes, this definition is most probably lacking a few abstractions, but it will be enough to define that, for example, a Pizza is a combination of “dough”, some type of “cheese”, and at least one “topping”.

Lets suppose we have a typical builder, extracted from the GoF book for this class. I don’t know about your neighborhood, but here we call the people that make food “chefs”. So most probably our Chef will look something like this:

case class Chef {
...
def build: Food =
if (hasDoughCheeseAndToppings(ingredients)) Food(ingredients)
else throw new FoodBuildingException("You tried to build a pizza without enough ingredients")
}

This approach has several downsides, but I personally think the worst one is that we delay the validation of the builder until right before creating de Pizza, that is, this code fails at runtime. We’ll try to see how we can apply some Functional Programming concepts to decompose this problem and create an approach that fails at compile-time.

Phantom Types

A Phantom Type is a fancy name that we give to types that are never instantiated by the application. In fact, they’re just used by the compiler to statically check properties of the code but they never have any effect in the code at runtime. I really like the definition the Scala guys have in Dotty Docs:

A phantom type is a manifestation of abstract type that has no effect on the runtime. These are useful to prove static properties of the code using type evidences. As they have no effect on the runtime they can be erased from the resulting code by the compiler once it has shown the constraints hold.

I have found Phantom Types to be particularily useful when representing models that have a particularily defined structural state with transitions, which drastically alters or limits the way an entity behaves, but that structural change is still not strong enough to imply an inheritance model.

… Wait, what?

You see, we are used to fall too fast into the “Composition over Inheritance” problem when we try to model entities that have states that define the way they behave, and we default for composition to avoid “using our only Inheritance shot”. But there are some cases on which neither Composition nor Inheritance completely solves our problems. Consider the following example:

trait DoorState
case class Open() extends DoorState
case class Closed() extends DoorState
case class Door(state: DoorState) {
def open = state match {
case _: Open => throw new DoorStateException("You cannot open a door thats already open")
case _ => Door(Open())
}
def close = state match {
case _: Closed => throw new DoorStateException("You cannot close a door thats already closed")
case _ => Door(Closed())
}
}

It’s not that I’ve been struggling too much to write this code as awful as it got, but you can clearly see here how Composition, for as good as it usually is, made the implementation of the code far more declarative and far less expressive than anyone would like. Of course we can add some refactors here and there, and probably we can make the code look much better, but the main issue will still be there: we have to test whether we’re in the correct state (closed or open) to validate the transition that’s asked.

No wonder you can see now how this relates to our issue while talking about pizzas, now. The only way we can validate that we’re telling the object to transition to the right state is at runtime, and if we write bad code, we get no help from the compiler.

I‘d like to add a few notes about this example before seeing how Phantom Types can help us solve this issue. If you see closely, little to none behaviour changes between the opened and closed door, as we’ve defined no method that delegates behaviour at all. At the end, the current state is what defines what an entity can or cannot do. This is what I like to call Structural State.

You have a case of Structural State when an entity varies it’s stucture (internal composition or properties) with the given state.

On the other hand, there are some entities that depend on a state to delegate behaviour to it, for example, when a Bank Account delegates to its Account Type the calculation of an interest rate. This I call Behavioural State.

Behavioural State manifests when an entity has a state on which it delegates specific behaviour for completing tasks.

As you can see in our Door example, we decided to compose the entity with its Closed or Open status. As it turns out, Composition is a Behavioural State pattern, resulting in the issues we previously discussed.

“Of course! Use inheritance instead!” As it turns out, inheritance is indeed an Structural State pattern, for it defines a structure that can alter the structure of the entity. We can even define our OpenDoor and CloseDoor in a way that they can only transition to the correct states, without the need of throwing an exception. But no so fast! There is a major caveat in this: We use our silver bullet here, defining the inheritance.

This is when Phantom Types come to the rescue. Pantom Types are incredibly useful when simple Structural State problems come to us. As you can remember, they are types that only matter at compile-time and define the structure of the entity. Let’s see what we can achieve with our Door example, first defining the Structural State Types:

sealed trait DoorState
sealed trait Open extends DoorState
sealed trait Closed extends DoorState

Here we define the phantom types. There are many ways we can achieve this in Scala, and this is a pretty simplistic one: we just seal the types for avoiding them to ever be extended.

Then there’s the implementation of the Door class:

case class Door[State <: DoorState](){
def open(implicit ev: State =:= Closed) = Door[Open]()
def close(implicit ev: State =:= Open) = Door[Closed]()
}

Looks good, doesn’t it? Let’s decode it a little.

The case class Door[State <: DoorState] receives a parametric type State that is bound to be a subtype of DoorState. This restricts the Structural State of the Door to be either Open or Closed.

On the other hand, the most interesting part of this pattern: method which depends on structure are restricted by an implicit evidence which binds them to a specific DoorState.

If you aren’t already aware of this, Scala allow us to work with implicits, which are context-bound references that we can provide as parameters. For example, we can have an application context passed to a method without having to explicitly write it:

implicit val context: Context = ...
def methodThatRequiresContext(str: String)(implicit context: Context) = ...

methodThatRequiresContext("foo")

Scala resolves implicits based on some context rules taking, in this case, the context value defined in the same scope. Implicits are resolved by the compiler at compile-time, so the references are written when the program is built, and not in runtime.

Now, one interesting thing about implicits is that they let us “ask” the compiler for some meta-information about the program it’s building. One of those things the compiler can provide us is an evidence of a certain relationship between two types. This is what we were doing in the Door methods:

def open(implicit ev: State =:= Closed) = Door[Open]()

Here we ask the compiler to “check that there is a Type Equality relationship between the door’s type parameter State and Closed”, and “provide an evidence of that”. What is that ev object for? Nothing, but if the compiler can resolve it, it means that the door State is Closed.

It’s interesting to notice what happens if the Door’s State is not Closed. Look at what scala compiler shows when we try to open an already open door:

scala> Door[Open]().open
<console>:17: error: Cannot prove that Open =:= Closed.

If we look closely here, we can see that this is a compile-time error, which means that if the compiler cannot prove this relationship, the compilation itself will fail.

Amazingly, we managed to remove the if condition that checked at runtime the structural state of the first Door we build by delegating the check to the compiler.

We removed an if. We saved a kitten.

Phantom Types and Builder Pattern

Now that we know what a Phantom Type is and how it help us solve problems that models Structural State, lets see how we can apply it to our pattern.

Remember the Pizza-making builder we defined earlier? Lets come back to that. Recall that we defined that Pizza is a Food that has dough, cheese and some toppings, right? Let’s start by trying to identify where the Structural State is on the builder.

The main operation any builder has is build, which creates a new instance of a given entity. This operation has a very similar behaviour than our Door example: A builder can be either ready or not (closed or open) to build that entity.

Our chef is ready to build a pizza if and only if he has ingredients that contain dough, cheese and a topping. If the chef lacks of any of those elements, then he should not be able to make the pizza. This can be seen as the following Phantom Types:

object Chef {

sealed trait Pizza
object Pizza {
sealed trait EmptyPizza extends Pizza
sealed trait Cheese extends Pizza
sealed trait Topping extends Pizza
sealed trait Dough extends Pizza

type FullPizza = EmptyPizza with Cheese with Topping with Dough
}
}

Here we define the Pizza, which is the supertype containing all the elements, and the no-pizza itself (remember that any set contains the empty set by definition). Then, a Pizza ready to be built is the empty one that has cheese, a topping and dough.

See how the FullPizza is defined? Scala allow us to define a type alias that is the conjunction of several other types. This will make our code much cleaner.

Now let’s dive into the builder implementation:

class Chef[Pizza <: Chef.Pizza](ingredients: Seq[String] = Seq()) {
import Chef.Pizza._

def addCheese(cheeseType: String): Chef[Pizza with Cheese] = new Chef(ingredients :+ cheeseType)

def addTopping(toppingType: String): Chef[Pizza with Topping] = new Chef(ingredients :+ toppingType)

def addDough: Chef[Pizza with Dough] = new Chef(ingredients :+ "dough")

def build(implicit ev: Pizza =:= FullPizza): Food = Food(ingredients)
}

There are two things to note here. Firstly, the ingredients addition is done by creating a new builder with the parametric type extended with the ingredient. Then we create a new chef that has the previous ingredients with the added ones. As you can see, I defined the return type of every function to be a Chef[Pizza with Ingredient] where Ingredient is the type of ingredient I wanted to add to that mix. This allow us to extend the parametric type Pizza with the given ingredient.

Secondly, we use what we learnt from the Door example how to ask the compiler in the build function for an evidence that the Pizza is really a FullPizza, or else it won’t compile:

scala> new Chef[Chef.Pizza.EmptyPizza]().addDough.build
<console>:18: error: Cannot prove that Chef.Pizza.EmptyPizza with Chef.Pizza.Dough =:= Chef.Pizza.FullPizza.

But if we add all the ingredients:

scala> new Chef[Chef.Pizza.EmptyPizza]()
.addCheese("mozzarella")
.addDough
.addTopping("olives")
.build
res1: Food = Food(List(mozzarella, dough, olives))

Finally! We managed to code a builder that not only fails at compile time, but is also strongly typed checked. One interesting concept I woudn’t like to avoid mentioning, though I will not extend myself too much on this, is how Immutability helped us thoughout this process. Of course this has a great lot to do with the fact that we’re using a Functional Programming concept to model our solution. There is no Phantom Types pattern without creating new instances of the builder.

You can see a full version of this code here.

Conclusion

We’ve seen how to change a pretty standarized Builder Pattern in a way that it let us do a compile-time validation of the structure of our entities. We achieved this by deconstructing the Structural State of the Builder and using Phantom Types to model the solution.

What I think is left, is a clear example of clean, declarative but expressive code that is actually very easy to read.

I know that it might be a little tough to extend this solution for the typical OOP with little or no background on FP and type usage, but please believe that this pattern can be extended in a lot of ways.

This implementation is not the top of the roof, though. There are lots of more complex domains on which Phantom Types can make things a lot easier.

I hope you enjoyed it.