Extensible Effects in Node.js, Part 1

I'm a huge fan of typed functional programming. I've also been working with JavaScript and Node.js for a lot longer than I've been working with languages like Haskell. So when we were building out the server for Ellie I wanted to use what I've learned studying functional programming while sticking with a language and platform familiar to web developers.

A huge theme of my programming practice so far has been understanding how to represent effects like database calls and network requests in a way that is still testable. This was a major motivation behind the structure of effects in redux-loop. I've also tried to implement data-driven effects using generators in a similar fashion to redux-saga for API endpoints in Node.js. Once I started learning Haskell, reading papers and watching talks I discovered that all of these things have a formal representation.

Let's Talk About Monads

In typed functional programming, dependent sequential operations are represented by the Monad typeclass. Monads have been mischaracterized and misrepresented to death, especially when explained in the context of their existence in JavaScript. My preference is to stick to the fantasy-land spec. A Monad is an object with a chain method and an of static method that implements certain laws. It works out so that you can represent some kind of computation within that object that takes some argument and returns another of that particular Monad, and use chain to group those computations together. Here's an example using the often-quoted Maybe using daggy:

const daggy = require('daggy')

const Maybe =
  daggy.taggedSum({
    Just: ['value'],
    Nothing: []
  })

Maybe.of = value =>
  Maybe.Just(value)

Maybe.prototype.chain = function chain(callback) {
  return this.cata({
    Just: value => callback(value),
    Nothing: () => Maybe.Nothing
  })
}

// maybeTimesTwo is a value of Maybe.Just(4)
const maybeTimesTwo =
  Maybe
    .of(2)
    .chain(x => Maybe.Just(x * 2))

// maybeTimesThree is a value of Maybe.Nothing
const maybeTimesThree =
  Maybe
    .Nothing
    .chain(x => Maybe.Just(x * 3))

Maybe is a Monad because it implements the proper methods and laws. But more importantly, Maybe is useful because it encodes the computation of verifying the existence of a value. It is a type that represents the act of checking for null or undefined in a way that is purely functional and lacks the risk of forgetting to do so. Being able to encode an explicit type of computation as a type is an incredibly powerful and generalizable concept. Let's look at another example.

Below we're importing the Task class from Folktale's data.task

const fs = require('fs')
const Task = require('data.task')

const readFile = path =>
  new Task((reject, resolve) => {
    fs.readFile(path, (error, data) => {
      if (error) reject(error)
      else resolve(data)
    })
  })

const writeFile = (path, data) =>
  new Task((reject, resolve) => {
    fs.writeFile(path, data, (error) => {
      if (error) reject(error)
      else resolve(null)
    })
  })

