Comparing Coeffects and Effects+Handlers

This document assumes you know what effects+handlers and continuations are. https://effekt-lang.org/docs/concepts/effect-handlers has an interactive introduction and https://ocaml.org/manual/5.2/effects.html has in-depth OCaml examples.

Examples

One use case for coeffects is in implementing implicit parameters. The following example prints 201 in the playground at Coeffects: Context-aware programming languages:

let plus_implicit =
  (fun x -> x + ?y)
in
let ?y = 200 in plus_implicit 1

Effects+handlers can be thought of as a generalization of exceptions, where the handler has access to a continuation. The following example prints "Hello" and returns 201 in the Effekt playground:

interface GetX { def getX(): Int }

def helloWorld() = try {
  1 + do getX()
} with GetX {
  def getX() = { println("Hello"); resume(200) }
}

Comparison of Use Cases

Differences:
- Coeffects do not allow abstracting over control flow. Effects+handlers enable abstracting over control flow, and can be used to implement things like backtracking, error-handling, async/await-style concurrency, inversion-of-control, and user-level threads. See https://ocaml.org/manual/5.2/effects.html for three examples that afaict can't be implemented with coeffects.
- Examples of applications of coeffects include implicit parameters and dataflow analysis, which afaik have not been explained in terms of effects+handlers. I suspect implementing implicit parameters or dataflow analysis would be awkward at best with effects+handlers.
Similarities
- Either coeffects or effects can be used for providing access to things without explicit parameter passing (like in the examples above). That said, abstracting over multiple implementations would probably be easier with effects+handlers (run the same function with different handlers).
See "Coeffects in Hack", below, for Hack's use case for coeffects for privacy. For this use case, coeffects probably require fewer changes to how code is written and are likely easier to adopt than if we had gone with effects+handlers.

Conceptual Comparison

Coeffects do not affect control flow:
- Coeffects have nothing corresponding to handlers for effects, nor (afaict) any relationship to continuations.
- Effect handlers, on the other hand, enable fine-grained control of control-flow
Coeffects are inputs to functions, whereas effects are outputs of functions:
- w.r.t. to typing judgments: coeffect stuff is to the left of the turnstile and effect stuff is to the right of the turnstile
- Operationally, effects are traditionally treated as additional outputs of functions. However, the distinction can get blurry. For example, in Effeckt (Brachthäuser et al., 2020), effects+handlers are compiled to capability-passing via parameters.
Formal semantics:
- Coeffects can be given a semantics in terms of indexed comonads (Petricek et. al., 2014). In contrast, at least some effects+handlers tend to be macro-translateable to monads (Forster, 2019).

Coeffects in Hack

Here's how coeffects are used in Hack:

We use coeffects to control access to sensitive data.
Coeffects are propagated via a dedicated parameter list, where arguments are always passed implicitly and are never explicitly referenced from expressions.
Coeffects represent capabilities. For example, a function with the empty coeffect set cannot mutate things nor perform most side effects.

An example:

// `[]` indicates empty set of coeffects ("pure")
function access_secret((function (string)[]: void) $f)[]: void {
  $f("the secret");
}

// Exfiltrating the secret is blocked here by the coeffect system
// Note: absence of this coeffect parameter list (square brackets)
// indicates default set of coeffect
// which enables access to printing+mutating outer scopes, etc.
function example1(): void {
  $ref = new Ref("dummy");
  // Error: expected a function with the empty coeffect set.
  // Note that lambdas inherit the enclosing coeffect set.
  access_secret(($x) ==> {$ref->value = $x;});
}

function example2(): void {
  $ref = new Ref("dummy");
  // Error, the lambda uses the `write_property` coeffect
  // but is marked as requiring no coeffects
  access_secret(($x)[] ==> {$ref->value = $x;});
}

function example3()[]: void {
  // OK
  access_secret(($x)[] ==> {});
  // OK: lambdas inherit the enclosing coeffect set
  // so this is typed the same as the previous call
  access_secret(($x) ==> {});
}

References

Brachthäuser, J. I., Schuster, P., & Ostermann, K. (2020). Effects as capabilities: Effect handlers and lightweight effect polymorphism. Proceedings of the ACM on Programming Languages, 4(OOPSLA), 1–30. https://doi.org/10.1145/3428194

Petricek, T., Orchard, D., & Mycroft, A. (2014). Coeffects: A calculus of context-dependent computation. Proceedings of the 19th ACM SIGPLAN International Conference on Functional Programming, 123–135. https://doi.org/10.1145/2628136.2628160

Forster, Y. (2019). On the expressive power of user-deﬁned effects: Effect handlers, monadic reﬂection, delimited control. https://dl.acm.org/doi/pdf/10.1145/3110257

Hack docs: https://docs.hhvm.com/hack/contexts-and-capabilities/available-contexts-and-capabilities