The Y combinator in Javascript

#1

Post by ColinWright » Mon, Sep 05, 2011, 4:26 PM UTC

The Y combinator in Javascript
matt.might.net

Re: The Y combinator in Javascript

#2

Post by pcwalton » Mon, Sep 05, 2011, 5:10 PM UTC

Curiously enough, the JavaScript Y combinator is in the Firefox source and has been since at least 2007: http://hg.mozilla.org/mozilla-central/file/fc78ee766770/js/s...

Re: The Y combinator in Javascript

#3

Post by cygx » Mon, Sep 05, 2011, 5:58 PM UTC

There's actually a simpler fixed-point combinator for JavaScript than the 'standard Y' - see http://rosettacode.org/wiki/Y_combinator#JavaScript

Re: The Y combinator in Javascript

#4

Post by 0x12 » Mon, Sep 05, 2011, 6:10 PM UTC

cygx wrote: post #3

There's actually a simpler fixed-point combinator for JavaScript than the 'standard Y' - see http://rosettacode.org/wiki/Y_combinator#JavaScript

"However, pseudoY() is not a fixed-point combinator'".

Re: The Y combinator in Javascript

#5

Post by cygx » Mon, Sep 05, 2011, 6:18 PM UTC

0x12 wrote: post #4

cygx wrote: post #3

There's actually a simpler fixed-point combinator for JavaScript than the 'standard Y' - see http://rosettacode.org/wiki/Y_combinator#JavaScript

"However, pseudoY() is not a fixed-point combinator'".

I'm not talking about pseudoY(), but Y()

Re: The Y combinator in Javascript

#6

Post by dpkendal » Mon, Sep 05, 2011, 7:07 PM UTC

pcwalton wrote: post #2

Curiously enough, the JavaScript Y combinator is in the Firefox source and has been since at least 2007: http://hg.mozilla.org/mozilla-central/file/fc78ee766770/js/s...

That is by far the clearest implementation of the Y-combinator I've ever seen. And I'm not even a JavaScript programmer.

Re: The Y combinator in Javascript

#7

Post by hesselink » Mon, Sep 05, 2011, 8:19 PM UTC

pcwalton wrote: post #2

Curiously enough, the JavaScript Y combinator is in the Firefox source and has been since at least 2007: http://hg.mozilla.org/mozilla-central/file/fc78ee766770/js/s...

Why is it in there? Is it a test case?

Re: The Y combinator in Javascript

#8

Post by cygx » Mon, Sep 05, 2011, 8:43 PM UTC

dpkendal wrote: post #6

pcwalton wrote: post #2

Curiously enough, the JavaScript Y combinator is in the Firefox source and has been since at least 2007: http://hg.mozilla.org/mozilla-central/file/fc78ee766770/js/s...

That is by far the clearest implementation of the Y-combinator I've ever seen. And I'm not even a JavaScript programmer.

Really? What about

    function Y(f) {
        var g = f(function(arg) {
            return g(arg);
        });
        return g;
    }

The inner() function from Mozilla's implementation is actually unnecessary in languages that support lexical closures.

Re: The Y combinator in Javascript

#9

Post by jaekwon » Mon, Sep 05, 2011, 8:48 PM UTC

it looks like all the magic happens with the U combinator, where "recursion" is avoided by finding F = f(f), and passing f as a parameter such that F can be reconstructed.

which still smells like recursion, a type of recursion where the recursive element keeps getting punted around as a parameter like an epileptic cannibalistic stem-cell with no name.

Re: The Y combinator in Javascript

#10

Post by [deleted] » Mon, Sep 05, 2011, 8:48 PM UTC

[deleted]