"Y Combinator--a computer term for a program that runs other programs"

Heh... completely wrong, but I suppose it's the best you can expect a non-techie/math nerd readership to get. Heck, it's probably close to the most you can expect the average programmer to get.

EDIT: And another one...

"Graham met Morris, an authority on the Unix computer language"

> Heh... completely wrong, but I suppose it's the best you can expect a non-techie/math nerd readership to get. Heck, it's probably close to the most you can expect the average programmer to get.

How would you explain the Y Combinator to the Hacker News readership?

The Y combinator is a programming construct allowing one to write recursive functions without explicitly calling themselves (unnamed recursive functions):

  (define Y
   (lambda (X)
    ((lambda (procedure)
       (X (lambda (arg) ((procedure procedure) arg))))
     (lambda (procedure)
       (X (lambda (arg) ((procedure procedure) arg)))))))

  (define F*
   (lambda (func-arg)
    (lambda (n)
      (if (zero? n)
          1
          (* n (func-arg (- n 1)))))))

  (define fact (Y F*))
  (write (fact 8))

Note that F* is a label for a recursive factorial-computing function without a name.

I took the liberty of translating this to JavaScript, primarily to help me understand it, but thought I should share:

    // (define Y
    //   (lambda (X)
    //    ((lambda (procedure)
    //       (X (lambda (arg) ((procedure procedure) arg))))
    //     (lambda (procedure)
    //       (X (lambda (arg) ((procedure procedure) arg)))))))
    var Y = function(X) {
        return (function (procedure) {
            return X(function (arg) {
                return procedure(procedure)(arg);
            });
        })(function (procedure) {
            return X(function (arg) {
                return procedure(procedure)(arg);
            });
        });
    }

    //  (define F*
    //   (lambda (func-arg)
    //    (lambda (n)
    //      (if (zero? n)
    //          1
    //          (* n (func-arg (- n 1)))))))
    var F = function(func_arg) {
        return function(n) {
            if (n === 0)
                return 1;
            else
                return n * func_arg(n - 1);
        };
    }

    //  (define fact (Y F*))
    var fact = Y(F);

    //  (write (fact 8))
    console.log(fact(8));

This will probably go unnoticed, but this function seems to be equivalent, at least for the factorial example. What's the difference?

    var Y = function(X) {
        var Z = X(function(arg) {
            return Z(arg);
        });
        return Z;
    }

The difference is that the whole point of the Y combinator is that it's a fixed-point combinator that doesn't use explicit recursion. Imagine that you didn't have "var", and couldn't name anything (which is the situation in, say, the lambda calculus). Using the Y combinator you could still define recursive functions.

Like others have mentioned it's rather academic, but also pretty cool. It's a way of introducing recursive functions into the untyped lambda calculus. I think the easiest way to see it is using it in scheme to define an anonymous recursive function:

  (((lambda (fact)
      ((lambda (f)
         (fact (lambda (n) ((f f) n))))
       (lambda (f)
         (fact (lambda (n) ((f f) n))))))
    (lambda (fact)
      (lambda (n)
        (if (= n  0)
          1
          (* n (fact (- n 1)))))))
   10)

Computes 10!

You'll notice that lines 6-10 define a procedure that takes a factorial function, performs one level of the recursion, and then calls the factorial function to compute the rest. The Y combinator, implemented in lines 1-5, basically allows us to start the recursion. A step by step derivation can be found at http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html

The really neat thing about this is that all that was required to create that factorial function was lambda, some arithmetic functions, and if. Arithmetic can be implemented using only lambdas (google church numerals) and so can if. Using these techniques you can create a factorial function using only lambda and function application (which is exactly the lambda calculus).

If you replace "program" in the Forbes article with "function" I don't think they're terribly far off.

You can even get rid of the lambdas, with SKI calculus. (And the I in SKI calculus is also unnecessary.)

