Tutorial

This tutorial is intentionally structured like the Free monad tutorial for cats so that a side-by-side comparison of the 2 approaches is possible.

Study your topic

Let’s imagine that we want to create a DSL for a key-value store. We want to be able to do three things with keys:

The idea is to write a sequence of these operations in the embedded DSL as a “program”, interpret the “program”, and finally execute the “program” to interact with the actual key-value store.

For example:

 put("toto", 3)
 get("toto") // returns 3
 delete("toto")

But we want:

Create an ADT representing your grammar

ADT stands for “Algebraic Data Type”. In this context, it refers to a closed set of types which can be combined to build up complex, recursive values.

We need to create an ADT to represent our key-value operations:

// the type parameter A can be read as the type of value returned by the operation
  sealed trait KVStore[+A]

  case class Put[T](key: String, value: T) extends KVStore[Unit]
  case class Get[T](key: String) extends KVStore[Option[T]]
  case class Delete(key: String) extends KVStore[Unit]

Free your ADT

There are four basic steps to “freeing” the ADT:

  1. Create smart constructors for KVStore[_] using Eff.send
  2. Build a program out of key-value DSL operations
  3. Build an interpreter for programs of DSL operations
  4. Execute our interpreted program
  5. [optional] add some syntax for the interpreter

Create smart constructors using Eff.send

These methods will let you create Eff values for your key-value store “Effect”:

  import org.atnos.eff._

// T |= R is an alias for MemberIn[T, R]
// stating that effects of type T[_] can be injected in the effect stack R
// It is also equivalent to MemberIn[KVStore, R]
  type _kvstore[R] = KVStore |= R

  /** store returns nothing (i.e. Unit) */
  def store[T, R: _kvstore](key: String, value: T): Eff[R, Unit] =
    Eff.send[KVStore, R, Unit](Put(key, value))

  /** find returns a T value if the key exists */
  def find[T, R: _kvstore](key: String): Eff[R, Option[T]] =
    Eff.send[KVStore, R, Option[T]](Get(key))

  /** delete returns nothing (i.e. Unit) */
  def delete[T, R: _kvstore](key: String): Eff[R, Unit] =
    Eff.send(Delete(key))

  /** update composes get and put, and returns nothing. */
  def update[T, R: _kvstore](key: String, f: T => T): Eff[R, Unit] =
    for {
      ot <- find[T, R](key)
      _ <- ot.map(t => store[T, R](key, f(t))).getOrElse(Eff.pure(()))
    } yield ()

Each method requires the KVStore effect to be a member of an “effect stack” R. The return values are of type Eff[R, A] where R is a stack of effects possibly containing other effects than key-value store operations and yielding values of type A.

Build a program

Now that we can construct values with KVStore effects we can use our DSL to write “programs” using a for-comprehension:

  import org.atnos.eff._

  def program[R: _kvstore]: Eff[R, Option[Int]] =
    for {
      _ <- store("wild-cats", 2)
      _ <- update[Int, R]("wild-cats", _ + 12)
      _ <- store("tame-cats", 5)
      n <- find[Int, R]("wild-cats")
      _ <- delete("tame-cats")
    } yield n

This looks like a monadic flow. However, it just builds a recursive data structure representing the sequence of operations.

Write an interpreter for your program

As you may have understood now, Eff is used to create an embedded DSL. By itself, this DSL only represents a sequence of operations (defined by a recursive data structure); it doesn’t produce anything.

Eff is a programming language inside your programming language!

So, like any other programming language, we need to interpret our abstract language into concrete values.

To do this, we will use an interpreter transforming our KVStore effects using a simple mutable map:

  import org.atnos.eff._
  import interpret._
  import cats.Traverse
  import cats.syntax.all._
  import scala.collection.mutable._

  /**
 * Unsafe interpreter for KVStore effects
 *
 * the program will crash if a type is incorrectly specified.
 *
 * The interpreter requires the KVStore effect to be a Member of R (with <=)
 * Meaning that we can statically know the resulting type once we have removed
 * KVStore from R, and this type is m.Out.
 *
 * The interpreter uses the `interpretUnsafe` method from `org.atnos.eff.Interpreter` to implement a
 * stack-safe interpretation of effects as a side-effect.
 *
 * `interpretUnsafe` needs the definition of a side-effect where
 * we get each `KVStore[X]` effect, run side-effects and return a value `X`.
 *
 * The resulting effect stack is m.Out which is R without the KVStore effects
 *
 */
  def runKVStoreUnsafe[R, A](effects: Eff[R, A])(implicit m: KVStore <= R): Eff[m.Out, A] = {
    // a very simple (and imprecise) key-value store
    val kvs = Map.empty[String, Any]

    val sideEffect = new SideEffect[KVStore] {
      def apply[X](kv: KVStore[X]): X =
        kv match {
          case Put(key, value) =>
            println(s"put($key, $value)")
            kvs.put(key, value)
            ()

          case Get(key) =>
            println(s"get($key)")
            kvs.get(key)

          case Delete(key) =>
            println(s"delete($key)")
            kvs.remove(key)
            ()
        }

      def applicative[X, Tr[_]: Traverse](ms: Tr[KVStore[X]]): Tr[X] =
        ms.map(apply)
    }
    interpretUnsafe(effects)(sideEffect)(m)

  }

