b-studios

#lang racket
(require racket/control)
(require racket/syntax)

(struct operation (name effect))

(struct effect-call (op args cont))

(define (do op . args)
  (control0-at (operation-effect op) k (effect-call op args k)))

b-studios

Some people say "effect handlers are the new monads". So I thought, before all these "Effect Handlers are like X" (for X in { Burritos, Containers, ... }) blog posts come into existence, I contribute another point-of-view. This blog post does not really explain the theory behind algebraic effects and handlers. Neither does it explain why you should use them, or how. We just look at how effect handlers work operationally, by implementing them.

This post is a bit longer. If you are in a hurry, I recommend you jump to Step 2.

I do recommend the blog post [Algebraic effects for the rest of us][RestOfUs] which explores another aspect of the topic.

Prelude

I spend most of my awake time doing research on [effect handlers][EffectsResearch] (in particular in [Scala][ScalaEffekt] and [Java][JavaEffekt]). Unsurprisingly, I am happy to see that effect handlers not only catch on in research, but also programmers in industry find them interesting. In particular, some [developers at Facebook][RestOf

b-studios

Did you ever run into the situation, where you thought you need higher ranked polymoprhism in Scala? While it is somewhat supported in Scala, once you go down this route, you loose some convenience that eventually disrupts your API. In this post, I show how in some cases we can use our old friend unapply in Scala to recover some of the convenience.

The Problem

Let's assume in your API you want to have users write functions of type:

b-studios

package examples

import scala.quoted._

object bug extends App {

  val toolbox = scala.quoted.Toolbox.make(getClass.getClassLoader)
  implied for scala.quoted.Toolbox = toolbox

  sealed trait HList

b-studios

Delimiting the lifetime of a resource to a particular scope is a common problem. In this post, I revisit "Lightweight Monadic Regions" (Kiselyov and Shan, [2008][kiselyov2008lightweight]) and show how to generalize the ST-trick to nest monadic regions in a new way.

TLDR; The core idea is to index a monadic type by the set of regions it requires to be "alive". This is not a new idea, but typically the set is represented by some typelevel list. Region subtyping then requires implicit evidence that one typelevel list is a sublist of another one.

b-studios

// probably could be used for some cool type state stuff

sealed trait HList
case class HCons[A, R <: HList](head: A, tail: R) extends HList {
  def ::[B](b: B): B :+: A :+: R = HCons(b, this)
}
case object HNil extends HList {
  def ::[A](a: A): A :+: HNil = HCons(a, this)
}
type HNil = HNil.type

b-studios

effect exc {
  raise(n: int): a;
}

val inc = handler {
  raise(n) -> raise(n + 1)
}

val get = handler {
  raise(n) -> n

b-studios

function * get()  { return yield { label: "get", payload: null }; }
function * put(s) { return yield { label: "put", payload: s }; }

function * state(init, prog) {
  var s = init;
  var cmd = prog.next();
  while (!cmd.done) {
    switch (cmd.value.label) {
      case "get":
        cmd = prog.next(s);

b-studios

trait AmbList[R] extends Amb with Handler[R, List[R]] {

    private var coin: Boolean = true

    def pure = r => List(r)

    @Suspendable
    def flip() = {
      println("Called with coin state: " + coin)

b-studios

import java.nio.ByteBuffer;
import java.util.Arrays;

class Header {
    private final Short framesize;
    public Header(short framesize) {
        this(new Short(framesize));
    }
    public Header(Short framesize) {
        this.framesize = framesize;