31
$\begingroup$

The Y combinator is a concept in functional programming, borrowed from the lambda calculus. It is a fixed-point combinator. A fixed point combinator $G$ is a higher-order function (a functional, in mathematical language) that, given a function $f$, returns a fixed point of $f$. In mathematical language,

$f(G(f)) = G(f)$

This can be considered the defining equation of a fixed-point combinator.

Note that $f$ might be a function whose range and domain are themselves function spaces -- in fact this is the most common use of a fixed-point combinator: you can define a function $\alpha$ by specifying that it is the fixed point of another function $f$, and then compute $\alpha$ as $G(f)$.

As mathematicians we're used to functions having names, eg $f:x\mapsto x^2$ is the function called $f$ that maps $x$ to $x^2$. But there's no reason why you can't have anonymous function. Since the lambda calculus deals with these a lot, there's a special notation for them:

$\lambda x.x^2$

is the function that takes $x$ to $x^2$, so that e.g. $(\lambda x.x^2)(2) = 4$. When there's no ambiguity, we can write function application by concatenation: $(\lambda x.x^2) 2 = 4$, and if we defined $f = \lambda x.x^2$ then $f\; 2 = 4$.

Okay, now we get to the meat of the question. The Y combinator is a higher-order function (functional) defined as

$Y = \lambda f. (\lambda x. f (x\;x)) \; (\lambda x. f (x\;x))$

I can follow through the algebra and see that this is indeed a fixed-point combinator:

$\begin{align} Y\; g & = (\lambda f. (\lambda x. f (x\;x)) \; (\lambda x. f (x\;x))) \; g \\ & = (\lambda x. g (x\;x)) \; (\lambda x. g (x\;x)) \\ & = (\lambda y. g (y\;y)) \; (\lambda x. g (x\;x)) \\ & = g \; (\lambda x. g (x\;x)) (\lambda x. g (x\;x)) \\ & = g\; (Y\; g) \end{align}$

but I have no intuition as to why it works, or how someone might have come up with it. More to the point, I don't see how it can be practically used to compute functions as fixed-points of functionals.

Anyone got a good 'intuitive' explanation?

  • 3
    The Y combinator is informally quite similar to the proof of Kleene's recursion theorem and to the proof of the fixed-point theorem in formal arithmetic. Here is a question where people tried to explain the version in arithmetic: http://mathoverflow.net/questions/30874/arithmetic-fixed-point-theorem/30878#308782011-07-13

3 Answers 3

23

The $Y$ combinator is a function that takes a function $f$ and returns something applied to itself (specifically $\lambda x.f(xx)$). So if we want to make $Y(f)$ a fixed point of $f$, $Y(f)$ has to be equal to $f(Y(f))$. So we want some $a$ such that $aa = f(aa)$. Now, $a$ has access to itself (it is applied to itself). Because of this, we can directly create such an $a$. $aa=f(aa)$ $a=\lambda a.f(aa)$ $a=\lambda x.f(xx)$ $Y=\lambda f.aa=\lambda f.(\lambda x.f(xx))(\lambda x.f(xx))$ Essentially, by applying $a$ to itself, you are giving $a$ a reference to itself, allowing it to use itself in a recursive manner. However, $a$ is only an intermediate value - it is not the recursive function itself, as it still needs a reference to itself to do the recursion. The $Y$ combinator completely eliminates this need by finding the fixed point - giving a function its final, recursive form.

6

The $Y$ combinator can be defined also Turing way. Let us use less formal but more descriptive variable names to define the combinator: $ \begin{align} A &= \lambda \text{self}.\lambda f.f\ (\text{self}\ \text{self}\ f);\\ Y &= A\ A. \end{align} $

The $A$ combinator can be considered as a function that takes itself as its first argument and the target function, fixed point of which is to be found, as the second one. It returns the function applied to $A\ A\ f$, just like we wanted.

Then, an arbitrary combinator F which is defined in the terms of itself like $ F\ x\ y = F\ y\ x\ F $ can be defined in terms of $Y$ and some other combinator $F_r$. Specifically, $ F\ x\ y = F\ y\ x\ F $ is equivalent to $ F = \lambda x.\lambda y.F\ y\ x\ F, $ which in turn follows from $ F = (\lambda \text{self}.\lambda x.\lambda y.\text{self}\ y\ x\ \text{self}) F. $ Finally, let us call the resulting subexpression $ F_r = \lambda \text{self}.\lambda x.\lambda y.\text{self}\ y\ x\ \text{self}. $ Then $F = Y\ F_r$.