Promises are the monad of asynchronous programming

In my introduction to monads in JavaScript we saw a couple of monads and examined the commonality between them to expose an underlying design pattern. Before I get on to how that applies to asynchronous programming we need to take one final diversion and discuss polymorphism.

Consider the list monad that we implemented before:

var compose = function(f, g) {
  return function(x) { return f(g(x)) };
};

// unit :: a -> [a]
var unit = function(x) { return [x] };

// bind :: (a -> [a]) -> ([a] -> [a])
var bind = function(f) {
  return function(list) {
    var output = [];
    for (var i = 0, n = list.length; i < n; i++) {
      output = output.concat(f(list[i]));
    }
    return output;
  };
};

In our previous example, we just had functions that accepted an HTMLElement and returned a list of HTMLElements. Notice the type signature of bind above: (a -> [a]) -> ([a] -> [a]). That ‘a‘ just means we can put any type in its place, but the signature a -> [a] implies that the functions must return a list of things of the same type as the input. This is actually not the case, and the correct signature is:

bind :: (a -> [b]) -> ([a] -> [b])

For example, bind may take a function that maps a single String to a list of HTMLElements, and return a function that maps a list of Strings to a list of HTMLElements. Consider these two functions: the first takes a string and returns a list of nodes with that tag name, and the second takes a node and returns a list of all the class names it has.

// byTagName :: String -> [HTMLElement]
var byTagName = function(name) {
  var nodes = document.getElementsByTagName(name);
  return Array.prototype.slice.call(nodes);
};

// classNames :: HTMLElement -> [String]
var classNames = function(node) {
  return node.className.split(/\s+/);
};

If we ignore the ‘returns a list of’ aspect, we’d expect to be able to compose these to get all the class names of all the links in a document:

var classNamesByTag = compose(classNames, byTagName);

Of course, we do have lists to contend with, but because the monad just cares about the lists, not what’s in the lists, we can use it to compose the functions:

// classNamesByTag :: [String] -> [String]
var classNamesByTag = compose(bind(classNames), bind(byTagName));

classNamesByTag(unit('a'))
// -> ['profile-links', 'signout-button', ...]

The monad just cares about the ‘list of’ part, not the contents of the list. Just as a reminder, let’s recast this using the pipeline syntax we developed in the previous article:

// bind :: [a] -> (a -> [b]) -> [b]
var bind = function(list, f) {
  var result = [];
  for (var i = 0, n = list.length; i < n; i++) {
    result = result.concat(f(list[i]));
  }
  return result;
};

// pipe :: [a] -> [a -> [b]] -> [b]
var pipe = function(x, functions) {
  for (var i = 0, n = functions.length; i < n; i++) {
    x = bind(x, functions[i]);
  }
  return x;
};

// for example
pipe(unit('a'), [byTagName, classNames])
// -> ['profile-links', 'signout-button', ...]

The pipe function doesn’t actually care that bind deals with lists, and we can write its signature in a more generic way:

pipe :: m a -> [a -> m b] -> m b

In this notation, m a means ‘a monadic wrapper around a‘. For example, if the input is a list of strings, under the List monad the m refers to ‘list of’, and a refers to ‘string’. This concept of generic containers becomes extremely important when we consider how we can apply these ideas to asynchronous programming.

One common complaint levelled against Node.js is that it is easy to become mired in ‘callback hell’, where callbacks become nested so deeply it’s impossible to maintain the resulting code. There are various ways to solve this, but I think monads provide an interesting approach that highlights the need to separate business logic from code that simply glues data together.

Let’s consider a fairly contrived example: we have a file called urls.json, that contains a JSON document that contains a URL. We want to read the file, extract this URL, request the URL from the web, and print the response body. Monads encourage us to think in terms of types of data, and how they flow through a pipeline. We can model this problem using our pipeline syntax:

pipe(unit(__dirname + '/urls.json'),
        [ readFile,
          getUrl,
          httpGet,
          responseBody,
          print         ]);

Beginning with the pathname (a String), we can trace the data as it flows through this pipe:

  • readFile takes a String (pathname) and returns a String (file contents)
  • getUrl takes a String (a JSON document) and returns a URI object
  • httpGet takes a URI and returns a Response
  • responseBody takes a Response and returns a String
  • print takes a String and returns nothing

So each link in the chain produces a data type that is consumed by the next. But in Node, many of these operations are asynchronous. Rather than use continuation-passing style and deeply nested callbacks, how can we modify the return types of these functions to indicate the result might not be known yet? By wrapping them in Promises:

readFile      :: String   -> Promise String
getUrl        :: String   -> Promise URI
httpGet       :: URI      -> Promise Response
responseBody  :: Response -> Promise String
print         :: String   -> Promise null

The Promise monad needs three things: a wrapper object, a unit function to wrap a value in this object, and a bind function to help us compose the above functions. We can implement promises using the Deferrable module from JS.Class:

var Promise = new JS.Class({
  include: JS.Deferrable,
  
  initialize: function(value) {
    // if value is already known, succeed immediately
    if (value !== undefined) this.succeed(value);
  }
});

With this class, we can then implement the functions we need to solve our problem. The functions that can return a value immediately just return a value wrapped in a Promise object:

// readFile :: String -> Promise String
var readFile = function(path) {
  var promise = new Promise();
  fs.readFile(path, function(err, content) {
    promise.succeed(content);
  });
  return promise;
};

// getUrl :: String -> Promise URI
var getUrl = function(json) {
  var uri = url.parse(JSON.parse(json).url);
  return new Promise(uri);
};

// httpGet :: URI -> Promise Response
var httpGet = function(uri) {
  var client  = http.createClient(80, uri.hostname),
      request = client.request('GET', uri.pathname, {'Host': uri.hostname}),
      promise = new Promise();
  
  request.addListener('response', function(response) {
    promise.succeed(response);
  });
  request.end();
  return promise;
};

// responseBody :: Response -> Promise String
var responseBody = function(response) {
  var promise = new Promise(),
      body    = '';
  
  response.addListener('data', function(c) { body += c });
  response.addListener('end', function() {
    promise.succeed(body);
  });
  return promise;
};

// print :: String -> Promise null
var print = function(string) {
  return new Promise(sys.puts(string));
};

So we’ve now got a way to represent a deferred value simply using data types, no nested callbacks required. The next step is to implement unit and bind in such a way that the callback glue is contained within these functions. unit is very simple, it just needs to wrap a value in a Promise. bind is more complex: it accepts a Promise and a function. It must extract the value of the Promise, give this value to the function, which returns another Promise, then wait for this final Promise to complete.

// unit :: a -> Promise a
var unit = function(x) {
  return new Promise(x);
};

// bind :: Promise a -> (a -> Promise b) -> Promise b
var bind = function(input, f) {
  var output = new Promise();
  input.callback(function(x) {
    f(x).callback(function(y) {
      output.succeed(y);
    });
  });
  return output;
};

With these definitions, you should find that the pipeline shown above just works, for example if I’ve placed my GitHub API URL in the urls.json file:

pipe(unit(__dirname + '/urls.json'),
        [ readFile,
          getUrl,
          httpGet,
          responseBody,
          print         ]);

// prints:
// {"user":{"name":"James Coglan","location":"London, UK", ...

I hope this has shown why Promises (also known as Deferreds in jQuery and Dojo) are valuable, how they can help you pipe data through your code, and how this piping glue can be contained in quite a neat way. On the client side, you’ll find this pattern applies equally well to Ajax and animation; in fact MethodChain (which I’ve been using as async glue for years) is just the Promise monad applied to method calls instead of function calls.

The full working code for this article is on GitHub if you’d like to tinker with it. After that, you can dive into jQuery’s Deferred API. There’s also talk of promises making a return to Node, after they were banished in favour of continuation-passing style, so you may find you can do this without writing so much plumbing in future.

Monad syntax for JavaScript

Following on from my introduction to monads in JavaScript, and before I get into how they apply to asynchronous programming, I’d like to take a quick detour to improve the usability of the tools we’ve built up. Recall we have a function for composing functions:

var compose = function(f, g) {
  return function(x) { return f(g(x)) };
};

We have some ‘debuggable’ functions:

// sine :: Number -> (Number,String)
var sine = function(x) {
  return [Math.sin(x), 'sine was called.'];
};

// cube :: Number -> (Number,String)
var cube = function(x) {
  return [x * x * x, 'cube was called.'];
};

And finally we have the unit and bind functions for the ‘debuggable’ monad:

// unit :: Number -> (Number,String)
var unit = function(x) { return [x, ''] };

// bind :: (Number -> (Number,String)) -> ((Number,String) -> (Number,String))
var bind = function(f) {
  return function(tuple) {
    var x  = tuple[0],
        s  = tuple[1],
        fx = f(x),
        y  = fx[0],
        t  = fx[1];

    return [y, s + t];
  };
};

