reperiendi

Monads for functional JavaScript programming

Posted in Uncategorized by Mike Stay on 2010 March 26

Introduction

Philip Wadler’s excellent paper “Monads for Functional Programming” is about how to achieve some of the benefits of using side-effecting languages using a purely functional language. Wadler uses Haskell to illustrate his examples. To me, that has the effect of preaching to the choir—you can’t do anything in a purely functional language without a monad, so anyone proficient in Haskell will already have had to understand the point he’s trying to make.

“It’s easier to port programmers than to port programs”, so I’ll take a different tack: purely functional programs are far easier to test. If you are concerned about the reliability of your code, programming in a functional style is something to consider seriously. So in my opinion, the examples should be given in the impure language; I’m going to use JavaScript.

In one example, Wadler assumes that computing 1/0 throws an error. Since JavaScript says 1/0 === Infinity instead, I’m going to use silentmatt’s BigInteger library, which does throw an error.

In what follows, I simply give a direct translation from Wadler’s Haskell code in section 2 of his paper.

The basic evaluator

Wadler’s motivating example is a purposely oversimplified term evaluator:

    function ev(term) {
      if (term[0] === 'Con') {
        var a = term[1];
        return BigInteger(a);
      }
      if (term[0] === 'Div') {
        var t = term[1], u = term[2];
        return ev(t).divide(ev(u));
      }
    }

    var answer = ['Div', ['Div', ['Con', 1972], ['Con', 2]], ['Con', 23]];
    var error = ['Div', ['Con', 1], ['Con', 0]];

Computing ev(answer) gives 42, and computing ev(error) throws an Error.

Exceptions

    var undef = {};
    function ev(term) {
      if (term[0] === 'Con') {
        var a = term[1];
        return BigInteger(a);
      }
      if (term[0] === 'Div') {
        var t = term[1], u = term[2];
        var a = ev(t);
        if (a === undef) {
           return undef;
        }
        var b = ev(u);
        if (b === undef) {
           return undef;
        }
        if (b === 0) {
           return undef;
        }
        return a.divide(b);
      }
    }

State

    function ev(term) {
      return function (x) {
        if (term[0] === 'Con') {
          var a = term[1];
          return [BigInteger(a), x];
        }
        if (term[0] === 'Div') {
          var t = term[1], u = term[2];
          var a_y = ev(t), a = a_y[0], y = a_y[1];
          var b_z = ev(u), b = b_z[0], z = b_z[1];
          return [a.divide(b), z + 1];
        }
      }
    }

Output

    function ev(term) {
      if (term[0] === 'Con') {
        var a = term[1];
        return [
          line(['Con', BigInteger(a)], BigInteger(a)),
          BigInteger(a)
        ];
      }
      if (term[0] === 'Div') {
        var t = term[1], u = term[2];
        var x_a = ev(t), x = x_a[0], a = x_a[1];
        var y_b = ev(u), y = y_b[0], b = y_b[1];
        return [
          x + y + line(['Div', t, u], a.divide(b)),
          a.divide(b)
        ];
      }
    }

Wadler notes that if you were appending to an output stream instead of constructing a string, it would be hard to reverse the order in which the trace was displayed, since you can’t prepend to an output stream.

A monadic evaluator

    function ev(term) {
      if (term[0] === 'Con') {
        var a = term[1];
        return unit(BigInteger(a));
      }
      if (term[0] === 'Div') {
        var t = term[1], u = term[2];
        return apply(ev(t), function(a) { 
            return apply(ev(u), function(b) { 
              return unit(a.divide(b));
            });
        });
      }
    }

where apply corresponds to Wadler’s * and is defined below.

The basic evaluator

    function unit(a) {
      return a;
    }

    function apply(a, k) {
      return k(a);
    }

Exceptions

    var undef = {};

    function unit(a) {
      return a;
    };

    function apply(m, k) {
      if (m === undef) {
        return undef;
      }
      return k(m);
    }

Now we replace unit(a.divide(b)) with

    (b === 0) ? undef : unit(a.divide(b))

 

State

    function unit(a) {
      return function (x) {
        return [a, x];
      };
    }

    function apply(m, k) {
      return function (x) {
        var a_y = m(x), a = a_y[0], y = a_y[1];
        return k(a)(y);
      };
    }

    function tick(x) {
      return [void 0, x+1];
    }

Now we replace unit(a.divide(b)) by

    apply(tick, function () { return unit(a.divide(b)); })

The result of computing ev(term) is a function that takes an initial count and increments it by the number of divisions in term, then returns a pair with the evaluated term and the final count.

Output

    function unit(a) {
      return ['', a];
    }

    function apply(m, k) {
      var x_a = m   , x = x_a[0], a = x_a[1];
      var y_b = k(a), y = y_b[0], b = y_b[1];
      return [x + y, b];
    }

    function out(x) {
      return [x, void 0];
    }

Now we replace unit(BigInteger(a)) with

    apply(
        out(line(['Con', a], a)),
        function () { return unit(BigInteger(a)); })

and unit(a.divide(b)) with

    apply(
        out(line(['Div', t, u], a.divide(b))), 
        function () { return unit(a.divide(b)); })

Conclusion

I think that JavaScript would need some syntactic sugar similar to Haskell’s <<< to make monads truly easy to use, but hopefully these translations will make them a little more accessible.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: