Friday, March 29, 2013

Implementing Monads in JavaScript

UPDATE: This post has been updated to a new post. All the code has been refactored and redone in the new post. http://functionaljavascript.blogspot.in/2013/07/monads.html

Consider the problem of doing a series of computations (calling a series of functions), and you want each successive computation to have access to the results of the previous computations. We will write a function called doComputations, and here is how a call to doComputations would look like.

var result = doComputations(
    "a", function(scope) {
             return 2;
         },
    "b", function(scope) {
             with (scope) {
                 return a * 3;
             }
         },
    function(scope) {
        with(scope) {
            return a + b;
        }
    }
);

The arguments to doComputaions are one or more "string - function" pairs and the last argument is just a "result" function. The string is a variable name which will be assigned the value returned from calling the function. So in the first case "a" will be assigned the value 2. What is interesting is that "a" is visible inside the next function whose value gets assigned to "b". And both "a" and "b" are visible inside the last function. Every function is called with a "scope" object which carries key value pairs corresponding to the previous computations carried out. Here we use the "with" statement to scope the "scope" object within the function. If you don't want to use the "with" statement you could access the variable from the scope object directly eg. scope.a, scope.b. The value returned by doComputations is the value returned by the last "result" function, in this case the final value is 8. And here is the definition of doComputations.

function doComputations() {
    var args = arguments;
    var scope = {};
    function iterator(i) {
        if (args.length === i + 1) {return args[i](scope);}
        var varName = args[i];
        var func = args[i + 1];
        var value = func(scope);
        scope[varName] = value;
        return iterator(i + 2);
    }
    return iterator(0);
}

Inside doComputations we define an iterator function, which recursively iterates over the arguments array of doComputations. In the first line of the iterator function we check to see if we have reached the last "result function", if yes we call it with scope and return the result. In the next three lines we create three variables initialised to the variable name, function, and value returned by calling the function with the scope. In the next line we attach the key-value to scope. And finally we make a recursive call to the iterator to do the next computation. In the last line of doComputations we start the iterator with initial values 0 for the index.

Copy the two code fragments above into a file, add the a final line:
console.log(result);
and run it. You should get the result as 8.

All this looks like lots of work just to add and multiply a couple of integers, but we have done something useful. For one we have abstracted away the nitty gritty of iterating over computations, with visibility of previous results, into a function called doComputations.

Computations are not always so simple and straight forward as the one above. What if we wanted to abort the computations midway for some reason? eg. If any of the functions returns "null" we want to abort the computations. There are many other types of computations and to write a version of doComputations for each type is not a good idea. Instead we could make doComputations call another function between computations so that any thing different, we want to do, is done in this function. This function is passed to doComputations as its first argument. We will call this function "mBind". Now all we have to do is write a version of mBind for every type of computation. For every computation, doComputations will call mBind which in turn will call the next computation. First we write the mBind function to handle null values returned by any computation.
var mBind = function(mValue, mFunction) {
    if (mValue === null)
        return null;
    else
        return mFunction(i + 2);
}

Now the iterator function will call mBind, which is passed as an argument to doComputations, which in turn will recursively call the iterator.

function doComputations(mBind) {
    var args = arguments;
    var scope = {};
    function iterator(i) {
        if (args.length === i + 1) {return args[i](scope);}
        var varName = args[i];
        var func = args[i + 1];
        var value = func(scope);
        return mBind(value, function() {
            scope[varName] = value;
            return iterator(i + 2);
        });
    }
    return iterator(1);
}

Below we call doComputations whose first argument is the mBind function. Also we want to abort the computations in case the browser does not support the console.log function.

var result = doComputations(mBind,
    "a", function(scope) {
         if (typeof console === "object" && console.log)
             return 2;
         else
             return null;
         },
    "b", function(scope) {
          with (scope) {
                 return a * 3;
             }
         },
    function(scope) {
        with(scope) {
            return a + b;
        }
    }
);

We can now use doComputations for various types of computations by simply changing the mBind function passed to it. It would be even better if we could predefine the mBind function for various types of computations. And that is what we will do below. We will also change the name of doComputations to doMonad. And we will add mBind as the property of an object called "monad".

