PHP 10.0 Blog

What if…

Y-Combinator in PHP

Posted by Stas on April 13, 2009

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.

About these ads

15 Responses to “Y-Combinator in PHP”

  1. 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.

  2. anilkumar said

    what is this “y” combinator in php……..

  3. Žilvinas said

    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?

    • Stas said

      Ž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.

  4. [...] from the PHP 10.0 blog today is this look at trying to set up recursive closures in the upcoming PHP 5.3 release (it includes closures, but [...]

  5. [...] Read the original post: Y-Combinator in PHP " PHP 10.0 Blog [...]

  6. Richard Quadling said

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

  7. rquadling said

    Would scandir() (when used recursively) be a good candidate for a YCombinator?

  8. Webdev said

    Thank you very much :) I was wondering how PHP can handle recursive closures and you just gave me the answer.

  9. Cederash said

    Да, есть над чем задуматься. Спасибо!

  10. [...] and anonymous functions! PHP now has first-class functions, and you can do all kinds of crazy stuff with it. Or just make your code easier to read and [...]

  11. [...] and anonymous functions! PHP now has first-class functions, and you can do all kinds of crazy stuff with it. Or just make your code easier to read and [...]

  12. [...] Y-Combinator in PHP [...]

  13. [...] any non recursive function to a recursive one. It is written by Stanislav Malyshev in his article Y-Combinator in PHP. It is interesting that Y-combinator has a strong relation with lambda [...]

  14. [...] Щоб перетворити не рекурсивну функцію в рекурсивну в php потрібно заюзати Y combinator [...]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
Follow

Get every new post delivered to your Inbox.

%d bloggers like this: