Discuss
  • One-shot Delimited Continuations with Effect Handlers

One-shot Delimited Continuations with Effect Handlers

# Sebastian Markbåge (9 years ago)

Has anyone previously proposed a Algebraic Effects (e.g. Eff like handlers of continuations) for ECMAScript? #lazyweb I could only find variations that aren't quite this.

I'm specifically looking at the OCaml implementation for inspiration:

kcsrk.info/ocaml/multicore/2015/05/20/effects-multicore

kcsrk.info/slides/multicore_fb16.pdf

I'm not proposing the multicore aspect of this but just the delimited continuations.

Basically, the idea is that you can capture effects by wrapping a call in a "try". That spawns a fiber. Then any function can "perform" an effect as a new language feature. That works effectively like "throw" expect it also captures a reified continuation, in a tuple. The continuation can be invoked to continue where you left off.

Imaginary syntax:

function otherFunction() {
  console.log(1);
  let a = perform { x: 1, y: 2 };
  console.log(a);
  return a;
}

do try {
  let b = otherFunction();
  b + 1;
} catch effect -> [{ x, y }, continuation] {
  console.log(2);
  let c = continuation(x + y);
  console.log(c);
  c + 1;
}

Prints:

1
2
3
4

Evalutes to: 5

(perform is a contextual keyword to "throw" and catch effect is a keyword for catching it. Guest starring Pattern Matching)

We've experimented with changing React's implementation to use these internally to handle concurrency and being able to solve complex algorithms that require a lot of back and forth such as layout calculation. It seems to make these implementations much easier while remaining efficient.

It also allows for seamless async I/O handling by yielding deep in a fiber.

Effectively this is just solving the same thing as generator and async/await.

However, the benefit is that you don't have a split between "async" functions, generator functions and synchronous functions. You still have an explicit entry point through the place where you catch effects.

With generators and async functions, anytime you want to change any deep effects you have to unwind all potential callers. Any intermediate library have to be turned into async functions. The refactoring is painful and leaves you with a lot of syntax overhead.

If you want to nest different effects such as layout, iterations and async functions that complexity explodes because now every intermediate function has to be able to handle all those concepts.

The performance characteristics demonstrated by KC Sivaramakrishnan are also much more promising than JS VMs has been able to do with async/await and generators so far. It's plausible that VMs can optimize this in similar way, in time. I suspect that the leakiness of the microtask queue might cause problems though.

I converted the OCaml example scheduler to this ECMAScript compatible syntax:

// RoundRobinScheduler.js

class Fork {
  constructor(fn) {
    this.fn = fn;
  }
}
export function fork(f) {
  perform new Fork(f)
}

class Yield { }
export function yieldHere() {
  perform new Yield();
}

export function run(main) {
  const run_q = [];
  function enqueue(k) {
    run_q.push(k);
  }
  function dequeue() {
    if (run_q.length) {
      run_q.shift()();
    }
  }
  function spawn(f) {
    try {
      f();
      dequeue();
    } catch (e) {
      console.log(e.toString());
    } catch effect Yield -> [_, k] {
      enqueue(k);
      dequeue();
    } catch effect Fork -> [fork, k] {
      enqueue(k);
      spawn(fork.fn);
    }
  }
  spawn(main);
}

// Example.js

import * as Sched from "RoundRobinScheduler";

function f(id, depth) {
  console.log("Starting number %i", id);
  if (depth > 0) {
    console.log("Forking number %i", id * 2 + 1);
    Sched.fork(() => f(id * 2 + 1, depth - 1));
    console.log("Forking number %i", id * 2 + 2);
    Sched.fork(() => f(id * 2 + 2, depth - 1));
  } else {
    console.log("Yielding in number %i", id);
    Sched.yieldHere();
    console.log("Resumed number %i", id);
  }
  console.log("Finishing number %i", id);
}

Sched.run(() => f(0, 2));
# Ben Newman (9 years ago)

What if we simply allowed await expressions anywhere in the call stack of an async function, rather than only in the bodies of async functions? That would give us all the power of "yielding deep in a fiber" with a much more familiar syntax, and an easy way to capture effects, since an async function returns a Promise that allows for asynchronous error handling. No new catch effect … syntax needed.

I've talked about this before benjamn.github.io/goto2015-talk/#/17,

and it's my understanding that TC39 needs a lot of convincing that coroutines are a good idea. We haven't really discussed the topic in the context of async functions, which are soon to be an official part of the language, so perhaps the time for discussing coroutines/continuations/etc. is drawing near!

# Sebastian Markbåge (9 years ago)

