What is a Y-combinator?

A Y-combinator is a "functional" (a function that operates on other functions) that enables recursion, when you can't refer to the function from within itself. In computer-science theory, it generalizes recursion, abstracting its implementation, and thereby separating it from the actual work of the function in question. The benefit of not needing a compile-time name for the recursive function is sort of a bonus. =)

This is applicable in languages that support lambda functions. The expression-based nature of lambdas usually means that they cannot refer to themselves by name. And working around this by way of declaring the variable, refering to it, then assigning the lambda to it, to complete the self-reference loop, is brittle. The lambda variable can be copied, and the original variable re-assigned, which breaks the self-reference.

Y-combinators are cumbersome to implement, and often to use, in static-typed languages (which procedural languages often are), because usually typing restrictions require the number of arguments for the function in question to be known at compile time. This means that a y-combinator must be written for any argument count that one needs to use.

Below is an example of how the usage and working of a Y-Combinator, in C#.

Using a Y-combinator involves an "unusual" way of constructing a recursive function. First you must write your function as a piece of code that calls a pre-existing function, rather than itself:

// Factorial, if func does the same thing as this bit of code...
x == 0 ? 1: x * func(x - 1);

Then you turn that into a function that takes a function to call, and returns a function that does so. This is called a functional, because it takes one function, and performs an operation with it that results in another function.

// A function that creates a factorial, but only if you pass in
// a function that does what the inner function is doing.
Func<Func<Double, Double>, Func<Double, Double>> fact =
  (recurs) =>
    (x) =>
      x == 0 ? 1 : x * recurs(x - 1);

Now you have a function that takes a function, and returns another function that sort of looks like a factorial, but instead of calling itself, it calls the argument passed into the outer function. How do you make this the factorial? Pass the inner function to itself. The Y-Combinator does that, by being a function with a permanent name, which can introduce the recursion.

// One-argument Y-Combinator.
public static Func<T, TResult> Y<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> F)
{
  return
    t =>  // A function that...
      F(  // Calls the factorial creator, passing in...
        Y(F)  // The result of this same Y-combinator function call...
              // (Here is where the recursion is introduced.)
        )
      (t); // And passes the argument into the work function.
}

Rather than the factorial calling itself, what happens is that the factorial calls the factorial generator (returned by the recursive call to Y-Combinator). And depending on the current value of t the function returned from the generator will either call the generator again, with t - 1, or just return 1, terminating the recursion.

It's complicated and cryptic, but it all shakes out at run-time, and the key to its working is "deferred execution", and the breaking up of the recursion to span two functions. The inner F is passed as an argument, to be called in the next iteration, only if necessary.

If you're ready for a long read, Mike Vanier has a great explanation. Long story short, it allows you to implement recursion in a language that doesn't necessarily support it natively.

y-combinator in JavaScript:

var Y = function(f) {
  return (function(g) {
    return g(g);
  })(function(h) {
    return function() {
      return f(h(h)).apply(null, arguments);
    };
  });
};

var factorial = Y(function(recurse) {
  return function(x) {
    return x == 0 ? 1 : x * recurse(x-1);
  };
});

factorial(5)  // -> 120

Edit: I learn a lot from looking at code, but this one is a bit tough to swallow without some background - sorry about that. With some general knowledge presented by other answers, you can begin to pick apart what is happening.