There have been explanations for the HN readers. Here's one that I'd put in a non-techy newspaper:

The Y Combinator is a way to make computer code self-referential without having to introduce names for parts of the code.

Or a bit less accurate:

The Y Combinator is a clever way to make computer code self-referential.

Non-techy readers would have no idea what "self-referential" means. Probably best to just leave it alone.

I'm a coder/writer at Forbes. If I had to guess, that's exactly what an editor might say. Also, we're always crammed for word space so shorter (even if perhaps less nuanced) always wins.

You do need names for some parts. I would modify that to:

"It's a program that lets other programs see themselves."

I wouldn't. I barely understand the concept myself. :-)

...but I know it's much more involved than "a program that runs other programs".

afaik it's pretty academic. The only practical application is to allow recursion in languages that don't do recursion which is pretty much none.

This is a good description if you're into that sort of thing: http://mvanier.livejournal.com/2897.html

The meat of it is that you can 'do' recursion by building up functions that call other functions :/ meh

Wow, hmm.. I worked a MEDITECH a long time ago, and they actually used a programming language, MAGIC, that you couldn't recurse in. It used macro code expansion to take MAGIC code and output into a lower level language and recursion would make it loop infinitely. Maybe at MEDITECH it wouldn't have been so academic.

Edit: Not sure why this got downvoted, but in their internal programming course they talked about the recursion problem explicitly--I'm not making this up, as crazy as it sounds.

If you don't believe me, here is a link to a blog post with someone else mentioning it in the comments:

http://htmlcoderhelper.com/what-is-the-worst-programming-lan...

Why is it an issue though? Recursion is an optional thing some programmers like using. It's not necessary.

edit: rather than downmod me to -1 for stating a fact, why not reply?

That's like saying integers are an optional thing, and it's no big deal if your programming language doesn't have them. True, they aren't necessary (look at peano arith or pure lambda calc) - but it sure makes things a lot easier. It's much more concise and intuitive to write some search or divide and conquer algos recursively than imperatively.

javascript doesn't have an integer type.

Possibly it makes things easier for some algorithms, but as I said, it is optional. It's not rocket science to rewrite any algorithm that relies on recursion to not need it.

The "meat" of it is really that (Y F) = (F (Y F)). In other words Y applied to a function F expands to F applied the original expression, so it builds up nested calls of F.

I can't do it justice, but it's definitely much more interesting and even beautiful than "meh". I guess there are always "practical" vs "academic" arguments to be made but I find stuff like the lambda calculus, Y, Church numerals, all really cool.

Yeah ok, it's sort of interesting as a curiosity. But it's going to be terribly inefficient if used, and doesn't really have any practical application.

I've always been more of a practical "why not just use a loop" kinda guy, so it's probably wasted on me.

Right, it's not really supposed to be used, but it's impressive and interesting in the same way that e^πi = -1 is.

I didn't really find that. It's just functions calling other functions. How exciting can that get :/

If you told me (before I knew about the Y combinator) that there was a function Y such that Y(F) = F(Y(F)) for every other function F, I doubt I would have believed you.

Loops are just a special case of recursion, and only necessary for languages that don't support recursion very well. As an example, Scheme and Haskell have no use for loops.

Loops are how most people think. They're also how most CPUs think.

It seems to me logical for both parties to express programs mostly using loops.

Except there is no difference at the machine instruction level between a recursive and iterative approaches. They are isomorphic to each other. That is why you can implement all recursive algorithms using an explicit stack and a loop and all iterative algorithms as recursive functions.

Huh?

There's a lot of difference in the unoptimized form of recursion - namely stack usage. Yes you can hack together tail call recursion to try and make recursion perform as well as iteration does, but what really is the point?

The concept of recursion in is independent of computers. Recursion is just the mathematicians idea of how to repeat get arbitrarily big objects out of limited definitions.

