There is this blog post by Caltech computer scientist, Mike Vanier. The code in Mike's article uses the Scheme programming language. This one uses Python.

A $Y$ combinator is a higher-order function which, given argument $f$ (say,) satisfies the equation $Y f = f\;(Y f)$. They are said to compute a "fixed point" $f^{'}$ of their argument $f$ since $f^{'} = Y\;f = f\;(Y\;f) = f \;f^{'}$.

A $Y$ combinator takes a function that isn't recursive and returns a version of the function that is. That is, $Y$ is a function that takes $f$ and returns $f (f (f (\cdots)))$.

The existence of $Y$ combinators is amazing in that it tells us that it is possible to write recursive functions even in a programming language that says nothing about recursion!

The goal here is to derive a $Y$.

Start with the classic recursive definition of the factorial function.

def fact (n) : if n == 0 : return 1 else: return n * fact (n - 1)

We are trying to eliminate explicit recursion. To that end, factor out the recursive call and make it an application of a function argument.

def part_fact (this, n): if n == 0 : return 1 else: return n * this (this, (n - 1)) fact = functools.partial(part_fact, part_fact)That's sufficient to get rid of the explicit recursion but we mean to push on in search of a "library" solution to this problem, that is, some general result that can be re-used.

Next let's get this down to a function in one argument as is this way in the $\lambda$ calculus.

def part_fact (this): return lambda n : 1 if n == 0 else n * (this (this)) (n - 1) fact = part_fact (part_fact)

We'd recover something tantalizingly close to the original factorial function if we factored out `this (this)`

into a function of one argument.

def part_fact (this): f = this (this) return lambda n : 1 if n == 0 else n * f (n - 1) fact = part_fact(part_fact)

This would be fine in a lazy language but Python is a strict language and exhibits infinite recursion because to evaluate `part_fact (part_fact)`

requires evaluating `f = part_fact (part_fact)`

and so on. The solution is to delay the evaluation until it's needed.

def part_fact (this): f = lambda y : (this (this)) y return lambda n : 1 if n == 0 else n * f (n - 1) fact = part_fact(part_fact)

Refactor this into two parts.

def almost_fact (f): return lambda n : 1 if n == 0 else f (n - 1) def part_fact (this): f = lambda y : (this (this))(y) return almost_fact (f) fact = part_fact(part_fact)

Rephrase `part_frac`

as a lambda and change the argument name to `x`

.

def almost_fact (f): return lambda n : 1 if n == 0 else f (n - 1) part_fract = lambda x : almost_fact (lambda y : (x (x))(y)) fact = part_fact (part_fact)

Eliminate 'part_fact'.

def almost_fact (f): return lambda n : 1 if n == 0 else f (n - 1) fact = (lambda x : almost_fact (lambda y : (x (x))(y))) \ (lambda x : almost_fact (lambda y : (x (x))(y)))

That's it! There's the $Y$ combinator. Generalize.

def Y (f): return (lambda x : f (lambda y : (x (x))(y))) \ (lambda x : f (lambda y : (x (x))(y))) def almost_fact (f): return lambda n : 1 if n == 0 else f (n - 1) fact = Y (almost_fact)That is, $Y = \lambda f.(\lambda x. f\;(\lambda y. (x\;x)\;y))\;(\lambda x. f\;(\lambda y. (x\;x)\;y))$. This $Y$ combinator is known s Curry's paradoxical combinator (in its "applicative order" form to account for the fact that Python is strict).

Try this on another function. Fibonacci numbers say.

def almost_fib (f) : return lambda n : 1 if n <= 2 else f (n - 1) + f (n - 2) fib = Y (almost_fib) print (str (fib (6))+"\n") #Prints '8'