PHP 10.0 Blog

What if…

Posts Tagged ‘y-combinator’

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

Posted in Engine, PHP | Tagged: , , , | 15 Comments »


Get every new post delivered to your Inbox.