The Y combinator in Javascript

http://matt.might.net/articles/implementation-of-recursive-fixed-point-y-combinator-in-javascript-for-memoization

by ColinWright • 15 years ago

70 20 15 years ago

matt.might.net

pcwalton• 15 years ago

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...

dpkendal• 15 years ago

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

cygx3• 15 years ago

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.

hesselink• 15 years ago

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

cygx3• 15 years ago

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

0x12• 15 years ago

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

cygx3• 15 years ago

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

jaekwon• 15 years ago

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.

jpadvo3• 15 years ago

This is absolutely fascinating, but I'm having trouble really grokking the principle behind this. I understand fixed points of mathematical functions with numbers, but my mind seems to explode in the transition to functions of functions.

Is there a really clear explanation anywhere of the idea behind all this? Or is it the kind of thing where this is simple as it gets, and I just need to put in more work to get it?

qntm2• 15 years ago

I'm going to write up some sort of explanation once I can get my head around it myself.

dilap2• 15 years ago

I don't know if these ramblings will help, but here are some thoughts :)

First of all, the Y-combinator is a function of a function of a function (of a number), so we're three levels deep, which is part of what causes the head-spinning, I think. So ignore the Y-combinator for the moment.

Simply consider the function of a function (of a number) F:

  F = function (f) {
   return function(n) {
    return (n == 0) ? 1 : (n*f(n - 1)); };
  };

Here the argument f is a function number -> number, and the return value from F is itself also a function number -> number.

We can pass whatever functions from numbers to numbers we want to F to make new functions from numbers to numbers.

E.g., we could pass in

  exf1 = function(n) { return n };

and we'd have

  F(exf1) = function(n) { return (n == 0) ? 1 : (n*(n - 1)) };

Or we could pass in something like

  exf2 = function(n) { return 1; }

in which case we'd get

  F(exf2) = function(n) { (n == 0) 1 : n - 1 };

So now imagine god gives us the factorial function:

   fact: number -> number 
   fact(n) = n*(n - 1)*...*1

Then if we pass this in to F we get

   F(fact) = function(n) { return n == 0 ? 1 : n*fact(n - 1) }

But the above is simply a recursive definition of fact! So F(fact) = fact, i.e., fact is a fixed point of F.

Now consider the Y combinator. We know the Y combinator gives us a fixed point of a functional, i.e.,

  F(Y(F)) = Y(F)

(Note Y(F) is simply a function, even though the argument to Y is a functional, i.e.,

  Y: functional -> function

  Y: (function -> function) -> function

  Y: ((number -> number) -> (number -> number)) -> (number -> number))

So we know that one possible value for Y(F) is fact.

The article makes the claim that there is only one fixed point of F, which means Y(f) must actually be fact, but to be honest, I'm not sure why we know there can't be other fixed points of F which Y(F) might give us (though maybe this is obvious and I'm being stupid :).

But anyway we can tell by tracing through the definition of Y that it we really do get Y(F) = fact.

dilap2• 15 years ago

Oh, in the morning it occurs to me that a simple argument by induction will show that any function g with g = F(g) must in fact be factorial, so that's one way we can know the fixed point is unique. :)

jpadvo3• 15 years ago

Thanks, dilap! That does make the concept a lot clearer. Especially the Haskell-ish typing. :)

qntm2• 15 years ago

The best I've managed is this: http://qntm.org/fib

I find that removing all mention of Y combinators made the whole thing a lot easier to read.

jpadvo3• 15 years ago

Thank you! That was very helpful. :)

SteveJS2• 15 years ago

"Clearly there is no recursion, iteration, or mutation."

I don't see how it's clear there is no recursion. Perhaps my definition of recursion is overly broad? I will now proceed to demonstrate my deep ignorance. :-) [edit ... I'm not being sarcastic here ... I suspect I may be wrong on some definition or other.]

Drop the example in a debugger and you can step in until there are 7 instances of the callsite "return ((n == 0) ? 1 : (n*fact(n-1))) ;" on every other frame of the callstack.

I would describe this as the anonymous function in the Ycombinator calls the generator corecursively making a callstack proportional to the number of times you must call the generator before it finds the fixed point.

walrus• 15 years ago

Your definition of recursion is overly broad.

    var Y = function (F) {
     return (function (x) {
      return F(function (y) { return (x(x))(y);});
      })
            (function (x) {
      return F(function (y) { return (x(x))(y);});
      }) ;
    } ;
    
    [...]
    
    The Y combinator is a closed expression--it makes no
    explicit reference to an outside variable or to itself.
    Clearly, there is no recursion, iteration or mutation.

Look at the definition of Y—there are no capital Ys after the 5th character (or any equivalent things like arguments.callee).

SteveJS2• 15 years ago

Ah ... I misinterpreted the statement to encompass the expression rather then just the application of the Ycombinator.

Y(F) is not recursive. (Y(F))(X) is recursive. Is that accurate?

5teev• 15 years ago

I flubbed a job interview when asked how I'd implement a factorial. Of course I did the well-known recursive version, but then they asked how I could do it without recursion, and I blanked. I think they wanted me to talk about memoizing and the Y-combinator, but...I don't know, maybe they'd have settled for a naive for-loop.

The Y combinator in Javascript

Related Stories