From Callback to Future -> Functor -> Monad

Motivation

A fundamental concept in functional programming is composition. It simply describes the mechanism by which we combine simpler things to build more complicated things, then combine the new resulting things to build higher-complicated things and so on.

With composition, you never hit a wall, because you must always ask yourself “What is the return value of this function ?”, or put another way “What is the meaning of this thing ?”

If you’ve been in Node.js you are certainly aware of the code below

fs.readFile('...', function (err, data) {if (err) throw err;....});

As a quick reminder, the code above is a typical use of _continuation-passing style (CPS)_functions. The CPS function, ‘fs.readFile’, takes an extra parameter, which is a callback representing the continuation. Once finished, the CPS, instead of returning a value to the caller, calls the continuation function, the callback, passing it the result of it’s own computation.

I don’t mind using callbacks in my code. In fact, callbacks are great for things such as representing side effects or event notification, but once your start using them to manage your control flow, you’re trapped. Why ? because they do not compose.

So let’s just ask “What’s the meaning, the denotation or the return value of the above function ?”. The answer is ‘undefined’. And we can’t do anything useful with ‘undefined’, apart from testing that it’s actually … undefined.

The problem is that, inside the callback, you’ve been teleported to another flow of execution and this is a one way ticket.

Think of callbacks as the famous Black holes of physics:

A black hole is a mathematically defined region of spacetime exhibiting such a strong gravitational pull that no particle or electromagnetic radiation can escape from it

Particularly

In many ways a black hole acts like an ideal black body, as it reflects no light

Callback functions, also, reflect no light in a program flow.

If later, while trapped inside the first callback, you use another callback style function, then you lose the second flow and you fall into another hole. The more you use callbacks, the more you sink into hell.

So how can we move forward in our code without falling into black holes?

The answer is composition. But to use composition, we must get something from a function, and we know that CPS functions do not reflect anything. So we must, someway, make them return something. But what value are they supposed to return ? Well this is the motivation for this article.

Even if you are already aware of existing JavaScript solutions. I, strongly, recommend you to go through this post. You’ll see the power of denotational (ie functional) thinking and how it allows us to derive clean and concise semantics for those solutions.

Welcome to the future

If we think about those functions: file read operations, network requests, DOM events, … what do they have in common?

They describe operations that can not be achieved in the immediate, I mean we can not afford to wait for their completion in our current program flow (like we do with normal functions). So they describe future results.

So let’s make them return a special type: Future, to denote their eventual outcome. The key idea is to have a first class value which can be passed to other functions.

What’s the meaning of a Future ? it simply denotes a value who will occur after a certain time (which can be 0). The meaning of time can be an explicit event like when we say after x seconds, but can also given in relative terms, like when we say that 2 Futures complete at the same time or that a Future completes after another one.

Now this is important:

Outcome of a Future always denotes an immutable value.

That means, in any way we can’t change the completion value. This constraint doesn’t just simplify our implementation, it also simplifies our reasoning about its semantics.

Our Future could be implemented with a dead simple state machine. The machine starts as pending then evolves to completed and will stop here. Once completed, it’ll stay forever.

Internally, the ‘Future’ type will still rely on callbacks, but they will not serve any control flow mechanism. Instead, we’ll use them only for their right purpose: event notification.

