Advanced 5
Hello! This is page 17 of the course called “Y Combinator for Non-programmers”. If you just got here, click here to read from the beginning.

Y Combinator for
Non-programmers

Epilogue: Computer Science, Lambda Calculus, and Y Combinator

Slide 1 / 7

This is the final page!

This is the final page!

Looking for some other page?

Advanced 5·
Slide 2 / 7

Who invented lunchboxes?

In the last page, a villager from Lambda Village asked the following question:

Are there any calculations that lunchboxes cannot do?

To answer this question, we need to ask another question: Who invented lunchboxes?

Who invented lunchboxes?

Answer: Lunchboxes were invented in the 1930s by a mathematician Alonzo Church.

Lunchboxes were invented in the 1930s
by a mathematician Alonzo Church

However: Alonzo Church did not call it a “lunchbox” when he invented it. Instead, he called it “Lambda calculus”.

It was called “Lambda calculus”
instead of a “lunchbox”

Let’s now talk about lambda calculus.

Slide 3 / 7

Lambda calculus and lunchboxes

Lambda calculus, invented by Alonzo Church, works exactly like a lunchbox—although they look different.

Lambda calculus works exactly like
a lunchbox

Here is an example of lambda calculus. The leftmost letter, λ, is a Greek letter “lambda”. That’s why it’s called “lambda calculus.

λA.B C

The above lambda calculus expression is exactly the same as the following lunchbox:

λA.B C
The above lambda calculus expression is
exactly the same as this lunchbox:
1
1

If you run the above lunchbox, it will become . Press Run :

1
1

Similarly: If you “run” the earlier lambda calculus expression, the result will also be B.

λA.B C
B

Of course, there are more complicated lambda calculus expressions. Take a look at this one:

λA.(λB.A(B B))(λB.A(B B))

The above lambda calculus expression is exactly the same as this lunchbox:

1
12
2
1
1
12
2
1

If you replace with sushi , and replace with a sandwich , it will be the same as the Y Combinator lunchbox we used on previous pages.

If you replace with , and
with , it’s the same as
the Y Combinator lunchbox
1
12
2
1
1
12
2
1

So: The previous lambda expression represents Y Combinator.

λA.(λB.A(B B))(λB.A(B B))
Y Combinator

We have been talking about lunchboxes in this course. But we really were talking about lambda calculus. I invented lunchboxes to make lambda calculus more approachable for non-programmers.

I invented lunchboxes to make
lambda calculus more approachable
Slide 4 / 7

Back to the villager’s question

Now, let’s revisit the villager’s question:

Are there any calculations that lunchboxes cannot do?

Earlier, we said that: Lambda calculus works exactly like a lunchbox.

Lambda calculus works exactly like
a lunchbox

So we can rephrase the above question as follows:

Are there any calculations that lambda calculus cannot do?

And here’s the answer: Lambda calculus can do any calculations that can be done by today’s computers. Therefore, any calculations that your computer or smartphone can do are also possible for lambda calculus.

Lambda calculus can do
any calculations that can be
done by today’s computers

And because lunchboxes are the same as lambda calculus: If something can be calculated by today’s computer, it can also be done using a lunchbox.

So, to answer the villager’s question: Lunchboxes can do any calculations that can be done by today’s computers.

Lunchboxes can do
any calculations that can be
done by today’s computers
Slide 5 / 7

Legacy of lambda calculus

Lambda calculus, invented by Alonzo Church in the 1930s, had a big impact in the evolution of modern computer science.

Lambda calculus had a big impact
in the evolution of modern computer science

Specifically: Lambda calculus influenced many programming languages. Today’s popular programming languages usually have a feature that originated from lambda calculus.

Example: Python is one of the most popular programming languages today, especially in the field of AI.

Python Programming Language

The python language has a feature called “lambda”, which is similar to lambda calculus.

Here’s an example of python’s “lambda” feature: Take a look at the Python code below (we’ll use green for the Python code).