async functions only address the async use case and they're all scheduled on a simple micro-task queue. We need fine grained control over scheduling. Perhaps Zones can help a bit with that but that's just one of severals concepts that need this.

It doesn't solve other more general generator use cases. You could potentially expand it to generators as well.

However, then you'd also need to solve the nested handlers case efficiently. That's my use case. What if you have a layout handler, in an iteration handler in an async scheduler handler?

The async functions could be implemented in terms of this though since they're just a more specific and locked down version.

# Ben Newman (9 years ago)

Ok, I think I understand how your needs differ from the async/relaxed-await idea. You need a way to

  • extract values from deeply nested yields, which is not allowed by await expressions,
  • resume execution whenever you choose, which is a decision await expressions make for you, i.e. they resume whenever the Promise is resolved/rejected, and
  • execute everything synchronously (if desired).

Perhaps if there was a way to wrap any arbitrary expression with a generator that captured any yielded values and allowed resumption by calling .next(), then you could accomplish this without inventing new try-catch syntax?

# Sebastian Markbåge (9 years ago)

Perhaps if there was a way to wrap any arbitrary expression with a generator that captured any yielded values and allowed resumption by calling .next(), then you could accomplish this without inventing new try-catch syntax?

Yea, except you need to be able to nest them inside each other as well.

If a generator captured any yielded values, then it would be yielded at the inner most caller.

You could handle this the way JavaScript does exception handling by "rethrowing" errors it didn't handle. I.e. if you see a yield that you don't recognize you would re-yield it.

In my use case I can have many nested handlers and I want to handle a particular type at the top of the stack. If you have to conditionally "reyield" all the way up there, you miss out on potential important optimizations.

This is related to "enums" and "pattern matching" too. The current pattern matching proposal also doesn't have any optimizations either.

# Sebastian Markbåge (9 years ago)

It's possible that this pattern matching feature can be decoupled into a separate proposal though. You'd need a way to call an iterator but only receive specific matches and reyield the rest.

# Benjamin Gruenbaum (9 years ago)

async functions only address the async use case and they're all scheduled on a simple micro-task queue. We need fine grained control over scheduling. Perhaps Zones can help a bit with that but that's just one of severals concepts that need this.

Isn't the problem we actually need to solve here the fact we're not able to control scheduling or context in async functions? Other languages with async functions like Python and C# provide the means to control the scheduling of async functions.

This is also indeed deeply related to zones since there is no inherent reason the same doesn't apply to async things that are not promises (like observables, async iterators and event emitters).

# /#!/JoePea (9 years ago)

The effect addition to try-catch seems like some sort of hacky workaround, that would get the job done, but then would make try-catch be used for purposes other than catching errors, which defeats it's original purpose. I think it's important to keep that error-based meaning and not mix it with anything else. "Try this, catch errors" and that's all.

What if we simply allowed await expressions anywhere in the call stack of an async function, rather than only in the bodies of async functions?

Although it is more work for the person writing code, I believe having to explicitly use keywords (await or yield) in function bodies makes it very clear what is happening, and ultimately leads to better code with less potential for human error in the long run. I would vote against allowing a relaxed await anywhere in the call stack. One of the pains I had with Java was realizing after debugging for a while that something I was doing was async (I was new to Java).

The beauty of JavaScript from the very beginning (the reason I love JavaScript) is that dealing with asynchronous behavior is something a JavaScript developer is forced to do from the get go. Introducing invisible asynchronous behavior would deviate from that (and be more like Java). It might be suitable at first, for new programmers, but as soon as they have problems, the source of those problems could be invisible unless they go read the docs on every API (and if lucky, that API mentions that a function is async). Requiring await will force everyone to learn how to deal with async behavior from the get go, just like we all had to learn how to deal with callback hell from the get go, which was a good thing (despite the syntax "hell").

we're not able to control scheduling or context in async functions?

I think we can:

import {run} from 'some/scheduler/library'

let ctrl = run(async function() {
  await ctrl(sleep(1000))
  await ctrl(somePromise)
})

// ...
ctrl.pause() // paused at the sleep statement.
setTimeout(() => ctrl.resume(), 5000)

// ----- or

import {Task, sleep} from 'some/scheduler/library'

let task = new Task(async function(...args) {
  console.log(args) // [1,2,3]
  await task.ctrl(sleep(1000))
  await task.ctrl(somePromise)
})
task.run(1,2,3)

// ...
task.pause()
setTimeout(() => task.resume(), 5000)

// ----- or

import {Task} from 'some/scheduler/library'