var maybeMonad = {
    mBind: function(mValue, mFunction) {
        if (mValue === null)
            return null;
        else
            return mFunction(mValue);
    }
};

function doMonad(monad) {
    var args = arguments;
    var scope = {};
    function iterator(i) {
        if (args.length === i + 1) {return args[i](scope);}
        var varName = args[i];
        var func = args[i + 1];
        var value = func(scope);
        return monad.mBind(value, function() {
            scope[varName] = value;
            return iterator(i + 2);
        });
    }
    return iterator(1);
}

Compare the above code to the previous listing. It is pretty much the same, except that we have renamed doComputations, and the mBind function is now passed as the property of an object, and this object is called a monad, and in this specific case we called the monad the "maybeMonad". Because "maybe" the computations are carried out, or "maybe" they won't be.

A monad MUST have two properties defined for it to be a proper monad. "mBind" and "mResult". We have not seen mResult so far. mResult is a wrapper function for the "result" function. So we add support for mResult in doMonad below. Also we define a new monad called the arrayMonad below and we do some computations with the it.

function doMonad(monad) {
    var args = arguments, scope = {};
    function iterator(i) {
        if (args.length === i + 1) {
            return monad.mResult(args[i](scope));
        }
        var varName = args[i];
        var func = args[i + 1];
        var value = func(scope);
        return monad.mBind(value, function(value) {
            scope[varName] = value;
            return iterator(i + 2);
        });
    }
    return iterator(1);
}

var arrayMonad = {
    mBind: function(mValue, mFunc) {
        var accum = [];
        mValue.forEach(function(elem){
            accum = accum.concat(mFunc(elem));
        });
        return accum;
    },
    mResult: function(value) {
        return [value];
    }
}

var result = doMonad(arrayMonad,
    "a", function() {
             return [1, 2];
         },
    "b", function() {
             return [3, 4];
         },
    function(scope) {
        with(scope) {
            return a + b;
        }
    }
);

console.log(result);

Running the code above will yield a result of [ 4, 5, 5, 6 ]. The computations using the arrayMonad each return an array. The final result function is called with values a and b, for each element of both arrays. ie it will be called with (1,3), (1,4), (2,3), (2,4). And the addition of each of the elements yields the returned array of [ 4, 5, 5, 6 ].

Using the arrayMonad let us implement a two dimensional iterator function in JavaScript called forEach2D. It will take 3 arguments, an iArray, a jArray, and a callback. The callback is called for each value of i and j. Here is the code below.

function forEach2D(iArray, jArray, callback) {
    return doMonad(arrayMonad,
        "i", function() {
                 return iArray;
             },
        "j", function() {
                 return jArray;
             },
        function(scope) {
            with(scope) {
                return callback(i, j);
            }
        }
    );
}

var result = forEach2D([1, 2, 3], [4, 5, 6], function(i, j) {
    return [i, j];
});

console.log(result);
Running the code above will yield result:
[ [1, 4],[1, 5],[1, 6],[2, 4],[2, 5],[2, 6],[3, 4],[3, 5],[3, 6] ]

How about a function for iterating over three arrays? A forEach3D function. Easy!

function forEach3D(iArray, jArray, kArray, callback) {
    return doMonad(arrayMonad,
        "i", function() {
                 return iArray;
             },
        "j", function() {
                 return jArray;
             },
        "k", function() {
                 return kArray;
             },
        function(scope) {
            with(scope) {
                return callback(i, j, k);
            }
        }
    );
}

var result = forEach3D([1, 2], [3, 4], [5, 6], function(i, j, k) {
    return [i, j, k];
});

console.log(result);
And running this code will print out:
[ [1, 3, 5], [1, 3, 6], [1, 4, 5], [1, 4, 6], [2, 3, 5], [2, 3, 6], [2, 4, 5], [2, 4, 6] ]

You can begin to see the power of monads here. They abstract away the complicated part of your code and simplify the problem at hand. Monads are a hard concept to understand, and I hope that I have simplified its understanding here. If there is any part not clear enough please let me know. In the next post I hope to take a more in depth look and monads with some interesting examples.

Wednesday, March 27, 2013

