Anonymous recursion in PHP

By Ryan in php, php 5.3, closure, new features, recursion

The scenario

You’re neck deep in 3-year old production code, amazon one-click checkout isn’t working, and your wife just left you for someone who “doesn’t spend so much time writing unit tests.” You need to save the world by implementing an algorithm using an anonymous function now. Wait, what if the problem you need to solve is well served with a recursive approach? Maybe you attack the problem optimistically, starting with something like this:

“Well, crap,” you say, seeing the Fatal error reported by PHP. Turns out that variables called as functions must be an instance of Closure, an instance of a class which implements __invoke(), or a string representing a named function in the global namespace. In the anonymous function body above, $fibonacci is none of these. It is an undeclared, free variable in the closure created by the anonymous function. At the time when it’s called, it hasn’t been bound—hence the Notice that you would have gotten if error reporting were set at a high enough threshold—and therefore can’t be called as anything, let alone as a function.

So how should you proceed? The classical solution would be simply to name this function; instead of binding the function to a variable called $fibonacci, we should just name the function fibonacci. That would certainly be convenient. But what if we encounter a higher-order function that expects a function as a parameter? It happens that many higher-order functions in PHP can simply accept as callbacks the names of functions, but I prefer not to rely on that. In fact, any userland function you write which expects a lambda will work just as happily being sent a string. But what if we must provide the higher-order function with the means of calculating the nth Fibonacci number? How could we even go about implementing the recursion required to pull it off? I’m so glad you asked.

Naming the nameless

The difficult part about the above is that we have no good way to actually call the function in whose body we are executing while we’re still in it. The thing’s anonymous, after all—we are essentially looking for some way to break its anonymity, to call the nameless by name. Well, we may not be able to actually extract the name of this function for the purpose of calling it again, but we do have some information about the location where it’s held in memory. This location is known to $fibonacci, the value we’re using in the parent scope to hold the function itself. Therefore, if we could grab the value of $fibonacci, we could actually use it to recurse. The problem here is that $fibonacci does not exist in the scope where we need to use it.

If you had read my article about closures, you would know that we have the ability in PHP to do something that sounds very much like this. With PHP’s use keyword for anonymous function definition, we can pull either a value or a reference into a function’s scope. Let’s be naive and pull in the value of $fibonacci in a forshadowingly misguided attempt to recurse:

This new function actually has the exact same body as our original attempt; the only difference is that we are now pulling in the value of $fibonacci from the parent scope and binding it at definition-time. Running this, we actually get the exact same error we got above. Why?

Without going into the nitty gritty details, let’s walk through what’s happening here. First, we declare a variable called $fibonacci and then assign to it the anonymous function. Here’s the problem: this function statement doesn’t terminate until after the value of $fibonacci is pulled into its body and used. Since we are @use@ing $fibonacci by value, that value is declared but undefined when we actually pull it into the function scope. Notice that there is no fatal error here until we actually execute $fibonacci(). That’s very important.

Closure-by-reference

Seeing that this doesn’t work, let’s take a slightly different approach by bringing $fibonacci into the anonymous function by reference (in functional parlance, let’s close our anonymous function over $fibonacci). By doing so, we still pull $fibonacci into our function before it actually refers to anything useful. However, because we are closing by reference, rather than by value, $fibonacci will be properly defined by the time we actually need to run it. Remember how we didn’t get the error by value until we executed the function? That problem goes away now, because by the time we execute the function, the variable holding it for us is actually holding it for us.

Now that we have a working recursive anonymous function, let’s explore some examples of what we can do with it. One nice thing about this particular implementation (which emphatically isn’t due to its anonymous nature, but rather by design) is that it is completely non-destructive.

Applications

Here are some applications of what we’ve accomplished above:

map:

Functional programming in PHP is a whole ‘nother level of ugly. Here’s an implementation of map, a higher-order function which takes a single-argument function and applies it to each element in a collection. Here, we pass it $fibonacci, which holds our recursive anonymous function.

reduce:

reduce is another common higher-order function. It takes a function of two arguments and a collection and maps the array pairwise into a single value using the function.

Conclusion

If we were in a situation where we needed to make use of a higher-order function like one of these above, it would be very inconvenient to be limited to only using anonymous functions which could not be written recursively. With these “pass-by-reference closures” in PHP, we can circumvent that limitation and provide our anonymous function to any higher-order function that can use it.

This is still a somewhat poor solution, however, because our functions are no longer truly anonymous. Instead of binding the name of the function to an identifier, we are binding the name of our function to a variable. In case we wanted to change the name of the function, or provide recursion like this in an inner-anonymous function, we might struggle.