Introduction to Tagless final

In this previous post we’ve seen that before using Scala’s Future it might be worth taking some time to think of the use cases (especially error cases), the execution model we need, … as it might be more advantageous to choose a solution like Monix’s Task (although not available in standard library) to gain finer control over the execution. However some might not be able to make a decision at this stage and like to keep their options open. Let’s see how we can revisit our product repository in such way that we don’t have to make a decision too early.

Remember our repository looked something like this:

trait ProductRepository {
  def findProduct(
    productId: ProductId
  )(implicit executor: ExecutionContext): Future[Option[Product]]
   
  def saveProduct(
    product: Product
  )(implicit executor: ExecutionContext): Future[Unit]
   
  def incrementProductSells(
    productId: ProductId, 
    quantity: Int
  )(implicit executor: ExecutionContext): Future[Unit]
   
  // More methods ...
}

Now let’s remove anything related to Future (including the ExecutionContext) but we don’t want to have blocking calls either so we introduce a type parameter M and we will decide later whether M is actually a Future or a Task or something else.

trait ProductRepository[M[_]] {
  def findProduct(productId: ProductId): M[Option[Product]]
  def saveProduct(product: Product): M[Unit]
  def incrementProductSells(productId: ProductId, quantity: Int): M[Unit]
  // More methods ...
}

We can now start to write our program so that it looks like something like this

import cats.Monad

class Program[M[_] : Monad](repo: ProductRepository[M]) {
  def renameProduct(id: ProductId, name: String): M[Option[Product]] =
    repo
      .findProduct(productId = id)
      .flatMap {
        case Some(p) => 
          val renamed = p.copy(name = name)
          repo.saveProduct(renamed) map (_ => Some(renamed))
        case None => 
          Monad[M].pure(None)
      }
}

Nothing to complicated here. We look up a product, then change its name and save it back.

So far we haven’t impose any constraint on our type constructor M. However we now need to compose different M together with the flatMap operation. In order to do it we specify that M needs to be a monad.

We could also have imposed this constraint on the ProductRepository trait itself (only works in Scala3/Dotty as earlier versions don’t support trait with parameters):

trait ProductRepository[M[_] : Monad] {
 // ...
}

Now that M is a monad we can even increment sell counts for list of products using the traverse operation.

Monad[M].traverse(products)(p => repo.incrementProductSells(p.id, p.quantity))

Since we don’t know what M is we can’t reason about what happens here. E.g. Are all the increments triggered in parallel or sequentially? It all depends on which monad we choose for M to be.

We can write the whole program this way. However we have to make a decision at some point. In order to run the program we must choose what M is.

We have to make this decision when we write a concrete instance of the ProductRepository trait.

If we choose Scala Future to implement the ProductRepository we would have something like

import scala.concurrent.Future

// we need an ExecutionContext in scope
import scala.concurrent.ExecutionContext.Implicits.global

val productRepoWithFuture: ProductRepository[Future] = 
  new ProductRepository[Future]{
    def findProduct(productId: ProductId): Future[Option[Product]] = {
      // lookup product in repo
      Future.successful(Some(Product(productId, "Default product")))
    }
    def saveProduct(product: Product): Future[Unit] = {
      // save product in repo
      Future.successful(())
    }
    def incrementProductSells(productId: ProductId, quantity: Int): Future[Unit] {
      // increment sells count in repo
      Future.successful(())
    }
    // More methods ...
  }

or we could have used Monix’s Task

import monix.eval.Task

val productRepoWithTask: ProductRepository[Task] = 
  new ProductRepository[Task]{
    def findProduct(productId: ProductId): Task[Option[Product]] = {
      // lookup product in repo
      Task.now(Some(Product(productId, "Default product")))
    }
    def saveProduct(product: Product): Future[Unit] = {
      // save product in repo
      Task.unit
    }
    def incrementProductSells(productId: ProductId, quantity: Int): Task[Unit] {
      // increment sells count in repo
      Task.unit
    }
    // More methods ...
  }

We could also have used blocking calls by using the Id monad which is defined as

type Id[A] = A