Introduction to Functional JavaScript

JavaScript was a functional programming language even before it got its name! Back in 1995 Netscape Communications the makers of the Netscape Browser realized that their browser needed a scripting language embedded in HTML. They hired Brendan Eich to embed the Scheme programming language in HTML. Scheme was a full fledged functional programming language. To his dismay “the powers that be” encouraged Brendan to come up with a more traditional programming language. His first cut was a language called “Mocha” in May 1995, and it retained that name till December 1995. It was first renamed “LiveScript” and soon after that Netscape and Sun did a license agreement and it was called “JavaScript”. But by then Brendan Eich had sneaked in some “functional programming” features into JavaScript.

The story gets more complicated, and we will delve into it. Because this story will tell you why JavaScript is what it is today. Brendan Eich claims that hiring him to embed the Scheme language, might actually have been a “bait and switch operation”. But at that point in time Netscape was also negotiating with Sun to embed Java in the browser. Note that JavaScript was for embedding in HTML while Java was for embedding in the Browser. The idea was that Java would be used for component development while JavaScript would be used for lightweight scripting within HTML.

We don't know what actually transpired, but the orders from above to Brendan where clear. The new scripting language must “look like Java” and must be “object based”. Any hopes Brendan might have harboured for Scheme, where now out of the window. We will see why.

Programming Paradigms

We can only speculate on what “look like Java” meant. However we can be certain that it had to be a “curly brace” language. Curly brace languages define statement blocks using curly braces, the “{“ and “}” characters. Indeed Java syntax was fashioned on another curly brace language “C++”, which in turn was fashioned on “C”. Here is how a for-loop looks in Java.

for (int i = 0; i < 10; i++) {
    System.out.println("Hello");
    System.out.println("World");
}
The same for-loop in C.
int i;
for (i = 0; i < 10; i++) {
    printf("Hello\n");
    printf("World\n");
}
And the for-loop in JavaScript.
for (var i = 0; i < 10; i++) {
    console.log("Hello");
    console.log("World");
}

Indeed JavaScript does look like Java. And C too. However curly braces where not the only implications for a language to “look like Java”. Java is an imperative/object oriented style programming language. JavaScript also had to be an imperative/object oriented style language.

Programming languages are made up of operators, conditional statements, loop statements and functions. Having conditional statements and loop statements are hallmarks of an “imperative” style programming language. Functional style languages tend to support operators and functions only.

It is interesting that none of the three languages, Java, C++ and C, were functional programming languages. While C was an imperative programming language, C++ and Java were Imperative/Objected Oriented programming languages. By now you would have guessed that the three programming paradigms (styles) were imperative, object oriented and functional. There is one more, the declarative paradigm.

The differences between these paradigms are because of the foundations on which they were based. Imperative and object oriented programming are based on the “turing machine”. Functional programming is based on “lambda calculus” and declarative programming is based on “first order logic”. In this post we will look at the differences between, imperative, object oriented and functional programming at a more practical level.

An imperative programming language is one in which program state change is achieved by executing a series of statements, and does flow control primarily using conditional statements, loop statements and function calls. The program given below is a simple implementation of the JavaScript Array.join method in an imperative manner.

function simpleJoin(stringArray) {
    var accumulator = '';
    for (var i=0, l=stringArray.length; i < l; i++) {
        accumulator = accumulator + stringArray[i];
    }
    return accumulator;
}

The code above is straight forward. We iterate through an array and add each string element to the accumulator and return the accumulator. We will now rewrite this function in an object oriented manner. Since JavaScript has an Array class, we will add this method to the Array class, so that every instance of this class has access to this function. JavaScript use prototypal inheritance and so we add this function to the Array prototype.

Array.prototype.simpleJoin = function() {
    var accumulator = "";
    for (var i=0, l=this.length; i < l; i++) {
        accumulator = accumulator + this[i];
    }
    return accumulator;
}

As we can see, the object oriented version is quite like the imperative version, except that the function (method) is now a method of the class. Object oriented languages tend to be imperative languages also.

Now let us write the functional version of this function.
function simpleJoin(stringArray, i, accumulator) {
    if (i === stringArray.length) {
     return accumulator;
    } else {
     return simpleJoin(stringArray, i+1, accumulator+stringArray[i])
    }
}

