Enjoy an ad free experience by logging in. Not a member yet? Register.

Results 1 to 5 of 5
Thread: Applicative Order Y Combinator

11282003, 01:57 AM #1
 Join Date
 Feb 2003
 Location
 Umeå, Sweden
 Posts
 5,575
 Thanks
 0
 Thanked 83 Times in 74 Posts
Applicative Order Y Combinator
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":Code:(define Y (lambda (le) ((lambda (f) (f f)) (lambda (f) (le (lambda (x) ((f f) x)))))))
Code:function Y(le) { return function (f) { return f(f); }(function (f) { return le(function (x) { return f(f)(x); }); }); }
liorean <[lio@wg]>
Articles: RegEx evolt wsabstract , Named Arguments
Useful Threads: JavaScript Docs & Refs, FAQ  HTML & CSS Docs, FAQ  XML Doc & Refs
Moz: JavaScript DOM Interfaces MSDN: JScript DHTML KDE: KJS KHTML Opera: Standards
11282003, 04:02 AM
#2
*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...
11282003, 04:31 AM
#3
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.
Last edited by jkd; 11282003 at 04:40 AM.
11282003, 11:36 AM
#4
 Join Date
 Feb 2003
 Location
 Umeå, Sweden
 Posts
 5,575
 Thanks
 0
 Thanked 83 Times in 74 Posts
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/mact...lus/index.html>, and I still don't get it.
Last edited by liorean; 11292003 at 02:15 AM.
liorean <[lio@wg]>
Articles: RegEx evolt wsabstract , Named Arguments
Useful Threads: JavaScript Docs & Refs, FAQ  HTML & CSS Docs, FAQ  XML Doc & Refs
Moz: JavaScript DOM Interfaces MSDN: JScript DHTML KDE: KJS KHTML Opera: Standards
11292003, 01:04 AM
#5
 Join Date
 Feb 2003
 Location
 Umeå, Sweden
 Posts
 5,575
 Thanks
 0
 Thanked 83 Times in 74 Posts
Ok, a new take on it
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:Let's examine what this 'fact' function does:Code:function fact(h){ return function(n){ return (n < 2 ? 1 : n * h( n ) ) } }
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 n1.
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: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:Code:function (n) { return (n < 2 ? 1 : n * h(n)); }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:Code: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?Code:function (f) { return le((function (x) {return f(f)(x);})); }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.Code:function fact(h) { return (function (n) { return (n < 2 ? 1 : n * h(n)); }); }
....so let's have a try at putting them together: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.Code:// 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)); }
First, a table of results and an explanation of how those results were arrived at: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:Code: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, this is not the same as when we use Y for it. What about if we use fact(fact()) then?Code:function fact(h) { return (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?Code:function (n) { return (n < 2 ? 1 : n * h(n)); }
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?)
Last edited by liorean; 11292003 at 01:39 AM.
liorean <[lio@wg]>
Articles: RegEx evolt wsabstract , Named Arguments
Useful Threads: JavaScript Docs & Refs, FAQ  HTML & CSS Docs, FAQ  XML Doc & Refs
Moz: JavaScript DOM Interfaces MSDN: JScript DHTML KDE: KJS KHTML Opera: Standards