Functional Programming

It has been couple of years since I have been hearing about Functional Programming. Finally I could find some time to delve into the topic to understand what the fuss is all about! To my surprise, I found it quite interesting and a totally different thought process. It differs a lot from the conventional way we have learnt programming, which is Von Neumann style. Functional Programming brings all together another perspective to the table.

As I searched more about the same, I came across loads of material which explains the idea.

The following write up is an attempt to put together all the information I have obtained and researched. It includes material from various sources, direct links and also my personal take as I traversed through the concept of  Functional Programming. The aim is to enable to aggregate the know how at one place in order to help a beginner like me to understand the background and concept of Functional Programming without meandering around for various resources.  I hope it achieves the goal. Being a novice in this programming style, I might have some mistakes however the I am open to any corrections as one might perceive while reading the following.

Having said that lets start the exciting journey…..

Though it may seem like the whole idea (of Functional Programming) has picked up not long before , I must state that it has been in existence decades before.  Way back in 1977 it was argued can programming be liberated from the Von Neumann style ?

What is a Von Neumann architecture ?

Earlier computers were fed programs and data for processing while they were running. Von Neumann came up with the idea behind the stored program computer, our standard model, which is also known as the von Neumann architecture. In the von Neumann architecture, programs and data are held in memory; the processor and memory are separate and data moves between the two.

In simple terms a Von Neumann computer has three parts: a central processing unit (or CPU), a store (memory), and a bus that can transmit a single word between the CPU and the store (and send an address to the store). Von Neumann languages have imperative statements — requests to the CPU to make some change to the store, and expressions (conceptually simpler) to denote values that need to be calculated by the CPU.

The following pictures tell it in a simple way..

Structure of Von Neumann machine
Structure of Von Neumann machine
Many Von Neumann inspired languages allow the processing of expressions to include side-effects that change the contents of the store during expression evaluation. The main difficulty with imperative statements and side effects is that they do not commute: we cannot change their order without changing the meaning of our program.

Instruction flow
Instruction flow
Although the above architecture was able to solve many typical problems faces during 1950s, later on it suffered an inherent limitation called the Von Neumann bottleneck.

In recent years, as the processor speeds have increased significantly the memory improvements, on the other hand, have mostly been in density – the ability to store more data in less space – rather than transfer rates. As a result, the processor has to spend an increasing amount of time idle, waiting for data to be fetched from memory. Irrespective of how fast a given processor can work, in effect it is limited to the rate of transfer allowed by the bottleneck. Faster the processor, more the time it spends idling.

There have been certain workarounds proposed and used such as Caching, Multi-threading etc. However none of them are seen to be addressing the bottleneck problems entirely. The  von Neumann bottleneck has often been considered a problem that can only be overcome through significant changes to computer or processor architectures.

Alternatives ?

There are alternatives like Harvard Architecture – which has separate data and instruction busses, allowing transfers to be performed simultaneously on both busses. They are ubiquitously used in small scale machines powered by for ex. ARM processors.

However there is another set of languages called as purely functional, also called “applicative”, programming languages which try to address the above side effects and restore commutativity and preserve the rules of mathematics so that proofs concerning the correctness of functional programs are easier to establish.

What is Functional Programming ?

The functional programming as explained by Wikipedia,

In computer science, functional programming is a programming paradigm—a style of building the structure and elements of computer programs—that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data.

The Functional Programming is a  programming paradigm which deals with breaking down problems into smaller manageable functions each doing a clearly defined task without changing any state or behaviour of the system under consideration. Functions behave the same way when similar input is fed each time. Actually this paradigm derives its roots from the world of Lambda Calculus.

The case of Functional Programming (FP) is growing even stronger every other day with necessity of extreme parallelization and the fact that traditional imperative languages are finally hitting the Amdahl’s Law.

Where can I find more about Functional Programming ?

An insight into the realm of Functional Programming stresses the same further

Now the question arises why Functional Programming ?

The answer lies in the text written at DrDobbs. The two important question from the same I have listed below.

What Problem Spaces are Naturally Addressed by Functional Programming? courtesy DrDobbs

Growing up, I’d occasionally help my dad fix things around the house, paint, etc., and from the many things he taught me, “the right tool for the job” stands out clearly. When faced with a problem, you need to consider what you have in your “toolbox” and decide the best way to solve it. Certain problems can be solved easily with a hammer, whereas with others you need a saw. You need to apply the same thought process to choosing programming paradigms and the languages that support them.

Functional programming is appropriate for applications that exhibit one or more of the following characteristics: require significant computation (compute-bound) as they can be parallelized easily, are themselves parallel in nature, can benefit from asynchronous calls, need to be provable, or require sophisticated pattern matching. This means that functional programs are not generally applicable to typical line-of-business applications that deal with objects and their state over time; however, there may be portions of those programs, e.g., portfolio basket optimization for fixed-income securities, that would benefit greatly from using functionally-based libraries. We typically see functional programming applied to image processing, machine algebra, lexing and parsing, artificial intelligence, and data mining.

Why Should I Care About Functional Programming? – courtesy DrDobbs

While you can develop concurrent, scalable and asynchronous software without embracing functional programming, it’s simpler, safer, and easier to use the right tool for the job. Functional programming enables you to take advantage of multi-core systems, develop robust concurrent algorithms, parallelize compute-intensive algorithms, and to readily leverage the growing number of cloud computing platforms.

In addition, if you’ve not already explored non-imperative programming, it’s a great way to expand your problem solving skills and your horizons. The new concepts that you’ll learn will help you to look at many problems from a different perspective and will help you to become a better and more insightful OO programmer.

What are the most popular Functional Programming Languages ?

To name a few

  • F#
  • Clojure
  • Scheme
  • Scala
  • OCaml/SML
  • Erlang

However this best answered in thread discussion at quora.

Which commercial entities are using FP for mainstream businesses ?

One could answer this question fairly quickly by looking at the various case studies available. For instance, on Typesafe’s Case Studies & Stories page are listed:

Nevertheless following are the few well-known companies using functional languages

  • LinkedIn
  • Twitter
  • Gilt Groupe
  • Ticketfly
  • Foursquare

But then how are the languages classified ?

Languages classification
Languages classification
Do you think it was interesting and another point of view could be even better ?

I have found an old but nice introduction to functional programming. Read on…

The above text was enough to trigger the curiosity bug and you want to learn Functional Programming ?

Here is very good course arranged by Coursera – Functional Programming Principles in Scala hosted by non other than Martin Odersky himself (designer of the Scala Language).

Lastly, having said a lot about Functional Programming, one might think are there any drawbacks of the same ?

Bingo !! So you thought about it !!!

Every thing comes with its own set of advantages and disadvantages and so does Functional Programming style as well.

Well, as one might think following could be listed as shortcomings

  • Steep learning curve – since one has to unlearn few imperative things to embrace this new style, it is not always easy
  • Too many allocations – since mutation are not allowed, a program might end up in allocating lots of objects, and then has to rely on other entities for ex. garbage collectors for the cleanup
  • Convoluted simple tasks – Sometimes a simple task like reading and modifying a file content can get messy owing to avoiding of mutations
  • Data Structures – There are certain data structures / algorithms designed to work in imperative way which are then difficult to include in functional programming
  • Efficiency – I better not comment on it at the moment, as there experiments going on and one can find lots of discussions for and against the same. For ex. follow here… Its best left to the use case it has been deployed
  • Laziness – It moves evaluation—i.e. the actual computational cost—from the place where a computation is defined to where its used, hence could directly impact performance
  • Performance – Most functional languages are not particularly good choices for soft or hard realtime systems or embedded computing

Though the list may seem to be a bit longer, the advantages to productivity and maintainability are worth the up-front learning cost and the increased difficulty in performance. The mathematical approach and  expression like structure is aimed to solved a different class of problems.

As a ending note, at times let practicality override one size fits all solution

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s