Loops are a just a special case, and not really closer to the hardware. Branches and jumps are closer to the hardware. "Yes you can hack together [a compiler] to try and make [structured programming] perform as well as [goto] does, but what really is the point?"

>> The only practical application is to allow recursion in languages that don't do recursion which is pretty much none.

Above is a very hard sentence to parse for non-native speakers, just saying ;)

I did not have too hard a time. But the sentence is not a model of clarity.

... such is my brain.

You can find an explanation on Wikipedia too: http://en.wikipedia.org/wiki/Fixed_point_combinator

Here is the actual cover:

http://imgur.com/gOyI9.jpg

A nice, striking (against the red), somewhat atypical picture of PG. Did the photographer coach to suppress the usual smile?

His eyes are smiling, I bet he's about to crack up.

his left eye makes me happy. i wonder why.

i think it's a right brain bicameral lateralization thing, but if someone more knowledgeable than me can get more explicit, i would absolutely love to hear

Why is this getting voted down? Look at the picture!

His expression seems to say, "Let's just get this over with." It's surprising how long a photo shoot can take.

What struck me in that photo is that he looks a bit older than he is. Which, for Forbes' audience, I suspect is deliberate.

He knew they were cropping out the Tevas

Birkenstocks, actually

Thanks for the actual cover shot, I got my copy in the mail this morning while running out the door to go write a midterm. I noticed PG on the cover and spent half the day wondering if anything new was in the article.

Slipping a link into the headline to (presumably) your startup, even if it is inside a "// not related" comment, is pretty tacky. You might even call it spam.

Update: Thanks for removing the link.

I think this is a repeat of http://news.ycombinator.com/item?id=1831471

And also http://news.ycombinator.com/item?id=1813445 (which is even older, and has quite a lot of comments)

I've got to imagine any photographer trying for a YC photo would look at the Inc cover which reprised The Last Supper and just despair.

And here was I expecting a typically insightful commentary by PG regarding the front page of a business journal.

It has unusually clean design. I've noticed that in other consumer goods lately. E.g. cereal boxes. I wonder if it's the result of a/b testing, or just a fashion.

It was an existing trend accelerated by the recession. An excess of stuff is no longer fashionable. Hopefully it lasts awhile (the fashion, not the recession).

Print version (with single page view): http://www.forbes.com/forbes/2010/1108/best-small-companies-...

♫ I wanna be on the cover of Forbes magazine, smiling next to Oprah and Paul Graham. ♫ Heh.

Congratulations, pg. If nothing else, being on the cover of Forbes must put a smile on your face.

Y-Combinator has something in common with the Moore Law: self-fulfilling prophecy.

http://en.wikipedia.org/wiki/Moore_Law

http://en.wikipedia.org/wiki/Self-fulfilling_prophecy

There weren't any prophecies behind YC. We just decided to make something to make more startups, and executed.

Same with the Moore Law.

Why?

i thought the virtual absence of women was interesting. Jessica Mah got two paragraphs near the end, Demi Moore a passing mention, and Jessica Livingston merited two sentences. she co-founded YC and is married to Paul, and they couldn't even ask her for a quote?

other than that it was guys, guys, guys. http://bit.ly/ycturgor2 has more.

That's because most founders are guys?

It's like the leaflet I got from our local hospital the other day. It features on the cover an african, an indian, a few other minorities, and one small white person. It's like they're trying way too hard to appear diverse. (The area it serves is probably 90%+ white).

I'd rather they project what is actually out there.

JL got more of a mention than Morris or Blackwell. I don't think the article writer chose to avoid or include women particularly, rather it just reflected the subject matter they were writing about.

Very true, Forbes often overlooks the women behind innovation. They tried to make up for it with the 100 most influential women issue last month, I would much rather see them include a few more articles each month on the subject.

That cover is awesome. Congrats pg!

And an earlier occasion:

http://news.ycombinator.com/item?id=1831471

This brought a smile to my face :)