The first thing to note is that we are not using the for loop here for iteration. Instead we use recursion for iteration. Recursion happens when the function calls itself from within itself. Indeed this is one of the characteristics of a functional programming language. eg. Scheme does not have any loop statements. Instead it uses recursion for iteration. The function is called for the first time with the given array in stringArray, i set to 0, and accumulator set to "". The second time around the function is called from within itself with the same stringArray, i set to i + 1, and accumulator set to accumulator + stringArray[i]. And we continue the same way until i === stringArray.length when we return the accumulator. We will discuss recursion in detail later in a later post. Just remember we used recursion for doing iteration here.

There is still something imperative about this function. The if statement. Functional languages tend to use expressions that evaluate to some value, instead of statements that don't evaluate to anything. So let us rewrite the function, to make it as functional as possible in JavaScript.

function simpleJoin(stringArray, i, accumulator) {
    return (i === stringArray.length) ? accumulator :
        simpleJoin(stringArray, i + 1, accumulator + stringArray[i])
}

Now this as functional as you can get with JavaScript. Instead of the if statement we return the value evaluated by the conditional operator ?. The conditional operator ? Takes a conditional expression and returns the value of one of the two expressions based the condition being true or false. The value of the first expression is returned if true and the second if false.

We can see that the functional version is concise. Indeed one of the advantages of functional programming is that it lends itself to lesser code to accomplish the same thing, leading to better readability and maintainability.

However in the case of JavaScript, as of now you cannot use recursion for doing iteration. You should continue to use the imperative or object oriented method for iteration. This is because JavaScript does not (yet) support “tail call optimization”. For doing proper recursion, tail call optimization is required. We will discuss tail recursion, and tail call optimization, and how to get around this problem in a future post. As of writing this post tail call optimization is expected in ecmascript 6.

So is JavaScript an imperative language, or an object oriented language, or a functional language? It is a multi paradigm language. It does not have all the functional features implemented. But it is slowly getting there. This is also true of most other languages. Most languages (other than functional languages to begin with) have added functional features to various degrees over the years. A good example of the multi paradigm nature of JavaScript is the Array.forEach method. Here is a possible simple implementation. Note that all modern browsers have already implemented this.

Array.prototype.forEach = function(callback) {
    for (var i = 0, len = this.length; i < len; ++i) {
        callback(this[i], i, this);
    }
}

In the code above the for-loop part of the code is imperative. Adding to the array prototype and usage of this is object oriented. Passing a function as an argument to another function (callback) is functional and is a feature of functional programming known as “higher order function”. In JavaScript, we take this for granted, passing functions as an argument. Surprisingly this was not a feature found in the most popular languages until recently. eg. You cannot pass functions as arguments in Java, though you can do it indirectly via Interfaces. Same is the case with C, though you can do it indirectly using pointers.

Programming Abstractions

What if JavaScript did not have the “passing functions as arguments feature”? The answer to this question is crucial to understanding what functional programming brings to the table. For one, we would not be able to write the Array.forEach function above. And even worse, every time we had to iterate over an array, we would have to write the same for-loop again and again. If we had Array.foreach we need to think only about writing the callback. We need to think only of what to do with each element of the array, and need not concern ourselves with iterating over the array. In other words we have “abstracted” away the iteration part of the problem, and freed ourselves to concentrate on each element of the array.

Abstractions are about hiding away implementation details, thereby reducing and factoring out details, so that programmers can focus on the problem at a higher level. Abstractions can be code abstractions, as we saw in the example above, and data abstractions. Objected oriented programming is about combining code and data abstractions into one abstraction called the class. In functional programming we use functional features like first class functions, nested functions, anonymous functions and closures to abstract away code and sometimes even data. Monads are an esoteric feature of functional programming that can even abstract away program structure!

Macro's are another feature that allows code abstraction. However macros are not a feature of functional programming. But they are found in all Lisp like functional languages like Lisp, Scheme, Clojure etc. There are attempts to bring Macro's to JavaScript and at the moment it is very much early days.

