From Callback to Future -> Functor -> Monad

Motivation A fundamental concept in functional programming is . 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. composition With composition, you never hit a wall, because you must always ask yourself , or put another way “What is the return value of this function ?” “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 . 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. continuation 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, 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 denotation 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 of physics: Black holes 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 and you fall into another hole. The more you use callbacks, the more you sink into hell. flow So how can we move forward in our code without falling into black holes? The answer is . 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. composition Even if you are already aware of existing 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. JavaScript 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 , 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 results. the immediate future So let’s make them return a special type: , to denote their eventual outcome. The key idea is to have a first class value which can be passed to other functions. Future What’s the meaning of a ? 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. Future 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 then evolves to and will stop here. Once completed, it’ll stay forever. pending completed 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 Future Future.unit = function(val) {var fut = new Future();fut.complete(val);return fut;} logF( Future.unit('hi now') ); Above, i used a to makes it simple to reason about the code: type annotation ‘unit : Value → Future ’ means simply that: ‘unit’ is a function it takes a generic type ‘Value’ as input and 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 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 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 -> Number) ) -> Future 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: a Future value 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 , func ) = Future 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 . That’s because they can take a normal function, apply it to whatever inside and return another instance representing the result of the transformation. Functors Array and Future aren’t the only Functors, whenever you encounter a type acting as a for other types context 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 -> Future 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 function. a function over a like functors promotes function application from normal values to the values. In our case, we are lifting a function ‘length: String -> Number’ which acts on Strings to a function ‘lengthF: Future -> Future ’ which acts on Futures. lifted Lifting box-type box-type 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 ’ 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 ’, 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 >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 Read the content of a directory which gives us a Future holding an array of Strings representing file names. 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, Future to complete before going on. nested 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 ’ (a 2 layered Future) into a simple Future // flatten: Future > -> Future 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 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). sequencing Now let me introduce our second guest, Besides being a Functor, a Future is also a , 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. Monad 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 one: in our example, it’s the ‘Future.unit’ which makes a Future from a normal value. Monadic 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 , ...) -> Future 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 , Future ) -> Future )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 ones which describes sequential operations (like ‘readFile’ inside ‘readDir’). Monadic 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 operations. parallel 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 . 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. 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 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 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. catch We’ll have to define a function for ‘fmap’, we’ll call it ‘fmapError’. It’s like a flipped version of fmap peer 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 version of flatMap. peer 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 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 ). chained 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 of Promises is far more complicated. He may even tell me something like . Fully compliant specification 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 . This is why, in the specification, you can notice references to things like execution model 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, 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). Denotational semantics 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