My new blog here at www.mostovenko.com

Wednesday, January 16, 2013

javascript functions partial evaluation

Recently i discovered a very useful and powerful feature - functions partial evaluation. This feature comes from functional programming languages, and gives us possibility to init some functions arguments before calling this function itself.
At first,  i looked at existing implementations in some popular frameworks - such as underscore e  t. c. and find out, that there is no magic in implementing this. After that i looked at some simple implementations,  they were quite good, but had some limitations, so i decided to upgrade them to get what i wanted.  Here are some of implementations that i found :



function partial(fn) {
    var args = Array.prototype.slice.call(arguments);
    args.shift();
    return function() {
        var new_args = Array.prototype.slice.call(arguments);
        args = args.concat(new_args);
        return fn.apply(window, args);
    }
}

and now we can use it in this way :
// Simple, dummy, useless function... just for demonstrating partial evaluation
function list(a, b, c) {
    return [a, b, c]  
}

omg_list_func = partial(list, 1, 2)
omg_list_func(3) // will produce [1, 2, 3]

As we see - it works well, we just initialized first two arguments, and received expected result after function call. This implementation has one significant limitation - initialization happens only from the beginning of argument list, and we can't partially apply only the last and first arguments, but not the second. Than i found more advanced and flexible implementation, that solves this problem:
  Function.prototype.partial = function(){
    var fn = this, args = Array.prototype.slice.call(arguments);
    return function(){
      var arg = 0;
      for ( var i = 0; i < args.length && arg < arguments.length; i++ )
        if ( args[i] === undefined )
          args[i] = arguments[arg++];
      return fn.apply(this, args);
    };
  };

This gives us ability to do this :
function list(a, b, c) {
    return [a, b, c]  
}

omg_list = list.partial(1, undefined, 3);
omg_list(2) // will produce [1, 2, 3]

As we see, here we can use placeholders for defining which arguments must be replaced with function arguments, and which must be partially applied. This is quite a good solution, but it also has one disadvantage. If we will look more closer, we may see that our "args" variable is modified by returned function. And if we will try to call our partially applied function for several times with different arguments we will receive not expected behaviour :
function list(a, b, c) {
    return [a, b, c]  
}

omg_list = list.partial(1, undefined, 3);
omg_list(2) // will produce [1, 2, 3] - ok
omg_list(5) // will produce [1, 2, 3] - oops !!!

This is happening,  because of shared mutable variable - "args". I reworked the last example and what i've got in the end :
function partial(fn) {
  var partial_args;
  partial_args = Array.prototype.slice.call(arguments);
  partial_args.shift(); // remove function from arguments list

  return function() {
    var i, new_args, arg;
    new_args = [];
    arg = 0;
    for (i = 0; i < partial_args.length; i++) {
      if (partial_args[i] === void 0) {
        new_args.push(arguments[arg++]);
      } else {
        new_args.push(partial_args[i]);
      }
    }
    return fn.apply(this, new_args);
  };
}

As we see, our returned function has it's own copy of arguments, and doesn't mutate partial args, also i moved implementation from the function prototype.

function list(a, b, c) {
    return [a, b, c]  
}

omg_list = partial(list, 1, undefined, 3);
omg_list(2) // will produce [1, 2, 3] - ok
omg_list(5) // will produce [1, 5, 3] - works fine =)

Coffeescript version looks like more attractive
partial = (fn) ->
        partial_args = Array::slice.call arguments
        partial_args.shift()
        ->
            [new_args, arg] = [[], 0]
            for a, i in partial_args
                new_args.push(
                    unless partial_args[i] then arguments[arg++] else partial_args[i])
            fn.apply this, new_args

Thanks, will be glad to see your feedback =)





No comments:

Post a Comment