(lambda A: A)('B')

The above Python code is pretty much the same as the lambda calculus expression below:

λA.A B

If we represent this using a lunchbox, the final result will be .

Because the bottom two are the same…
1
1
on the top remains

Similarly, if you run the earlier Python code, the result will be 'B' as well.

(lambda A: A)('B')
'B'

Summary: Today’s popular programming languages like Python have a feature that originated from lambda calculus.

Popular programming languages
like Python have a feature
that originated from lambda calculus
Slide 6 / 7

Building a complex thing from simple things

We’re almost done, but let me say a few things about computer science and Y Combinator.


One of the most important ideas in computer science is to build a complex thing from simple things. After all, computers are made of very simple things: 0’s and 1’s.

One of the most important ideas
in computer science:

Build a complex thing from
simple things

In this course, we learned about lunchboxes (or lambda calculus). And lunchboxes are simple. There are only a few rules you need to know:

Lunchboxes are simple:
There are only a few rules
you need to know
tlr
tlr
tlr
tl

But we learned that: Even though lunchboxes are very simple, they can do any calculations that can be done by today’s computers.

Lunchboxes can do
any calculations that can be
done by today’s computers

Why is that possible? Because, as we’ve seen so far, by combining simple lunchboxes, you can build a complex lunchbox that can do complex calculations.

By combining simple lunchboxes,
you can build a complex lunchbox
that can do complex calculations

For example: We learned that we can use the Y Combinator lunchbox to do complex calculations like factorials.

By combining Y Combinator
1
12
2
1
1
12
2
1
…with a lunchbox that can
calculate multiplications…
You can do complicated calculations like factorials

Again: Computer science is all about building a complex thing from simple things. I think lunchboxes—especially Y Combinator—are a great example of this idea.

Computer science is all about
building a complex thing from simple things.
Lunchboxes and Y Combinator are
a great example of this idea.

We didn’t have time to talk about any other topics in computer science. But in every sub-field of computer science, you’ll learn to build a complex thing from simple things.

For example: If you study artificial intelligence, you’ll learn to build a “neural network” —a complex thing that can be used to process images—by combining simple things called “neurons” .

In AI, you’ll learn to build
a neural network (a complex thing)
using neurons (a simple thing)

Hopefully, this course gave you an idea of what learning computer science is like. If you do end up learning computer science, you’ll be surprised that most innovative ideas in computer science are based on lots of simple ideas.

Slide 7 / 7

Conclusion

Here’s a quick summary of what we learned in this course:

  1. Lunchboxes are simple, but by combining them, you can create a lunchbox that can do complex calculations.
  2. Y Combinator is a special kind of a lunchbox that allows you to repeat any calculations.
  3. Lunchboxes are the same thing as lambda calculus, which was invented in the 1930s and influenced many programming languages.
  4. Computer science is all about building a complex thing from simple things. Lunchboxes—especially Y Combinator—are a great example of this.

That’s it for this course!

If you’re a programmer and are interested in trying out the Y Combinator program, press “Test Y Combinator in devtools” below.

You need to be on a desktop browser though—you can’t do it on a smartphone.

Thank you for reading!

Thank you for reading! I’d appreciate it if you could share your thoughts by quote-retweeting the following tweet:

If you have a question or a comment: Please reply to the above tweet with a screenshot, or email me at shu@chibicode.com. You can also discuss this on Hacker News.

If you’re a programmer:

  • You should also check out this article of mine: “You Can Explain Functional Programming Using Emojis”.
  • This course is built using TypeScript and React. Check out the source on GitHub.

Once again, thank you for reading!

About me: I’m Shu Uesugi, a full-stack developer based in San Francisco Bay Area, USA.

Available for hire: I’m looking for a full-time senior engineering position. Press “Continue reading” below to learn more about me!

Testimonials

Here are some of the readers’ comments:

Press the button below to continue to the course!

Advanced 5
Japanese Site (日本語版) · About this Site · Twemoji