These let us compose our debuggable functions to create new debuggable functions:

var f = compose(bind(sine), bind(cube));
f(unit(3)) // -> [0.956, 'cube was called.sine was called.']

This is all well and good, but we should really be able to compute sin(x^3) as a one-liner. With the code we have, this expression would be:

bind(sine)(bind(cube)(unit(3)))

This is hardly convenient, especially when I tell you that the equivalent Haskell expression is:

return 3 >>= cube >>= sine

This reads like a pipeline: take 3, pass it through cube, then pass the result of that through sine. In Haskell, unit is called return, and bind is actually an operator (or infix function) called >>=. The operator >>= doesn’t just convert functions into composable form, it takes a monadic value – in our example, a (Number,String) tuple – and a debuggable function, and deals with unpacking the value from the monad, applying the function to it, and combining the result with the monad in a meaningful way.

Using our existing names, a direct translation to JavaScript of this would be:

bind( bind( unit(3), cube), sine)

Where the bind function now looks like this:

// bind :: (Number,String) -> (Number -> (Number,String)) -> (Number,String)
var bind = function(x, f) {   //  e.g. x = [3, ''], f = cube
  var y  = x[0],              //           3
      s  = x[1],              //           ''
      fy = f(y),              // cube(3) = [27, 'cube was called.']
      z  = fy[0],             //           27
      t  = fy[1];             //           'cube was called.'
  
  return [z, s + t];
};

This representation is clearer, but not quite as expressive as the Haskell version. Let’s go one step forward:

var y = pipe(unit(3), [cube, sine])

This seems reasonably close to Haskell’s version, and to go any further we’d really need some syntactic abstractions that JavaScript does not have. This pipe function is straightforward to implement: it takes a monadic value, and uses bind to pipe it through the list of debuggable functions:

// pipe :: (Number,String) -> [Number -> (Number,String)] -> (Number,String)
var pipe = function(x, functions) {
  for (var i = 0, n = functions.length; i < n; i++) {
    x = bind(x, functions[i]);
  }
  return x;
};

We can easily use this with anonymous inline functions without losing much expressiveness:

var z = pipe(unit(7), [ function(x) { return [x+1, 'inc.'] },
                        function(x) { return [2*x, 'double.'] },
                        function(x) { return [x-1, 'dec.'] }
                      ])

// z == [15, 'inc.double.dec.']

Here we’ve calculated (2 * (7 + 1)) - 1 using fairly direct syntax, where the operations and the log messages are nicely separated. If you’ve done a lot of asynchronous programming, this will probably be starting to look somewhat familiar, and indeed I’ll be showing where this leads in the next article.

Translation from Haskell to JavaScript of selected portions of the best introduction to monads I’ve ever read

(With apologies to John Gruber and A Neighborhood of Infinity.)

I know, I know, the world does not need yet another introduction to monads (or yet another article complaining that world does not need yet another introduction to monads). So you’ll be glad to know this isn’t one of those, in the sense that it’s not new. I thought I’d write it because, first, monads are worth knowing about, and second, because I want to get into how they relate to asynchronous programming and I want a baseline in JavaScript to help explain things I might write later. It’s also a valuable exercise in thinking in terms of types. If you’re fine reading a little Haskell, I highly recommend you read the original article, You Could Have Invented Monads (And Maybe You Already Have).

First up, a little back story. Monads are more prevalent in Haskell because it only allows pure functions, that is functions that do not have side effects. Pure functions accept input as arguments and emit output as return values, and that’s it. The languages I typically use (Ruby and JavaScript) do not have this constraint, but it often turns out to be a useful discipline to enforce yourself. The typical monad introduction will tell you that monads are all about sneaking side effects into this model so you can do I/O, but that’s just one application. Monads are really about composing functions, as we’ll see.

Let’s consider an example. Suppose you have a function for finding the sine of a number, which in JavaScript would be a simple wrapper around the Math library:

var sine = function(x) { return Math.sin(x) };

And you have another function for taking the cube of a number:

var cube = function(x) { return x * x * x };

These functions take one number as input and return one number as output, making them composable: you can use the output of one as the input to the next:

var sineCubed = cube(sine(x));

Let’s create a function to encapsulate function composition. This takes two functions f and g and returns another function that computes f(g(x)).

var compose = function(f, g) {
  return function(x) {
    return f(g(x));
  };
};

var sineOfCube = compose(sine, cube);
var y = sineOfCube(x);

