Photo by Ludde Lorentz on Unsplash

Why You Must Actually Understand The Ω and Y Combinators

They are the most basic keys to recursion in λ-Calculus, yet are so difficult to visualize

An Alternative Notation

The problem with learning concepts from lambda calculus is that you have to deal with lambda calculus

To mitigate this language’s effect on the eyes, I will be using a notation that I came up with a while back. I hope it helps…

We can translate the formal λ notation:

S := λx.λy.λz.x z (y z)

Into a more familiar syntax:

S = x -> y -> z -> x(z, y(z))

But, we don’t need to explicitly curry our functions either.
Why not use a product type?

x * y * z -> x(z, y(z))

Or even the most common syntax for function arguments, a list?

(x, y, z) -> x(z, y(z))

Remember, it’s still curried.

Sometimes, it makes more sense to apply functions left to right.

Instead of f(x) (read “f of x”)
We can use x > f (read “x into f”)

This is very beneficial for readability with highly nested compositions.

h(g(y, f(x, z)))

Can be expressed as a natural flow of data:

z > f(x) > g(y) > h

Infinite Loop with Unnamed Functions

The big idea behind The Ω Combinator is that it expresses recursion without referencing itself

Typically when you want an infinite loop, you define a function that calls itself. But in lambda calculus and some programming languages, this is impossible. The Omega Combinator is just the simplest function which infinitely recurs without calling itself.

Here’s the formal definition:

(λx.x x) (λx.x x)

That does a terrible job explaining what is going on. To start off, we need to understand a strange function that I’ll call itself.

itself = x -> x > x

itself takes a function as an argument, and returns that function applied to itself. In most contexts this is quite useless. In javascript for example, if you called itself(console.log), the result would be console.log(console.log).

But, this is already enough to implement an infinite loop. Try this:

itself > itself

Pretty meta, huh? Let’s evaluate it…

  itself > itself
≡ itself > (x -> x > x)
≡ itself > (______ > ______)
≡          (itself > itself)
≡ itself > itself

… and we went around full circle. Evaluation has yielded itself — an ouroboros loop.

Don’t forget that even though we shortcut with itself > itself, we only used an anonymous function. If we expand the nickname…

  itself > itself
≡ (x -> x > x) > (x -> x > x)
≡ (λx.x x) (λx.x x)

…aha! Lambda Calculus is a lot easier with nicknames.

Hijacking Ω With Our Own Function

Although The Ω Combinator is quite useless, we can exploit its looping property with our own function, so that said function will loop

If we inject a function f into Ω, we get The Y Combinator.

Ω =       itself >      itself
Y = f -> (itself > f) > itself

Now that looks really funny, let’s see what it’s made of:

  (itself > f) > itself
≡ (itself > f) > (x -> x > x)
≡ (itself > f) > (____________ > ____________)
                  (itself > f) > (itself > f)
≡ (itself > f) > itself > f

See that! When we evaluate The Y Combinator, we get The Y Combinator back, but with an extra > f at the end.

Then we just evaluate again — and get another extra > f. This means that:

  f > Y
≡ f > Y > f
≡ f > Y > f > f
≡ f > Y > f > f > f
≡ f > Y > f > f > f > f
≡ f > Y > f > f > f > f > f
≡ f > Y > f > f > f > f > f > f ...
Or more traditionally:
  Y(f)
≡ f(Y(f))
≡ f(f(Y(f)))
≡ f(f(f(Y(f))))
≡ f(f(f(f(Y(f)))))
≡ f(f(f(f(f(Y(f))))))
≡ f(f(f(f(f(f...(Y(f)))))))

Just in case you wanted to see the formal definition from here:

  f -> (itself > f) > itself
≡ f -> (x -> x > x > f) > (x -> x > x > f)
≡ λf.(λx.f (x x)) (λx.f (x x))

That’s Cool and All, But How Can I Use It?

Note: This section borrows heavily from this very helpful website:

http://matt.might.net/articles/implementation-of-recursive-fixed-point-y-combinator-in-javascript-for-memoization/

Well, we can sort of hijack the default method of recursion in other languages. Let’s say that we have a very easily optimizable function in javascript. The issue is that we need to memoize it, and the javascript runtime we use doesn’t do that for us.

For example, this Fibonacci function needlessly recalculates values, leading to exponentially long computation times:

fib = n => {
 if (n == 0) return 0
 if (n == 1) return 1
 return fib(n-1) + fib(n-2)
}

We can implement this using The Y Combinator (adjusted for javascript’s eager evaluation):

itself = x => x(x)
// Won't work due to javascript's eager evaluation. This will run infinitely before even assigning to Y
Y = f => itself(f(itself))
// Force lazy evaluation in the form of "x" to "() => x"
Y = f => itself(x => f(y => itself(x) (y)))
// Yet another way to represent Y, this is possible only because javascript allows self-reference
Y = f => arg => f(y => Y(f) (y)) (arg)
fib = Y(f =>
n => {
 if (n == 0) return 0
 if (n == 1) return 1
 return f(n-1) + f(n-2)
})

Now, there are zero benefits to the above transformation in javascript. That is, until we change the implementation of Y to memoize in the backend:

// The implementation from above
Y = f => arg => f(y => Y(f) (y)) (arg)
// An invisibly memoizing implementation. If you squint, they have the same shape
Y = (f, cache = {}) => arg =>
  cache[arg]
   ? cache[arg]
   : cache[arg] = f(y => Y(f, cache) (y)) (arg)

Now with our magical memoizing Y combinator, we can calculate instantly

Y = (f, cache = {}) => arg =>
  cache[arg]
   ? cache[arg]
   : cache[arg] = f(y => Y(f, cache) (y)) (arg)
// We will use BigInt for this, as the standard javascript Number type is imprecise
fib = Y(f =>
n => {
 if (n == 0n) return 0n
 if (n == 1n) return 1n
 return f(n-1n) + f(n-2n)
})
fib(1001n)
// returns 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501n

Check it out! We got it exactly right, instantly. Here’s proof:

The first 1001 Fibonacci Numbers - Full Text Free Book

Hope you learned something new. Comment something I should explain next, I’d be glad to put up more content! Also, don’t forget that I got this idea from http://matt.might.net/.