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'