let task = new Task
let {run, ctrl} = task // run and ctrl are bound to the `task` by the
Task constructor.

run(async function() {
  await ctrl(sleep(1000))
  await ctrl(somePromise)
})

run(otherAsyncFunction) // runs after the first run completes.

// ...
task.pause()
setTimeout(() => task.resume(), 5000)

// ----- or

import {Task} from 'some/scheduler/library'

let task = new Task
let ctrl = task.ctrl

async function foo() {
  await somePromise
}
async function bar() {
  await ctrl(someOtherPromise)
}
~async function() {
  await ctrl(sleep(1000))
  await ctrl(foo)
  await ctrl(Promise.all(yetAnotherPromise, bar))
}()

// ...
task.pause()
setTimeout(() => task.resume(), 5000)

ctrl() could accept promises, zone things, generator functions, async functions, anything async. ctrl() obviously uses a Promise to resume the execution of the "context".

# Sebastian Markbåge (9 years ago)

Isn't the problem we actually need to solve here the fact we're not able to control scheduling or context in async functions? Other languages with async functions like Python and C# provide the means to control the scheduling of async functions.

Algebraic effects also allows the side-effect itself (e.g. the network request), to be intercepted in a context. Zones doesn't let you do that.

However async is only part of the problem. See Ben Newman's describing the capabilities of generators that are not available to async functions.

There are many use cases for generators that are not limited to the "async" use case and those still have to be solved.

So, yes, that's a limitation but not the only limitation.

# Sebastian Markbåge (9 years ago)

Although it is more work for the person writing code, I believe having to explicitly use keywords (await or yield) in function bodies makes it very clear what is happening, and ultimately leads to better code with less potential for human error in the long run. ... The beauty of JavaScript from the very beginning (the reason I love JavaScript) is that dealing with asynchronous behavior is something a JavaScript developer is forced to do from the get go.

I start from the premise that this explicitness is already a huge and unmanageable problem through observation. Note my observation that nesting various types of effects (async isn't the only one) makes this totally unmanageable. If it wasn't, the status quo would be fine, but it isn't.

Introducing invisible asynchronous behavior would deviate from that (and be more like Java).

The beauty of algebraic effects is that these side-effects can't just randomly leak. If you're concerned about any particular code path having these side-effects you can catch all the effects in that code-path. This is very much unlike Java. That way you opt-in to that guarantee when you need it, instead of forcing every little thing along the way make that decision.

we're not able to control scheduling or context in async functions?

I think we can:

Your example demonstrates that explicitness can solve it but that is exactly the problem that this proposal is trying to address. If you don't agree with the premise that this is unmanageable there isn't much more to it.

# 森建 (6 years ago)

React Hooks, a new feature of React v16.7.0-alpha, is a hacky implementation, so there are restrictions that must be called in order. reactjs.org/docs/hooks-rules.html

One of React members says below:

Finally, if you’re a functional programming purist and feel uneasy about React relying on mutable state as an implementation detail, you might find it satisfactory that handling Hooks could be implemented in a pure way using algebraic effects (if JavaScript supported them). And of course React has always relied on mutable state internally — precisely so that you don’t have to.

medium.com/@dan_abramov/making-sense-of-react-hooks-fdbde8803889

IMHO, it's worth considering that we'll include Algebraic Effects specifications in ECMAScript.

# 森建 (6 years ago)

Sorry for my hasty reply, the restriction seems to be not related to Algebraic Effects. But I think that Algebraic Effects specifications is useful for a pure implementation.

# Bruno Macabeus (5 years ago)

Hello for all,

I know that this discuss is a little old, but I just found it now and I think that it is still useful at this moment.

So I created a very simple Babel plugin to taste and validate the Sebatian's idea: macabeus/js-proposal-algebraic-effects, macabeus/js-proposal-algebraic-effects

Maybe it could be useful to test how much this proposal could be useful for our JS code.

Algebraic Effects/One-shot delimited continuations/effect handlers are viable proposals?

Thank you!

# kai zhu (5 years ago)

the usage-scenario is not compelling. the same effect can be achieved in 12-lines of throwaway-code (i copy pasted into console), with less tech-debt:

$ node -e ' var nameList = [null, "Gendry"]; nameList.forEach(async function (name) { // if name is null, then wait 1000ms, and default to "Arya Stark" if (name === null) { await new Promise(function (resolve) { setTimeout(resolve, 1000); }); name = "Arya Stark"; } var nameUpperCase = name.toUpperCase(); console.log(nameUpperCase); }); ' $ GENDRY $ ARYA STARK