Sunday, January 17, 2010

Functional Programming - An Overview

Let us start this blog post on ‘Functional Programming’ with a widely accepted definition of computer programming – “computer programming is the process of creating a sequence of instructions which will enable a computer to do something”. Computer programming is a means to translate problems in the real world that need solving, into a format that computers can process.

Computer programming languages help convey instructions to computers. The goal of programming languages is to translate human language to machine code, the native language that computers understand.

Before we move on to have an overview of functional programming, let us have a look at the different types (or paradigms) of programming languages. Please note that a given language is not limited to the use of a single paradigm, a classic case is that of Java programming language that has elements of both procedural and object oriented paradigms.

a) Procedural Programming Languages: These languages specify a list of operations that a program must execute to reach a desired state. Each program will have a starting state, a list of operations or instructions to complete and an ending state. Two popular examples of procedural programming languages are BASIC (Beginners All purpose Symbolic Instruction Code) and FORTRAN (The IBM Mathematical FORmula TRANslating System).

b) Structured Programming Languages: Structured programming can be considered as a special type of procedural programming, which requires the program to be broken down into small pieces of code, thereby increasing readability. Local variables (local to each subroutine) are preferred over global variables. These languages support a design approach called ‘top-down approach’ in which the design starts with a high-level overview of the system. System designers then add more details to the components in an iterative fashion until the design is complete. Popular languages include Pascal, Ada and C.

c) Object Oriented Programming Languages: This paradigm is the latest and considered the most powerful of all programming language paradigms so far. Here, system designers define both the data structures and the type of operations that can be applied to those data structures. This pair of data and operation(s) on the data is known as an object. A program can then be viewed as a collection of objects, which interact with one another. The important concepts associated with the object-oriented paradigm include classes/templates, inheritance, polymorphism, data encapsulation and messaging. However, a detailed note on these concepts is beyond the scope of our current discussion. Popular languages following this paradigm include Java, Visual Basic, C#, C++ and Python.

d) Functional and Other Programming Languages: The fourth list includes functional programming and other paradigms like concurrent programming and event driven programming, which is not included above.

We will now return to the focus of our discussion – Functional Programming.

In Mathematics, ‘functions’ express the connection between parameters (inputs, in the case of computers) and the result (the output, in the case of computers) of certain processes. In each computation, the result depends on the parameters in a particular way and hence a ‘function’ is a good way of specifying a computation. This is the basis of ‘Functional Programming’.

The above notion is also more close to the ‘human world’ than to the world of a computer where in the initial days of computing, programs consisted of instructions to modify the memory, executed by the central processing unit. Thus, functional programming languages match the mathematical idea of functions. Functional programming is a new approach to solve certain classes of problems, which we will cover later in this discussion.

The main characteristics of functional programming are as below:

(a) power and flexibility – many general, real world problems can be solved using functional constructs
(b) simplicity – most functional programming languages have a small set of key words and concise syntax for expressing concepts
(c) suitable for parallel processing – with immutable values and operators functional programs are more suited for asynchronous and parallel processing

Since the concept of ‘functions’ is core to Functional programming, let us define a function before we proceed further.

“A function is fundamentally a transformation. It transforms one or more inputs into exactly one output”.

An important property of functions is that they yield no side effects – this means that the same inputs will always yield the same outputs, and that the inputs will not be changed as a result of the function. Every symbol in functional programming language is immutable.

Functional programming treats computations – running a program, solving a numeric calculation – as the evaluation of functions.

Some of the classes of problems, which can benefit from a functional programming approach, are as below:

(i) multi-core and multi-threaded systems
(ii) sophisticated pattern matching
(iii) image processing
(iv) machine algebra
(v) lexing and parsing
(vi) artificial intelligence
(vii) data mining

Advantages of Functional Programming

(a) Unit Testing: We have already noted that every symbol in a functional programming language is final and hence immutable. This implies that no function can modify variables outside of its scope and hence there are no side effects caused by functions. This also implies that the only effect of evaluating a function is its return value and the only thing that affects the return value of function is its arguments (Please see the definition of ‘function’ above). This makes unit testing much easier since the boundary values of arguments need only be unit tested.

(b) Debugging: The absence of side effects as explained at (a) above makes debugging easier since bugs are local to a function. An examination of the stack quickly reveals the cause of error.

(c) Concurrency: Functional programming does not allow data to be modified by two different threads or twice by the same thread. Hence, there is no scope for deadlocks and race conditions. This allows ease of programming in concurrent systems.

Apart from being a more appropriate tool for certain classes of computing problems, functional programming also allows programmers to make more efficient use of multi-core systems, develop concurrent/parallel algorithms easily and utilize the growing number of cloud computing platforms.

Functional programming is also considered as a means for programmers to improve their problem solving skills; it also allows programmers to look at problems from a different perspective and become more insightful object-oriented programmers as well.

Popular functional programming languages include LISP, Haskell and F#. 

~ Sunish

No comments: