Y-Combinator in PHP

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.

Advertisements

Zend Server

The product that I (among many others here at Zend) was working on lately – Zend Server – was released today.

Basic version is free (as in “free beer”) and has fastest bytecode-cache that I know of, native RPM/DEB install, debugger and other goodiesFull version of course is even better.