The Y function is the "y-combinator". Now take a look at the var factorial line where Y is used. Notice you pass a function to it that has a parameter (in this example, recurse) that is also used later on in the inner function. The parameter name basically becomes the name of the inner function allowing it to perform a recursive call (since it uses recurse() in it's definition.) The y-combinator performs the magic of associating the otherwise anonymous inner function with the parameter name of the function passed to Y.

For the full explanation of how Y does the magic, checked out the linked article (not by me btw.)

Anonymous recursion

A fixed-point combinator is a higher-order function fix that by definition satisfies the equivalence

forall f.  fix f  =  f (fix f)

fix f represents a solution x to the fixed-point equation

               x  =  f x

The factorial of a natural number can be proved by

fact 0 = 1
fact n = n * fact (n - 1)

Using fix, arbitrary constructive proofs over general/μ-recursive functions can be derived without nonymous self-referentiality.

fact n = (fix fact') n

where

fact' rec n = if n == 0
                then 1
                else n * rec (n - 1)

such that

   fact 3
=  (fix fact') 3
=  fact' (fix fact') 3
=  if 3 == 0 then 1 else 3 * (fix fact') (3 - 1)
=  3 * (fix fact') 2
=  3 * fact' (fix fact') 2
=  3 * if 2 == 0 then 1 else 2 * (fix fact') (2 - 1)
=  3 * 2 * (fix fact') 1
=  3 * 2 * fact' (fix fact') 1
=  3 * 2 * if 1 == 0 then 1 else 1 * (fix fact') (1 - 1)
=  3 * 2 * 1 * (fix fact') 0
=  3 * 2 * 1 * fact' (fix fact') 0
=  3 * 2 * 1 * if 0 == 0 then 1 else 0 * (fix fact') (0 - 1)
=  3 * 2 * 1 * 1
=  6

This formal proof that

fact 3  =  6

methodically uses the fixed-point combinator equivalence for rewrites

fix fact'  ->  fact' (fix fact')

Lambda calculus

The untyped lambda calculus formalism consists in a context-free grammar

E ::= v        Variable
   |  λ v. E   Abstraction
   |  E E      Application

where v ranges over variables, together with the beta and eta reduction rules

(λ x. B) E  ->  B[x := E]                                 Beta
  λ x. E x  ->  E          if x doesn’t occur free in E   Eta

Beta reduction substitutes all free occurrences of the variable x in the abstraction (“function”) body B by the expression (“argument”) E. Eta reduction eliminates redundant abstraction. It is sometimes omitted from the formalism. An irreducible expression, to which no reduction rule applies, is in normal or canonical form.

λ x y. E

is shorthand for

λ x. λ y. E

(abstraction multiarity),

E F G

is shorthand for

(E F) G

(application left-associativity),

λ x. x

and

λ y. y

are alpha-equivalent.

Abstraction and application are the two only “language primitives” of the lambda calculus, but they allow encoding of arbitrarily complex data and operations.

The Church numerals are an encoding of the natural numbers similar to the Peano-axiomatic naturals.

   0  =  λ f x. x                 No application
   1  =  λ f x. f x               One application
   2  =  λ f x. f (f x)           Twofold
   3  =  λ f x. f (f (f x))       Threefold
    . . .

SUCC  =  λ n f x. f (n f x)       Successor
 ADD  =  λ n m f x. n f (m f x)   Addition
MULT  =  λ n m f x. n (m f) x     Multiplication
    . . .

A formal proof that

1 + 2  =  3

using the rewrite rule of beta reduction:

   ADD                      1            2
=  (λ n m f x. n f (m f x)) (λ g y. g y) (λ h z. h (h z))
=  (λ m f x. (λ g y. g y) f (m f x)) (λ h z. h (h z))
=  (λ m f x. (λ y. f y) (m f x)) (λ h z. h (h z))
=  (λ m f x. f (m f x)) (λ h z. h (h z))
=  λ f x. f ((λ h z. h (h z)) f x)
=  λ f x. f ((λ z. f (f z)) x)
=  λ f x. f (f (f x))                                       Normal form
=  3

Combinators

In lambda calculus, combinators are abstractions that contain no free variables. Most simply: I, the identity combinator

λ x. x

isomorphic to the identity function

id x = x

Such combinators are the primitive operators of combinator calculi like the SKI system.

S  =  λ x y z. x z (y z)
K  =  λ x y. x
I  =  λ x. x

Beta reduction is not strongly normalizing; not all reducible expressions, “redexes”, converge to normal form under beta reduction. A simple example is divergent application of the omega ω combinator

λ x. x x

to itself:

   (λ x. x x) (λ y. y y)
=  (λ y. y y) (λ y. y y)
. . .
=  _|_                     Bottom

Reduction of leftmost subexpressions (“heads”) is prioritized. Applicative order normalizes arguments before substitution, normal order does not. The two strategies are analogous to eager evaluation, e.g. C, and lazy evaluation, e.g. Haskell.

   K          (I a)        (ω ω)
=  (λ k l. k) ((λ i. i) a) ((λ x. x x) (λ y. y y))

diverges under eager applicative-order beta reduction

=  (λ k l. k) a ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ y. y y) (λ y. y y))
. . .
=  _|_

since in strict semantics

forall f.  f _|_  =  _|_

but converges under lazy normal-order beta reduction

=  (λ l. ((λ i. i) a)) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  a

If an expression has a normal form, normal-order beta reduction will find it.

Y

The essential property of the Y fixed-point combinator

λ f. (λ x. f (x x)) (λ x. f (x x))

is given by

   Y g
=  (λ f. (λ x. f (x x)) (λ x. f (x x))) g
=  (λ x. g (x x)) (λ x. g (x x))           =  Y g
=  g ((λ x. g (x x)) (λ x. g (x x)))       =  g (Y g)
=  g (g ((λ x. g (x x)) (λ x. g (x x))))   =  g (g (Y g))
. . .                                      . . .

The equivalence

Y g  =  g (Y g)

is isomorphic to

fix f  =  f (fix f)

The untyped lambda calculus can encode arbitrary constructive proofs over general/μ-recursive functions.

 FACT  =  λ n. Y FACT' n
FACT'  =  λ rec n. if n == 0 then 1 else n * rec (n - 1)

   FACT 3
=  (λ n. Y FACT' n) 3
=  Y FACT' 3
=  FACT' (Y FACT') 3
=  if 3 == 0 then 1 else 3 * (Y FACT') (3 - 1)
=  3 * (Y FACT') (3 - 1)
=  3 * FACT' (Y FACT') 2
=  3 * if 2 == 0 then 1 else 2 * (Y FACT') (2 - 1)
=  3 * 2 * (Y FACT') 1
=  3 * 2 * FACT' (Y FACT') 1
=  3 * 2 * if 1 == 0 then 1 else 1 * (Y FACT') (1 - 1)
=  3 * 2 * 1 * (Y FACT') 0
=  3 * 2 * 1 * FACT' (Y FACT') 0
=  3 * 2 * 1 * if 0 == 0 then 1 else 0 * (Y FACT') (0 - 1)
=  3 * 2 * 1 * 1
=  6

(Multiplication delayed, confluence)

For Churchian untyped lambda calculus, there has been shown to exist a recursively enumerable infinity of fixed-point combinators besides Y.

 X  =  λ f. (λ x. x x) (λ x. f (x x))
Y'  =  (λ x y. x y x) (λ y x. y (x y x))
 Z  =  λ f. (λ x. f (λ v. x x v)) (λ x. f (λ v. x x v))
 Θ  =  (λ x y. y (x x y)) (λ x y. y (x x y))
  . . .

Normal-order beta reduction makes the unextended untyped lambda calculus a Turing-complete rewrite system.

In Haskell, the fixed-point combinator can be elegantly implemented

fix :: forall t. (t -> t) -> t
fix f = f (fix f)

Haskell’s laziness normalizes to a finity before all subexpressions have been evaluated.

primes :: Integral t => [t]
primes = sieve [2 ..]
   where
      sieve = fix (\ rec (p : ns) ->
                     p : rec [n | n <- ns
                                , n `rem` p /= 0])

• David Turner: Church's Thesis and Functional Programming
• Alonzo Church: An Unsolvable Problem of Elementary Number Theory
• Lambda calculus
• Church–Rosser theorem

Here is a JavaScript implementation of the Y-Combinator and the Factorial function (from Douglas Crockford's article, available at: http://javascript.crockford.com/little.html).

function Y(le) {
    return (function (f) {
        return f(f);
    }(function (f) {
        return le(function (x) {
            return f(f)(x);
        });
    }));
}

var factorial = Y(function (fac) {
    return function (n) {
        return n <= 2 ? n : n * fac(n - 1);
    };
});

var number120 = factorial(5);

I have written a sort of "idiots guide" to the Y-Combinator in both Clojure and Scheme in order to help myself come to grips with it. They are influenced by material in "The Little Schemer"

In Scheme: https://gist.github.com/z5h/238891

or Clojure: https://gist.github.com/z5h/5102747

Both tutorials are code interspersed with comments and should be cut & pastable into your favourite editor.

A fixed point combinator (or fixed-point operator) is a higher-order function that computes a fixed point of other functions. This operation is relevant in programming language theory because it allows the implementation of recursion in the form of a rewrite rule, without explicit support from the language's runtime engine. (src Wikipedia)