val productRepoWithId: ProductRepository[Id] = 
  new ProductRepository[Id]{
    def findProduct(productId: ProductId): Id[Option[Product]] = {
      // lookup product in repo
      Some(Product(productId, "Default product"))
    }
    def saveProduct(product: Product): Id[Unit] = {
      // save product in repo
      ()
    }
    def incrementProductSells(productId: ProductId, quantity: Int): Task[Unit] {
      // increment sells count in repo
      ()
    }
    // More methods ...
  }

This is certainly not something we want to use in production however it might turn quite useful for testing as it avoids to deal with Futures in our test cases.

Execution

In order to run our program we just need to pass the right implementation (a.k.a. interpreter) into our program instance:

// using Future interpreter
val futureProg = new Program(productRepoWithFuture)
val future: Future[Option[Product]] = 
  futureProg.renameProduct(123, "Future product")

// using Task interpreter
val taskProg = new Program(productRepoWithTask)
val task: Task[Option[Product]] =
  taskProg.renameProduct(123, "Task product")

// using Id interpreter
val idProg = new Program(productRepoWithId)
val prod = idProg.renameProduct(123, "Id product")

As you can see by parameterising our algebra we gain more flexibility as we can choose which implementation to use to run our program. This technique is called “Tagless final”.

Combining algebras

Our ProductRepository defines an algebra. In order to write any “serious” program we need to combine multiple algebras.

In our toy example let’s add a simple algebra for logging:

trait Logger[M[_]] {
  def info(msg: => String): M[Unit]
  def error(msg: => String): M[Unit]
}

Similarly we can write interpreters for this algebra:

val futureLogger: Logger[Future] =
  new Logger[Future] {
    override def info(msg: => String): Future[Unit] =
      Future.successful(println(s"[INFO ] $msg"))
    override def error(msg: => String): Future[Unit] =
      Future.successful(println(s"[ERROR] $msg"))
  }

We can then modify the ProductRepository to take a Logger and logs its actions.

class ProductRepoFutureInterpreter(logger: Logger[Future]) 
extends ProductRepository[Future] {
  override def findProduct(productId: ProductId): Future[Option[Product]] = {
    // lookup product in repo
    for {
      _ <- logger.info(s"Looking up product $productId")
      // in real implementation there would be a database call 
      // returning a Future instead of Future.successful
      prod <- Future.successful(Some(Product(productId, "Default product")))
    } yield prod
  }
  override def saveProduct(product: Product): Future[Unit] = {
    // save product in repo
    for {
      _ <- logger.info(s"Saving product ${prod.id}: ${prod.name}")
      // in real implementation there would be a database call 
      // returning a Future instead of Future.successful
      _ <- Future.successful(())
    } yield ()
  }
  override def incrementProductSells(productId: ProductId, quantity: Int): Future[Unit] {
    // increment sells count in repo
    for {
      _ <- logger.info(s"Incrementing sells for product $productId by $quantity")
      // in real implementation there would be a database call 
      // returning a Future instead of Future.successful
      _ <- Future.successful(())
    } yield ()
  }
  // More methods ...
}

As long as both interpreters are using the same monad, it’s quite trivial to combine them together (we just need to use flatMap to chain the computations together – or use a for-comprehension as above).

Combining interpreters of different types

Now imagine that our Logger interpreter use blocking calls (as it’s often the case with logging frameworks). In this case we use the Id monad and the implementation is straight forward:

val logger: Logger[Id] =
  new Logger[Id] {
    override def info(msg: => String): Id[Unit] = 
      println(s"[INFO ] $msg")
    override def error(msg: => String): Id[Unit] = 
      println(s"[ERROR] $msg")
  }

Now if we want to use this Logger[Id] we would need to turn Ids into Futures so that we can use them in for-comprehension.

