Using Generators as syntax sugar for side effects

This story shows Generators as an explicit but seamless syntax for programs with asynchronous operations, shared mutable state and other side effects. The conversion is based on so-called Monads.

In spite of the scary name, Monads are a very simple concept. You already use them when you change some variable value or output anything or throw/catch an exception. Monads first appeared in Computer Science to support mathematical reasoning about side-effects in imperative languages such as JavaScript.

Other researchers were designing practical languages with only pure functions. Using only pure functions makes programs more verbose and harder to read. Monads were applied as a practical tool for converting programs with effects into pure ones. Here is a citation from one of the best monads tutorial — Monads for functional programming by Philip Wadler (1995):

It is with regard to modularity that explicit data flow becomes both a blessing and a curse. On the one hand, it is the ultimate in modularity. All data in and all data out are rendered manifest and accessible, providing a maximum of flexibility. On the other hand, it is the nadir of modularity. The essence of an algorithm can become buried under the plumbing required to carry data from its point of creation to its point of use.

Doesn’t it sound familiar? E.g., property drilling for React Components and one of the reasons for state management to solve it.

Original abstract do-notation is a macro converting programs looking like imperative one into abstract API calls. The concrete implementations of that APIs can construct an Iterable object, or a Promise or many other things. This way the same syntax (and the same programs) can be reused in different contexts.

JavaScript has syntax extensions similar to do-notation. They are async and/or generator functions. Unlike original do-notation they are converted to concrete API calls ( Promise#then, and Iterable constructors) by JavaScript compiler or some transpiler (e.g. regenerator). These concrete functions are almost instances of abstract monad API.

Async and generator functions are based on Coroutine monad. It can be converted into many other monads, but not all. There is a well-known fact in JavaScript community — generator functions can replace async functions. Asynchronous functions written using generators syntax can be canceled, unlike standard async functions. The only overhead is the need to call a wrapper function, which converts Iterable into a Promise.

There are many examples of using generators for async code so I’ll illustrate the idea on another case instead. It is maybe not so practical, but we can turn a generator function with a mutable state into a pure function.

function* incr() {
  return (yield set((yield get) + 1))
}

function* incrX2() {
  return (yield* incr()) + (yield* incr())
}

const main = state(incrX2)

// framework
function state(iter) {
  const i = iter()[Symbol.iterator]()
  return walk()

  function walk(arg) {
    const step = i.next(arg)
    return step.done ?
      state => [state, step.value] :
      state => {
        const [next, value] = step.value(state)
        return walk(value)(next)
      }
  }
}

function set(s) { return _ => [s, s] }
function get(s) { return [s, s] }

Here both functions incr and incrX2 have side effects. They change and read shared data. But the resulting function state(incrX2) is pure. The function state does actual conversion between Iterable into a State monad.
This is how it looks with inlined framework functions:

function incr(s) {
  const ns = s + 1
  return [ns, ns]
}

function incrX2(s) {
  const [s1, r1] = incr(s)
  const [s2, r2] = incr(s1)
  return [s2, r1 + r2]
}

The example skips abstract API layer. There are quite a few options to chose its basis, but the most simple one is two functions: of and chain. They both return monadic(effectful) value. It is an abstract thing and can be anything depending on the concrete API implementation. For the abstract interface, the values of this type are entirely opaque.

• of — takes any value and returns effectful value, what it does exactly with the argument is defined by interface implementation
• chain — takes some effectful value and a function mapping anything to another effectful value, returns some other effectful value

The concrete implementations of the function can do anything if this conforms to so-called monadic laws. In fact, my choice of chainname is typical for JavaScript libraries but a bit misleading. It suggests some concrete implementation, chaining of something. But, again, it is some abstract thing, and the only requirement is monad laws conformance.

Here are the laws:

• (f, x) => chain(of(x), f) should be equal to (f, x) => f(x)
• m => chain(m, x => of(x)) should be equal to m
• (m, f, g) => chain(chain(m, f), g) should be equal to (m, f, g) => chain(m, x => chain(f(x), g))

If the laws hold we can use the API in do-notation, or in some abstract functions working for any monad.

For example, the first law means the value of x should be stored somewhere by of until processing by chain. This is why monads are often explained as something wrapping some value (burrito). However, in the general case, monad values aren't required to wrap anything (if they are constructed by something but not of).

Let’s convert Iterable into this abstract interface. It is almost the same like for State except the functions are replaced with abstracted calls.

const run = (of, chain) => fun => {
  const i = fun()[Symbol.iterator]()
  return walk()
  function walk(arg) {
    const step = i.next(arg)
    return step.done ? of(step.value) : chain(step.value, walk)
  }
}

For State, effectful value is a function taking some original state and returning a pair of a resulting value and a new state value. Here is State monad definition using the abstract intermediate layer:

const state = run(v => s => [v, s],
                  (arg, fun) => s => {
                     const [nextArg, nextState] = arg(s)
                     return fun(nextArg)(nextState)
                   })
function set(s) { return _ => [s, s] }
function get(s) { return [s, s] }

And Promises:

const promise = run(v => Promise.resolve(v),
                    (arg, fun) => arg.then(fun))

The first monad law doesn’t work for Promises if x is another object with then method (Thenable). This then method will be called, but the law requires it to be returned as is.

It is okay for practical purposes. However, sometimes this leads to unwanted consequences. For example, dynamic importing a module that exports any then function will call it and do something unpredictable.

Considering generators are enough for Promises and Iterators one may wonder why we need Async Generators. Indeed it is pretty easy to convert monad combining the two effects from plain generators. However, there won’t be any replacement for await-of statement. It is yet another syntax sugar for traversal.

Coroutines/Iterables cannot define be converted to any monad. For example, Observable is a monad, but generators cannot be used as a do-notation for them.

Another useful example is non-determinism. I.e. a computation returning several values. This can be used for embedding logical programming into JavaScript. It is simple to make an implementation for the abstract interface:

const nonDet = run(
  function*(value) { yield value },
  function*(arg, fun) { 
    for(const i of arg)
       yield* fun(i) 
  })

There are libraries defining abstract APIs with a few concrete implementations in JavaScript, e.g. fantasy-land. There are also a few do notation as generators implementations trying to simulate multiple resumes by restarting and replaying iterators for the beginning example - burrido. The approach is not safe and not efficient.

There is an alternative single-layered way. React uses it for Suspense for data fetching and Hooks. I described this in more details in React Suspense is to a Monad as Hooks are to Applicative Notation.

I now work on a babel plugin based implementation for do-syntax working for any Monad — EffectfulJS. It offers many options, like persistent state, concrete implementation inlining, implicit parallelization. This may significantly simplify JavaScript code. I’m going to write more about it soon, stay tuned!

Comments

[Iven Marquardt]

I see you implemented delimited conts with prompts rather than shift/reset, which is quite cool. Do you have a multi-prompt coroutine implementation based on this, so that we could write every monad with it? Since your delim conts are based on functions we still wind up with nested monad hell, right?

[Vitaliy Akimov]

I think multi-prompt is possible, but the continuations are running at most once, which is the main stop for implementing all monads. However, in my transpiler I implemented multi-prompt - @effectful/cc, with all the well-known operators.

In @effectful/cc the continuation is a stack data structure, with some segments are functions and others are prompts markers, so only the part of the stack until the requested prompt is unwound. It is from A Monadic Framework for Delimited Continuations paper