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:

• put a value into the store, associated with its key.
• get a value from the store given its key.
• delete a value from the store given its key.

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:

• the computation to be represented as a pure, immutable value
• to separate the creation and execution of the program
• to be able to support many different methods of execution

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:

• State for maintaining the map of values
• Writer for logging
• Either[E, *] for type errors

  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:

• consuming each operation
• compiling the operation into a target language
• computing next operation

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:

• interpretUnsafe makes you define a SideEffect trait to return a value X from an effect T[X]

• translate makes you define a Translate trait to “translate” your effect into other effects in the same stack

• both are specialized version of interpret1 which makes you define a Recurse trait to either return a value X from an effect or produce another Eff computation

Run your program

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

• specify a concrete stack of effects containing the effect we want to interpret Fx.fx1[KVStore] (just one effect in the stack)
• call our interpreter to get a Eff[NoFx, A] value
• call a final run to get an A value

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

• specify an effect stack definition with all the effects
• call our “safe” interpreter
• call interpreters for all the other effects, including the final NoFx effect with run

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