Fluent – A deep dive into Shapeless and implicit resolution

Tweet about this on TwitterShare on LinkedInShare on FacebookShare on Google+Share on Reddit

As promised in my previous post we’re going to explore to internal of Fluent and how it uses Shapeless and implicit resolution to transform case classes.

Fluent started as an experiment (and still is), the code is rather small (about 300 lines of code) and yet I am still impressed by the variety of cases it can handle.

Before working with Shapeless I’ve often heard that is pure magic and I got the impression that most people (including me) don’t really know how it works. It turns out that the principles used in Shapeless are not really difficult to understand – especially if you read the well-written Type Astronaut’s guide to Shapeless.

Understanding how Shapeless works doesn’t mean it’s easy to work with. Actually Shapeless makes a heavy use of implicits and working with implicits is hard. Remember that implicits resolution is performed at compile time so when it fails, there is nothing to debug, no log messages or stack trace. We are just left with rather blunt messages like could not find implicit value for parameter ...

In this post I am going to explain the concept used in Fluent, the problem I faced during implementation and hopefully by the end of the post, you’ll know enough to understand and edit the code (Pull requests welcomed!).

Principle

At the heart of Fluent is a type class: Transformer.

trait Transformer[A, B] {
   def apply(a: A): B
}

That’s quite simple, a Transformer[A, B] is something that can transform an instance of A into an instance of B.

Then we have an implicit class that adds a method transformTo[B] to any instance A for which it exists an implicit Transformer[A, B] who can turn A into B.

implicit class TransformerOps[A](a: A) {
  def transformTo[B](implicit transform: Transformer[A, B]): B = 
    transform(a)
}

That really is the heart of Fluent. The remaining of the code uses Shapeless to automatically derive Transformer type class instances.

Deriving type class instances

As explained in this previous post we can use Shapeless’s Generic to convert case classes into/from HLists.

import shapeless._

case class Circle(x: Double, y: Double, radius: Double, colour: String)

val circle: Circle = Circle(1.0, 2.0, 3.0, "Blue")
val repr: Double :: Double :: Double :: String :: HNil = Generic[Circle].to(circle)
println(repr) // prints: 1.0 :: 2.0 :: 3.0 :: Blue :: HNil

That’s a good start but we need the field names as well otherwise there is no way to pick the right value between x, y and radius as they’re all of type Double.

To this matter Shapeless provides us with Singleton types. Let’s take an example: 1 is an Int so we can consider it as a subtype of Int which is just the value 1.

def onlyOne(one: Witness.`1`.T) = one

onlyOne(1) // works
onlyOne(2) // doesn't compile (type mismatch)

We can do the same with strings – "Hello" is a subtype of String.

def onlyHello(hello: Witness.`"Hello"`.T) = hello

onlyHello("Hello") // works
onlyHello("Hi") // doesn't compile (type mismatch)

That’s great we can use singleton types to represent our field names at the type level. What’s even better is that Shapeless does it for us if we use LabelledGeneric instead of Generic.

val labelledRepr = LabelledGeneric[Circle].to(circle)
println(labelledRepr) // prints: 1.0 :: 2.0 :: 3.0 :: Blue :: HNil

Wait! LabelledRepr looks exactly the same as repr. That’s right but its type looks different:

Double with KeyTag[Symbol with Tagged[String("x")],Double] :: 
Double with KeyTag[Symbol with Tagged[String("y")],Double] ::
Double with KeyTag[Symbol with Tagged[String("radius")],Double] ::
String with KeyTag[Symbol with Tagged[String("colour")],String] ::
HNil

Basically it’s still a HList but with refined types. Each refined type is called a Record.

Now that we know which is which we can go back to our generic derivation of Transformer type class instances.

The easiest case is that given a Transformer[A, BRepr] and a LabelledGeneric.Aux[B, BRepr] we can easily make a Transformer[A, B].

implicit def genericTransformer[A, B, BRepr <: HList](implicit
  generic: LabelledGeneric.Aux[B, BRepr],
  transform: Lazy[Transformer[A, BRepr]]
): Transformer[A, B] = new Transformer[A, B] {
  override def apply(a: A): B = generic.from(transform.value(a))
}

That’s one step in the right direction, but we still need a Transformer[A, BRepr]. BRepr is an HList so we can construct it recursively. The stop case is easy, it’s the one who turns an A into an HNil.

