Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 5 of 5
  1. #1
    Master Coder
    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)))))))
    And Douglas Crockford's JavaScript version (virtually the same) from <http://www.crockford.com/javascript/little.html>:
    Code:
    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.
    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

  • #2
    jkd
    jkd is offline
    Senior Coder jkd's Avatar
    Join Date
    May 2002
    Location
    metro DC
    Posts
    3,163
    Thanks
    1
    Thanked 18 Times in 18 Posts
    *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...

  • #3
    jkd
    jkd is offline
    Senior Coder jkd's Avatar
    Join Date
    May 2002
    Location
    metro DC
    Posts
    3,163
    Thanks
    1
    Thanked 18 Times in 18 Posts
    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; 11-28-2003 at 04:40 AM.

  • #4
    Master Coder
    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; 11-29-2003 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

  • #5
    Master Coder
    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:
    Code:
    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:
    Code:
    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:
    Code:
    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:
    Code:
    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?
    Code:
    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:
    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));
    }
    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:
    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, 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:
    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?
    Code:
    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?)
    Last edited by liorean; 11-29-2003 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


  •  

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •