News for hackers. Stuff that matters.
Re:PG on the cover of Forbes by meastham on Friday November 19, 2010 @05:41AM (#1921042)
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.

Re:PG on the cover of Forbes by eru on Friday November 19, 2010 @10:56AM (#1921714)
You can even get rid of the lambdas, with SKI calculus. (And the I in SKI calculus is also unnecessary.)