Skip to content

Instantly share code, notes, and snippets.

@b-studios
Last active Feb 18, 2019
Embed
What would you like to do?
Idiomatic Handlers

Note: This is very much WIP. An updated version is based on nesting freer and free-ap (as in Haxl) (4)

This document describes the basic idea behind idiomatic effect handlers in Scala Effekt (1). The repo contains a draft of the API, a quick&dirty implementation, and some examples.

Overall Idea (TLDR)

The idea behind Idiomatic Effect Handlers is threefold:

  1. Replace applicatives by idiom handlers like monadic handlers replace monads
  2. Allow to combine idiomatic computation and monadic computation while restricting which handlers can be applied (i.e. a monadic handler can be applied to both an idiomatic program and a monadic program. An idiomatic handler can only be applied to an idiomatic program)
  3. Convert idiomatic handlers into monadic handlers by providing a translation function (i.e. for an answertype R that the handler can choose: forall X. G[X] => (X => C[R]) => C[R])

The type X is the type of the position in the stack where flatMap is called for the first time on an otherwise idiomatic program. Everything builds up on the observation that the stack has the following shape:

     Top of the stack.
|       |               |
+-------+---------------|
|  op() |      k1       |  idiomatic fragment of the stack: G[X]
|  ...  | map2(...)     |                                  
+-------+---------------+                                  
| flatMap(f1: X -> ...) |                                  
| flatMap(f2)           |  monadic fragment of the stack: X => C[R]
|        ...            |
|-----------------------|
|   handler at type R   | C[R]
|-----------------------|
|        ...            |
=========================

Idiomatic and Monadic Programs

Let us dive in and revisit the github example from Markus Hauck (2).

def allUsers(owner: Owner, repo: Repo): C[List[(Issue,List[(Comment,User)])]] using Github = for {
  issues <- Github.listIssues(owner,repo)

  // idiomatic subcomputation
  issueComments <- issues.traverse(issue => Github.getComments(owner,repo,issue).map((issue,_)))

  // idiomatic subcomputation
  users <-
    issueComments.traverse { case (issue,comments) =>
      comments.traverse(comment =>
        Github.getUser(comment.user).map((comment,_))).map((issue,_))
    }
} yield users

The basic idea is, that there are two different kinds of programs: idiomatic programs (Idiom[T] or I[T]) and monadic programs (Control[T] or C[T]). Programs always start out being idiomatic, until flatMap is called for the first time. This (potentially) introduces a data / control flow dependency and thus makes the program monadic.

Example (3)

Some effect signatures:

trait Tick { def tick(): I[Unit] }
def Tick: Tick using Tick = implicit t => t

trait Put { def put(n: Int): I[Unit] }
def Put: Put using Put = implicit p => p

trait Get { def get(): I[Int] }
def Get: Get using Get = implicit g => g

A simple idiomatic program:

//    I for "idiomatic"   
//         v
val iprog: I[Int] using Tick and Get = 
  Tick.tick() *> Tick.tick() *> Get.get()

Using flatMap turns it into a monadic program:

//    C for the "normal control->Monad<"
//         v
val mprog: C[Unit] using Tick and Get and Put =
  iprog flatMap Put.put

Note that I[R] <: C[R].

Revisiting the github example, we can assign the following types:

//   v--- monadic
res: C[...] = for {
  //  v----- idiomatic
  i1: I[...] = Github.listIssues(owner,repo)
  issues <- i1
  i2: I[...] = issues.traverse(issue => Github.getComments(owner,repo,issue).map((issue,_)))
  issueComments <- i2
  i3: I[...] = issueComments.traverse { case (issue,comments) =>
      comments.traverse(comment =>
        Github.getUser(comment.user).map((comment,_))).map((issue,_))
    }
  users <- i3      
} yield users

The individual fragments i1, i2, and i3 of the program are idiomatic. The overall program is monadic (C[...]).

Handling Effects

Idiomatic programs take some expressivity from the user (the program writer) and hand it to the handler implementor.

In particular, the signature of idiomatic handlers looks like the following:

trait Idiomatic {
  // the handler implementor can pick the G
  type G[_]

  // G needs to be pointed.
  def unit[R]: R => G[R]

  // G needs to be a functor.
  def map[A, B]: (A => B) => G[A] => G[B]
  
  // this method is supplied by the handler and allows capturing
  // the "continuation".
  def use[A](body: G[A => ω] => G[ω]): I[A] = ???
}

Sidenote: Rank-2 Types

Here, the crazy ω (which is some abstract type member) is used to model rank-2 types. The body of use could also be assigned the type:

trait Body[A] { def apply[ω]: G[A => ω] => G[ω] }

but then lambda syntax can't be used anymore.

Equipped with Idiomatic, we can implement a handler for get that statically just counts the calls to get. While this is a bit artificial it shows the power of idiomatic handlers: The computational tree is static, when handled. Handling really just amounts to a fold and we don't need to supply a value to the continuation.

class CountGets extends Get with Idiomatic {
  type G[X] = Int
  def unit[R] = r => 0
  def map[A, B] = f => n => n
  def get() = use { n => n + 1 }
}
def countGets = new countGets

Compare this to a monadic handler that would need to come up with a fake result:

class CountGetsM[R] extends Get with Monadic[(R, Int)] {
  def get() = use { resume => resume(42) map { case (x, n) => (x, n + n) } }
}
def countGetsM = new CountGetsM

The different handlers also come with different handle methods that signify that monadic handlers can only handle monadic programs; Idiomatic handler on the other hand can handle idiomatic programs as well.

def handle[R](h: handler.Idiomatic)(prog: h.type => I[R]): I[h.G[R]]
def handle[R](h: handler.Monadic[R])(prog: h.type => C[R]): C[R]

Example (2)

Back to the github example. We can write interesting idiomatic handlers.

For instance, one handler that statically collects all the UserLogins that have been requested.

class RequestedLogins extends Github with Analyze[Set[UserLogin]] with Monoidal[Set[UserLogin]] {
  def getUser(login: UserLogin): I[User] = collect { Set(login) }
  def getComment(owner: Owner, repo: Repo, id: Int) = default
  def getComments(owner: Owner, repo: Repo, issue: Issue) = default
  def listIssues(owner: Owner, repo: Repo) = default
}

Mixing Idiomatic and Monadic Programs

We cannot use our RequesteLogins handler to handle a program like allUsers. The program is monadic, while our handler requires an idiomatic program. Wouldn't it be nice, if we could use the handler just for the idiomatic fragments? Automatically? Without lifting or explicitly handling the subprogram?

It turns out, we can convert an idiomatic handler into a monadic one, using the following function:

def dynamic[R](hi: handler.Idiomatic, run: h.G[ω] =>=> C[R]) => C[R])(prog: h.type => C[R]): C[R]

(While we don't return Monadic, the result type of (h.type => C[R]) => C[R] is actually equivalent to applying a monadic handler).

All of the magic happens by supplying run: We need to tell how to extract ωs out of G to then call the continuation (ω => C[R]) effectively sequencing the idiomatic fragments.

For our Github example we can use dynamic to implement some form of batching/prefetching:

def batched[R](prog: C[R] using Github): C[R] using Github =
  reify.dynamic(prog) {
    prog => resume => for {
      logins <- requestedLogins { prog } map { _.toList }
      _ = println("prefetching user logins: " + logins)
      users <- logins.traverse { Github.getUser }
      db = (logins zip users).toMap
      res <- prefetched(db).apply { prog } flatMap resume
    } yield res
  }

Please ignore reify here, which is a idiomatic handler that builds up the program tree. The important part is, that we can statically analyze the requested logins (using requestedLogins), prefetch the users once (logins.traverse { Github.getUser }) and then use the handler prefetched to actually handle the Github effect. prefetched forwards to an outer handler (hence the return type C[R] using Github) in case a result is not already prefetched.

The batched handler itself has an idiomatic fragment: logins.traverse { Github.getUser }. An outer idiomatic handler can make use of it. For instance this remote handler makes use of the applicative instance of Future to concurrently send http requests:

class GithubRemoteFuture[R](implicit ec: ExecutionContext) extends GithubApi with Functorial[Future] {
  def unit[R] = Future.apply
  def fetch[T](uri: String, parse: Parser[T]): I[T] = use { k =>
    Applicative[Future].ap(k) { Future { fetch(uri) }.map(parse) }
  }
}
// here we use `dynamic` to block on calls to `flatMap`.
def githubRemoteFuture[R](timeout: Duration)(prog: C[R] using Github): C[R] using ExecutionContext =
  new GithubRemoteFuture().dynamic[R](prog) { prog: Future[ω] => resume: (ω => C[R]) =>
    Await.result(prog.map(resume), timeout)
  }

As a result the following code both uses the applicative nature of Future and performs batching. All specified in a modular way. :)