Next we decide that we need to debug these functions, and we want to log the fact that they have been called. We might do this like so:

var cube = function(x) {
  console.log('cube was called.');
  return x * x * x;
};

But we’re not allowed to do this in a system that only allows pure functions: console.log() is neither an argument nor a return value of the function, it is a side effect. If we want to capture this logging information, it must form part of the return value. Let’s modify our functions to return a pair of values: the result, and some debugging information:

var sine = function(x) {
  return [Math.sin(x), 'sine was called.'];
};

var cube = function(x) {
  return [x * x * x, 'cube was called.'];
};

But we now find, to our horror, that these functions don’t compose:

cube(3) // -> [27, 'cube was called.']
compose(sine, cube)(3) // -> [NaN, 'sine was called.']

This is broken in two ways: sine is trying to calculate the sine of an array, which results in NaN, and we’re losing the debugging information from the call to cube. We’d expect the composition of these functions to return the sine of the cube of x, and a string stating that both cube and sine were called:

compose(sine, cube)(3)
// -> [0.956, 'cube was called.sine was called.']

A simple composition won’t work here because the return type of cube (an array) is not the same as the argument type to sine (a number). A little more glue is required. We could write a function to compose these ‘debuggable’ functions: it would break up the return values of each function and stitch them back together in a meaningful way:

var composeDebuggable = function(f, g) {
  return function(x) {
    var gx = g(x),      // e.g. cube(3) -> [27, 'cube was called.']
        y  = gx[0],     //                 27
        s  = gx[1],     //                 'cube was called.'
        fy = f(y),      //     sine(27) -> [0.956, 'sine was called.']
        z  = fy[0],     //                 0.956
        t  = fy[1];     //                 'sine was called.'
    
    return [z, s + t];
  };
};

composeDebuggable(sine, cube)(3)
// -> [0.956, 'cube was called.sine was called.']

We’ve composed two functions that take a number and return a number+string pair, and created another function with the same signature, meaning it can be composed further with other debuggable functions.

To simplify things, I’m going to need to borrow some Haskell notation. The following type signature says that the function cube accepts a number and returns a tuple containing a number and a string:

cube :: Number -> (Number,String)

This is the signature that all our debuggable functions and their compositions have. Our original functions had the simpler signature Number -> Number; the symmetry of the argument and return types is what makes these functions composable. Rather than writing customized composition logic for our debuggable functions, what if we could simply convert them such that their signature was:

cube :: (Number,String) -> (Number,String)

We could then use our original compose function for glueing them together. We could do this conversion by hand, and rewrite the source for cube and sine to accept (Number,String) instead of just Number but this doesn’t scale, and you end up writing the same boilerplate in all your functions. Far better to let each function just do its job, and provide one tool to coerce the functions into the desired format. We’ll call this tool bind, and its job is to take a Number -> (Number,String) function and return a (Number,String) -> (Number,String) function.

var bind = function(f) {
  return function(tuple) {
    var x  = tuple[0],
        s  = tuple[1],
        fx = f(x),
        y  = fx[0],
        t  = fx[1];
    
    return [y, s + t];
  };
};

We can use this to convert our functions to have composable signatures, and then compose the results.

var f = compose(bind(sine), bind(cube));
f([3, '']) // -> [0.956, 'cube was called.sine was called.']

But now all the functions we’re working with take (Number,String) as their argument, and we’d much rather just pass a Number. As well as converting functions, we need a way of converting values to acceptable types, that is we need the following function:

unit :: Number -> (Number,String)

The role of unit is to take a value and wrap it in a basic container that the functions we’re working with can consume. For our debuggable functions, this just means pairing the number with a blank string:

// unit :: Number -> (Number,String)
var unit = function(x) { return [x, ''] };

var f = compose(bind(sine), bind(cube));
f(unit(3)) // -> [0.956, 'cube was called.sine was called.']

// or ...
compose(f, unit)(3) // -> [0.956, 'cube was called.sine was called.']

This unit function also lets us convert any function into a debuggable one, by converting its return value into an acceptable input for debuggable functions:

// round :: Number -> Number
var round = function(x) { return Math.round(x) };

// roundDebug :: Number -> (Number,String)
var roundDebug = function(x) { return unit(round(x)) };

Again, this type of conversion, from a ‘plain’ function to a debuggable one, can be abstracted into a function we’ll call lift. The type signature says that lift takes a function with signature Number -> Number and returns a function with signature Number -> (Number,String)

