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.
Local variables are named. I don't see a significant differance. Also, I think 'famous' might be a slight exaggeration. :)
/ Fredrik (Naranek) Hubinette (Real Build Master)
Previous text:
2003-10-06 21:20: Subject: Re: Some tasks from the conference
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)