Hacker News Reader

Comment by j_baker | Hacker News Reader

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

View on HN

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

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

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

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

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

http://lambdawesome.com

Reply on news.ycombinator.com