Blog

This came up while manipulating taxonomy children and their children recursively, so it’s as not far from Drupal as you’d think. First, we will learn how to create recursive closures which in itself is a bit tricky. Then, as an option, you can learn about getting rid of them which is really tricky.

Let’s say for the sake of simplicity we have a factorial function:

<?php
function factorial($x) {
  return $x ? $x * factorial($x -1) : 1;
}
?>

This is a classic, horribly inefficient way to calculate a factorial (see http://cs.stackexchange.com/a/14476/10273 for a more efficient way, but that’s not our topic today). Now let’s say you wanted to do this in an anonymous function:

<?php
$factorial = function($x) use (&$factorial) {
  return $x ? $x * $factorial($x -1) : 1;
};
?>

Although the variable $factorial does not exist when use(&$factorial) is reached, the reference sign will force PHP to create the variable with a value of NULL and not throw a notice. However when PHP finishes evaluating the expression function… it will assign the closure to $factorial so now, inside the closure, the same function can be called. Neat trick.

However, this is somewhat ugly, requires a reference, and won’t work if you change the variable $factorial outside of the closure which violates the principle of a closure being, well, a closed thing.

Instead, we could do this:

<?php
$factorial = function($func, $x) {
  return $x ? $x * $func($x -1) : 1;
};
?>

Now you need to do $factorial($factorial, $x) which is uglier but much more correct. Still, it’s quite error prone: if you pass in something else as the first argument or nothing at all, it breaks. We can fix this with the following function:

<?php
function fix($func) {
  return function() use ($func) {
    $args = func_get_args();
    array_unshift($args, fix($func));
    return call_user_func_array($func, $args);
  };
}
$original_factorial = function($func, $x) {
  return $x ? $x * $func($x -1) : 1;
};
$factorial = fix($original_factorial);
?>

What happens if you call $factorial(5) ? Well, $func inside $factorial equals $original_factorial so when the array_unshift runs, then it puts fix($original_factorial) as the first argument which is the same as $factorial. So then it calls $original_factorial with $func = $original_factorial, $x = 5.

This is also called “fix” because it is (almost) a fix point combinator. If that sounds familiar, perhaps it’s because you’ve heard of the most famous one: the Y combinator. Now, our example fails some of the fix point combinator criteria, but it’s pretty close. And it does allow the chief practical programming task: recursion on a higher-order function!