Y combinator

$\lambda f.(\lambda x.f(x~x))~(\lambda x.f(x~x))$

• The y combinator is a way to implement recursion in lambda calculus
• Most basic recursion representation:
loop = loop

• Consider representing “loop” in lambda calculus (the “omega combinator”):

$(\lambda x.x~x)~(\lambda x.x~x)$

• the function $\lambda x.x~x$ takes an input $x$ and returns $x$ as output
• we apply this function to itself
• this concept of “self application” is the key to recursion

simple example:

$(\lambda x.x~x)~(\lambda x.x~x)$

• expanded:

$\rarr ~~(\lambda (\lambda x.x~x).(\lambda x.x~x)~(\lambda x.x~x))~(\lambda x.x~x)$

• result:

$\rarr ~~(\lambda x.x~x)~(λx.x~x)$

general example:

$rec~f = f(rec~f)\\ = f(f(f( ...$

a definition of “rec” in lambda calculus (y combinator):

$\lambda f.(\lambda x.f(x~x))~(\lambda x.f(x~x))$

• note that the y combinator includes the same sort of “self application” or “omega combinator” included in “loop”, though the y combinator is not itself recursive because it relies on the $f$ input, which is the function that should be recursed
• as the “omega combinator” is applied to itself, expanded, and evaluated, it naturally calls the $f$ function input each time it’s evaluated, allowing for recursion