function Future() {// a list to store pending subscribersthis.slots = [];}

// notify completionFuture.prototype.ready = function(slot) {if(this.completed)slot(this.value);elsethis.slots.push(slot);}

//a simple log utilityfunction logF(f) {f.ready( v => console.log(v) );}

We provide external implementors with a method to complete the Future

Future.prototype.complete = function(val) {// ensure immutabilityif(this.completed)throw "Can't complete an already completed future!"

this.value = val;  
this.completed = true;

// notify subscribers  
for(var i=0, len=this.slots.length; i<len; i++) {  
    this.slots\[i\](val);  
}

// release all, we don't need this anymore  
this.slots = null;  

}

The simplest example of a Future, is one that completes immediately with a given value. We’ll define a method called unit with that purpose

// unit : Value -> Future<Value>Future.unit = function(val) {var fut = new Future();fut.complete(val);return fut;}

logF( Future.unit('hi now') );

Above, i used a type annotation to makes it simple to reason about the code:

‘unit : Value → Future<Value>’ means simply that:

1. ‘unit’ is a function
2. it takes a generic type ‘Value’ as input and
3. returns a ‘Future’ instance holding a value of this generic type.

Using the generic term ‘Value’ means we don’t actually care about the type, because the type information is irrelevant here.

another example is a value delayed by some time

// delay: (Value, Number) -> Future<Value>Future.delay = function(v, millis) {var f = new Future();setTimeout(function(){f.complete(v);}, millis);return f;}

logF( Future.delay('hi, it\'s been 5 seconds', 5000) );

The result of ‘delay’ is a Future that completes after a given duration with a given value.

Getting back to the ‘readFile’ example, instead of CPS functions, we can now uses a function returning a Future :

var fs = require('fs');

// readFileF: (String, Object) -> Future<String>function readFileF(file, options) {var f = new Future();fs.readFile(file, options, function (err, data) {// We'll deal with errors later in the postif (err) throw err;f.complete(data);});return f;}

logF( readFileF('test.txt', { encoding: 'utf8'}) )

The result of ‘readFileF’ denotes a Future holding the content of a file whose name is given as argument.

Acting on Futures: meet our 1st guest

You can think of ‘Future’ as a magic box holding the eventual outcome of a function.

But in order to do anything useful, we have to provide our Future type with some useful operations. Otherwise i’ll be just as if we’ve created another useless `undefined`.

So what operations can we describe in terms of Futures ?

Let’s start with computations on values held by the Future box, we’ll call it ‘fmap’ (a contraction of function map or perhaps better future map)

Here’s an example of ‘fmap’. Given a Future holding the content of a text file, we’d like to calculate the length of this content.

var textF = readFileF('test.txt', { encoding: 'utf8'});

// fmap: ( Future<String>, (String -> Number) ) -> Future<Number>var lengthF = textF.fmap( text => text.length )logF( lengthF )

The meaning of ‘lengthF’ is a Future holding the length of a file whose content is held itself by a given Future.

To generalize, ‘fmap’ takes 2 inputs:

1. a Future value
2. a mapping function over normal values.

Its output is a Future holding the result of the mapping function applied to the outcome of the input Future. Note that both input and output complete at the same time.

Informally, we can describe it like this

fmap( Future<value>, func ) = Future< func(value) >

Implementing `fmap` is just a few lines (we’re going to define it as a method on the Future prototype)

Future.prototype.fmap = function(fn) {var fut = new Future();this.ready(function(val) {fut.complete( fn(val) );});return fut;}

We complete the output Future when the input Future completes. And we take care of applying the mapping function.

Back to the example above, we transformed a Future holding the content of a file to another Future holding the length of this content.

Sounds familiar ? it’s quite similar to the well known map method of JavaScript arrays. Actually, it’s exactly the same concept:

• the ‘Array’ type is a box holding multiple values
• the ‘Future’ type is a box holding a future value
• ‘Array.map(…)’ transforms the values inside the Array box and gives us another Array box encapsulating the transformed values
• ‘Future.fmap(…)’ transforms the value inside the Future box and gives us another Future box encapsulating the transformed value.

So meet our 1st guest, we say both Array and Future types are Functors. That’s because they can take a normal function, apply it to whatever inside and return another instance representing the result of the transformation.

Array and Future aren’t the only Functors, whenever you encounter

• a type acting as a context for other types
• knows how to apply a normal function inside it

then there is a good chance that this type is a Functor.

Now that we are able to map futures to another futures. it would be be cool if we can apply functions directly to Futures like we do with normal values.

So Instead of calling

textF.fmap( c => c.length )

we would like to have a special kind of function ‘lengthF’ that acts directly on Futures

// lengthF : Future<String> -> Future<Number>function lengthF(strF) {return strF.fmap( s => s.length )}

Looks trivial, yet we can now rewrite the file example like this

nbCharsF = lengthF( readFileF('...') )

We say that ‘lengthF’ is a lifted function. Lifting a function over a box-type like functors promotes function application from normal values to the box-type values. In our case, we are lifting a function ‘length: String -> Number’ which acts on Strings to a function ‘lengthF: Future<String> -> Future<Number>’ which acts on Futures.

To generalize, we define a function called ‘lift1’ (because it lifts only functions with arity 1, ie taking 1 input)

Future.lift1 = function(fn) {return fut => fut.fmap(fn);}

This simple abstraction allows us to convert an asynchronous invocation into a normal function invocation. In our example ‘lengthF( readFileF(…) )’.

By composing ‘readFileF’ with ‘lengthF’ we are able to denote asynchronous computations yet without leaving the main program flow.

How about functions with many arguments ? (or Meet our 2nd guest)

Before we answer this question, let’s take a little time to think about a fundamental fact: What types are allowed to live inside our Future box ? do a Future have the same meaning for all types ?

The meaning of a ‘Future<String>’ is obvious: a value of type string that will be available in the future. Can the same reasoning be extended to all other types ? Numbers, Objects, Arrays ? certainly … How about Futures themselves ? what’s the meaning of ‘Future<Future>’, ie a Future of a Future ?

To get an intuition for this idea, let’s pick a simple example, we want to inspect a directory then read the content of the first file inside (for simplicity we’ll suppose there are no nested directories).

in Node we can use the async function ‘fs.readdir’ to get an array of file names inside a given directory. We’ll first derive our Future-ish function

// readDirF : String -> Future< Array<String> >function readDirF(path) {var f = new Future();fs.readdir(path, (err, files) => {// hold on, it's comingif (err) throw err;f.complete(files);});return f;}

The meaning of ‘readDirF’ is a Future holding an array of the names of the files in a given directory.

In order to solve our problem, we need to

1. Read the content of a directory which gives us a Future holding an array of Strings representing file names.
2. Pick the first file name then read its content.

Can we use ‘fmap’ here ? let’s see what happens if we run this code in Node

var resultF = readDirF("testdir").fmap(files => readFileF(files[0]))

logF( resultF )

And we get…oops

{ slots: [] }

Clearly, there is something wrong here. Instead of getting the content of the file in the console, we get the the textual representation of an object which is obviously a Future instance.

That’s because ‘fmap’ takes whatever result is returned by its mapping function and completes the output Future with it. As the mapping function above returned another Future (the result of ‘readFileF’), ‘fmap’ just blindly completed ‘resultF’ with it.

But a Future can’t complete with another Future, it has still to wait for the resulting, nested Future to complete before going on.

So we need a guard function to watch for this case. Instead of completing immediately, it’ll wait for the nested Future to complete.

We’ll call it ‘flatten’, because it flattens a ‘Future<Future>’ (a 2 layered Future) into a simple Future

// flatten: Future< Future<Value> > -> Future<Value>Future.prototype.flatten = function() {var fut = new Future();this.ready(function(fut2) {fut2.ready( function(val){fut.complete(val);} );});return fut;}

And we can get our result like this

var result =readDirF("testdir").fmap(files => readFileF(files[0], {encoding: 'utf8'}))

logF( result.flatten() )

Instead of calling ‘fmap’ and ‘flatten’ each time, we’ll pack this use case in a single call: an ad-hoc function that will do both operations : map to a 2 Layered Future then flatten it. To stay meaningful, we’ll name it ‘flatMap’ (awful, i know)

Future.prototype.flatMap = function( fn ) {return this.fmap(fn).flatten();}

Conceptually, what we described above is a way of sequencing 2 dependent computations, ‘readFileF’ depends on ‘readDirF’ because the first function takes its input (file name) from the outcome of the second function (list of file names).

Now let me introduce our second guest, Besides being a Functor, a Future is also a Monad, because it defines a way for describing a computation as a sequence of steps. using the above ‘flatMap’ method we can chain together multiple function calls with each step taking its input from the previous step.

As for Functors, there are many use cases for Monads; technically, all a Monad needs is

• a way of lifting a normal value to a Monadic one: in our example, it’s the ‘Future.unit’ which makes a Future from a normal value.
• a way of chaining 2 consecutive operations: each Monad has its proper logic of chaining. In our case, the logic is handled with ‘flatMap’ which is to wait for the completion of a Future before moving forward.

We’ve seen that the 2nd operation (flatMap) can also be defined in terms of 2 other operations (‘fmap’ and ‘flatten’), if you have a Functor which defines an ‘fmap’ function, all you need is a flattening operation to simplify a 2 layered structure.

So now, let’s return to the main question, how can we lift a function that takes multiple arguments to act on Futures?

Let’s pick the file example again, this time we would like to concatenate the content of all files in a given directory, our code will look like

// concatF : (Future<String>, ...) -> Future<String>var resultF = concatF( text1F, text1F, ...)

What is the meaning of the above function? The result denotes a Future holding the concatenation of all strings held by the input Futures. Logically, ‘concatF’ needs to wait for all the input Futures in order to proceed, so the output completes when all inputs compete.

for implementation, We’ll start with the case of 2 arguments

// lift2: ( (a, b) -> c) -> ( (Future<a>, Future<b>) -> Future<c>)Future.lift2 = function(fn) {return (fut1, fut2) => {fut1.flatMap( value1 =>fut2.flatMap( value2 =>Future.unit( fn(value1, value2) );))};}

In spite of the appearances, the code’s logic is rather simple, let’s go step by step:

• ‘Future.lift2’ takes a “function which acts on 2 normal values” and returns a “function which acts on 2 Futures”
• What the returned (lifted) function does actually is
• use ‘flatMap’ to sequence 2 operations (with a nested call),
• the first operation does nothing by itself, it just binds the first outcome to the variable ‘value1’ which remains visible in the scope
• the second , nested, operation, apply the function fn to the 2 outcomes: ‘value1’ and ‘value2’
• since ‘fn’ returns a normal value, and ‘flatMap’ expects a Future value, we use ‘Future.unit’ to lift the normal result to a Future result.

The trick here is: run ‘flatMap’ on all Futures in sequence allows the function to wait on all futures, and nested ‘flatMap’ calls gives the function a scope for all completion values.

The last use of ‘Future.unit’ to lift the result suggests that multi-argument lifted functions are different from Monadic ones which describes sequential operations (like ‘readFile’ inside ‘readDir’).

Here is an example that concatenates the content of 2 files

var concat2F = Future.lift2( (str1, str2) => str1+' '+str2 );

var text1F = readFileF('test1.txt', {encoding: 'utf8'});var text2F = readFileF('test2.txt', {encoding: 'utf8'});

logF( concat2F(text1F, text2F) );

Note that even in the case of the second Future ‘text2F’ completes before the first ‘text1F’, the function has still to wait for ‘text1F’. Upon its completion, the function will proceed immediately because ‘text2F’ has already completed.

We can conclude that a multi-argument function does not depend on the order of completion of its inputs, nor their interdependence. In fact, we can also reformulate this meaning like this:

• if ‘fmap’ denotes a single operation, and
• ‘flatMap’ denotes sequential operations, then
• multi-argument lifted functions denotes parallel operations.

That makes sense, because, like in the example above, we run the Futures all at once and wait for their completion before proceeding to the computation.

We can easily extend the the pattern used in lift2 to lift3 or lift4, but we’ll just generalize to an arbitrary number of arguments, all we need is the 2 tricks from above: nesting and scoping

function toArray(args) {return Array.prototype.slice.call(args);}

Future.lift = function(fn) {return function() {var futArgs = toArray(arguments), // our future argumentsctx = this; // save context ('this')

return bindArg(0, \[\]);

function bindArg(index, valArgs) {          
  // wait the current Future argument          
  return futArgs\[index\].flatMap(function(val) {    
    // collect completion values                 
    valArgs= valArgs.concat(val);

    // not yet the last Future argument ?  
    return (index <  futArgs.length - 1) ?                    
      // flatMap (wait) the next argument  
      bindArg(index+1, valArgs) :   
       
      // last reached, apply the collected vales  
      Future.unit( fn.apply(ctx, valArgs) );   
  });             
}  

}}

‘lift’ reuse the same trick used in ‘lift2’. Since we don’t know in advance the exact number of inputs, we use a recursive call to iterate over all of them, waiting for their completion then collecting the outcomes on the way (wait/flatMap Future at index, then save the completion value and repeat the process with the next Future input until all inputs are processed). Once we reach the last input Future in the chain we proceed to function application, then we return the lifted result.

We could have used another structure called ‘Applicative Functor’ to implement n-ary lifting. But then we’d have to go through some explanations involving terms like lambdas and currying, so will just skip this today.

Error handling

Recall in our process of converting ‘fs.readFile’ how we’ve ignored the error value

function readFileF(file, options) {var f = new Future();fs.readFile(file, options, function (err, data) {if (err) throw err;...

We can’t do that in a real code. Because we’re not in the main program flow (the outest), there is no way for us to catch the error. In the case above, the error propagates upward and finding no handler in the way, Node just aborts the whole program.

What if we need instead to catch the error to have a chance to fix it, or possibly redirect it to somewhere like a meaningful error message for the user.

A possible solution is to augment the semantics of Future with the notion of failure. Until now we didn’t gave any meaning to the outcome of a Future, but now we’ll think of Future as a context with 2 possible outcomes (completion or failure), so we have to review the semantics in the context of a possible failure.

First, we had a method ready to notify completion so we also define a method to notify failure.

function Future() {this.slots = [];this.failslots = [];}

Future.prototype.failed = function(slot) {if(this.hasFailed)slot(this.error);elsethis.failslots.push(slot);}

We also define a method to fail the future.

Future.prototype.fail = function(err) {if(this.completed || this.hasFailed)throw "Can't fail an already settled future!"this.hasFailed = true;this.error = err;for(var i=0, len=this.failslots.length; i<len; i++) {this.failslots[i](err);}}

Now what’s the new meaning of the ‘fmap’ operation ?

In the example ‘readFileF(…).fmap( s => s.length)’, No meaning can be given to the length of a non existing file. Logically, we’d like to transform only valid results so the output Future will complete with a transformed value only if the input Future completed with success, otherwise it’ll just fail with the same error. Also, if the mapping function failed in its transformation, we must also fail the output.

Future.prototype.fmap = function(fn) {var fut = new Future();this.ready( val => {try { fut.complete( fn(val) ); }catch(err) { fut.fail(err); }});

this.failed( err => fut.fail(err) );

return fut;  

}

For ‘flatten’ it’s a little more complicated. We have 2 futures : outer and inner, and each one has also 2 possible outcomes : completion or failure. That gives us 4 cases to handle (2x2)

Future.prototype.flatten = function() {var fut = new Future();

// 1- outer fails && inner fails => output fails  
// 2- outer fails && inner completes => output fails  
this.failed( \_ => fut.fail(err) );

// 3- outer completes && inner fails => output fails   
this.ready( fut2 =>  
    fut2.failed( err => fut.fail(err) );             
); 

// 4- outer completes && inner completes => output completes  
this.ready( fut2 =>  
    fut2.ready( val => fut.complete(val) );  
);        
return fut;  

}

In the case of ‘flatten’, the output completes only and only if both inner and outer inputs complete.

We don’t have to modify ‘flatMap’ or ‘lift’. Since they are derived from ‘fmap’ and ‘flatten’, they automatically inherit their error handling semantics.

Ok, we made our future skip all subsequent computations in case of failure, which leaves us with a failed Future. So what operations can we do with a failed Future ?

There is only one, we can catch future errors and try to fix them, how ? by defining an operation that can transform a failed Future to a completed one, which can then be reintegrated again in our computation.

We’ll have to define a peer function for ‘fmap’, we’ll call it ‘fmapError’. It’s like a flipped version of fmap

Future.prototype.fmapError = function(fn) {var fut = new Future();this.ready( val => fut.complete(val) );this.failed( err => {try { fut.complete( fn(err) ); }catch(err1) { fut.fail( err1 ); }});return fut;}

‘fmapError’ acts as an async catch statement, valid results pass through the function while errors are caught and sent in to the mapping function.

Here is a simple example

readFileF('unknown file').fmapError( err => 'alternate content' )

But what if you we want to catch errors in a monadic fashion, ie inside a pipeline of sequential operations ?

For this, we’ll define flatMapError which is nothing more than the peer version of flatMap.

Future.prototype.flatMapError = function( fn ) {return this.fmapError(fn).flatten();}

As an example of use, suppose we are trying to fetch some content from some web URL that can be sometimes unavailable, upon a failure of our request, we’ll try an alternative URL, we can use ‘flatMapError’ to catch the first failure and return the alternative request

resultF = requestF('/url1').flatMapError( err => requestF('/url2') )

The meaning of ‘resultF’ is a Future whose content is the outcome of the first request to ‘url1’ in case of a success and the outcome of the second request to ‘url2’ if the first request failed.

Side effects

We’ve defined all needed operations to describe computations in a composable way. Using the so far defined functions, we can work with asynchronous functions in a simple synchronous style, passing our Futures around as if they were normal values.

But each computation has to reach an end. That’s the right time to do our side effects operations: updating our UI, logging into the console, saving to a database…

A quick temptation is to define a special method ‘do’ to denote this type of operations. But then we have, as usual, to ask what is the meaning of do, what’s its return value ?

If we simply make it return a Future with no value transformation, then it’ll have the same denotation as ‘future.fmap( Id )’ (Id being the identity function x => x); But we know actually they are not the same. We should not have this kind of distortions in our abstract model: things that denotes the same thing are just supposed to be the same thing.

Another question is related to the meaning of time: does ‘do’ complete in the same time as the input Future ? What if our side effect operation consist of sending updates to a remote server ? we should wait for the server response. Morever the server response can (and it’s often) be relevant to our app.

In fact, it’s clear from the above, that side effect operations are nothing more than functions that are chained to a given Future and returns themselves another Future. This is precisely the denotation of ‘flatMap’ and ‘flatMapError’. Put another way, side effect operations are just Monadic functions (if you have some Haskell background, you’ve probably made the link to the IO Monad).

So what’s the point about Promises

If you are already aware of Promises, then you obviously noted the similarities between Futures and Promises, you may have also noted how I avoided to mention them all the way.

If you want, take the Future class, mix together fmap, flatMap, mapError and flatMapError into a single big monolithic method and you’ll end up with something more or less similar to the ‘Promise.then’ method.

Of course, There will be always someone to argue that implementing a Fully compliant specification of Promises is far more complicated. He may even tell me something like You’re Missing the Point of Promises.

If you take a minute to read the above Promise/A+ specification, you’ll notice it doesn’t describe the Promise operations in terms of the values they denote but rather describes a process to be followed by any compliant implementation. Put another way, the specification is operational and not denotational. Operational semantics are strongly tied to their execution model. This is why, in the specification, you can notice references to things like

onFulfilled or onRejected must not be called until the execution context stack contains only platform code

or also references to the state internals of a promise

A promise must be in one of three states: pending, fulfilled, or rejected. When pending, a promise: may transition to either the fulfilled or rejected state.

In contrast to operational semantics, Denotational semantics do not focus on what steps should be carried out, nor the internal representation in order to achieve some computation. It rather focus on the meaning of things, and this meaning must be defined in term of other meanings that are either: well defined themselves, or fairly obvious to be defined (like values or functions).

If you understand from above that the Promise specification is useless, or that Promises themselves are useless, then You are missing the point of my article. And probably you’re also (partly) missing the point of Promises.

You can always view Promises only as an imperative construct that mimics the ‘;’ (used to sequence synchronous statements), and then use them exclusively to sequence asynchronous statements. Another way is to consider them from a more functional view; ie as future values. Then you’ll start more to use them as asynchronous results of function evaluation. You’ll more and more use lifting to derive Future-ish functions and then compose those functions as you do with normal ones.

The point of this article is not to present any alternative to Promises, but essentially to demonstrate the power of denotational thinking. Along the way, we kept asking about the meaning of things and this led us to a fairly clear specification of our concept, (even if the semantics were presented in informal terms).

Using well known abstractions, like Functors and Monads, which already have solid mathematical underpinning, made it quite easy to reason about properties of Futures and derive the implementation of some operations. this may be a question of style, but i doubt we could have achieved that if we took a purely operational reasoning.

Source code is available at this Gist