The beauty of Lambda Calculus

Have you ever heard of a Turing Machine?
A Turing Machine is an abstract model which can perform any function that is algorithmically computable.

Lambda calculus is Turing Complete, which means has the same computational power as a Turing Machine does.
In simpler terms, it is a full-functional way of representing data, performing operations on them and returning the expected result... but here's the catch: It's all functions. The whole system is just a bunch of functions, which take functions and return functions. Even the numbers are represented as functions. And that's amazing.

Let's outline the syntax, here is the simplest, useful lambda function:

λx.x

x is a function here as well (everything is). But how do these functions accept their inputs?

We show data flow by simply putting the input (function) and the applied function together.

xa

Here, the function x is applied to the input a. We would do the same for a series of functions lined up:

xab

What would be the order? Let's say for now we settle it to prioritize the leftmost operations. So first a is going to enter x and b would join them consequently.

Here is another one

λxλy.plusxy

This one, accepts x and y and returns the sum of them, using another (presumably) predefined function plus.

Just a reminder, everything is a function here. The above lambda function doesn't even have any name. We have put plus for convenience and readability.

So, how do we represent numbers?
Here is the idea. We don't have numbers, but, we do have functions at our hand. We have to somehow manifest the nature of numbers within a function. How about this, we take two inputs and apply the first one n times on the second one.

for instance, C0 which would be the zero of our lambda world, is define as C0=λsλz.z. Similarly, C1 is defined as C1=λsλz.sz and C2=λsλz.ssz

Now, let's say we want a function which accepts a number Cn (Church number in fact, which is what they are called) and return the next number Cn+1
How do we do that? simply by using another s at the end of our current number.

SCC=λnλsλz.s(nsz)

Question 1: What is(nsz) doing here?

Answer: As we said, these Church numbers (here n which represents Cn) are just functions that take two parameters and apply the first one n times (not the n in Cn) on the second one. So, in order to do any further operations, their initial inputs must be satisfied.

Question 2: How does paratheses work in Lambda Calculus?

Answer: Intuitively, they determine the operation order we wish to preserve.

So, our SCC function is accepting a number n and returning the next number.

Now, let's say we want to add two numbers together.
Here is how we do it:

PLUS:λnλmλsλz.nSCCmsz

Question: What is the order here?

As mentioned above, unless we have parenthesis, the correct order is the leftmost function and leftmost inputs going through it. Therefore, n (which is a function that accepts two parameters and performs the first one n times on the second input) is taking SCC as it's first input (which is a function that accepts three parameters, returning the successor of the first one) and SCC is taking m as it's first parameter and later on s and z to produce numeral behavior for Church numerals.
The result, is that (based on the specific definition of our number here) the number n is making SCC happen n times on m, and s and z are joining the equation to help.

Now how to do multiplication?

MULT:λnλmλsλz.n(ms)z

Here, ms is happening n times on z which essentially makes it nm

See! this is great! We can eventually define any function we desire, purely in terms of functions. For instance, in order to define subtraction, we would define a predecessor function and call it as many times as needed.

We can even represent logical expressions here. Let's assume we define

tru:λtλf.t

as the equivalent of TRUE. What it does, is that it takes two inputs and returns the first one. Now the way it could be used as TRUE isn't that intuitive here, but let's add fls as well:

fls:λtλf.f

Now what would happen if we define conditions as :

if:λbλxλy.bxy

It's taking three parameters and performing the first one on the last two. But hey, if we give our tru to this function, it would be truxy which returns x (as we defined true). And if we set b as fls, it would return the second parameter, which is y. Isn't this exactly what we want from a conditional expression? If b (is true) then (return) x else (if b is false) y.

And this is beautiful. The internal mechanism behind this world is the same as ours, even though basic concepts like numbers are not innately present in it. We merely need to carefully demonstrate the nature behind our familiar concepts using functions.