From d476cc6ddbd00541f2f7ec2d32401219de765002 Mon Sep 17 00:00:00 2001 From: JJ Date: Thu, 8 Aug 2024 18:34:14 -0700 Subject: meow --- plt/effects.md | 180 +++++++++++++++++++++++++++++++++++++-------------------- 1 file changed, 116 insertions(+), 64 deletions(-) (limited to 'plt/effects.md') diff --git a/plt/effects.md b/plt/effects.md index ef97667..f1f73f1 100644 --- a/plt/effects.md +++ b/plt/effects.md @@ -3,48 +3,51 @@ layout: plt title: computation/effects --- -# effects and handlers: a comprehensive introduction +# algebraic effects and effect handlers What are effects? -Effects are a lot of things. Like other terms in computer science, it is overloaded, and refers typically to two similar but notably different concepts: -1. a *side* effect, i.e. some sort of impurity in the computation of an otherwise [pure function] -2. an *algebraic effect*. We'll get back to this later. +Effects are a lot of things. Like other terms in computer science, it is overloaded, and refers typically to two similar but notably distinct concepts: +1. a *side* effect, i.e. some sort of impurity in the computation of an otherwise [pure function](/wiki/plt/glossary#pure) +2. an *algebraic effect*. These are occasionally referred to as *abilities* or *capabilities*. - -What is an effects system? +The term "effects system" gets thrown around with "effects" a lot. But what is an effects system? -Effects systems, too, are a couple of things. +Effects systems, too, are a couple of things: 1. a system for *tracking side-effects* of routines -2. for algebraic effects and alongside **handlers**, a *broad generalization of non-local control flow*. +2. for algebraic effects and alongside *handlers*, a **broad generalization of non-local control flow**. By "effects system", most programmers generally mean the first. Academics near-universally mean the second. [This can be the cause of some confusion.](https://github.com/nim-lang/RFCs/issues/491) -... +## toc - [Background](#background) -- [An Intuition](#an-intuition-exceptions-as-an-effect) (exceptions as an effect) -- [Resuming Continuations](#resuming-continuations-iteration-as-an-effect) (iteration as an effect) -- [Resumption with a Value](#resuming-with-a-value-io-as-an-effect) (i/o as an effect) -- [...]() (mutable global state as an effect) -- [Subsuming Effects Tracking](#subsuming-effects-tracking-safety-as-an-effect) (safety as an effect) -- [Multiple Resumptions](#multiple-resumptions-nondeterminism-as-an-effect) (nondeterminism as an effect) -- [Communication Protocols](#communication-protocols-ping-pong-as-effects) (ping/pong as effects) -- [Colourless Functions](#colourless-functions-async-as-an-effect) (async as an effect) -- [Unified Control Flow Semantics](#unified-control-flow-semantics-async-await-as-an-effect) (async/await as an effect) -- [Why Not Undelimited Control?](#why-not-undelimited-control-effects-as-a-sweet-spot) (effects as a sweet spot) -- [Some Design Considerations](#some-design-considerations-for-future-effectful-systems) (for future effectful systems) +- [An Intuition](#an-intuition) (exceptions as an effect) +- [Resuming Continuations](#resuming-continuations) (iteration as an effect) +- [Resumption with a Value](#resuming-with-a-value) (i/o as an effect) +- [Side Effects are Effects, Too](#side-effects) (mutable global state as an effect) +- [Subsuming Effects Tracking](#subsuming-effects-tracking) (safety as an effect) +- [Multiple Resumptions](#multiple-resumptions) (nondeterminism as an effect) +- [Communication Protocols](#communication-protocols) (ping/pong as effects) +- [Colourless Functions](#colourless-functions) (async as an effect) +- [Unified Control Flow Semantics](#unified-control-flow-semantics) (async/await as an effect) +- [What is Algebraic About Algebraic Effects?](#algebraic-effects) +- [Why Not Undelimited Control?](#undelimited-control) (effects as a sweet spot) +- [Some Design Considerations](#some-design-considerations) (for future effectful systems) ## background -Effects-and-handlers systems are *experimental*, even within computer science academia. There are scant few languages implementing them, and they all do so with their own unique quirks: -Koka (and Frank) have complexities around parametric effect polymorphism, while OCaml (and Eff) handlers are untyped as to satisfy backwards compatibility... +Effects-and-handlers systems are *experimental*, even within academia. There are scant few languages implementing them, and they all do so with their own unique quirks: Koka (and Frank) have complexities around parametric effect polymorphism, while OCaml (and Eff) handlers are untyped as to satisfy backwards compatibility. There is a lot of unexplored ground around soundness and usability! Out of existing languages, though, I think [**Effekt**](https://effekt-lang.org) does the best job. The examples throughout this entry are given in Effekt. They compile, and run, and I encourage the reader to download and play around with Effekt themselves. (I have also given corresponding examples in a syntax of my own division. These examples neither compile nor run, but are meant to illustrate what a future system could look like.) If sitting down and working through a paper appeals to you, I recommend watching/reading, in the following order: -- [✨ Deliminated Continuations, Demystified](https://www.youtube.com/watch?v=TE48LsgVlIU) (fundamental ideas of continuations; which effects handlers build atop) -- [✨ Effects as Capabilities: Effect Handlers and Lightweight Polymorphism](https://dl.acm.org/doi/pdf/10.1145/3428194) ([talk](https://www.youtube.com/watch?v=ITRyzJadgMw) (the Effekt programming language; drastically simplifies polymorphism in such systems) -- [✨ Handling Bidirectional Control Flow] ([talk](https://www.youtube.com/watch?v=RLTEuZNtRCc)) (generalization of exceptions to capture mutating iterators; good exceptions+async example) -- [✨ Continuing WebAssembly with Effect Handlers](https://arxiv.org/pdf/2308.08347) ([talk](https://www.youtube.com/watch?v=2iiVhzzvnGA)) (a compilation target for effectful languages) +- [✨ Deliminated Continuations, Demystified](https://www.youtube.com/watch?v=TE48LsgVlIU) + - fundamental ideas of continuations; which effects handlers build atop +- [✨ Effects as Capabilities](https://dl.acm.org/doi/pdf/10.1145/3428194) ([talk](https://www.youtube.com/watch?v=ITRyzJadgMw) + - the Effekt programming language; drastically simplifies polymorphism in such systems +- [✨ Handling Bidirectional Control Flow](https://dl.acm.org/doi/pdf/10.1145/3428207) ([talk](https://www.youtube.com/watch?v=RLTEuZNtRCc)) + - generalization of exceptions to capture mutating iterators; good exceptions+async example; implemented in Effekt +- [✨ Continuing WebAssembly with Effect Handlers](https://arxiv.org/pdf/2308.08347) ([talk](https://www.youtube.com/watch?v=2iiVhzzvnGA)) + - an efficient compilation target for effectful languages These are all very recent papers (all in the last ~5 years). This is kind of surprising! The idea of effects and handlers has been around since at least the 90s. But it seems that computer science academia is only now getting a handle on how to coherently present and implement such systems: thanks in large part to the hard work of the authors of these papers (and thanks in larger part, of course, to the authors of the papers they in turn built upon). @@ -54,18 +57,41 @@ This is all covered in much more depth in Alexis King's excellent talk on contin - **continuations**: "the rest of the program". Evaluation can be broken up into reducing *redexes* (reducible expressions) and substituting them back into their corresponding *continuations*. - For example, consider `(1 + 2) * 3`. - - We can consider `(1 + 2)` a redex with continuation `∙ * 3`. Evaluation proceeds by reducing `(1 + 2)` to `3` and substituting it into the hole of the continuation `∙ * 3`, giving us `3 * 3`. - - We can consider `3 * 3` a redex with continuation `∙`. Evaluation proceeds by reducing `3 * 3` to `9` and substituting it into the hole of the empty continuation `∙`, giving us the value `9`. -- **deliminated continuations**: continuations that are split up and *manipulated*. + - We can consider `(1 + 2)` a redex with continuation `● * 3`. Evaluation proceeds by reducing `(1 + 2)` to `3` and substituting it into the hole of the continuation `● * 3`, giving us `3 * 3`. + - We can consider `3 * 3` a redex with continuation `●`. Evaluation proceeds by reducing `3 * 3` to `9` and substituting it into the hole of the empty continuation `●`, giving us the value `9`. +- **delimited continuations**: continuations that are split up (delimited) and *manipulated*. - For example, consider `exit(1) * 3`. - - We can consider `exit(1)` a redex with continuation `∙ * 3`. Evaluation proceeds by hitting `exit(1)`: which *discards* the continuation `∙ * 3`, and thus exits. - - This treatment of continuations as a thing + - We can consider `exit(1)` a redex with continuation `● * 3`. Evaluation proceeds by hitting `exit(1)`: which *discards* the continuation `● * 3`, and thus exits. - For a better example, consider [`1 + catch(2 * throw(5), (n) => 3 * n)`](https://www.youtube.com/watch?v=TE48LsgVlIU&t=840s). -- **one-shot continuations**: continuations that may be continued only once. The prototypical idea of a continuation is a one-shot continuation. -- **multi-shot continuations**: continuations that may be continued multiple times. See [Multiple Resumptions](#multiple-resumptions-nondeterminism-as-an-effect) for an example. +- **one-shot continuations**: continuations that may be continued *only once*. + - The prototypical idea of a continuation is a one-shot continuation. +- **multi-shot continuations**: continuations that may be continued *multiple times*. + - See [Multiple Resumptions](#multiple-resumptions-nondeterminism-as-an-effect) for an example. - **effectful**: having to do with effects, vaguely. -## an intuition: exceptions as an effect +