class ProductRepoFutureInterpreter(logger: Logger[Id]) 
extends ProductRepository[Future] {
  override def findProduct(productId: ProductId): Future[Option[Product]] = {
    // lookup product in repo
    for {
      _ <- logger.info(s"Looking up product $productId").toFuture
      // in real implementation there would be a database call 
      // returning a Future instead of Future.successful
      prod <- Future.successful(Some(Product(productId, "Default product")))
    } yield prod
  }
  override def saveProduct(product: Product): Future[Unit] = {
    // save product in repo
    for {
      _ <- logger.info(s"Saving product ${prod.id}: ${prod.name}").toFuture
      // in real implementation there would be a database call 
      // returning a Future instead of Future.successful
      _ <- Future.successful(())
    } yield ()
  }
  override def incrementProductSells(productId: ProductId, quantity: Int): Future[Unit] {
    // increment sells count in repo
    for {
      _ <- logger.info(s"Incrementing sells for product $productId by $quantity").toFuture
      // in real implementation there would be a database call 
      // returning a Future instead of Future.successful
      _ <- Future.successful(())
    } yield ()
  }
  // More methods ...
}

implicit class IdToFuture[A](a: Id[A]) {
  def toFuture: Future[A] = Future.successful(a)
}

In order to turn an Id into a Future we have defined an implicit class that adds a toFuture method (which just wraps the value into a Future.successful).

Should we have used Task we would have an implicit class IdToTask. Let’s make this implicit class more generic so that we can turn any monad F into a monad G.

import cats.~>
implicit class NaturalTransformation[F[_], A](fa: F[A]) {
  def liftTo[G[_]](implicit transform: F ~> G): G[A] = 
    transform(fa)
}

Basically this code says that given a natural transformation F ~> G we can turn any F[A] into a G[A] and it provides a liftTo method to do so.

All we have to do is replace toFuture by liftTo[Future] in our product repository interpreter.

Turning an Id into a monad (such as Future) is also strait forward:

implicit def idToMonad[M[_] : Monad] = new (Id ~> M) {
  override def apply[A](a: Id[A]): M[A] = Monad[M].pure(a)
}

Building an algebra stack

An interpreter doesn’t have to perform an effect right away (e.g. making a database call). It can instead translate the instruction into a lower-level algebra.

For example our product repository can be backed by a key-value store defined with its own algebra

trait KeyValueStore[M[_]] {
  def get[K, V](key: K): M[Option[V]]
  def put[K, V](key: K, value: V): M[Unit]
}

We can then have an interpreter for the product repository which generate a set of Key-Value store instructions:

def productRepository[M[_]](store: KeyValueStore[M]): ProductRepository[M] =
  new ProductRepository[M] {
    def findProduct(productId: ProductId): M[Option[Product]] = {
      store.get(productId)
    }
    def saveProduct(product: Product): M[Unit] = {
      store.put(product.id, product)
    }
    // More methods ...
  }

This actually transforms the product repository algebra into the key-value store API but doesn’t perform any actions. For that we need an interpreter for the key-value store:

val keyValueStore: KeyValueStore[Id] = 
  new KeyValueStore[Id] {
    private var store: Map[Any, Any] = Map()
    override def get[K, V](key: K): Id[Option[V]] = 
      store.get(key).map(_.asInstanceOf[V])
    override def put[K, V](key: K, value: V): Id[Unit] = 
      store += (key -> value)
  }

and we can now simply create a product repository instance:

val productRepo: ProductRepository[Id] = productRepository(keyValueStore)

A more complex example

Interpreters can be combined in a similar fashion as it can be done with the Free monad. So let’s take the warehouse example we’ve used in the Free monad series and see how it goes using “tagless final”.

This example “inbounds” a purchase order and increments the stock available inside the warehouse. It involves several algebras:

• A stock service which creates and moves stock inside the warehouse.

  trait Stock[F[_]] {
    def poContent(poId: PurchaseOrderId): F[Map[ProductId, Int]]
    def createStock(productId: ProductId, locationId: LocationId, quantity: Int): F[Unit]
    def moveStock(productId: ProductId, source: LocationId, destination: LocationId, quantity: Int): F[Unit]
  }
  

• An inventory service which increments and decrements stock at specific locations. The stock service implementation relies on the inventory service.

  trait Inventory[F[_]] {
      def increment(locationId: LocationId, productId: ProductId, quantity: Int): F[Unit]
      def decrement(locationId: LocationId, productId: ProductId, quantity: Int): F[Unit]
    }
  

• A key-value store used to keep track of the products inventory in the warehouse. The inventory service is backed by a key-value store.

  trait Storage[F[_]] {
    def get[K, V](key: K): F[Option[V]]
    def put[K, V](key: K, value: V): F[Unit]
  }
  

• Finally there is a logging algebra used to print the program execution on the console. The console algebra is used at different levels of the stack.

  trait Logging[F[_]] {
    def error(message: String): F[Unit]
    def info(message: String): F[Unit]
  }
  

This is how our program combines the different algebras

To make it look more interesting I’ve used interpreters based on different monads. The Logging interpreter is based on the Id monad, while the key-value store uses Future.

val consoleLogger = new Logging[Id] {
  override def error(message: String): Id[Unit] =
    println(s"[ERROR] $message")
  override def info(message: String): Id[Unit] =
    println(s"[INFO ] $message")
}

val keyValueStore = new Storage[Future] {
  var store = Map.empty[Any, Any]
  override def get[K, V](key: K): Future[Option[V]] =
    Future.successful(store.get(key).asInstanceOf[Option[V]])
  override def put[K, V](key: K, value: V): Future[Unit] =
    Future.successful(store += key -> value)
}

We can keep all the interpreter from the upper layers abstract (i.e. accept any Monad) and only provide a concrete implementation at the lowest level.

For example the inventory interpreter converts (or compiles) Inventory instructions into Logging and Storage instructions.

def inventory[F[_], G[_], H[_]](
  logger: Logging[F],
  store: Storage[G]
)(implicit
  storeM: Monad[G],
  transToG: F ~> G,
  transToH: G ~> H
) = new Inventory[H] {
  private def stockAt(locationId: LocationId, productId: ProductId): G[Int] =
    storeM.map(store.get[(LocationId, ProductId), Int](locationId -> productId))(_ getOrElse 0)

  override def increment(locationId: LocationId, productId: ProductId, quantity: Int): H[Unit] = {
    import cats.Monad.ops._
    for {
      _ <- logger.info(s"Add $quantity $productId at $locationId").liftTo[G]
      existing <- stockAt(locationId, productId)
      _ <- store.put(locationId -> productId, existing + quantity)
    } yield ()
    }.liftTo[H]

  override def decrement(locationId: LocationId, productId: ProductId, quantity: Int): H[Unit] = {
    import cats.Monad.ops._
    for {
      _ <- logger.info(s"Remove $quantity $productId from $locationId").liftTo[G]
      existing <- stockAt(locationId, productId)
      _ <- store.put(locationId -> productId, existing - quantity)
    } yield ()
  }.liftTo[H]
}

It turns out that deriving natural transformation is not too hard either. All I needed was:

import cats.instances.future._

implicit def identityTransform[T[_]] = new (T ~> T) {
  override def apply[A](fa: T[A]): T[A] = fa
}
implicit def monadTransform[T[_] : Monad] = new (Id ~> T) {
  override def apply[A](a: Id[A]): T[A] = Monad[T].pure(a)
}

If you’re interested you can have a look at the whole example in this gist.

A word on stack-safety

Tagless-final is quite a natural way to gain maximum flexibility when working with monads. However unlike the Free monad it might not be stack-safe. It all depends of the monad chosen in the interpreter. Obviously the Id monad isn’t stack-safe but Future or Task are.

It’s also possible to use a Trampoline instead of the Id monad to ensure stack-safety. (It’s possible to use Monix’s Task with a specific Scheduler to have something similar to a Trampoline).

Conclusion

I kind of feel that “tagless final” is much more easy to grasp than the Free monad. It seems to me a natural thing to do when working with monads and ensuring a maximum flexibility.

Like the Free monad it keeps the implementation details away from the business logic which makes any evolution smoother. (Ever had to change your persistent store? What if you only have to change one interpreter and leave the business logic untouched? It certainly sounds less risky).

Finally you have to keep an eye on the stack-safety as “tagless final” doesn’t guarantee stack-safety. It all depends on the chosen monad to run the program.

In terms of performance it all boils down to the same conclusion: It depends on the implementation. However it seems more efficient than the Free monad which instantiates more objects to run (especially CoProduct instances when combining algebras).