implicit def hnilTransformer[A]: Transformer[A, HNil] = new Transformer[A, HNil] {
  override def apply(a: A): HNil = HNil
}

Now the recursive case. Basically we need a Transformer for the tail of the HList and a Transformer for the head.

implicit def hlistTransformer[A, ARepr <: HList, F, K, V, T <: HList](implicit
  generic: LabelledGeneric.Aux[A, ARepr],
  selector: Selector.Aux[ARepr, K, F],
  transformHead: Transformer[F, V],
  transformTail: Transformer[A, T]
): Transformer[A, FieldType[K, V] :: T] = new Transformer[A, FieldType[K, V] :: T] {
  override def apply(a: A): ::[FieldType[K, V], T] = {
    val h = transformHead(selector(generic.to(a)))
    field[K](h) :: transformTail(a)
  }
}

It looks complicated, so let’s break it down. First we need to turn A into an HList. That’s the job of the LabelledGeneric.Aux[A, ARepr].
Once we have ARepr we need to pick the right field from the List. That’s why we need a Selector.
Once we have picked the right field we need to transform it into the type expected in BRepr. In our example we’re going to turn a Double into a Double so the identity transformer will do.
At this point we’re ready to compute the head of BRepr. Remember it needs to be a Record which we can easily construct : transformHead(selector(generic.to(a))) gives the expected head of type V which we then refine into a Record by calling field[K](h).
Once we have our new head we just need to append the tail that we compute directly using our tail transformer.

The only missing bit is the identity transformer that I mentioned above:

implicit def identityTransformer[A]: Transformer[A, A] = new Transformer[A, A] {
  override def apply(a: A): A = a
}

Example

Now that we’re all setup let’s turn our Circle into a Point.

case class Point(x: Double, y: Double)

val point = circle.transformTo[Point]

If we print every step of the execution, this is what we get:

- IdentityTransformer:    1.0 -> 1.0
- IdentityTransformer:    2.0 -> 2.0
- HNilTransformer:        Circle(1.0,2.0,3.0,Blue) -> HNil
- HListTransformer:       Circle(1.0,2.0,3.0,Blue) -> 2.0 :: HNil
- HListTransformer:       Circle(1.0,2.0,3.0,Blue) -> 1.0 :: 2.0 :: HNil
- GenericTransformer:     Circle(1.0,2.0,3.0,Blue) -> Point(1.0,2.0)

As you can see we use all the transformers we have defined above. It’s interesting to see how the HList of B representation gets constructed recursively.

Common pitfalls

Ambiguous implicits

The remaining of the Fluent code is just more implicit transformers. However as I added more implicit definition I ended up the following error `ambiguous implicit values`.

It happens when there is more than one implicit of a given type in scope. I encountered this problem when I added support for user-defined function. The initial implementation used to turn the implicit function into a Transformer

implicit def customTransformer[A, B](implicit f: A => B): Transformer[A, B] = new Transformer[A, B] {
  override def apply(a: A): B = f(a)
}

and then transform A into B‘s HList with the following:

implicit def hlistGlobalTransformer[A, K, V, T <: HList](implicit
    transformHead: Transformer[A, V],
    transformTail: Transformer[A, T]
  ): Transformer[A, FieldType[K, V] :: T] = new Transformer[A, FieldType[K, V] :: T] {
    override def apply(a: A): ::[FieldType[K, V], T] = 
      field[K](transformHead(a)) :: transformTail(a)
  }

The problem is that now both hlistTransformer and hlistGloablTransformer conflicts with each other. But what I really wanted to do was to use hlistGlobalTransformer only when the user provides an implicit function and default to the hlistTransformer when hlistGlobalTransformer is not applicable.

The problem is that hlistTransformer is always applicable so if hlistGlobalTransformer is also applicable we end up with the ambiguous implicit values error.

We need some sort of priority rules between the possible implicit values. To solve this issue we have to turn to the Scala implicit resolution rules. It turns out that the compiler looks first into the current instance definition and then into its parent definition (i.e. the class or traits that the current object extends).

We can then move the hlistTransformer into a lower priority trait which the Transformer companion object extends.

trait LowPriorityImplicits {
  implicit def hlistTransformer[A, ARepr <: HList, F, K, V, T <: HList](implicit
    generic: LabelledGeneric.Aux[A, ARepr],
    selector: Selector.Aux[ARepr, K, F],
    transformHead: Transformer[F, V],
    transformTail: Transformer[A, T]
  ): Transformer[A, FieldType[K, V] :: T] = new Transformer[A, FieldType[K, V] :: T] {
    override def apply(a: A): ::[FieldType[K, V], T] = {
      val h = transformHead(selector(generic.to(a)))
      field[K](h) :: transformTail(a)
    }
  }
}
object Transformer extends LowPriorityImplicits {
  implicit def hlistGlobalTransformer[A, K, V, T <: HList](implicit
    transformHead: Transformer[A, V],
    transformTail: Transformer[A, T]
  ): Transformer[A, FieldType[K, V] :: T] = new Transformer[A, FieldType[K, V] :: T] {
    override def apply(a: A): ::[FieldType[K, V], T] = 
      field[K](transformHead(a)) :: transformTail(a)
  }
  // more implicits here ...
}

This is actually working quite nicely and used in multiple places in Shapeless.

Note: that in the current implementation the hlistGlobalTransformer has been moved into a low priority trait and user defined functions are supported with higher-priority by the hlistCustomTransformer who takes the user’s implicit function as a parameter.

Diverging implicits

When using recursive implicit resolution it’s common to encounter the `diverging implicit expansion for type …`. Fortunately Shapeless provide us with the Lazy macro where all we have to do is wrapped our type into a Lazy construct and use value to get the wrapped value.

This is what is done in the genericTransformer:

implicit def genericTransformer[A, B, BRepr <: HList](implicit
  generic: LabelledGeneric.Aux[B, BRepr],
  transform: Lazy[Transformer[A, BRepr]]
): Transformer[A, B] = new Transformer[A, B] {
  override def apply(a: A): B = generic.from(transform.value(a))
}

Cats

Cats was introduced to deal with repeated or optional fields. It is used for the functorTransformer.
This transformer can turn any F[A] into an F[B] given that F is a functor (we can map over it) and a transformer from A to B is available.

implicit def functorTransformer[F[_], A, B](implicit
  functor: Functor[F],
  transform: Transformer[A, B]
): Transformer[F[A], F[B]] = new Transformer[F[A], F[B]] {
  override def apply(a: F[A]): F[B] = functor.map(a)(transform.apply)
}

That’s why you then need to import cats.instances.all._ when you use Fluent. You can of course be more specific and import only the cats instances you need.

DeepHLister

The DeepHLister comes in handy when transforming nested case classes into a flatter one. Let’s consider this use case:

case class Cylinder(origin: Point, radius: Double, height: Double, colour: String)

If we want to turn a Cylinder into a Circle we need to get the x and y inside the Point.

If we use a LabelledGeneric to get the List for the Cylinder we get something like:

Point  with KeyTag[Symbol with Tagged[String("origin")],Point]  :: 
Double with KeyTag[Symbol with Tagged[String("radius")],Double] ::
Double with KeyTag[Symbol with Tagged[String("height")],Double] ::
String with KeyTag[Symbol with Tagged[String("colour")],String] ::
HNil

There is no x and y available here. For that we need to further expand Point into

Double with KeyTag[Symbol with Tagged[String("x")],Double] ::
Double with KeyTag[Symbol with Tagged[String("y")],Double] ::
HNil

but we’d like to get a “deep” HList for our Cylinder in order to get something like

Double with KeyTag[Symbol with Tagged[String("x")],Double] ::
Double with KeyTag[Symbol with Tagged[String("y")],Double] :: 
Double with KeyTag[Symbol with Tagged[String("radius")],Double] ::
Double with KeyTag[Symbol with Tagged[String("height")],Double] ::
String with KeyTag[Symbol with Tagged[String("colour")],String] ::
HNil

This is the job of our DeepHLister. It is inspired by this example and adapted to work with LabelledGeneric and flatten the resulting HList using hlist’s Prepend operation.

Conclusion

This is a rather long post but hopefully it gives a pretty good understanding of Fluent implementation and how it uses Shapeless’s generic programming to derive Transformer type class instances.

Remember that Fluent is still very experimental and won’t cover all possible cases. If you find yourself in such situation you should be able to define your own implicit function or even submit a PR to handle your use case. Any contribution is welcomed!