Lambda

22 Aug 2008

PHP has been in dire need of some new features for some time. PHP 5.3 plans to add a slew of new features, finally adding lambdas a/k/a anonymous functions to the language.

That is… …once it gets out of alpha. Then out of beta. Then onto production systems.

(PHP haters can now stop sipping quite so much hater-ade in that PHP now also supports namespaces, but I don’t find that new feature particularly interesting.)

What makes lambdas so interesting is how much simpler and cleaner they can make your code.

Consider the problem of wanting to sort a list where some of the items have the words ‘The’ or ‘A’ as a prefix. We want to sort the list

  • Beck
  • The Starting Line
  • Blue October
  • The All American Rejects

to be

  • The All American Rejects
  • Beck
  • Blue October
  • The Starting Line

and not

  • Beck
  • Blue October
  • The All American Rejects
  • The Starting Line

Without the use of lambdas, we have to do something like this in old PHP:

function stem_the($a)
{
    return preg_replace( 
    '/^(a|the) *(.*)$/i', '$2', $a 
    );
}

function cmp_the($a,$b)
{
    $a = stem_the($a);
    $b = stem_the($b);
    return strcmp($a,$b);
}

$bands = array( 'The All American Rejects',
        'Beck', 'Blue October',
        'The Starting Line' );

usort( $bands, 'cmp_the' );

usort()’s second argument is a string. This is really ugly. Old PHP didn’t have functions as first-class citizens, so that was the only way we could do something like this. It’s ugly and slow.

Moreover, we’re forced to create two functions stem_the() and cmp_the() (my names are always this creative). We’ve cluttered the global function namespace for our very trivial task.

Enter stage left, Dr. Martin Luther Lambda. His dream is promoting functions to first-class citizens…

With lambdas, we can rewrite that entire mess to be the clean, simple, elegant mess that follows:

$bands = array( 'The All American Rejects',
        'Beck', 'Blue October',
        'The Starting Line' );

usort( $bands, function($a,$b)
{
    list($a,$b) = array_map(function($s) {
    return preg_replace('/^(a|the) *(.*)$/i','$2', $s);
    }, array($a,$b));
    return strcmp($a,$b);
});

Notice that this code doesn’t create any new functions in the global namespace. It’s slightly harder to read initially (mostly because of the gratuitous use of the list() language construct), but it is vastly cleaner and, in a word elegant.

(Aside: calling super geeky things elegant is not even close to pass’e yet.)

We can also now perform the operation of currying-partially instantiating a function with multiple parameters. Let’s say we want to apply a function to each item in a list that adds 7 to that item. PHP has a built-in array_map() function, used above, that allows us to apply a function to every item in an array, but its argument is again a string, and we still have to create a global-namespace function to accomplish this.

Let’s just say we have a function add() such as

function add($x,$y) { return $x + $y; }

and we want to create a function add7($x) that returns $x + 7. We could simply create it:

function add7($x){ return $x + 7; }

Now what we want to do is partially instantiate our add() function to have a sort of ‘hard-coded’ first argument 7. In this way, we would define add7() to be

    function add7($x){ return add(7,$x); }

We just had to create another function in the global namespace: bloating our memory footprint and creating an obtrusive disaster of our codebase to accomplish a trivial task.

With currying, we could simply do this:

$add  = function()( $x, $y ) { return $x + $y; };
$add7 = curry($add,7);

The punchline is that curry() returns a function. It’s a robot that gives birth to new robots. Elegant?

So we can increment every item in an array by 7 very simply:

$nums = array( 1, 2, 3, 4 );
$add  = function()( $x, $y ) { return $x + $y; };
$nums = array_map( curry($add,7), $num );

(This example is very contrived, of course, since there was no reason to use currying here-we could have simply had

$nums = array( 1, 2, 3, 4 );
$nums = array_map( function($x){ return $x + 7; }, $num );

but cut me some slack.)

Unfortunately curry() is not yet part of the PHP standard library. It’s also not inherently obvious how to implement it-the necessary language constructs were only introduced a mere three weeks ago today.

Fortunately, I have implemented curry() for you. It’s a bit ugly, but it works. It’s actually fairly fast as well (although my initial tests of it were not exhaustive).

function curry($fn, $arg)
{
    return function() use ($fn, $arg)
    {
        $args = func_get_args();
        array_unshift( $args, $arg );
        return call_user_func_array( $fn, $args );
    };
}

It’s cool because you can chain it to itself. So if you wanted a function that always returned 7, you could simply say:

$return7 = curry(curry($add,3),4);

Or if you had a function that took three arguments and you wanted a new function with the first two ‘hard-coded’ (imagine g(x) = f(1,3,x) from math), you could simply “curry f()” twice:

$g = curry(curry($f,3),1);

A better implementation would be for curry() to take a variable number of arguments and to curry all of them in:

$g = curry($f,3,1); // or `curry($f,1,3)` maybe?

I’ll leave this as ‘an exercise for the reader’, but it’s not too difficult to implement.

Awesome, n’est-ce pas?

You, too, can have some PHP 5.3 alpha goodness by running the following nonsense on your command line:

mkdir -p "$HOME/src/php53alpha/build"
cd "$HOME/src/php53alpha"
wget http://downloads.php.net/johannes/php-5.3.0alpha1.tar.gz
tar zxf php-5.3.0alpha1.tar.gz
cd php-5.3.0alpha1
./configure --prefix="$PWD/../build"
make
make install

This installs the php binary in ~/src/php53alpha/build/bin, so you can run your .php scripts by simply calling, e.g.,

~/src/php53alpha/build/bin/php my_script_file.php

Also read:

Enjoy.