Thursday 2 February 2012

Currying vs. Partial Application

I am a longtime fan of functional programming. I came in contact with it through articles by Paul Graham and Joel Spolsky.

Since first class functions (or closures, anonymous functions, lambda functions) are possibly *the* cornerstone of functional programming, there wasn't much to do in the pre-5.3 days. The closest you'd get to closures was create_function(), which is awkward at best and non-functional at worst.
So now we have closures, which has its quirks, but is mostly functional I guess.

By the way, in the above paragraph I talk about closures, anonymous functions and lambda functions as being equal. I know there are subtle differences, but I think in the context of PHP they are negligible. I will usually use the term 'closure' or 'anonymous function', but they both refer to the same concept.

Now, on to the meat of this post. Currying vs. Partial Application. Two terms most programmers that know about functional languages have most likely heard about, but a lot of people get them mixed up or use them interchangeably.
I will first explain and demonstrate currying in the context of PHP, since this is the most misunderstood and, in my opinion, most useless of the two.

Currying
What is currying? From Wikipedia:
Currying is the technique of transforming a function that takes multiple arguments in such a way that it can be called as a chain of functions each with a single argument.
This is best explained using an example. Say we have a function that expects three arguments and returns the sum:

    
function sum3($x$y$z)
    {
        return 
$x $y $z;
    }


Now we need to create a function that returns a chain of functions that only accept a single argument.

    function curried_sum3($x)
    {
        return function (
$y) use ($x) {
            return function (
$z) use ($x$y) {
                return 
sum3 ($x$y$z);
            };
        };
    }



We would want to call it like this:

    $result curried_sum3(1)(2)(3);


Unfortunately, PHP won't let us. But if I'm not mistaken we get that functionality in PHP 5.4 as part of the (new Foo())->method() syntax. So we have to assign each step to a temporary variable.

    $f1 =  curried_sum3(1);
    
$f2 $f1(2);
    
$result $f2(3);


So this is currying. I honestly can't see a practical use for this in a language (and associated scope) like PHP. But I'd love to be proven wrong! If you can make an argument and use case where function currying wouldn't be as awkward as it seems, or even beneficial, please let me know in the comments.

Partial Application
Now comes the interesting bit: Partial Application. A technique that is oftentimes called currying, but it's actually a whole different animal. Per Wikipedia the definition of partial application is:
Partial application (or partial function application) refers to the process of fixing a number of arguments to a function, producing another function of smaller arity.
Basically it is a technique to reduce the number of arguments to a function. If we build upon the sum3() function we have used earlier, we can fix the first argument to 1 and receive a new function that only requires two arguments:

    function partial_sum3($x)
    {
        return function(
$y$z) use($x) {
            return 
sum3($x$y$z);
        };
    }


The resulting function requires only two arguments: $y and $z. $x will be fixed as the argument passed to partial_sum3().

    //create the partial
    
$f1 partial_sum3(1);
    
//execute the partial with the two remaining arguments
    
$result $f1(23);

The problem with this situation is that it's not dynamic. What we want is a partial function generator. A function that expects a function and n number of arguments. Fortunately, now we can create something like that fairly easy:

    function partial($func$arg1 /**, rest*/)
    {
        
$args func_get_args();
        
$func array_shift($args);

        return function() use(
$func$args) {
            
$full_args array_merge($argsfunc_get_args());
            return 
call_user_func_array($func$full_args);
        };
    }


With this function we can create any partial we want:

    $f1 partial('sum3'12);
    
$result $f1(3);

We reduced the number of arguments to sum3() to only one.
A practical example of this could be to easily map an array of timestamps into nicely formatted date/time's:

    //array of timestamps
    
$timestamps = array(132537600013280544001330560000);
    
//create the date formatter by fixing the format and effectively removing the first argument
    
$date_formatter partial('date''Y-m-d H:i:s');
    
//map the timestamps to their nicely formatted counterparts
    
$datetimes array_map($date_formatter$timestamps);
    
var_dump($datetimes);
/**
Output:
array(3) {
  [0]=>
  string(19) "2012-01-01 01:00:00"
  [1]=>
  string(19) "2012-02-01 01:00:00"
  [2]=>
  string(19) "2012-03-01 01:00:00"
}
*/


I think this should pretty much cover the basics of currying and partial application and how it applies to PHP. I hope you enjoyed reading it as much as I enjoyed writing it.

Happy coding!

3 comments:

  1. Thanks, your discussion here was exactly what I needed to solve a problem I had posed for myself: I am taking an informal course in PHP at work that is rather elementary. Rather than solving the problems in class using a simple procedural style, I am attempting to figure out a functional alternative.

    In particular, your partial function resolved the problem of how to pass a function as an argument, when the passed function needed to be 'primed' with a particular argument (in my case a simple of array of strings).

    What is surprising and powerful about your partial function: it can also receive a multiple functions as arguments. In that way it allows for composing functions together and deferring execution of the functions, until a result is needed.

    ReplyDelete
  2. I often use a similar partial application function, although mine doesn't specify any arguments like your "$func" and "$arg1", since that causes PHP to complain if they're not provided.

    In fact I find it quite useful to give other functions the ability to do partial application. For example, many of PHP's functions aren't designed with partial application in mind, so they take their arguments in an unfortunate order (see http://www.haskell.org/haskellwiki/Parameter_order ). If we want to change their order, we might use a flip function:

    function flip($f) {
    return function() use ($f) {
    $args = func_get_args();
    return call_user_func_array($f, array_merge([$args[1], $args[0]], array_slice($args, 2)));
    };
    }

    This looks quite similar to the "partial" function, since both take a function and return a function and both use call_user_func_array, array_merge and func_get_args. In fact, I use "flip" and "partial" together so much that I've started using this definition of flip which also partially-applies!

    function flip() {
    $args1 = func_get_args();
    return function() use ($args1) {
    $args2 = array_merge($args1, func_get_args());
    list(, $x, $y) = $args2;
    $args2[1] = $y; $args2[2] = $x;
    return call_user_func_array('call_user_func', $args2);
    };
    }

    I've actually automated this somewhat with a currying function that sends any extra arguments to inner functions: http://lambda-the-ultimate.org/node/4953

    ReplyDelete
  3. This comment has been removed by the author.

    ReplyDelete