7 ms·

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

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

j_baker 16y ago
I wouldn't. I barely understand the concept myself. :-) ...but I know it's much more involved than "a program that runs other programs".
- axod 16y ago
  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 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
  - simplegeek 16y ago
    >> 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 ;)
    - eru 16y ago
      I did not have too hard a time. But the sentence is not a model of clarity.
      - axod 16y ago
        ... such is my brain.
  - ericb 16y ago
    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-language-you-ever-worked-with/ http://htmlcoderhelper.com/what-is-the-worst-programming-lan...
    - axod 16y ago
      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?
      - smanek 16y ago
        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.
        axod 16y ago
        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.
  - spacemanaki 16y ago
    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.
    - axod 16y ago
      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.
      - abstractbill 16y ago
        Right, it's not really supposed to be used, but it's impressive and interesting in the same way that e^πi = -1 is.
        axod 16y ago
        I didn't really find that. It's just functions calling other functions. How exciting can that get :/
        abstractbill 16y ago
        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.
      - eru 16y ago
        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.
eliben 16y ago
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.
- tlrobinson 16y ago
  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));
  - tlrobinson 16y ago
    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; }
    - ostso 16y ago
      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.
meastham 16y ago
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 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.
- eru 16y ago
  You can even get rid of the lambdas, with SKI calculus. (And the I in SKI calculus is also unnecessary.)
perlgeek 16y ago
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.
- roadnottaken 16y ago
  Non-techy readers would have no idea what "self-referential" means. Probably best to just leave it alone.
  - taylorbuley 16y ago
    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.
- sesqu 16y ago
  You do need names for some parts. I would modify that to: "It's a program that lets other programs see themselves."
DeusExMachina 16y ago
You can find an explanation on Wikipedia too: http://en.wikipedia.org/wiki/Fixed_point_combinator http://en.wikipedia.org/wiki/Fixed_point_combinator
meese_ 16y ago
http://lambdawesome.com http://lambdawesome.com

j_baker 16y ago

I wouldn't. I barely understand the concept myself. :-) ...but I know it's much more involved than "a program that runs other programs".

axod 16y ago
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 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
- simplegeek 16y ago
  >> 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 ;)
  - eru 16y ago
    I did not have too hard a time. But the sentence is not a model of clarity.
    - axod 16y ago
      ... such is my brain.
- ericb 16y ago
  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-language-you-ever-worked-with/ http://htmlcoderhelper.com/what-is-the-worst-programming-lan...
  - axod 16y ago
    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?
    - smanek 16y ago
      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.
      - axod 16y ago
        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.
- spacemanaki 16y ago
  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.
  - axod 16y ago
    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.
    - abstractbill 16y ago
      Right, it's not really supposed to be used, but it's impressive and interesting in the same way that e^πi = -1 is.
      - axod 16y ago
        I didn't really find that. It's just functions calling other functions. How exciting can that get :/
        abstractbill 16y ago
        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.
    - eru 16y ago
      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.

eliben 16y ago

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.

tlrobinson 16y ago
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));
- tlrobinson 16y ago
  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; }
  - ostso 16y ago
    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.

meastham 16y ago

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

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

perlgeek 16y ago

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.

roadnottaken 16y ago
Non-techy readers would have no idea what "self-referential" means. Probably best to just leave it alone.
- taylorbuley 16y ago
  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.
sesqu 16y ago
You do need names for some parts. I would modify that to: "It's a program that lets other programs see themselves."

DeusExMachina 16y ago

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

meese_ 16y ago

http://lambdawesome.com http://lambdawesome.com