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.

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

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]
``````

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._, interpret._
import cats.Traverse
import cats.implicits._
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)
().asInstanceOf[X]

case Get(key) =>
println(s"get(\$key)")
kvs.get(key).asInstanceOf[X]

case Delete(key) =>
println(s"delete(\$key)")
kvs.remove(key)
().asInstanceOf[X]
}

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
• `E Either ?` 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.implicits._
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(().asInstanceOf[X]))
} yield r

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

case Delete(key) =>
for {
_ <- tell(s"delete(\$key)")
u <- modify((map: Map[String, Any]) => map - key)
r <- fromEither(Either.catchNonFatal(().asInstanceOf[X]))
} 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

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, Throwable Either ?, 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)``````

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)``````

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._, 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] =

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] =

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?")
cats <- getAllCats
_    <- tellUser("Current cats: "+cats.mkString(", "))
} yield ()``````

Finally we write one interpreter per ADT:

``````import cats._
import cats.implicits._
import org.atnos.eff._, interpret._

"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 {
i match {
println(prompt)

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

def onApplicative[X, T[_] : Traverse](ms: T[Interact[X]]): T[X] Either Interact[T[X]] =
Left(ms.map {
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 {
i match {
case GetAllCats() => memDataSet.toList
}
}

def onApplicative[X, T[_]: Traverse](ms: T[DataOp[X]]): T[X] Either DataOp[T[X]] =
Left(ms.map {
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]))``````
``````What's the kitty's name?
Current cats: snuggles``````