Revival of the Functional Programming Paradigm

I have been programming for some years now and I started with C++ (unusual because C is the most general starter) back in school. Then as I moved to high school and later on, undergrad, I learnt a little more of C++ and then it was Java all along. It should be about 6 years since I started programming in Java (on an academic level, that is) and all this is only to say that Imperative Programming which is pretty intuitive and easy to learn has become quite popular today.

Somewhere in my final year of undergrad, I was exposed to Lisp and I never quite got the head or tail of it for it seemed to work rather differently. Luckily for me, then, it was just an introduction and confined to a few basic programming examples and I didn't have to worry about learning the same from a test perspective. Then, last year, my professor remarked rather casually that Functional Programming which is a rather old paradigm has now a future and that it would be a great idea for passionate programmers to revisit it. 

I did start exploring Scala (a functional programming language) and my initial exploration was largely confined to a handful of web links that didn't really get the crux of the idea of Functional Programming across to me. Then, I happen to stumble upon this great YouTube video in which leading scientist, Martin Odersky speaks about Functional Programming at the O'Reilly OSCON Java 2011 conference. I have linked the video below and like I always do, provided a brief explanation regarding the same a little later, down below.

One of the biggest challenges faced by programmers these days is Non-Determinism. Now, consider a program having the following block of code below:

x = x + 1;

x = x / 2;

Say, you have two threads running in the same program. What is deterministic here is that each thread runs the above block of code in programmatic order from top to bottom within itself. But, what is non-deterministic, however, is the order in which these two lines of code execute in the two threads with respect to each other. Let me provide an example here to make things a little more clearer: 

One possible execution context, A:

Thread 1: x = x + 1

Thread 2: x = x + 1

Thread 2: x = x / 2

Thread 1: x = x / 2

Another valid execution context, B:

Thread 1: x = x + 1

Thread 1: x = x / 2

Thread 2: x = x + 1

Thread 2: x = x / 2

There is in fact, a few more possible execution execution contexts. But, what's clear is that in multi-threaded programs, the sequence of execution of instructions with respect to Time as a dimension is not certain or deterministic  given that it is entirely in the operating system's discretion to schedule and dispatch threads for execution. While memory models such as JMM guarantee top-down order of execution within each thread, there are really no guarantees regarding the interleaving of these instructions with respect to different concurrent threads as can be seen from the above example.

This Non-Determinism is a result of two widely seen aspects of modern day programs:

a. Parallelism , b. Variable/Reference Mutability

We have already seen pretty clearly as to how Parallelism can lead to uncertainty or Non-Determinism. What we need to see now is the role of Variable/Reference Mutability to bring about the same effect.

Taking a deeper look at the above example, we can see that, x is a variable and its value is being mutated in the program. Now, if x is a thread-local variable, there is really no reason to worry for the programming language memory model ensures that the instruction execution sequence is strictly the program order. But, that's only as far as x is thread-local. If x is a global variable (for the two threads), the final value of x depends on the complete execution sequence. 

Let's consider contexts A and B now:

If the initial value of x is 1, execution context A would give final value, 0.75 whereas B would result in final value, 1 for x.

This is because the value of x computed at each stage is dependent on the value of x from the previous stage. We can now quite clearly see as to how Variable/Reference Mutability can play its part in rendering the result of the program, non-deterministic.

Here is where Functional Programming comes to the rescue with its varied emphasis upon looking at the problem from the perspective of Space as against Time. This different approach now accomplishes Parallelism and better resource utilization, but differently. Here, a task is divided into units that can be independently worked on by multiple execution units working in parallel. That is, execution unit works on a specific task unit and its execution scope is outside the scope of execution of other execution units. This is in contrast to division of task into sub-units that are worked upon by execution units in a pipeline fashion one after the other. While such pipelined execution is faster than the simplistic one sub-unit at a time execution, it is definitely not parallelism in the true sense. 

So, we have now seen as to how Functional Programming aids Parallelism by knocking off the impact of aspect b, which is Variable/Reference Mutability. Languages such as Scala have given Functional Programming a whole new face by combining its benefits with those of OOP and modern day trends such as Agile Development. This is sufficient to see that solutions to needs of the future largely lie across a multitude of individual candidate solutions.