Lambda and Functional Programming

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:

位x. e

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.

BasicFunction

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:

  1. Crash Course on Lambda Calculus by Ayaka Nonaka聽
  2. Lambda Calculus – Computerphile
  3. Lambda Calculus by Jim Grandpre
  4. 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.

Going functional: the journey begins!

For a long time, I really didn’t get to treat this blog as my own blog. I mean, sure, I said things I’m enthusiastic about. But I think the purpose of having a blog is not about catching attention rather having a safe place where you can have a dialogue with your mind.

I recently started dabbling with functional programming. I don’t know why though. For long I heard a lot over it from the constant stream of social networks. I never managed to find a reason why should I ever care about this. I think secretly I was afraid if I ever take this up, I might succumb to my curiosity and finally spend time learning things I really don’t need right now. Then again, knowledge never fails.

So, here I am. After spending around 8 or 9 hours of active reading, I barely made a scratch in the surface of it. But it’s a start. My major breakthrough was to be able to get back to that mindset where I could just play with something when I have the least knowledge backing it. It’s a scary game but boy is this fun to play.

 

Ahoy! functional programming!

The first and foremost notion of functional programming I got from watching people talk about it is that it probably has something to do with ‘functions’ being the first citizen in a programming language. And immutability plays a big part. That lead me to the same place where I started learning programming. 聽I mean I knew “what” was I learning, I did not know “why” I was learning that. I didn’t have the guts to ask because I didn’t know anything about the context. Now, I stand in a corner where I get to ask the question. Why?

 

Why functional programming is like this?

Surprisingly functional programming didn’t spawn from the concept of programming construct “function” being the first class citizen in a programming language. The fun thing is the word ‘functional’ in the very title doesn’t even point to programming functions. It actually points to mathematical functions. Before I go into that, please allow me to tell yourself to ‘unlearn’ programming as you know it. Especially if you are a person like me who knows imperative programming only. 聽The reason to unlearn what you know is to give you a clean fresh slate to work with. I know that is easier said than done. But as long as you know it and open to see things, you’d be fine!

So, let’s dive in. Let’s assume a simple, very simple mathematical function like the following:

let add1 x = x + 1

For reference I’m using F# here. The two programming languages I want to at least try out is F# and Scala. There’s a solid debate on Scala not being a total functional programming language. But, that is a story for another day. My goal is to understand Apache Spark better in the process too and Scala is just too friendly with it. In the process I’m trying to kill two birds with one bullet. This blog will roughly use F# for reference but nothing here is not understandable even if you haven’t seen F# in your life.

If we have a look at the function here we will see that we are adding 1 to another number here. Any programming language in existence is capable of doing that. What is the difference here except the syntax? This is where I send you back to the “unlearn” step. Let’s see how this is interpreted inside. The F# interpreter will read the function signature like the following:

val add1 : x:int -> int

the聽 val add1 part is self explanatory, we don’t want to worry about that part right now. What about the next part聽x:int -> int. This is where my聽imperative programming brain聽came into work and devised a misleading explanation. And it sounded something like :

The聽x:int -> int聽stands for a method signature that takes an input parameter聽x of type聽int and it returns another聽int.

Like I said, this is wrong but it felt legit when I devised it in my brain. The more I delved into it, the more I realized the wrongs in my ways. Years of imperative programming have assembled my neurons to reinforce these concepts as the general means of programming. Since functional programming resorts to mathematical functions, why can’t we see it from that specific aspect?

A mathematical function takes a set of values that are used as聽inputs into the聽function domain聽and the聽function maps it to a set of possible聽outputs. The set of the outputs are called聽range. All the functions do here is聽map the inputs to the聽outputs.

To visualize:

Functions_Add1

I’m not sure whether I have explained enough how my brain was convinced that it is different. To reinforce that the biggest difference here to look for is the process of doing things. We are聽transforming the聽inputs here. Not necessarily returning a value.聽Mathematical functions transforms inputs, they don’t produce聽any聽 side effect to the聽inputs. What I want to mean is if you add 5 and 1 you will get back 6. The input parameter 5 will not have any possible side effect on it. And a聽mathematical function always gives the聽same output for a specific given聽input. My聽imperative programming brain got it almost right. The right explanation for 聽x:int -> int is an int domain to int range mapping.

The function聽add1 maps an int input domain to an int range. And for the fact that mathematical functions DO NOT implicate any side effects, it was implicitly important聽to have聽immutability embedded inside them. Because if your programming function generates a state or a side effect then it will 聽not comply with mathematical functions. So the implementation layer will fail to comply with the theoretical counterpart. And that is why聽immutability聽is vital in functional programming.

 

I still don’t see the difference

This is really nice and all. But from my聽imperative programmer brain’s perspective, is it really that different? If I didn’t take this journey to figure out why functional programming is like this, won’t I be able to write anything in any possible functional programming language? And yes, for sure my brain will be able to. But here is the fun part. What our brain learns implicitly is really hard to explain using the same brain. Otherwise, machine learning will be a piece of cake. My point was to actually try to “know” it, not get habituated to it. Thus when I encounter a problem I can deduce a solution through what I know rather than just plugging constructs I have seen.

Still, I need an answer. Where is the difference? I still see inputs and outputs. Nothing else. My聽imperative programmer brain is quite right here, we聽assign a value to a聽variable and the聽function returns a聽result.聽

Now, wait a minute and lets see a bit into the word聽variable and聽assign. The word聽variable and聽assign points to the fact where we use the聽variable as a placeholder for the actual聽value聽. And the concept of聽assigning a聽value to a variable points to the concept of storing something in that placeholder. Is it the same here? No. Mathematical methods don’t imply placeholders. It creates a mapping and generalizes that mapping. So saying聽add1 5 is not assigning聽5 to x. It is actually聽binding 5 to聽x. The process of binding is not reusing聽add1.聽add1 5 is pointing to a method binding that says when聽I’m invoked you will end up in the range.聽 It looks really the same but it is not. Think of basically doing a string replace where the x is replaced with 5.

Hopefully now you will see more reasons reinforcing聽immutability.聽And thus the function name, 聽add1聽is not a reusable construct for the function. It’s just a shortcut expression for the聽range it returns. We are replacing a聽function value, not the聽function!

To sum it up the generic function value signature is聽

val functionName : domain -> range

So, here’s a trick question. How do we define constants then? The answer is writing a function where the range is just the value from any possible domain. 馃檪

The motivation behind starting to write again while I learn something goes straight to Chris Smith. He wrote Programming F#聽and his MSDN blog while he was writing F# is found here. They are highly entertaining and please don’t refrain yourself from looking into them.聽According to him it is one of the best ways to learn a language and I kind of agree with him despite the fact I lost the courage or interest to do that regularly before.

I also found Learn X in Y Minutes聽very very fun to have a blind date with a number of programming languages. If I ever get to talk about Scala (that depends on me having time to learn it), I will definitely talk more about this website.

The resources for this blog are taken from:

  1. F# for fun and profit
  2. Learn X in Y Minutes

Hope this was entertaining albeit it comprises of boring details! I intend to write a dummies note onthe church-turing hypothesis which essentially blossomed into lambda calculus. Functional Programming is almost directly derived from it. But, it all depends on how much time I will possibly have to cover that. Until then, see ya.