No, it's the famous Y combinator. The point is that *no* naming is needed, the names "Y" and "fac" were used only for convenience.
Just try
(lambda (function f) { return lambda(mixed y) { return (lambda(function x, mixed w) { return f(lambda(mixed z) { return x(x, z); }, w); }) (lambda(function x, mixed w) { return f(lambda(mixed z) { return x(x, z); }, w); }, y); };}) (lambda (function this_function, int x) { return (x == 0) ? 1 : x * this_function(x - 1); }) (17);
Say you have a function f(function g, x), this can be viewed as a transformation from (x->g(x)) to (x->f(g,x))f. In this case it's
lambda (function this_function, int x) { return (x == 0) ? 1 : x * this_function(x - 1); }
Y constructs a kind of "fix point" to this function:
f(Y(f), x) = Y(f)(x).
It's quite a remarkable fact that such a fix point operator exists, and even more remarkable that it can be written as a fairly short lambda expression.
To see why, one can start with Y(f)(x), and do one round of argument substitution of into the first lambda call. After some rewriting out comes an expression that is equivalent to f(Y(f), x).
The usual definition is in a lambda language with curryfication of function arguments:
Y := (lambda (f) ((lambda (x) (f (lambda (z) ((x x) z)))) (lambda (x) (f (lambda (z) ((x x) z)))) ))
/ Niels Möller (igelkottsräddare)
Previous text:
2003-10-06 20:04: Subject: Re: Some tasks from the conference
Whoa, now that was a good entry for the next obfuscated Pike contest. :)
I take it that it's some kind of cheating to simply give a name to a lambda?
function Y (function f) { mixed g (mixed... args) { return f (g, @args); }; return g; }
/ Martin Stjernholm, Roxen IS