Please note this interpreter is impure – it mutates kvs and also produces logging output using println. The whole purpose of functional programming isn’t to prevent side-effects, it is just to push side-effects to the boundaries of your system in a well-known and controlled way.

We can also interpret KVStore effects differently and delegate the results to other effects in the same stack:

  import org.atnos.eff._
  import org.atnos.eff.either._
  import org.atnos.eff.writer._
  import org.atnos.eff.state._
  import org.atnos.eff.interpret._
  import cats.syntax.all._
  import cats.data._

  type _writerString[R] = Writer[String, *] |= R
  type _stateMap[R] = State[Map[String, Any], *] |= R

  /**
 * Safe interpreter for KVStore effects
 *
 * It uses the following effects:
 *
 *  - Writer to create log statements
 *  - State to update a key-value Map
 *  - Either to raise errors if the type of an object in the map is not of the expected type
 *
 *  The resulting effect stack is U which is R without the KVStore effects
 *
 *  Note that we just require the Throwable, Writer and State effects to
 *  be able to be created in the stack U
 *
 * This interpreter uses the org.atnos.eff.interpreter.translate method
 * translating one effect of the stack to other effects in the same stack
 *
 *
 * NOTE:
 * - It is really important for type inference that the effects for U are listed after those for R!
 *
 * Implicit member definitions will NOT be found with the following definition:
 *
 * def runKVStore[R, U :_throwableEither :_writerString :_stateMap, A](effects: Eff[R, A]) (
 *   implicit m: Member.Aux[KVStore, R, U]): Eff[U, A] = {
 *
 */
  def runKVStore[R, U, A](
    effects: Eff[R, A]
  )(implicit m: Member.Aux[KVStore, R, U], throwable: _throwableEither[U], writer: _writerString[U], state: _stateMap[U]): Eff[U, A] = {

    translate(effects)(new Translate[KVStore, U] {
      def apply[X](kv: KVStore[X]): Eff[U, X] =
        kv match {
          case Put(key, value) =>
            for {
              _ <- tell(s"put($key, $value)")
              _ <- modify((map: Map[String, Any]) => map.updated(key, value))
              r <- fromEither(Either.catchNonFatal(()))
            } yield r

          case Get(key) =>
            for {
              _ <- tell(s"get($key)")
              m <- get[U, Map[String, Any]]
              r <- fromEither(Either.catchNonFatal(m.get(key)))
            } yield r

          case Delete(key) =>
            for {
              _ <- tell(s"delete($key)")
              _ <- modify((map: Map[String, Any]) => map - key)
              r <- fromEither(Either.catchNonFatal(()))
            } yield r
        }
    })
  }

Eff is just a recursive structure that can be seen as sequence of operations producing other operations, with potentially other effects. In this way it is similar to folding a List. We often use folds (e.g. foldRight) to obtain a single value from a list; this recurses over the structure, combining its contents.

The idea behind an Eff interpreter is exactly the same. We “fold” the recursive structure by:

An important aspect of interpreters is stack-safety. An interpreter evaluates each step of a computation on the stack then calls itself to evaluate the other steps. The org.atnos.eff.interpreter object provides various methods helping you write a stack-safe interpreter:

Run your program

The final step is naturally running your program after interpreting it to another Eff value. We need to

Like this:

      import org.atnos.eff._, syntax.all._

// run the program with the unsafe interpreter
      runKVStoreUnsafe(program[Fx.fx1[KVStore]]).run

> Some(14)

With the safe interpreter, the process is the same and we need to

Like that:

      import org.atnos.eff._, syntax.all._
      import cats._, data._

// run the program with the safe interpreter
      type Stack = Fx.fx4[KVStore, Either[Throwable, *], State[Map[String, Any], *], Writer[String, *]]

      val (result, logs) =
        runKVStore(program[Stack]).runEither.evalState(Map.empty[String, Any]).runWriter.run

      (result.toString +: logs).mkString("\n")
