After I started looking at the core of functional programming here, more and more question followed their ways into my head. It’s pretty common now a days to face new and newer piece of reusable code components on a daily basis. They redefine how things ought to be done. I’m not complaining at all, it is indeed intriguing to see them come forward so fast. And the fun part is all of them follows the principles laid out years ago. Functional programming is no different.
Greek alphabet of coolness, λ
The reason the first word in the title of the blog is lambda because the character is λ is almost synonymous with anonymous methods/functions, almost all the programming language around has the capabilities to create some form of support of constructing lambdas that contain a unit of work. Greek people made even their alphabets cooler than anyone else. And when I started thinking of actually learning a functional language, my first question was why would I need a language that enforces immutability? Can’t I myself keep immutability intact and yet code with the same principles in any other imperial programming language? The answer is yes, sure I can. The point lies somewhere else. Functional Programming is not something really new. It is not something refactored out of imperial programming. In fact, the tale is as old as general/state driven computing as we know it.
Turing and his states
The moment you start talking about computing, you will start living in Alan Turing‘s head. Whatever we build today, whatever we are doing is still following the principles of his infamous computational model Turing Machine. This was his work in 1936 and we still can’t imagine anything out of it. Amazing, isn’t it? A simple tape drive driven machine model is empowering every possible machine you see now. He is indeed the puppet master of computing.
If we look around carefully, everything around is state driven. Object Oriented programming is state driven. Every instance we write of a class is state driven. When you use a cool framework like redux to maintain your application state, you are doing nothing except following the same principles of a basic state machine, especially a DFA. I can’t emphasize this enough, Turing is synonymous to computation.
Now we get into the head of someone else. Someone else named Alonzo Church. Alonzo Church was building a computational model at the same time Turing was working on his own. His computational model was mathematical function driven where every function is a black box, takes an input and drives out an output. Functions can be sent as inputs and every logical relation is based on a simple domain to range mapping. Sounds familiar? Yes, his work was the father of Functional Programming published in the same year, 1936. Alonzo’s model was based off his work on Lambda Calculus. Fret not, the name is scary, the actual thing is way simpler than it sounds, I think it sounds way cooler because the damn name has lambda on it.
The last but not the least amazing part is, Turing didn’t know any of these. And Alonzo was his doctoral advisor. 😉 The whole hypothesis is named after both of them since Turing proved that Alonzo’s model is equivalent of his computational model. And thus Church-Turing Thesis was born.
What is Lambda Calculus?
We are going to take a very very quick tour of lambda calculus. It doesn’t have any traditional calculus-esque constructs in it. There are multiple variants of it. We will only take a quick tour of pure lambda calculus. Just enough to know how functional programming is devised so we can think alike.
The syntax is simple, in context free grammar:
expr ::= constant| variable | (expr expr) | (λ .variable expr )
If you are not used to context free grammar, this construct tells how a lambda calculus expression is written. It says an expression can be a constant, a variable, a set of expressions and at the very end, the abstract form of lambda calculus that states a definition of a function like:
Here, the x is the input parameter and e is the expression. The input parameter is bound in that expression e. And the abstract form of lambda calculus defines a function. Remember this is the definition, it can be invoked and used with real arguments. If this is get all confusing for you, let’s jump into an example. Let’s say we want to define a function that adds 1 to a variable X.
From my perspective we are building a blackbox function that takes one input and converts it to a output.
Now, to express it as a lambda calculus abstract we will use the character λ to define the function, x as the input parameter and the output will be x+1. So this will end up in the expression body e. So, it looks like
λx. x+1
We have our first lambda abstract! yay! This is the function definition. To invoke it, let’s say, we want to use 5 as an input argument. The invocation will look like
(λx. x+1) 5
If this is getting confusing again, remember, we don’t have a name for our function here. The definition itself is the name and the body. And the input parameter as x is 5 now. To deduce the next line, we replace x by 5 and we take the λx off.
(λx. x+1) 5
5 + 1
6
This is a very basic sample of beta reduction. Remember lambda calculus only have inputs, expression and the output. It is indeed that simple.
Now, back to programming world. Remember Javascript’s infamous self invoking method?
(function (x) {
return x + 1;
})(x);
I hope now you see where the principles come from. Amazing. Isn’t it?
The notion of recursion
We are taking a pretty big jump here. Ever wondered how recursions work? We invoke the same method inside of it and we end up in the same place over and over again. Can lambda calculus define recursion?
It can. Lets assume that we have a function λx. x x. And we invoke it with itself as a parameter. So, it looks like:
(λx. x x) (λx. x x)
(λx. (λx. x x) (λx. x x)) (λx. x x) // replacing x x with the (λx. x x) itself
(λx. x x) (λx. x x) // by the same rule of beta reduction, we take of the λ notation and the input
We applied beta reduction here but we still ended up in the same place we started. This is called Omega Combinator which is a divergent combinator since it has no normal form. If you apply beta reduction on it, you will end up in the same construct again. This is basically a simple mathematical model for an infinite loop…pointing to a recursion.
A combinator in a lambda calculus is defined by an lambda expression that has no free variables. What is a free variable you ask? Looks like you want a nice course on Lambda Calculus. 🙂
I found these very helpful if they are read or viewed in order:
- Crash Course on Lambda Calculus by Ayaka Nonaka
- Lambda Calculus – Computerphile
- Lambda Calculus by Jim Grandpre
- Y combinator function. What is it?
If you read/viewed all these already, you probably know this already. The lambda calculus way to self reference a function inside itself is called the Y Combinator. Yeah, mind blown, isn’t it?
Computation is not really far from philosophy or history. It also starts from the alpha and ends in omega. I stay clear of religion but had to mention this. (It sounded cool in my head, doh!)
So, next time you write a lambda to look cool on your codebase or while you are talking to people about the nifty map, reduce and various unit of work methods, pay a little homage to Church and Turing. What they said years ago makes you look cool now.
I Love C# 