Skip to content

Lambda Calculus for people a step behind me (3): Little Omega, Omega Combinator, Y-Combinator

Disclaimer: I’m not a computer scientist or mathematician. This post is about what I’ve learnt so far about Lambda Calculus. Most of the resources I’ve come across seem to assume either prior knowledge of advanced maths notation or extensive practical experience of lambda functions in software engineering. I’ve tried to avoid this and explain things step by step, but have no doubt made assumptions and mistakes of my own. Corrections (or questions) are welcome. I’ll include a list of the resources I’ve used to piece this together in a later post.

[For those who came in late… part 1 is here, part 2 here]

Revision – Identity

In part 1 we covered the identity function:

λx.x

And we discovered that if we apply it to itself, we get itself:

(λx.x) (λx.x) -> λx.x

Little Omega

Little Omega ( ω ) is simply a function that makes two copies of whatever is fed into it.

It looks like this:

ω=λx.x x

Note: I found this notation quite confusing at first (is it 2x? x2 ?). But in Lambda Calculus notation it simply means “x applied to x.

For example, here it is applied to the function t (which could stand for any function):

ω t=(λx.x x) t
ω t = t t

Applied to (y + 5):

(λx.x x)(λy. y + 5) 3
= (λy. y + 5)(λy. y + 5) 3
= ((λy. y + 5) + 5) 3
= (3 + 5 + 5)
= 13
(I think – I may have the notation a bit off here but the general ideas is right)

(Big) Ωmega Combinator

The Omega combinator is almost the same, but we apply little omega to itself to produce two copies of little omega, which will go on to make two copies of themselves:

Ω = (λx. x x) (λx. x x)

If we evaluate the function we get:

(λx. x x) (λx. x x) -> (λx. x x) (λx. x x)

And evaluating the output gets us the same thing:

(λx. x x) (λx. x x) -> (λx. x x) (λx. x x)

So we can evaluate the function endlessly and always end up with the same thing. Hence omega, the last letter of the Greek alphabet: this is a function that will go on to the end.

The Y Combinator

With those foundations, the Y combinator is a fairly simple tweak. It’s what we get when we try to do something useful with the omega combinator.

We can use the omega combinator to create a recursive function (more on recursion in a future post) – that is, a function that calls itself inside itself. It looks like this:

YF = (λy.(λx. y (x x)) (λx. y (x x))) F
Where F is a function – many places don’t include the F at the end, and would write it as λf.(λx. f (x x)) (λx. f (x x)) but I found that a bit confusing on first parse).

This reduces to:

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

Which reduces to:

F ( (λx. F (x x)) (λx. F (x x)))
That is, it applies function F to the original pair of functions

Which will reduce to:

F ( F ( (λx. F (xx)) (λx. F (x x))))
So now we have a second F applied again to the original pair of functions.

And that’s it. Forever. This is written as:

YF

And it evaluates as:

F(YF)
F(F(YF))
F(F(F(YF)))
etc

Left to its own devices, this behaviour will continue forever, just like Ω. But by combining Y with an if operator as in a computer program (or if you’re really smart and patient, in Lambda Calculus) you can write a recursive function that does useful work.

This is the reason that the startup incubator Y Combinator chose this name: they are a company that makes other companies. Of course, to be truly faithful to their name they’d be a company that made other companies that in turn made other companies… but maybe that’s what we’re starting to see in the world of startups.

For further reading, you can look into fixed-point mathematics, which is a bit beyond me.

Simplest example of the Y Combinator-type recursion in action

We use recursion for a function that can be (or has to be) defined in terms of itself.

As an example, take Σ (sigma), which adds up all the terms in a given range. For our purposes, let’s keep it simple and use integers between one and another number:

Σ(1 – 5) = 5 + 4 + 3 + 2 + 1 = 15.

One way to think of this is that sigma of any given number X is that number (X) plus the sigma of the number beneath it (X -1)… which is the new number (X – 1), plus the sigma of the number beneath ((X-1) – 1)):

Σ(x) = X + Σ(x-1)
We just need to add the condition that if X is 1, the answer returned should be X:

Σ(1 – 5) = 5 + ( 4 + ( 3 + (2 + (1)))) = 15

I don’t quite understand how to put this into Lambda Calculus notation (yet!?) but I hope you see that the pattern’s the same, with all those brackets opening up down the chain – only here they all ping shut once the if conditional is met when X reaches 1.

And there you have it.

Tune in next time for the Lambda Calculus Reading/Play- list.

https://www.diderot.one/courses/22/books/78/chapter/817

https://www.diderot.one/courses/22/books/78/chapter/817

I'd love to hear your thoughts and recommended resources...

%d bloggers like this: