Sunday, June 28, 2009

Currying in PHP

What happens if you don't have all the arguments handy for a function, but you want to give whatever arguments you do have now and then provide the rest of them to the function later? This is called currying, and is a core concept in functional programming. It's messy, but possible to curry functions in PHP now that closures have been added.

First, let me show you how currying looks in a functional language. Here's a basic example in OCaml/F#:
let do_math op x y =
match op with
'+' -> x + y
| '-' -> x – y
| _ -> failwith "Invalid op"

let add = do_math '+'

let inc = add 1
let dec = add (-1)
;;
A function named do_math is defined that accepts an operator and two operands. The function's return value will be either the sum or difference of the operands, depending on whether the given operator is + or -. Notice how do_math is then called with a single argument. OCaml doesn't raise an error; it simply returns a function that "remembers" the first argument and accepts the remaining two arguments later (this is an over-simplified and slightly inaccurate statement, but a good enough description for our purpose here). This intermediate function can be used elsewhere, as in the bindings for inc and dec.

Now here's a version of the do_math() function in PHP:
function do_math($op, $x, $y) {
switch ($op) {
case '+':
return $x + $y;

case '-':
return $x - $y;

default:
throw new Exception("Invalid op");
}
}
Unfortunately, PHP will throw warnings if you call do_math() without the three arguments it expects.

Warning: Missing argument 2 for do_math(), called in /home/tboronczyk/curry.php on line 16 and defined in /home/tboronczyk/curry.php on line 2

Warning: Missing argument 3 for do_math(), called in /home/tboronczyk/curry.php on line 16 and defined in /home/tboronczyk/curry.php on line 2


Whereas functional languages have currying "built-in," you must explicitly code this ability in an imperative language. Doing so in PHP requires the use of closures:
function do_math($op) {
return function ($x) use ($op) {
return function ($y) use ($op, $x) {
switch ($op) {
case "+":
return $x + $y;

case "-":
return $x - $y;

default:
throw new Exception("Invalid op");
}
};
};
}
It's also possible to extend the function using func_num_args() and func_get_arg() functions, anonymous functions, and closures, so that any number of parameters can be given at a time. This is a more general form of currying known as "partial functions".
function do_math() {
if (func_num_args() >= 1) $op = func_get_arg(0);
if (func_num_args() >= 2) $x = func_get_arg(1);
if (func_num_args() == 3) $y = func_get_arg(2);

switch (func_num_args()) {
case 1:
return function () use ($op) {
if (func_num_args() >= 1) $x = func_get_arg(0);
if (func_num_args() == 2) $y = func_get_arg(1);

switch (func_num_args()) {
case 1:
return function ($y) use ($op, $x) {
return do_math($op, $x, $y);
};

case 2:
return do_math($op, $x, $y);

default:
trigger_error(
"invalid argument count",
E_USER_WARNING);
}
};

case 2:
return function ($y) use ($op, $x) {
return do_math($op, $x, $y);
};

case 3:
switch ($op) {
case "+":
return $x + $y;

case "-":
return $x - $y;

default:
throw new Exception("Invalid op");
}

default:
trigger_error("invalid argument count",
E_USER_WARNING);
}
}
It's messy... but it works! Now you are able to pass one or two arguments to do_math(), capture the intermediate function that's returned, and pass the remaining argument(s) later.
$add = do_math("+");

$inc = $add(1);
$dec = $add(-1);

echo do_math("-", 3, 2);
echo do_math("+", 1, 1);
echo $inc(2);
echo $add(2, 2);
echo $dec(6);
echo $add($inc(4), $dec(2));
The switch statements are rather unmanageable and the spaghettification of code grows exponentially with the addition of each argument. This pattern is straight forward, though. You may want to consider writing a code generator to handle the dirty work of retrofitting a function to one capable of being curried rather than writing them all by hand. Of course, if you know of a better way to curry functions in PHP then let me know by leaving a comment!

Update 06/29/09: Someone asked me what the "real-world use" for all this would be. Currying is used all the time in functional programming, but the hassle of explicitly enabling the behavior in PHP makes that a valid question. My motivation was just to see if it were possible and share my results. Indeed it is. Functions can be curried in any language that supports closures. But for those who want something a little more concrete, let's consider callback functions.

In a previous post I gave the following example to illustrate the use of closures:
$userPercent = 0.5;
$userList = array_filter($percentVowels,
function($percent) use ($userPercent) {
return ($percent >= $userPercent);
});
It showed an anonymous function being used with array_filter() to filter an array. The array is filtered based on a dynamic value, and a closure is used to "inject" the threshold rather than using a global statement. The same could also be accomplished with currying.

The problem is array_filter() expects a callback function that accepts one argument--the current array element. Currying will allow us to prepare the function with the sorting threshold, and the intermediate function can be used as the callback.
function callback($userPercent) {
return function($percent) use ($userPercent) {
return ($percent >= $userPercent);
};
}
$userList = array_filter($percentVowels, callback(0.5));

8 comments:

  1. I'd never heard of Currying before, thanks for sharing.

    ReplyDelete
  2. I don't know if this is a better way - but I wrote about the same thing back before we had closures in PHP (see http://metapundit.net/tech_blog/partial_function_application_in_php )

    I used a class to build an object holding the function to be applied and it's arguments and returned a "callback" psuedo type - an array holding an object and a method name. This can be passed as a callable to things like array_filter which is what I wanted it for. Of course this wouldn't be chainable since the result is not actually a function... (And parenthetically: I thought at the time partial function application and currying were separate techniques but I think people use them interchangeably).

    One other comment on your code I know it's just an example but switch statements frequently turn out to be bad code smells in my code. I'd probably refactor using a strategy pattern - and even use eval in your third case. Amazing as it seems, this is actually an appropriate use for eval as the inputs can be easily sanitized and the operation is straightforward. Case 3 above might then be:

    case 3:
     if(in_array($op, array("*","+","-","/") == false)
      throw new Exception("Invalid op");
     if(!(is_numeric($x) and is_numeric($y)))
      throw new Exception("Invalid argument");
     return eval("$x $op $y;");


    Just my 5 cents...

    ReplyDelete
  3. I never quite understood what currying "actually" is before I read this sentence:

    "Methods may define multiple parameter lists. When a method is called with a fewer number of parameter lists, then this will yield a function taking the missing parameter lists as its arguments."
    http://www.scala-lang.org/node/135

    ReplyDelete
  4. There's a more generic version at http://github.com/Burgestrand/Funcy

    ReplyDelete
  5. I have made an implementation of the canonical Haskell fibonacci-implementation:

    fibs = 0:1:zipWith (+) fibs (tail fibs)

    in PHP. It wasn't obvious how to express such a recursively defined lazy list, without making variables of the "Lazy List"-class mutable. I achieved this by nesting some anonymous functions..

    I'm interested in hearing if any of you can come up with a better solution to this "problem"..

    http://imada.sdu.dk/~sorenh07/misc/fibseq.phps

    :-)

    ReplyDelete
  6. That's an interesting approach, Søren. I would approach it using the Iterator interface to calculate the members sequentially. As you can calculate Fib(n) for any positive n use something like Binet's formula, the ArrayAccess interface can be used to allow arbitrary access to elements in the series. Here's a quick sample I wrote up to demonstrate: http://pastebin.com/udLZJC5n. I haven't rigorously tested it so beware of bugs, but it should get the point across.

    Once you do new Fib() you can access random elements:

    $fib = new Fib();
    var_dump($fib[42]);

    ...or iterate through the series:

    foreach($fib as $f) {
    var_dump($f);
    }

    ReplyDelete
  7. Thank you for your answer :-). My idea was to try to implement the sequence as close to "fibs = 0:1:zipWith (+) fibs (tail fibs)" as I could get - to see how far I could push usage of PHP's anonymous functions.

    Functional programming is all about composing functions to get new behavior, and I thought it could be interesting to replicate some of that in PHP.

    Here is a different approach: In Haskell it will look like this:

    nextfib (a,b) = (b,a+b)
    fibs = map fst $ iterate nextfib (0,1)

    In PHP:


    function nextfib(array $p) { return array($p[1], $p[0]+$p[1]); }
    function fst(array $p) { return $p[0]; }
    $l = new FunMap('fst',new FunIterate('nextfib', array(0,1)));

    http://imada.sdu.dk/~sorenh07/misc/fibseq2.phps

    Lazy lists are now implemented with the Iterator-interface, in the same spirit as your example.

    ReplyDelete
  8. Am a newbie as a developer and u have made a very good explanation on currying with a best programming code for it.Really helpful post dude.

    ReplyDelete