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