Y-Combinator in PHP

Posted on by

Since PHP 5.3 now has closures, all things that other languages with closures do should also be possible. One of them is having recursive closures. I.e. something like this:

$factorial = function($n) {
   if ($n <= 1)
     return 1;
   else
     return $n * call_user_func(__FUNCTION__, $n - 1);
};

which does not work. One of the ways to do it is to use Y combinator function, which allows, by application of dark magic and friendly spirits from other dimensions, to convert non-recursive code to recursive code. In PHP, Y combinator function would look like this:

function Y($F) {
    $func =  function ($f) { return $f($f); };
    return $func(function ($f) use($F) {
            return $F(function ($x) use($f) {
            $ff = $f($f);
            return $ff($x);
        });
    });
}

And then the factorial function would be:

$factorial = Y(function($fact) {
    return function($n) use($fact) {
        return ($n <= 1)?1:$n*$fact($n-1);
    };
});

Which does work:

var_dump($factorial(6)); ==> int(720)

Of course, we could also cheat and go this way:

$factorial = function($n) use (&$factorial) {
      if ($n <= 1)
        return 1;
      else
        return $n * $factorial($n - 1);
};

Doing Y-combinator in PHP was attempted before (and here), but now I think it works better. It could be even nicer if PHP syntax allowed chaining function invocations – ($foo($bar))($baz) – but for now it doesn’t.

If you wonder, using such techniques does have legitimate applications, though I’m not sure if doing it in PHP this way is worth the trouble.

15 thoughts on “Y-Combinator in PHP”

  1. Pingback: » Перетворення не рекурсивної функції в рекурсивну Замітки програмуючого програміста :)

  2. Pingback: PHP 5.3 : Practical look into Lambda functions and closures | Test site

  3. Pingback: Anonymous (lambda) functions in PHP | Living with PHP

  4. Pingback: 5.3!!! | BrainPair - the Techno Blog

  5. Pingback: 5.3!!! « PHP 10.0 Blog

  9. Would scandir() (when used to walk a directory structure, not just a single directory) be a good candidate for a YCombinator?

  10. Pingback: Y-Combinator in PHP " PHP 10.0 Blog « DevEzine

  11. Pingback: PHP 10.1 Blog: Y-Combinator in PHP : Dragonfly Networks

  12. Correct me if i’m wrong but the Y-combinator for Fibonacci is exponential. It becomes linear only when you add caching. Seems to me it is possible to add caching the recursive function either. So the performance boost comes not from using Y-combinator but caching.

    My question then is if there’s any performance boost to Y-combinator at all?

    • Žilvinas, yes – see the “legitimate applications” like for an example of caching Y-combinator for Fibonacci numbers.

      I’d doubt there’s much performance boost from using Y-combinator alone. But I won’t be surprised if some creative use of it allowed doing some stuff faster.

  14. amazing stuff, thanks for posting this Stas, and especially the link to the legitimate application usage. This faster recursion may be very useful in an app like phpDocumentor, which does lots of recursive processing.

Comments are closed.