Everything can be expressed as a function. But it shouldn't be used everywhere. Once it is populated with arguments, its state cannot be changed. Therefore, you have to create another function if you ever once to use the same function again. That creates more memory consumption. But the functional paradigm becomes popular again because it gives good readability abstracted in a short code. There's also enough memory to execute them nowadays.
This is the lower-level perspective of a programming language. You can say, "semantics of the functional programming." So, you need to be an expert in one of the high-level programming languages. And you also need to be a good problem solver. Otherwise, this is just wasting your time!
Now, you know what and why. And we're a bit behind the schedule. So, let's start learning it right now!
A function is a black box where you can't see what's inside. If you wanna know if two functions do the same thing, you have to put something in it and see if they give us the same result. Let's say there are two functions; f(x)=2x, and g(x)=x+x, you can't know if f(x) is equal g(x) without putting a value in it. This is called Extensional Equality.
f(x)=2x, f(2)=2*2=4
g(x)=x+x, g(2)=2+2=4
Hence, f(2) is equal to g(2).
We represent a function with a bird. Each bird is a function. Each function can have one or more functions or arguments inside it and we called them layers.
Half-circle on the left of the box represents a bird's ear and the right one represents its throat. The dotted box encloses the red solid line and one box represents one layer. The solid line is a pipe which shows the direction of flow the information from ear to throat. Normally, it goes from left to right. We don't use arrow head except to indicate reverse flow. FYI, ear to the throat is connected through a tube! The Eustachian tube is a small passageway that connects your throat to your middle ear.
This is the one layer bird. It takes only one argument and return it. It seems to have no intelligence at all. That's why we called it, "Idiot" or "Identity." And we present it with "I."
Just like f(x)=x, this one is I(a)=a. I is a function that takes a as an argument and returns a. It takes one argument and so Idiot is one-layered bird. You can try it, with the syntax of JavaScript's arrow function in console of a browser.
let I = a => a;
I(0) //returns 0.
I(1) //returns 1.
It is the two layer bird. It takes two arguments and return the first one. If you put 1 and then 2, it will only return 1. because the second argument has no connection from ear to throat. Note that pipes can be passed freely from outter box to inner box without having to pass through inner box's ear.
You can try it, with the syntax of JavaScript's arrow function in console of a browser.
let K = function(a) {
return function(b) {
return a;
}
}
let K = a => b => a;
K(0)(1) //will return 0.
K(1)(2) //will return 1.
As you can see, Kestrel always return the first thing and so you can neglect the second one. Kestrel can be used as a constant. For example, K(3) will always gives you back 3 regardless of the second one. That's called the constant. And we can create like this.
let K3 = K(3);
K3(0) //returns 3.
K3(1) //returns 3.
Forget about its syntax and look at the sequence that executes. Does it look familiar to you?
In the ternary operation of the high-level syntax, it will be like the following...
boolean?value1:value2;
If boolean is true, it returns the first one; value1. So, Kestrel is the TRUE function. So, what's the FALSE function? It returns the second thing. Now, you get both TRUE and FALSE functions.
let T = K;
Now, you can create the FALSE function like the following.
let F = a => b => b;
But instead of manually creating a new function like the above, you can combine existing functions to create a new one that gives us a new function.
What do we get if Kestrel heard an Idiot song? K will give us the first one and so we just note the second one with x.
K(I)(x) = I
When we put Idiot as the first argument to Kestrel, we will get an Idiot because it returns the first thing. But Idiot can take one argument.
K(I)(x)(y) = I(y) = y
The K function itself can take one argument but when it combines with another function, it becomes a new function and can take THREE arguments. But we don't use it like that. We combine the two functions and create a new function. Only after that, we use it with arguments.
When an input is a function, it breaks the layer of a bird once the input function's throat hits the ear of the bird. And the input function will go until its throat touches the end of the innermost layer's throat. But the input function will never get out of the innermost layer's throat. Only the argument gets out of the throat.
let KI = K(I); //new func.
KI(1)(2) //returns 2.
So, the KI function returns the second one. So, it's a FALSE function. As I mentioned above, sometimes, we don't need to create another function, we can combine existing functions to create a new one. Let's reassign F with KI.
F = KI;
When we check T in the console, It will give back K(a) that returns the first thing. It will only return the function because we didn't put some arguments. So, we are going to make it readable in the syntax of JavaScript.
let toBoolean = f => f(true)(false);
toBoolean function takes a function and applies two arguments; true and false. If the function is K, it will return the first one i.e., true.
toBoolean(K) //returns true.
toBoolean(KI) //returns false.
Remember that K is assigned to T and KI is assigned to F.
toBoolean(T) //returns true.
toBoolean(F) //returns false.
Don't lose the point. Functional Programming expresses everything with a function. We're just created "toBoolean function" only to check if it works in high-level perspective.
This is the three layer bird. It takes a function with two arguments and flip them. I assume you understand how the bird works and I won't use animation schema so that I could speed this up.
let C = f => a => b => f(b)(a);
C(K)(1)(2) //returns 2.
C(KI)(1)(2) //returns 1.
So, it just swap two arguments of a function. K gives the second one and KI gives the first one now. K becomes KI and KI becomes K.
C(K)(1)(2) == KI(1)(2)
C(KI)(1)(2) == K(1)(2)
That's how the functions meet extensional equality. Cardinal reverses the True and False functions. So, Cardinal is just a NOT function.
let NOT = C;
NOT(T)//returns C(a)
NOT(F)//returns C(a)
Sometimes, the result doesn't seem to be clear like this. We need to put some values and check it.
NOT(T)(true)(false) //returns false.
NOT(F)(true)(false) //returns true.
Instead of checking the result like this from above, it would be better in readability if we use some function like the following.
toBoolean(NOT(T)) //returns false.
toBoolean(NOT(F)) //returns true.
That's why we should to use some sophisticated functions to check the result.
How does it work? If all are TRUE, returns TRUE. If one of them is FALSE, returns FALSE.
let AND = p => q => p??
If p is true, we know p is K. K will return the first thing. So, we just need to check the other one. So, we know what to return. It is q.
let AND = p => q => p(q)?
If p is false, we know p is KI. KI will return the second thing. One of them is false, then returns false.
let AND = p => q => p(q)(F);
Or we can simplify it and return p that is already false.
let AND = p => q => p(q)(p);
Note: T = K and F = KI.
AND(p)(q) = p(q)(p)
AND(F)(F) = F(F)(F) = KI(KI)(KI) = KI = F
AND(F)(T) = F(T)(F) = KI(K)(KI) = KI = F
AND(T)(F) = T(F)(T) = K(KI)(K) = KI = F
AND(T)(T) = T(T)(T) = K(K)(K) = K = T
AND(F)(F)
AND(F)(T)
AND(T)(F)
AND(T)(T)
Those codes above will only returns a function. And so, we will have to use toBoolean Function to check the result.
toBoolean(AND(F)(F))
toBoolean(AND(F)(T))
toBoolean(AND(T)(F))
toBoolean(AND(T)(T))
How does it work? If one of the inputs is TRUE, returns TRUE. If all of them are FALSE, returns FALSE.
let OR = p => q => p??
If p is true, we know p is K. K will return the first thing. So, return the T.
let OR = p => q => p(T)?
If p is false, we know p is KI. KI will return the second thing. Then we need to check the other one. So, return q.
let OR = p => q => p(T)(q);
Or we can simplify it and return p that is already true.
let OR = p => q => p(p)(q);
Note: T = K and F = KI.
OR(p)(q) = p(p)(q)
OR(F)(F) = F(F)(F) = KI(KI)(KI) = KI = F
OR(F)(T) = F(F)(T) = KI(KI)(K) = K = T
OR(T)(F) = T(T)(F) = K(K)(KI) = K = T
OR(T)(T) = T(T)(T) = K(K)(K) = K = T
OR(F)(F)
OR(F)(T)
OR(T)(F)
OR(T)(T)
Those codes above will only returns a function. And so, we will have to use toBoolean Function to check the result.
toBoolean(OR(F)(F))
toBoolean(OR(F)(T))
toBoolean(OR(T)(F))
toBoolean(OR(T)(T))
How does it work? If two inputs are the same, returns TRUE. If one of them is different, returns FALSE.
Check the binary operation in below as an example.
0==0 ⇨ 1
0==1 ⇨ 0
1==0 ⇨ 0
1==1 ⇨ 1
The code for boolean equality is as follows:
BEQ = p => q => p(q)(NOT(q));
Inputs:
BEQ(p)(q) = p(q)(NOT(q));
BEQ(F)(F) = F(F)(NOT(F)) = NOT(F) = T;
BEQ(F)(T) = F(T)(NOT(T)) = NOT(T) = F;
BEQ(T)(F) = T(F)(NOT(F)) = F;
BEQ(T)(T) = T(T)(NOT(T)) = T;
BEQ(F)(F)
BEQ(F)(T)
BEQ(T)(F)
BEQ(T)(T)
Those codes above will only returns a function. And so, we will have to use toBoolean Function to check the result.
toBoolean(BEQ(F)(F))
toBoolean(BEQ(F)(T))
toBoolean(BEQ(T)(F))
toBoolean(BEQ(T)(T))