// lift :: (Number -> Number) -> (Number -> (Number,String))
var lift = function(f) {
  return function(x) {
    return unit(f(x));
  };
};

// or, more simply:
var lift = function(f) { return compose(unit, f) };

Let’s try this out with our existing functions and see if it works:

var round = function(x) { return Math.round(x) };

var roundDebug = lift(round);

var f = compose(bind(roundDebug), bind(sine));
f(unit(27)) // -> [1, 'sine was called.']

We’ve discovered three important abstractions for glueing debuggable functions together:

  • lift, which converts a ‘simple’ function into a debuggable function
  • bind, which converts a debuggable function into a composable form
  • unit, which converts a simple value into the format required for debugging, by placing it in a container

These abstractions (well, really just bind and unit), define a monad. In the Haskell standard library it’s called the Writer monad. It’s probably not clear what the generic parts of the pattern are yet, so let’s take another example.

One problem you’ve likely dealt with many times is deciding whether a function should accept a single item as input or a list of items. The distinction is usually a matter of inserting a for loop around the function body, and this is usually boilerplate. But it does have a significant impact on how you are allowed to compose these functions. For example, suppose you have a function whose job is to take one DOM node and return all its children as an array; its function signature says that it takes a single HTMLElement and returns an array of HTMLElements.


// children :: HTMLElement -> [HTMLElement]
var children = function(node) {
  var children = node.childNodes, ary = [];
  for (var i = 0, n = children.length; i < n; i++) {
    ary[i] = children[i];
  }
  return ary;
};

// e.g.
var heading = document.getElementsByTagName('h3')[0];
children(heading)
// -> [
//      "Translation from Haskell to JavaScript...",
//      <span class=​"edit">​…​</span>​
//    ]

Now suppose I want to find the grandchildren of the heading, that is the children of the children of the heading. Intuitively, this seems like a good definition:

var grandchildren = compose(children, children)

But children does not have symmetric input and output types, so we cannot compose it like this. If we were to write grandchildren by hand, it might look like this:

// grandchildren :: HTMLElement -> [HTMLElement]
var grandchildren = function(node) {
  var output = [], childs = children(node);
  for (var i = 0, n = childs.length; i < n; i++) {
    output = output.concat(children(childs[i]));
  }
  return output;
};

We simply find all the children of all the children of the input node, and concatenate the resulting lists to produce one flat list of all the grandchildren. But this is not a convenient way to write it, and in fact contains a lot of boiler plate that results from the fact we’re working with lists, not from the problem we’re trying to solve. We’d rather just be able to compose two list-handling functions and be done with it.

Thinking back to our previous example, we need to take two steps to fix this: provide a bind function to turn children into composable form, and write a unit function to turn the initial input – the heading – into an acceptable type.

The core of the problem here is that our function accepts one HTMLElement and returns a list of them, therefore our conversions should be concerned with turning one item into a list of items and vice versa. The fact that the items are HTMLElements is not important, and in Haskell when the concrete type of something may very we use single letters to take their place. unit take an item and returns a list containing that item, and bind takes a ‘one-to-many’ function and returns a ‘many-to-many’ function.

// unit :: a -> [a]
var unit = function(x) { return [x] };

// bind :: (a -> [a]) -> ([a] -> [a])
var bind = function(f) {
  return function(list) {
    var output = [];
    for (var i = 0, n = list.length; i < n; i++) {
      output = output.concat(f(list[i]));
    }
    return output;
  };
};

We can now compose children as desired:

var div = document.getElementsByTagName('div')[0];
var grandchildren = compose(bind(children), bind(children));

grandchildren(unit(div))
// -> [<h1>…</h1>, <p>…</p>, ...]

We’ve just implemented what in Haskell is called the List monad, which lets you compose functions that map a single item to a list of items.

So what is a monad? Well, it’s a design pattern. It says that whenever you have a class of functions that accept one type of thing and return another type of thing, there are two functions that can be applied across this class to make them composable:

  • There is a bind function that transforms any function so that accepts the same type as it returns, making it composable
  • There is a unit function that wraps a value in the type accepted by the composable functions.

I should stress that this is very hand-waving imprecise definition that ignores the mathematical foundations of monads, which I don’t pretend to understand. But to someone doing the sort of programming I do, it’s a very useful design pattern to be aware of because it helps you spot accidental complexity: code that isn’t dealing directly with the problem at hand, but which is dealing with glueing data types together. Being able to spot and extract such boilerplate can radically improve the clarity of your code.