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.
The idea behind Idiomatic Effect Handlers is threefold:
- Replace applicatives by idiom handlers like monadic handlers replace monads
- 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)
- Convert idiomatic handlers into monadic handlers by providing a translation function (i.e. for an answertype
Rthat 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]
|-----------------------|
| ... |
=========================
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 usersThe 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 => gA 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.putNote 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 usersThe individual fragments i1, i2, and i3 of the program are idiomatic. The overall program is monadic (C[...]).
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] = ???
}Here, the crazy
ω(which is some abstract type member) is used to model rank-2 types. The body ofusecould 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 countGetsCompare 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 CountGetsMThe 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
}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"))
}
}