Blog

Recursive Closures and How to Get Rid of Them

Károly (Chx) Négyesi

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!

Comments

Thanks I learnt something useful from this!

Advertisement

From our blog

Entity Storage, the Drupal 8 Way

In Drupal 7 the Field API introduced the concept of swappable field storage.

The Drupal 6 to 8 Upgrade Challenge - Part 2

Having concluded the readiness assessment, we turn next to migrating the content and configuration. In reality, there’s little chance that we would migrate anything but the blogs from our old site. For the sake of giving Migrate in Core a workout with real conditions, however, we’re going to upgrade with core’s Migrate Drupal module rather than rebuilding.

The Drupal 6 to 8 Upgrade Challenge - Part 1

Nathaniel Catchpole , the Drupal 8 release maintainer and Tag1 Senior Performance Engineer, suggested that Drupal shops everywhere could support the

DrupalCon Austin

The entertainment industry is not for the faint of heart.

Drupal Watchdog Joins the Linux New Media Family
Drupal Watchdog 6.01 is the first issue published by Linux New Media.

Drupal Watchdog 6.01 is the first issue published by Linux New Media. Come see the Drupal Watchdog team at DrupalCon 2016!

Drupal Watchdog was founded in 2011 by Tag1 Consulting as a resource for the Drupal community to share news and information. Now in its sixth year, Drupal Watchdog is ready to expand to meet the needs of this growing community.

Drupal Watchdog will now be published by Linux New Media, aptly described as the Pulse of Open Source.

Welcome to DrupalCon Barcelona - The Director's Cut

For all you schedule-challenged CEOs – and ADHD coders – this Abbreviated Official Director’s Cut is just what the doctor ordered.

Welcome to DrupalCon - The Barcelona Edition

Did we have fun in Barcelona?
OMG, yes!

Did we eat all the tapas on the menu and wash them down with pitchers of sangria?
Yes indeed!

Recursive Closures and How to Get Rid of Them

This came up while manipulating taxonomy children and their children recursively, so it’s as not far from Drupal as you’d think.