Applicative Order Y Combinator

[liorean]

Can anyone explain to me what this actually is? What is is supposed to do? Why does it work, and how? What use may it have?

I've been trying to wind my way through the actions of both the Scheme version as presented by "The Little Schemer":
(define Y
(lambda (le)
((lambda (f) (f f))
(lambda (f)
(le (lambda (x) ((f f) x)))))))
And Douglas Crockford's JavaScript version (virtually the same) from <http://www.crockford.com/javascript/little.html>:function Y(le) {
return function (f) {
return f(f);
}(function (f) {
return le(function (x) {
return f(f)(x);
});
});
}

I'm normally pretty good at thinking recursively, and I can follow recursive program flows pretty well, but this one just keeps evading my sense of what happens and is supposed to happen next.

[jkd]

*ouch* Empirically, the return value is whatever le() returns.

Y(function(x) { return 5 })

returns 5 for instance. When you start doing stuff with x though, it gets interesting.

Y(function(x) { return x })

returns

function(x) {
return f(f)(x);
}

and Y(function(x) { return x(x) }) just closes Mozilla immediately; no warning, no anything. Just bam, deadness.

I think it's about time I learn lambda calculus... :D

[jkd]

A little bit of research, Y(f) finds fixed points of f, namely where f(x)=x. From this, it follows that Y(f) = f(Y(f)). (Let x = Y(f), it being a point where x = f(x), which Y returns by definition. Then x = f(x), qed.)

The given function definition of Y is some crazy manipulation of the true definition in lambda calculus. I have no idea how you can prove it (since I've never studied lambda calculus), but if you wish, you can take it as a magical formula that returns fixed points.

So, for example, we have something like the factorial function; factorial(1) = 1, factorial(2) = 2.... 1 and 2 are fixed points of the factorial function. Therefore, Y(factorial) should return 1 and 2.

But, if that's the case, how then can we possibly use it to define recursive functions? Well, numbers themselves are apparently recursive functions in lambda calculus :-/:
http://en2.wikipedia.org/wiki/Church_integer

So really, we're supplying a function argument, and in lambda calculus, every function has a fixed point, so the Y function is generating a function that has a fixed point at our desired answer.

... I think at least. This is well above my head for the moment.

[liorean]

jkd: Well, this is the Applicative Order Y Combinator I'm talking about. You're talking about the Fix Point Y Combinator. From what I've managed to gather, there is a considerable difference, but I don't understand what yet. I've read through 'The Why Of Y' by Peter Gabriel <http://www.dreamsongs.com/NewFiles/WhyOfY.pdf> and 'Lambda Calculus' by André van Meulebrouck <http://www.mactech.com/articles/mactech/Vol.07/07.05/LambdaCalculus/index.html>, and I still don't get it.

[liorean]

Okay, I've had a look at a common Scheme example for the Applicative Order Y Combinator, the factorial function. I've turned it into JavaScript here so that you others that are not dabbling into Scheme can understand it. The Y function is of course the same as above, so let's look at the only other code we will be using:function fact(h){
return function(n){
return (n < 2 ?
1 :
n * h( --n ) )
}
}Let's examine what this 'fact' function does:
It returns a closure of a function that takes an argument n, which returns 1 if the argument is below 2, otherwise returns the n argument times the result of calling the fact argument h with n-1.

Thus, the results of fact are a function whose results are entirely dependent of the h argument sent to fact unless the n argument sent to it is below 2, in which case it will return 1.


Ok, let's see what our return value for Y(fact) is:function (n) {
return (n < 2 ? 1 : n * h(--n));
}It's the closure from the return value of the fact function. So, did that tell us anything? What is h in the closure, one might wonder. So, let's find out:function (x) {
return f(f)(x);
}This turns out to be one of the closures from within the Y function. Again we have an unknown, this time f. So, let's continue the same way and find out what f is:function (f) {
return le((function (x) {return f(f)(x);}));
}Again a closure from within Y. This time we know the value of f, however, so the question will be, what is the value of le this time?function fact(h) {
return (function (n) {
return (n < 2 ?
1 :
n * h(--n));
});
}Ah, the le value is the fact function, which we know comes from us passing it to Y! This means we now have gone through the closures built in the execution of this function, and thus can substitute the entire Y(fact) with it's expansion.


....so let's have a try at putting them together:// Y(fact) =>
function (n) {
return (n < 2 ? 1 : n * h(--n));
}

// We know what h is, now. So, let's
//expand h to it's value instead:

function (n) {
return (n < 2 ? 1 : n * (function (x) {
return f(f)(x);
})(--n));
}

// Likewise, we now know the value of
// f, so let's expand it as well:

function (n) {
return (n < 2 ? 1 : n * (function (x) {
return (function (f) {
return le((function (x) {return f(f)(x);}));
})(function (f) {
return le((function (x) {return f(f)(x);}));
})(x);
})(--n));
}

// Finally, let's have a look at what happens if we
// replace the last of them with it's value:

function (n) {
return (n < 2 ? 1 : n * (function (x) {
return (function (f) {
return (function fact(h) {
return (function (n) {
return (n < 2 ?
1 :
n * h(--n));
});
})((function (x) {return f(f)(x);}));
})(function (f) {
return (function fact(h) {
return (function (n) {
return (n < 2 ?
1 :
n * h(--n));
});
})((function (x) {return f(f)(x);}));
})(x);
})(--n));
}So, this last expansion is the entire result value of Y(fact), all it's closures exploded. Does it explain what Y did with the fact function? We'll have a look at what happens when we run this function with a value.


First, a table of results and an explanation of how those results were arrived at:x Y(fact)(x) fact(fact)(x) Why?
---- ---- ---- ----
0 1 1 (x < 2) => 1
1 1 1 (x < 2) => 1
2 2 NaN 1 * 2 = 2
3 6 NaN 1 * 2 * 3 = 6
4 24 NaN 1 * 2 * 3 * 4 = 24
...So, if you inspect the return values returned from Y(fact)(x) you see that it must be recursively progressing from an x value of 2 or larger to a point where the the x value is below 2. The fact(fact)(x) call on the other hand seems to not provide for the same recursion, and only works for values below 2. Does those closures have something to do with this? Let's have a look at h in the fact(fact) call:function fact(h) {
return (function (n){
return (n < 2 ?
1 :
n * h(--n));
});
}So, this is not the same as when we use Y for it. What about if we use fact(fact()) then?function (n) {
return (n < 2 ? 1 : n * h(--n));
}Okay, that's the same, but now we have an inner function that in turn has an h, but in this case it's undefined. So, how do we solve this? Well of course, we send it the results of the fact function, like this fact(fact(fact())). And now, we have two h values set to what they should, but a third that is undefined. What does that tell us about Y?

This is the important part: Y takes a function and applies it's return value on it's return value in a manner that means all return values will be sent the return value of itself, effectively expanding the example function to fact(fact(...(fact())...)), recursively. Won't this produce infinite loops, you ask? Well, that's the true brilliance of the Applicative Order Y Combinator - it will only do so if required. The fact function for example will first execute for a value 6, then a value 5, then a value 4, then a value 3, then a value 2, then a value 1. Since you don't need to call the function any longer when you have reached 1, you don't. This means that the actions performed by the Y Combinator, like any other recursive statement, must have a condition that breaks out of the recursion, which for each run must come closer and closer, by direct or indirect means. If no such condition is supplied, or if it exists but no progression towards it takes place, it will continue forever, never coming any closer to ending the loop.




(Yikes, that was intended to explain the Y Combinator as I had come to understand it, but it turned out to be rather lengthy. Maybe something for basing an article on?)