readFile('./in.txt')
  .chain(data => writeFile('./out.txt', data.toLowerCase())
  .chain(() => readFile('./out.txt'))
  .fork(
    error => console.error(error),
    result => console.log('success!', result))

Task is a Monad because it implements the proper methods and laws. But it is useful because it allows us to represent asynchronous control flow in a way that is still purely functional.

Note:

Tasks differ from Promises in a critical way. When you create a Promise either with new Promise(...) or by calling a function that returns one, you begin the async operation immediately. A Task, however, will hold on to its executor function (the thing we pass into new Promise(...) or new Task(...)) until you call task.fork(...). It saves its computation for later so that any function that returns a Task without forking it is still a pure function.

Now, Maybe and Task are way cool and I use them extensively in my Node.js services, but they are super specific in what they do. This means a couple things:

1. You can't chain a Maybe into a Task directly. You need to transform one into the other first.
2. Especially in the case of Tasks, you can't test the outcome of the logic you use to chain them together without executing them first. Tasks might technically be pure, but this comes at the cost of totally swallowing up your logic code, making it impossible to test the properties of your logic without including your whole effectful environment.

Freerdom

If we want to achieve the goal that I had previously sought with redux-loop, and tried to distill from redux-saga, what we really need are two Monads. One will serve as the representation of our computations and the other will serve as the semantics. We'll write our app code using the representaion, and then write a transformation from representation to semantics that we can call outside of that app code to do the real work like making calls to the database. We want this representation to be a simple data type, like we had with Maybe. Notice the difference between Task and Maybe from before. We could make Maybe from just a series of options that held on to values (a tagged sum type) using daggy, where as Task is much more complex and specialized. We don't have the testing issue laid out in concern #2 with Maybe because it is pure and allows data to just flow through it.

We want to do the same thing for our representation Monad, but we want to do it in a way that allows us to produce a Monad for any tagged sum type. This will allow us to refactor and add functionality at will without having to update our implementation for chain, of, or any of the other functions we might want to use in our app code. This kind of Monad exists and is formally known as the Freer Monad.

Here is a minimal formulation using daggy and adding our own functions.

const fmap = f => x => {
  if (x instanceof function) return compose(f, x)
  else if (typeof x.map === 'function') return x.map(f)
  else throw Error(`${x is not a Functor}`)
}

const Freer =
  daggy.taggedSum({
    Pure: ['a'],
    Lift: ['f a', 'a -> b'],
    Chain: ['Freer f (Freer f a)'],
  })

Freer.prototype.map = function map(f) {
  return this.cata({
    Pure: (x) => Freer.Pure(f(x)),
    Lift: (x, g) => Free.Lift(x, compose(f, g)),
    Chain: (x) => Free.Chain(fmap(fmap(f), x))
  })
}

Freer.prototype.chain = function chain(f) {
  return Freer.Chain(this.map(f))
}

Freer.prototype.foldMap = function foldMap(f, point) {
  return this.cata({
    Pure: a => point(a),
    Lift: (x, g) => f(x).map(g),
    Chain: x => x.foldMap(f, point).chain(y => y.foldMap(f, point)),
  })
}

Freer.of = a =>
  Freer.Pure(a)

Freer.liftF = f =>
  Freer.Lift(f, identity)

There's a lot going on here. Let's go over each part one at a time.

const fmap = f => x => ...

Here we need to define a way to map over values where we don't know ahead of time whether that value will implement Functor explicitly. For our particular usage we either want to map over something with an explicit Functor or map over a function. In Haskell a Functor instance is already defined for functions, but this is JavaScript so we have to be sneaky. Mapping over a function is the same as right composition.

Pure: ['a']

This member of our tagged sum will allow us to pick up any value and place it in the context of our Freer Monad. This allows us to bring in pure values to a computation like we did with Maybe and Maybe.of(2).

Lift: ['f a', 'a -> b']

This member of our tagged sum allows us to take another value f which is itself a container of some value a, and map over that value even though we don't expect f a to have a map method. Instead we hold on to the functions that we are mapping with in the second slot 'a -> b' and compose them together until we convert our f container to a Monad that does know how to map. This is a part of how Freer gets its name. For any container type f of some other type a, Freer f a is Functor.

Chain: ['Freer f (Freer f a)']

This member allows us to store up series of computations in our chain so that when we convert our representation Monad to a Monad that actually does something we can chain those computations together using our stored callbacks. Don't worry too much about the type of the value that Chain stores. It is sufficient to know that we'll be taking some container type f, the same f from before, and having it hold onto another value of our Freer Monad. This builds up a chain of descriptions of computations sort of like a list, and we can later step through it, create effects using Task, and then chain those Tasks together.

Freer.prototype.map = ...

Here we define how to map over each possible case. In the case of Pure, we can call the mapping function directly on the value. For Lift, we don't know how to map our container type yet so we just compose this new mapping function with the one that was already there. Chain is a bit more complicated. Remember, chain holds onto another value of Freer, creating almost literally a chain. Since we know it's a value of Freer we know we can map over it. The function we want to map, though, isn't the mapping function itself but a function that will map the inner value of the chain using the mapping function. We're delegating the responsibility to map to the value within as a new step in the chain.

Freer.prototype.chain = ...

Here we define how to insert new computations into the chain. Recall that the function coming in to the chain method takes any value and produces a Monad containing a new value, thereby encapsulating the computation inside of the Monad it returns. In the case of Freer, since Freer only represents computation rather than performing it, we just map the previous step onto a new value of Freer using the callback and then place it as a new step in the chain. As your computation description grows you end up with a Freer within a container within a Freer within a container, all the way down to either a Lift or a Pure. We'll never end up with an infinite Freer by accident because we will never expose a way to create a Freer that doesn't start with either Lift or Pure. This is the other side of the Freer Monad's name. Since we can map over a Freer thanks to Lift, we can also chain it. This gives us a Monad "for free".

Freer.prototype.foldMap = ...

This is where the magic happens! We've seen mentioned the idea of converting a Freer for some container into another Monad that does real work. That conversion is frequently called an interpreter, and we pass it into the first argument of foldMap. Rather than go into too much detail, we'll write our own effect container and interpreter soon to show how foldMap is used. The second argument to foldMap, point, is simply a way to create a value of our execution Monad from a pure value. In the case of Tasks, as we will soon see, you would pass in Task.of as the value for point.

Freer.of = ...

Not very exciting, the of static method just delegates to Pure like we said it would.

Freer.liftF = ...

Slightly more interesting, liftF lets us take one of these containers we keep mentioning and convert it into a Freer. Since Lift must always hold onto a function for mapping over the output once we convert our container to another Monad like Task, we can start with the identity function x => x and have a Freer for whatever our container is holding while still having something to compose with later on when we map and chain. Starting with identity is like starting with a baseline value, like you might do with an empty array or an empty string if you want to avoid using null in your code.

Putting Freer To Work

Okay! So we've waded through all the nasty definition stuff. Let's actually see how this ends up being useful in practice. Below we'll use daggy again to create a structure, often refered to as an AST, for some file system operations. Then we'll use Freer.liftF to expose an API for creating chainable file system effects. Lastly, we'll write our interpreter to convert our file system AST into a Task that will actually do the work of interacting with the file system.

const fs = require('fs')
const Task = require('data.task')
const daggy = require('daggy')
const Freer = require('./Freer')

const Effect =
  daggy.taggedSum({
    ReadFile: ['path', 'callback'],
    WriteFile: ['path', 'data', 'next']
  })

const readFile = path =>
  Freer.liftF(Effect.ReadFile(path, identity))

const writeFile = (path, data) =>
  Freer.liftF(Effect.WriteFile(path, data, null))

const interpreter = (effect) =>
  effect.cata({
    ReadFile: (path, callback) => {
      return new Task((reject, resolve) => {
        fs.readFile(path, (error, data) => {
          if (error) reject(error)
          else resolve(callback(data))
        })
      })
    },
    WriteFile: (path, data, next) => {
      return new Task((reject, resolve) => {
        fs.writeFile(path, data, (error) => {
          if (error) reject(error)
          else resolve(next)
        })
      })
    }
  })

readFile('./in.txt')                                         // Freer (Effect String)
  .chain(data => writeFile('./out.txt', data.toLowerCase())) // Freer (Effect null)
  .chain(() => readFile('./out.txt'))                        // Freer (Effect String)
  .foldMap(interpreter, Task.of)                             // Task Error String
  .fork(                                                     // undefined, we're doing side-effects now
    error => console.error(error),
    result => console.log(result))

We've heard a lot about how Freer contains data that is itself a container. This manifests itself in our Effect type for the file system through the last entry in each sum constructor. For ReadFile, it's callback. We take a callback because we'll be getting some result, a string, from the file system and we'll need to hand it off to the next value in the chain. The machinery of Freer determines what that callback actually is based on whether it's a Chain, a Lift, or a Pure. Freer's machinery also figures out within foldMap how to continue interpreting the result of that callback. The next value for WriteFile is a little simpler. Since we don't plan to pass on any data we just hold on to the next step in the chain, as determined by the machinery of Freer.

So now we have a nice little API in readFile, writeFile, and interpreter that we can use to represent the effects of the file system without actually tying ourselves to the code that interacts with the file system. Our intention is represented by the Freer (Effect x), and the meaning behind that intention is fully encapsulated by the interpreter. I know this looks like a ton of work for what we could just do with Tasks or Promises or even callback-style functions, but it has amazing implications.

The Interpretation is in the Eye of the Beholder

Remember when we discussed passing point to Freer.foldMap? This means that as long as our interpreter function returns a Monad, we can interpret it anyway we want! This includes interpreting to a synchronous, pure Monad like a State Monad that can interact with a fake file system, allowing us to test effectful file system code without having to deal with async control flow inside our tests, or even the existence of a file system. Crazy, right?

Note:

In this example, don't worry too much about the implementation of the State Monad. Just know that it allows for some shared object to be updated in a Monadic way from one computation to another, and that we can pass in that object once we're ready to execute our computation.

const test = require('tape')
const State = require('some-imaginary-state-monad-lib')

// ...

const testInterpreter = effect =>
  effect.cata({
    ReadFile: (path, callback) => {
      return State
        .get()
        .map(s => {
          if (!s.hasOwnProperty(path)) throw Error('not found')
          return callback(s[path])
        })
    },
    WriteFile: (path, data, next) => {
      return State
        .put({ [path]: data })
        .map(() => next)
    }
  })

test('file system stuff works', t => {
  const result =
    readFile('./in.txt')                                         // Freer (Effect String)
      .chain(data => writeFile('./out.txt', data.toLowerCase())) // Freer (Effect null)
      .chain(() => readFile('./out.txt'))                        // Freer (Effect String)
      .foldMap(testInterpreter, State.of)                        // State String
      .evalState({ './in.txt': 'HELLO' })                        // String

  t.equal(result, 'hello')
  t.end()
})

That's all it takes! We can reason about the logic in our tests without even needing to to know that there's an effectful interpretation of that logic somewhere else. This lets us dig in and verify properties of the code between the nodes of the chain so we can be sure our system is behaving as we expect without needing to run it inside of the whole enormous environment that it will live in during runtime.

That's all for Part 1. Next time we'll learn about making error handling a first-class feature, with the ability to both trigger and capture errors as a part of your Monad chains. We'll also learn about co-opting JavaScript's generators to introduce a nice, synchronous-looking syntax for chaining Freer inspired by Haskell's do. If you have any questions, please feel free to reach out on Twitter at @luke_dot_js.