> Right(Some(14))
put(wild-cats, 2)
get(wild-cats)
put(wild-cats, 14)
put(tame-cats, 5)
get(wild-cats)
delete(tame-cats)

Add some syntax

It is nice to be able to “chain” run methods with this additional piece of syntax:

      implicit class KVStoreOps[R, A](effects: Eff[R, A]) {
        def runStore[U](implicit
          m: Member.Aux[KVStore, R, U],
          throwable: _throwableEither[U],
          writer: _writerString[U],
          state: _stateMap[U]
        ): Eff[U, A] =
          runKVStore(effects)
      }

      val (result, logs) =
        program[Stack].runStore.runEither.evalState(Map.empty[String, Any]).runWriter.run

      (result.toString +: logs).mkString("\n")
> Right(Some(14))
put(wild-cats, 2)
get(wild-cats)
put(wild-cats, 14)
put(tame-cats, 5)
get(wild-cats)
delete(tame-cats)

Composing ADTs with the Eff monad

Real world applications often time combine different algebras. The typelevel set of effects R in Eff[R, A] lets us compose different algebras in the context of Eff.

Let’s see a trivial example of unrelated ADT’s getting composed that can form a more complex program. First you define your ADTs with smart constructors:

  import org.atnos.eff._
  import all._

  sealed trait Interact[A]

  case class Ask(prompt: String) extends Interact[String]
  case class Tell(msg: String) extends Interact[Unit]

  type _interact[R] = Interact |= R

  def askUser[R: _interact](prompt: String): Eff[R, String] =
    send(Ask(prompt))

  def tellUser[R: _interact](message: String): Eff[R, Unit] =
    send(Tell(message))

  sealed trait DataOp[A]

  type _dataOp[R] = DataOp |= R

  case class AddCat(a: String) extends DataOp[Unit]
  case class GetAllCats() extends DataOp[List[String]]

  def addCat[R: _dataOp](a: String): Eff[R, Unit] =
    send(AddCat(a))

  def getAllCats[R: _dataOp]: Eff[R, List[String]] =
    send(GetAllCats())

Then you simply require your program to have MemberIn instances for those effects:

  import org.atnos.eff._

  def program[R: _interact: _dataOp]: Eff[R, Unit] =
    for {
      cat <- askUser("What's the kitty's name?")
      _ <- addCat(cat)
      cats <- getAllCats
      _ <- tellUser("Current cats: " + cats.mkString(", "))
    } yield ()

Finally we write one interpreter per ADT:

  import cats._
  import cats.syntax.all._
  import org.atnos.eff._
  import interpret._

  def readLine(): String =
    "snuggles"

  def runInteract[R, A](effect: Eff[R, A])(implicit m: Interact <= R): Eff[m.Out, A] =
    recurse(effect)(new Recurser[Interact, m.Out, A, A] {
      def onPure(a: A): A = a

      def onEffect[X](i: Interact[X]): X Either Eff[m.Out, A] = Left[X, Eff[m.Out, A]] {
        i match {
          case Ask(prompt) =>
            println(prompt)
            readLine()

          case Tell(msg) =>
            println(msg)
        }
      }

      def onApplicative[X, T[_]: Traverse](ms: T[Interact[X]]): T[X] Either Interact[T[X]] =
        Left(ms.map {
          case Ask(prompt) => println(prompt); readLine()
          case Tell(msg) => println(msg)
        })

    })(m)

  def runDataOp[R, A](effect: Eff[R, A])(implicit m: DataOp <= R): Eff[m.Out, A] = {
    val memDataSet = new scala.collection.mutable.ListBuffer[String]

    recurse(effect)(new Recurser[DataOp, m.Out, A, A] {
      def onPure(a: A): A = a

      def onEffect[X](i: DataOp[X]): X Either Eff[m.Out, A] = Left[X, Eff[m.Out, A]] {
        i match {
          case AddCat(a) => memDataSet.append(a); ()
          case GetAllCats() => memDataSet.toList
        }
      }

      def onApplicative[X, T[_]: Traverse](ms: T[DataOp[X]]): T[X] Either DataOp[T[X]] =
        Left(ms.map {
          case AddCat(a) => memDataSet.append(a); ()
          case GetAllCats() => memDataSet.toList
        })
    })(m)

  }

Now if we run our program for a Stack combining both effects and type in “snuggles” when prompted, we see something like this:

      type Stack = Fx.fx2[Interact, DataOp]

      runInteract(runDataOp(program[Stack])).run
What's the kitty's name?
Current cats: snuggles