Generators mon amour

#javascript #typescript #effect #monad

If you were asked - what is the most valuable feature added to JavaScript in recent years, what would you answer? Personally, I'm in love with generators and here's why.

If you think generators are just fancy functions that can return intermediate values you are, of course, correct. But they are much more than that.

ES6 Generators can be seen as a form of delimited continuations. They don't provide the same primitives as defined in the academical papers on the topic, but still the abstraction is powerful enough.

Lets see how we can model any effectful (monadic) computation with it (assuming pure functions setup). The types won't be mathematically correct, I'm just demonstrating an idea, of how the effectful computations may look like in the "native" JavaScript notation.

One way of looking at the effectful computation is that in the place where an effect is used, a message is sent to the outer context, where it is handled (or "interpreted") and the result is returned. If you think about it, this is exactly what the yield construct does.

We start with the types for effect, and effect handler.

type Effect = { kind : string }
type EffectHandler<E extends Effect> = (e : E) => unknown

Then we define our "runner" - a function that receives the effect handler, the effectful generator and combines them together:

function runGeneratorSyncWithEffect<ResultT, YieldT extends Effect, ArgsT extends any[]> (
    effectHandler   : EffectHandler<YieldT>,
    func            : (...args : ArgsT) => Generator<YieldT, ResultT, any>,
    args            : ArgsT,
    scope?          : any
) : ResultT
{
    const gen       = func.apply(scope || null, args)

    let iteration   = gen.next()

    while (!iteration.done) {
        iteration   = gen.next(effectHandler(iteration.value))
    }

    return iteration.value
}

And we are ready to model the State effect (State monad). It consists from 2 effects - get and set:

type EffectStateGet = { kind : 'state_get' }
type EffectStateSet = { kind : 'state_set', value : number }

Our effectful function performs increment:

type EffectStateGet = { kind : 'state_get' }
type EffectStateSet = { kind : 'state_set', value : number }

const effectfulFunction = function * () : 
    Generator<EffectStateGet | EffectStateSet, void, { value : number }> 
{
    const state = yield { kind : 'state_get' }

    yield { kind : 'state_set', value : ++state.value }
}

Then, handler is tied to a local state with initial value 0:

const state = { value : 0 }

const effectHandler : EffectHandler<EffectStateGet | EffectStateSet> = e => {
    switch (e.kind) {
        case 'state_get': 
            return state
        case 'state_set': 
            return state.value = e.value
    } 
}

And finally we run the effectful function in our context:

runGeneratorSyncWithEffect(
    effectHandler,
    effectfulFunction,
    [],
    null
)

console.log(state.value) // 1

We have successfully incremented the 0 to 1, using pure functions only! :D

Note, how this example is similar to Haskell "run" functions, which usually accompanies every monadic type.

Of course this is just a toy example, more practical examples of what can be done with generators can be found here.

Still, this example has an interesting property of trivial effects composition. One just need to compose effect handlers - delegate to the next handler, if current can not handle the effect. Meanwhile, the effects composition is still an area of the active research in the FP community.

ChronoGraph uses generators to model stack-less computations - the stack is "extracted" into the data, so computations can reference each other at practically unlimited depth. More on this later.

How do you use generators in your codebase? Spread the knowledge in the comments.

Also, if you like the generators too, consider upvoting and bumping this bugzilla issue and see this issue why.

Chronograph of the week from:
Shane Lin, https://www.flickr.com/photos/shanelin/4294392709/, published under https://creativecommons.org/licenses/by-sa/2.0/