Functional Programming for Beginners

Recently, I’m facing many questions about functional programming. Instead of answering everybody one by one, I decided to write a blog post about functional programming. In this article, I’ll try to introduce you the FP concept. If you are interested, I advice you to have a hands-on experience. There are many widely used functional languages available today: LISP, Haskell, Erlang and F# (new but promising) are a few to name.

Firstly, a Brief History…

A long time ago, in 1930s, when the world was stuck in another economical recession, lives of four extra-ordinary mathematicians were crossed in Princeton, NJ.  These men were not interested in the physical world they were living but trying to create their own universe to find answers about limits of computation – a word not heard by many yet. The area they were interested in was called formal systems and their main problem was to answer which problems are solvable if processing power and memory were infinite. One of them were a truly materialist, a slave of questioning and curiosity, a British guy who decided to move to the new world after graduating from Trinity College. Second was a super brain whose Ph.D. dissertation was accepted when he was just 23 years old, nicknamed “Mr. Why”, a close friend of Albert Einstein. The other two were recent Princeton graduates who decided to go for graduate school. Correspondingly, the names of these men were Alan Turing, Kurt Gödel, Alonzo Church and Stephen Kleene. In 1936, Turing extended Gödel’s study on the limits of proof and computation with replacing Gödel’s universal arithmetic-based formal language with formal devices called Turing machines. At the same time, two young grad students Church and Kleene were designing a universal model of computation which was identical to Turing machines in power. Their formal system were called lambda calculus. Let’s say it in a clearer and less scientific-BS way: they invented a language, lambda calculus, that was capable to be the smallest universal programming language of the whole world.

Lambda Calculus

Lambda calculus is the common programming language of the world. The main aim or their inventors was to prove any computable function can be expressed and evaluated using this formulization. In the universe of lambda calculus, the key elements are <name>, <expression> and <application> where,

 

<name> in lambda calculus cannot be associated with different values, therefore it is not called a “variable.” Imagine your favourite iterative programming language don’t let you change values of the variables by default. Yes, it sounds like a headache at first, but the whole concept is standing on these rules. Now, let’s move on to a more practical example, for instance, to an function multiples its input by 2.

 

For great examples, I suggest you to read “A Tutorial Introduction to the Lambda Calculus” by Rojas.

Functional Programming Language Primitives

With no surprise, functional programming languages are artificial languages where the main application is made from a function (or nested functions), a very similar concept to the lambda calculus. In this chapter I’m going to underline most characteristic features (not restrictions) of functional languages.

1. No sequences of discrete commands. Traditional programming languages are based around the idea of a variable as a changeable association between a name and values. These languages are said to be imperative because they consist of sequences of commands. On the other hand, functional languages are based on structured function calls. A functional program is an expression consisting of a function call which calls other functions in turn (nested function calls).

 

2. Names may only be associated with a single value. In iterational languages, the value of a name (variable) can be modified. In functional languages, names are only introduced as the formal parameters of functions and given values by function calls with actual parameters. Once a formal parameter is associated with an actual parameter value there is no way for it to be associated with a new value.

3. No guaranteed execution order. Iterational languages executes line by line (if there are no multi-threaded pieces.) In contrast, functional languages don’t guarantee a thing about execution order. You have to declare the execution order by yourself.

 

4. No repetitions of names. In functional languages, because the same names cannot be reused with different values, nested function calls are used to create new versions of the names for new values. Similarly, because command repetition cannot be used to change the values associated with names, recursive function calls are used to repeatedly create new versions of names associated with new values.

Advantages of Thinking Differently

So, why do people need to think differently although we had all of the other rapid development languages off-the-shelf and not worrying about the marginal concepts FP brings? People who were interested in distributed computing somehow knows the answer. Have you even heard about mutual exclusion, racing condition or other problems in distributed/parallel programming? Shared memory is a problem and no matter how hard computer scientists work on methods to lock shared resources during critical area executions, usually communication needed to synchronize these events aren’t even worth to distribute the process. Consequently some engineers come ideas like MapReduce where dependency between distributed tasks are none. MapReduce applies most of the concepts I represented above about functional programming.

Secondly, functional programming is more than programming, it’s a way of thinking. You don’t need design patterns for functional programming because it’s a design pattern as itself. With Java, you have billions of features to run the world but when it comes designing a software system, it causes more shortcuts in brain. On the other hand, functional designs are deterministic.

There are many more such as advantages in unit testing, deploying and updating software. Please keep in mind, functional programming is a tough area to transfer knowledge with a blog post. Every section is this post can be extended with a few thousand words. I recommend you to search, try, read, code, live it to have a complete feeling.