Higher Order Javascript (by Piers Cawley)

JavaScript
1

Piers Cawley gave a talk at the software developer conference [url=http://oredev.org/2010]Øredev about Higher Order Javascript (in the spirit of Dominus’ Higher Order Perl).

Writing functionally, and event-driven, in any “lambda” language (language where functions are first-class objects) can keep your code separated and make it more reusable with less repetition in your code. Though honestly I have enough trouble reading the CoffeeScript to begin to keep track of it (though CoffeeScript itself looks kinda neat), plus I get dizzy just staring at one of those pictures where someone’s looking at a picture of themselves looking at a picture of themselves looking at a picture of themselves…

But for those people who can already do that, and for those who can do simple math in their heads without needing to take off their shoes (as I do), this article will make even more sense than it did to me. I can smell the awesomeness, but can’t quite taste it…

2

CoffeeScript gets it right. I, however, am a much less efficient CoffeeScript compiler than the real thing.

3

Yeah, the coffeescript code tended to blow my mind too. If I took the time to investigate coffeescript code more fully, I suspect that it would blow my mind in a much better way.

What he’s saying is that you can extract common behavior out to more generic implementations.

Since this is the JavaScript forum, I’ll translate the first set of examples in to javascript.

He starts off with adding and multiplying numbers


function sum(xs) {
    var r = 0,
        index;
    for (index = 0; i < xs.length; index += 1) {
        r += xs[index];
    }
    return r;
}

function prod(xs) {
    var r = 1,
        index;
    for (index = 0; i < xs.length; index += 1) {
        r *= xs[index];
    }
    return r;
}

There’s a lot of repetition in there, so he extracts it out to an inject function, that the sum and prod functions can use.


function inject(i, f, xs) {
    var r = i,
        index;
    for (index = 0; index < xs.length; index += 1) {
        r = f(r, xs[index]);
    }
    return r;
}
function sum(xs) {
    return inject(0, function (a, b) {
        return a + b;
    }, xs);
}
function prod(xs) {
    return inject(1, function (a, b) {
        return a * b;
    }, xs);
}

Now that we’ve found that inject function, it can be commonly used across many other types of functions, such as grep, map, and each


function grep (pred, xs) {
    return inject([], function (rs, x) {
        var rx = new RegExp(pred);
        if (rx.exec(x)) {
            rs.push(x);
        }
        return rs;
    }, xs);
}
function map (f, xs) {
    return inject([], function (rs, x) {
        rs.push(f(x));
        return rs;
    }, xs);
}
function each (f, xs) {
    return inject(undefined, function (_, x) {
        f(x);
        return _;
    }, xs);
}

Well with those three, and this is where it gets crazy for me, he spots repetition that can be extracted out as well to a function called with_list(), which will return the passed function and a certain number of arguments.

My poor old brain is fizzling out at this stage though, so I may have to sleep on this.

4

sorry, not me :frowning:

it’s an interesting read but my head is :weyes:

whatever happened to plain vanilla javascript and the KISS principle? :bawling:

5

Here’s the next part that was frying my brain last night:


var with_list = function (f) {
  var arity = f.length;
  return function () {
    var args = Array.prototype.slice.call(arguments, 0);
    if (arity > 0 && args.length !== arity - 1) {
      throw "Oops!";
    }
    return function(xs) {
      return f.apply(this, args.concat([xs]));
    };
  };
};

You pass it the function that processes a list


var inject = function (i, f, xs) {
    var r = i,
        index;
    for (index = 0; index < xs.length; index += 1) {
        r = f(r, xs[index]);
    }
    return r;
}
var injector = with_list(inject);

And you get back a function with all arguments except for the last one, which is the list.

When you call it, the list is obtained via closure.


var sum = injector(0, function (a, b) {
        return a + b;
    }
);
alert(sum([2, 3]));



var inject = function (i, f, xs) {
    var r = i,
        index;
    for (index = 0; index < xs.length; index += 1) {
        r = f(r, xs[index]);
    }
    return r;
}
var with_list = function (f) {
  var arity = f.length;
  return function () {
    var args = Array.prototype.slice.call(arguments, 0);
    if (arity > 0 && args.length !== arity - 1) {
      throw "Oops!";
    }
    return function(xs) {
      return f.apply(this, args.concat([xs]));
    };
  };
};
var injector = with_list(inject);
var sum = injector(0, function (a, b) {
        return a + b;
    }
);
alert(sum([2, 3]));

So now you can use that with_list construct with the sum and prod functions.



var sum = injector(0, function (a, b) {
    return a + b;
});
var prod = injector(1, function (a, b) {
    return a * b;
});

Which brings us to the next part:

It doesn’t help us out with grep, map and each, but I’m not feeling clever enough to fix that at the moment so I’ll leave it as an exercise for the interested reader.

Is anyone feeling clever enough to attempt this?

6

Wow. Thanks for those translations. I’ve added a link to this thread from the original article.

I think my ‘exercise for the interested reader’ is more along the lines of a red herring than a real exercise. The only fixes I could think of were at a language level.

7

Thanks. Even though CoffeeScript is most certainly going to be cleaner, the code samples could be useful as a comparison of how things get tricker with native JavaScript.

I suspected that it may not be practical to achieve. I can get the returned function to have extra parameters by passing them in an array at the end of the with_list call:


injector = with_list(inject, ['pred']);

It’s just a matter then of calling the injector with (i, f, pred) or with (i, f) and allowing closure to provide the rest.

I may have to expand everything out to separate functions so that I can try some different variations out, before crunching them down again. That’s how I resolved the above with_list function, so we’ll see how things go.

8

What? Hang on! What’s ‘new Function’ doing in that with_list definition? Here’s a slightly tidied up version of what the CoffeeScript compiler produces from my source:


var new_list = function (f) {
  var arity = f.length;
  return function () {
    args = arguments.slice(0);
      if (arity > 0 && args.length !== arity - 1) {
        throw "Oops!";
      }
      return function(xs) {
        f.apply(this, args.concat([xs]));
      };
    };
  };
}

I think you’re making things much more complicated than they actually are. There’s really no call to go decompiling stuff, and it simply won’t work in cases where the functions you’re wrapping are carrying their own state around in closures.

9

Thanks for that.

arguments.slice won’t work in many web browsers, so I’ve modified that to one that’s more compatible.

The f.apply result should be returned too, otherwise you’ll just get undefined, and RLM2008 noted that var should be used on the args variable, so here’s the updated version of the with_list function.


var with_list = function (f) {
  var arity = f.length;
  return function () {
    var args = Array.prototype.slice.call(arguments, 0);
    if (arity > 0 && args.length !== arity - 1) {
      throw "Oops!";
    }
    return function(xs) {
      return f.apply(this, args.concat([xs]));
    };
  };
};

The original post is now updated too.

10

D’oh! Now you know why I wrote the examples in CoffeeScript - the compiler remembers all those icky details for me

11

Really interesting thread. Well done for the breakdown pwm57.

I’m just trying to idiot comment the with_list to better understand the workings.

One little thing that stands out. Should’nt ‘args’ be ‘var args = Array.prototype.slice.call(arguments, 0);’. At the moment it’s global isn’t it?

var with_list = function (f) {
  // var arity = f.length = The number of expected arguments
  // e.g. var inject = function (i , f, xs) {...}. inject.length == 3.
  var arity = f.length;
  
  // with_list returns the following function along with function f and 
  // arity in it's scope/closure.
  return function () {
  // Arguments are assigned to the variable args.
  // arrity is checked to see if it has any parameters and
  // args is checked against arity to see if we have one less argument (minus the array to be worked).
  // Our array to be worked on will be passed in to the innermost function later.
    var args = Array.prototype.slice.call(arguments, 0);
    if (arity > 0 && args.length !== arity - 1) {
      throw "Oops!";
    }
  // injector returns the following function
  // this innermost function has access to function f and args via it's scope and closure
  // args.concat([xs]) now adds the array to be worked on to our arguments which inturn
  // is passed to function f.
    return function(xs) {
      return f.apply(this, args.concat([xs]));
    };
  };
};

RLM

12

Yes it should. I don’t know why CoffeeScript would allow that when compiling the code. Maybe Piers can provide some insight?

Regardless of that, I’ll update my post to tidy up that part of the code.

13

I’ve made some progress on the “exercise” piece.

With this update to with_list you can call the function from the injector with as many arguments as you like, as long as xs remains at the end.


var with_list = function (f) {
  var arity = f.length;
  return function () {
    var funcArgs = Array.prototype.slice.call(arguments, 0);
    if (arity > 0 && funcArgs.length !== arity - 1) {
      throw "Oops!";
    }
    return function(xs) {
      args = Array.prototype.slice.call(arguments, 0);
      args.unshift(args.pop()); // move xs before other args
      return f.apply(this, funcArgs.concat(args));
    };
  };
};

You can now inject in to functions for grep, map and each

For example, here is grep, called as grep(pred, xs)


var grep = injector([], function (rs, x) {
    var pred = args[1];
    var rx = new RegExp(pred);
    if (rx.exec(x)) {
        rs.push(x);
    }
    return rs;
});

var result = grep('\\\\d{2}', [7, 23, 'String with 1 number']);
alert(result); // 23

The double blackslashes on \\d is only due to it being written as a JavaScript string, so that the script doesn’t misinterpret \d as an escaped character.

Here’s the rest of the code that connects everything together, which fits in between the above two code blocks.


var inject = function (i, f, xs) {
    var args = arguments,
        r = i,
        index;
    for (index = 0; index < xs.length; index += 1) {
        r = f(r, xs[index]);
    }
    return r;
};
var injector = with_list(inject);

There is only one coding concession currently being made, and that is that the arguments from (pred, xs) are made globally available as (xs, pred) in an args variable, so that the injected function can gain access to them.

When inject() is called is expects the first argument to be the list, so we po off xs from the end of the arguments, and moving it to the front instead so that (xs, pred) is passed to inject.

We can now gain access to those same arguments, but it comes at the cost of polluting the global namespace with an args variable.

It’s not as clean as I would want, but provides something that can be made to work with grep, map and each.

It may also be possible for someone to clean things up a bit further too.