Tagless Final Notes

notes.md

Tagless Final

A bit of theory

• Functional programming

  • Separation of 3 parts: operations, programs, and interpreters
  • Push side-effect (anything that's not referentially transparent) to the outside of the program
  • Keep the core of the program pure

• Based on Church encoding

  • Use functions to represent data and operators, i.e. boolean, list, etc
  • Named after Alonzo Church - creator of Lambda calculus

• Not new

  • CS Paper on 2009: http://okmij.org/ftp/tagless-final/index.html#tagless-final

Why?

• Functional programming

  • Separation of 3 parts: operations, programs, and interpreters
  • Push side-effect (anything that's not referentially transparent) to the outside of the program
  • Keep the core of the program pure

• Blends OOP and FP nicely

  • OOP: adds new operation easily
  • FP: adds new result/effect easily

• Performance considerations

  • Comparable to OO approach - minimal overhead.
  • Less memory allocation compared to FP Free Monad technique.

• Simplest abstraction possible for both OOP and FP programmers

  • http://www.lihaoyi.com/post/StrategicScalaStylePrincipleofLeastPower.html

• Easier to test!

  • Test-only interpreter to test the program
  • Test the individual operation available to the interpreter independently

How: Tagless Final in Scala

Define your operations (or Algebraic data type)

trait UserAlgebra[F[_]] {
  def findById(input: UserId): F[User]
  def deleteUser(user: User): F[Done] = ???
}

• Two abstractions: trait and the F[_]
• The trait allows:
  • Swapping the implementation (i.e. interpreter).
  • Adding new operations via extends.
• The F[_] allows:
  • Swapping the result, i.e. Try vs Future vs Scalaz's Task vs Cat's IO.
  • Constraint: F[_] must have the flatMap(f: A => F[B]): F[B] method.

Define the interpreter

class UserServiceClientInterpreter extends UserAlgebra[Future] {
  def findById(input: UserId): Future[User] = ???
  def deleteUser(user: User): Future[Done] = ???
}

Also if DryRun is our own type - a "box" (i.e. monad) which has flatMap():

class UserDryRunInterpreter extends UserAlgebra[DryRun] {
  def findById(input: UserId): DryRun[User] = ???
  def deleteUser(user: User): DryRun[Done] = ???  
}

• This is where the side-effecting functions live.
• Also:
  • State
  • Config
  • Dependencies (easiest if injected via constructor)

Define the program

import cats.Monad

class Program[F[_] : Monad](a: UserAlgebra[F]) {
  def deleteUser(input: UserId): F[Done] = {
    import a._

    for {
      user <- findById(input)
      result <- deleteUser(user)
    } yield result
  }
}

• This is where the "pure" core of the program should be.

  • i.e. swap the interpreter, program logic doesn't change.

• Program above relies on Cats library to implicitly convert F[_] into an instance of Monad that has flatMap() method.

• Program can also "commit" on a type of result so no implicit conversions to Monad required.

  • "Almost" tagless final :-P

class Program(a: UserAlgebra[Future]) {
  def deleteUser(input: UserId): Future[Done] = {
    import a._

    for {
      user <- findById(input)
      result <- deleteUser(user)
    } yield result
  }
}

Does this actually work?

Yes!

Hadoop Migration - generate Help Center Article feature

• Algebra
• Interpreter + test
• Program + test

Also Partition Delta, Snapshot & Rich Audit functionality is running on prod without overhead from the tagless final approach.

Questions

Different "boxes"

trait Foo[F[_], M[_]] {
  def doThis(): F[String]
  def doThat(): M[Long]
}

Different "shapes"

What if I have different shape, i.e. List[Future[Option[User] but I must return Future[List[User]]] assuming the interpreter is has Future as its result?

Unpack the box from outside in.

• Use Future.sequence so that: List[Future[X]] => Future[List[X]]
  • Internally uses foldLeft (Scala Red Book Chapter 3) to traverse & collect the result from the list.
• Use List.flatten so that: List[Option[X]] => List[X]

class UserInterpreter extends UserAlgebra[Future] {
  def search(input: SearchTerms): Future[User] = {
    val result: List[Future[Option[User]]] = _
    
    for {
      list <- Future.sequence(result)
    } yield list.flatten
  }
}

Different interpreters

Compose:

trait Storage[F[_]] {
  def get[K, V](k: K): F[V]
  def put[K, V](k: K, v: V): F[V]
}

trait ProductRepo[G[_]] {
  def storage: Storage[G]
  
  def getProduct(id: ProductId): G[Product] = storage.get(id)
}

class MyProductRepo(val storage: Storage[Future]) extends ProductRepo[Future]

Or extend (afaik, this won't be possible with Free Monad FP approach):

trait ProductRepo[G[_]] extends Storage[G] {
  def getProduct(id: ProductId): G[Product] = get(id)
}

Stateful interpreter

trait StatefulAlgebra[F[_]] {
  def state: F[State]
  def lockUser(input: UserId): (F[Locked], StatefulAlgebra[F])
}

• Note the StatefulAlgebra[F] in the return.
• Returned instance of the interpreter carries the new state.
• Program can choose to continue with returned instance (with the new state), or not.
• Good fit for FSM-like situation, i.e. when using Akka Actor to model state.

References

• Scala Days 2018 - Functional Interpreters and You
• Scala Days 2017 - Uniting Church and State
• Chris Birchall - Free vs Tagless Final
  • Sample code: https://github.com/cb372/free-vs-tagless-final