A good example of the power of functional abstractions is jQuery. jQuery is the mother of all functional abstractions. It has abstracted away the JavaScript language itself! So much so that you wouldn't be surprised, if you found a jQuery programmer who knows very little or no JavaScript. As of Feb 2013 there was one publisher who had 32 jQuery books listed, and not a single JavaScript book! And jQuery has achieved so much mostly using only two functional features, functions as arguments and closures.

First Class Functions and Closures

The functional programming feature that Brendan Eich implemented in JavaScript was “first class functions”. Functions are first class if they are treated as “first class citizens” of that language. Which implies functions are treated just like all other variables. ie. You can pass them as arguments to functions, you can return them as values from other functions, or you can assign them to variables or data structures. We have seen “passing functions are arguments” earlier. Here is an example of assigning a function to a variable.

function greet(name) {
    console.log("Hello " + name);
}

greet("John"); // "Hello John"

var sayHello = greet;
sayHello("Alex"); // "Hello Alex"

Some programming language theorists consider “anonymous functions” as first class functions. Not to be outdone, Brendan Eich threw anonymous functions into the mix. This is like letting the cat among the pigeons so to speak. But not for Brendan Eich, he knew the solution to the problem. Here is an anonymous function in JavaScript.

function(name) {
    console.log(“Hello “ + name);
}

If you noticed we did not give this function a name. After all, it is an anonymous function. If you try to run the code above, you will get an error. Something to the effect “you cannot run the code in this context”. And rightly so. They can only be assigned to something, or passed as arguments to a function.

var sayHello = function(name) {
    console.log(“Hello “ + name);
}
sayHello("Jane"); // "Hello Jane"

What if we wanted to change the greeting? Sometimes we would like to say “Hi” instead of “Hello”. We could create a generic “createGreeting” function, which would in turn “compose” another function for you, and return the new composed function. So if we wanted to sat “Hi” it would return a function, and if we wanted to say “Hello” it would return another function that says “Hello”. We can do all that because JavaScript supports first class functions, and we can return functions from other functions. Here is the code.

function createGreeting(greeting) {
    return function(name) {
        console.log(greeting + " " + name);
    }
}
var sayHi = createGreeting("Hi");
sayHi("Jack"); // "Hi Jack"
var sayHello = createGreeting("Hello");
sayHello("Jack"); // "Hello Jack"

The createGreeting function takes a greeting as its argument. The function returns a newly created anonymous function. However the newly created anonymous function was created inside another function createGreeting. So it is also a nested function now. Now since our language supports anonymous functions it will also have to support nested functions. And when we return nested functions from our function we run into another problem. We will look at that in more detail.

The anonymous function takes a name argument and prints to the console greeting + name. The variable name is an argument to the anonymous function, and behaves just like any other variable defined within the function. In other words name is “local” to the anonymous function. But this is not true of the variable greeting. It is defined in another function called createGreeting and hence is “non local” to the anonymous function. However the anonymous function can access the variable greeting due to something called lexical scoping.

The “scope” of a variable is its “visibility” within a program. “Lexical scope” means that visibility is limited to all the text (code). So when we say “local variables are lexically scoped” within a function, it means that the function's local variables are visible to all the text (code) in the function, even if the code is within another nested function. This also means that when you run the nested function outside the lexically scoped environment, the nested functions non local variable will not be visible. And there lies the problem of returning nested functions from another function. And indeed thats what we are doing here.

var sayHi = createGreeting("Hi");

In the line above we assign the returned anonymous function to variable sayHi. And call the function in the next line.

sayHi(“Jack”)

We are calling sayHi outside of createGreeting. And the greeting variable is not available outside of createGreeting. The variables it may access in the scope where it was defined, may not be available in the scope where it was actually called. Thats why languages like C don't support nested functions. For this to work the language needs to support another functional programming feature called “closures”. JavaScript supports closures. As matter of fact it has to support closures. Any language that supports first class functions and nested functions has to support closures.

A function's closure is a reference to all its non local variables. In the previous example greeting was the non local variable and name was the local variable. A closure is a table of references to all of a functions non local variables. This allows the function to continue to refer to the non local variable even when the function is out of the scope of the variables.