githubRemoteFuture(30 seconds) {
  batched { 
    allUsers(Owner("koka-lang"), Repo("libhandler"))
  }
}
// In previous implementations, by forwarding idiomatic effects through monadic
// handlers we lost the idiomatic structure of the subprogram.
//
// Idea of this implementation: We treat the first `flatMap` as an effect.
// This way we don't need any special casing for "dynamic" handlers. Instead,
// the two types Impure and ImpureAp suffice.
//
// To focus on the operation semantics, this implementation is not effect safe.
// establishing static effect safety is a separate (and probably orthogonal)
// step.
// Type Aliases
// ============
type MonadCont[A, B] = A => Eff[B]
type IdiomCont[A, B] = Idiom[A => B]
// interpreters / handlers are *partial* natural transformations: Op ~> Domain
type ~>[-A, +B] = PartialFunction[A, B]
// Effect Operations
// =================
trait Op[X]
// all effect calls start out as idiomatic programs
def send[X](op: Op[X]): Idiom[X] = ImpureAp[X, X](op, pure(identity))
// Base Types
// ==========
sealed trait Eff[A] {
def map[B](f: A => B): Eff[B]
def flatMap[B](f: A => Eff[B]): Eff[B]
def ap[B](f: Eff[A => B]): Eff[B] = flatMap { a => f map { _ apply a } }
def andThen[B](f: Eff[B]): Eff[B] = ap(f map { b => a: A => b })
}
sealed trait Idiom[A] extends Eff[A] {
def map[B](f: A => B): Idiom[B]
def ap[B](f: Idiom[A => B]): Idiom[B]
def andThen[B](f: Idiom[B]): Idiom[B] = ap(f map { b => a: A => b })
def map2[B, C](mb: Idiom[B])(f: (A, B) => C): Idiom[C] = ap(mb.map { b: B => a: A => f(a, b) })
}
def pure[A](a: A): Idiom[A] = Pure(a)
// Bubble Types
// ============
case class Pure[A](value: A) extends Idiom[A] {
def map[B](f: A => B): Idiom[B] = Pure(f(value))
def flatMap[B](f: A => Eff[B]): Eff[B] = f(value)
def ap[B](ef: Idiom[A => B]): Idiom[B] = ef map { f => f(value) }
}
// This is just free applicative:
// https://hackage.haskell.org/package/free-5.1/docs/Control-Applicative-Free.html
case class ImpureAp[X, A](op: Op[X], continuation: IdiomCont[X, A]) extends Idiom[A] {
def map[B](f: A => B): Idiom[B] =
ImpureAp(op, continuation map { f compose _ })
def ap[B](ef: Idiom[A => B]): Idiom[B] =
ImpureAp(op, continuation ap (ef map { (f : A => B) => (g : X => A) => f compose g }))
def flatMap[B](f: A => Eff[B]): Eff[B] =
Impure(Bind(this), _ flatMap f)
}
// This is just freeer monads.
case class Impure[X, A](op: Op[X], continuation: MonadCont[X, A]) extends Eff[A] {
def map[B](f: A => B): Eff[B] = Impure(op, x => continuation(x) map f)
def flatMap[B](f: A => Eff[B]): Eff[B] = Impure(op, x => continuation(x) flatMap f)
}
// Interpreters
// ============
trait Interpreter[G[_]] {
// the pure clause is non-effectful for now
// can be changed to `A => Eff[G[A]]` for monadic and `Idiom[A] => Idiom[G[A]]` for idiomatic handlers
def onPure[A]: A => G[A]
}
// Idiomatic Handlers
// ------------------
trait Idiomatic[G[_]] extends Interpreter[G] {
// this is a simplified form of Idiom[G[X => R]] => Idiom[G[R]]
def map[A, B]: G[A] => (A => B) => G[B]
def onEffect[X, R]: Op[X] ~> (G[X => R] => G[R])
def apply[R](prog: Idiom[R]): Idiom[G[R]] = runIdiomatic(this)(prog)
def dynamic[R](prog: Eff[R])(sequence: Sequencer[G, R]): Eff[R] = runDynamic(this, sequence)(prog)
}
private def runIdiomatic[R, G[_]](interpreter: Idiomatic[G])(prog: Idiom[R]): Idiom[G[R]] = prog match {
case p @ Pure(_) =>
prog map interpreter.onPure
case ImpureAp(op, k) if interpreter.onEffect isDefinedAt op =>
interpreter(k) map interpreter.onEffect(op)
case ImpureAp(op, k) =>
// here we require G to be a functor to convert `gk: G[x => R]` to `x => G[R]`:
ImpureAp(op, interpreter(k) map { gk => x => interpreter.map(gk) { xr => xr(x) } })
}
// Monadic Handlers
// ----------------
trait Monadic[G[_]] extends Interpreter[G] {
def onEffect[X, R]: Op[X] ~> (MonadCont[X, G[R]] => Eff[G[R]])
def apply[R](prog: Eff[R]): Eff[G[R]] = runMonadic(this)(prog map onPure)
}
private def runMonadic[R, G[_]](interpreter: Monadic[G])(prog: Eff[G[R]]): Eff[G[R]] = prog match {
case p @ Pure(_) =>
p
case Impure(op, km) if interpreter.onEffect isDefinedAt op =>
interpreter.onEffect(op) { x => runMonadic(interpreter) { km(x) } }
case im: Impure[x, G[R]] =>
Impure(im.op, x => runMonadic(interpreter) { im.continuation(x) })
case ImpureAp(op, k) =>
runMonadic(interpreter) { prog flatMap pure }
}
// Idiom Injection
// ===============
// the first bind on an idiomatic computation sends a "Bind"-effect.
// Bind has return type Eff[A] to allow sending effectful values back to the original position. (Time traveling control!)
private case class Bind[X, A](ap: ImpureAp[X, A]) extends Op[Eff[A]]
// Default handler for Bind:
private object BindDefault extends MonadicId {
def onEffect[X, R] = {
case Bind(ImpureAp(op, k)) => resume => resume(Impure(op, x => k map { _ apply x }))
}
}
def run[A](ma: Eff[A]): A = BindDefault { ma } match {
case Pure(a) => a
case _ => sys error "Cannot run program with unhandled effects: " + ma
}
// Mediating between Idiomatic and Monadic Computation
// ---------------------------------------------------
// Defines how to sequence (embed) idiomatic computation into monadic computation.
trait Sequencer[G[_], R] {
def apply[X]: G[X] => (X => Eff[R]) => Eff[R]
}
private def runDynamic[R, G[_]](interpreter: Idiomatic[G], sequence: Sequencer[G, R])(prog: Eff[R]): Eff[R] = new MonadicId { outer =>
// collects the continuation
case class Dynamic[R](gr: G[R]) extends Op[R] { val prompt = outer }
def onEffect[X, R2] = {
case Bind(ap @ ImpureAp(op, k)) if interpreter.onEffect.isDefinedAt(op) => resume => {
// 1) inject idiomatic handler
val handled = interpreter { ap }
// send computation back to ...
// 2) runs the idiomatic handler in the original position of the bind
// 3) collects the continuation (using Dynamic) to be sequenced in a separate step
resume(handled flatMap (ga => send(Dynamic(ga))))
}
case d @ Dynamic(gr) if d.prompt eq this => resume => {
// this cast is a consequence of interpreters not being fixed to *one particular* answer type.
val seq = sequence.asInstanceOf[Sequencer[G, R2]]
seq(gr)(resume)
}
}
} apply prog
// Helpers
// =======
trait MonadicId extends Monadic[[X] => X] {
def onPure[A] = a => a
}
// Examples
// ========
case object Get extends Op[Int]
def get(): Idiom[Int] = send(Get)
case class Put(n: Int) extends Op[Unit]
def put(n: Int): Idiom[Unit] = send(Put(n))
case object Tick extends Op[Unit]
def tick(): Idiom[Unit] = send(Tick)
type Id[A] = A
// A simple monadic handler that prints the values it receives
object PrintPuts extends MonadicId {
def onEffect[X, R] = {
case Put(n) => resume => println(n); resume(())
}
}
// A handler that constantly returns 42
object Get42 extends MonadicId {
def onEffect[X, R] = {
case Get => resume => resume(42)
}
}
type WithInt[X] = (X, Int)
// An idiomatic handler for put, that statically sums all the puts.
object SumPuts extends Idiomatic[WithInt] {
def onPure[R] = r => (r, 0)
def map[A, B] = (a, n) => f => (f(a), n)
def onEffect[X, R] = {
case Put(n) => (k, m) => (k(()), m + n)
}
}
// An idiomatic handler for get, that statically counts all the puts.
object CountGets extends Idiomatic[WithInt] {
def onPure[R] = r => (r, 0)
def map[A, B] = (a, n) => f => (f(a), n)
def onEffect[X, R] = {
// here we make up a value (0) to continue. We could also pick `[X] => Int` to avoid this.
case Get => (k, m) => (k(0), m + 1)
}
}
type Trace = List[Int]
// Lifts an idiomatic handler that statically computes an Int to
// a dynamic trace over all idiomatic subprograms.
def trace[R](h: Idiomatic[WithInt]): Eff[R] => Eff[(R, Trace)] = prog =>
h.dynamic(prog map { r => (r, List.empty[Int]) })(new Sequencer {
def apply[X] = (x, n) => resume => resume(x) map { case (r, ms) => (r, n :: ms) }
})
def traceGets[R] = trace[R](CountGets)
def tracePuts[R] = trace[R](SumPuts)
// A purely idiomatic program
def prog(n: Int): Idiom[Int] =
put(n + 1) andThen put(n + 2) andThen put(n + 3) andThen get()
println { run { Get42 { PrintPuts { prog(0) } } } }
// 1
// 2
// 3
//> 42
println { run { Get42 { SumPuts { prog(0) } } } }
//> (42, 6)
// Doesn't type check since Get42 is a *monadic* handler
// println { run { SumPuts { Get42 { prog(0) } } } }
// however, we can use the tracing variant of puts:
println { run { Get42 { trace(SumPuts) { prog(0) } } } }
//> (42, List(6))
// now also works in this nesting:
println { run { trace(SumPuts) { Get42 { prog(0) } } } }
//> (42, List(6))
// A slightly larger example to illustrate "trace":
val prog2 = for {
x <- prog(0)
y <- prog(1).map2(get()) { _ + _ }
z <- prog(2)
} yield (x, y, z)
println { run { Get42 { trace(SumPuts) { prog2 } } } }
//> ((42,42,42), List(6, 9, 12))
println { run { trace(CountGets) { trace(SumPuts) { prog2 } } } }
//> (((0,0,0), List(6, 9, 12)), List(1, 2, 1))
// ^^^^^^ ^^^^^^^^^^ ^^^^^^^^^^^^
// the result the put trace the get trace
// A handler for tick, that calls the continuation twice
object AmbiguousTick extends Monadic[List] {
def onPure[R] = a => List(a)
def onEffect[X, R] = {
case Tick => resume => {
println("tick")
for {
first <- resume(())
second <- resume(())
} yield first ++ second
}
}
}
println { run { AmbiguousTick { tick() }}}
//> List((), ())
println { run { AmbiguousTick { tracePuts {
tick() andThen put(2)
}}}}
//> List(((),List(2)), ((),List(2)))
println { run { tracePuts { AmbiguousTick {
tick() andThen put(2)
}}}}
//> (List((), ()), List(2, 2))
// A larger program with nested idiomatic computation
val prog3: Eff[(Int, Int, Int)] = for {
x <- prog(0)
y <- put(1337) andThen (for {
a <- tick() andThen prog(1)
b <- tick() andThen prog(2)
} yield a + b)
z <- get() andThen prog(3)
} yield (x, y, z)
println("--------------------")
println { run { AmbiguousTick { Get42 { tracePuts { prog3 } } } } }
//> List(((42,84,42),List(6, 1337, 9, 12, 15)),
// ((42,84,42),List(6, 1337, 9, 12, 15)),
// ((42,84,42),List(6, 1337, 9, 12, 15)),
// ((42,84,42),List(6, 1337, 9, 12, 15)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment