Saturday 26 March 2011

Comparison of functional and imperative programming

Functional programming is very different from imperative programming. The most significant differences stem from the fact that functional programming avoids side effects, which are used in imperative programming to implement state and I/O. Pure functional programming disallows side effects completely. Disallowing side effects provides for referential transparency, which makes it easier to verify, optimize, and parallelize programs, and easier to write automated tools to perform those tasks.

Higher order functions are rarely used in older imperative programming. Where a traditional imperative program might use a loop to traverse a list, a functional style would often use a higher-order function, map, that takes as arguments a function and a list, applies the function to each element of the list, and returns a list of the results.
Simulating state

There are tasks (for example, maintaining a bank account balance) that often seem most naturally implemented with state. Pure functional programming performs these tasks, and I/O tasks such as accepting user input and printing to the screen, in a different way.

The pure functional programming language Haskell implements them using monads, derived from category theory. Monads are powerful and offer a way to abstract certain types of computational patterns, including (but not limited to) modeling of computations with mutable state (and other side effects such as I/O) in an imperative manner without losing purity. While existing monads may be easy to apply in a program, given appropriate templates and examples, many find them difficult to understand conceptually, e.g., when asked to define new monads (which is sometimes needed for certain types of libraries).[37]

Alternative methods such as Hoare logic and uniqueness have been developed to track side effects in programs. Some modern research languages use effect systems to make explicit the presence of side effects.
Efficiency issues
    This section may contain original research. Please improve it by verifying the claims made and adding references. Statements consisting only of original research may be removed. More details may be available on the talk page. (May 2009)

Functional programming languages are typically less efficient in their use of CPU and memory than imperative languages such as C and Pascal.[38] For purely functional languages, the worst-case slowdown is logarithmic in the number of memory cells used, because mutable memory can be represented by a purely functional data structure with logarithmic access time (such as a balanced tree).[citation needed] However, such slowdowns are not universal. For programs that perform intensive numerical computations, functional languages such as Objective Caml and Clean are only slightly slower than C.[39] For programs that handle large matrices and multidimensional databases, array functional languages (such as J and K) were designed with speed optimization.

Further, immutability of data can, in many cases, lead to execution efficiency in allowing the compiler to make assumptions that are unsafe in an imperative language, thus increasing opportunities for inline expansion.[citation needed]

Lazy evaluation may also speed up the program, even asymptotically, whereas it may slow it down at most by a constant factor (however, it may introduce memory leaks when used improperly)[citation needed].
Coding styles

Imperative programs tend to emphasize the series of steps taken by a program in carrying out an action, while functional programs tend to emphasize the composition and arrangement of functions, often without specifying explicit steps. A simple example illustrates this with two solutions to the same programming goal (calculating Fibonacci numbers). The imperative example is in C++.

// Fibonacci numbers, imperative style
int fibonacci(int iterations)
{
 int first=0, second=1; // seed values

 for (int i=0; i<iterations; ++i)
 {
  int sum = first + second;
  first = second;
  second = sum;
 }

 return first;
}

std::cout << fibonacci(10) << "\n";

A functional version (in Haskell) has a different feel to it:

-- Fibonacci numbers, functional style

-- describe an infinite list based on the recurrence relation for Fibonacci numbers
fibRecurrence first second = first : fibRecurrence second (first + second)

-- describe fibonacci list as fibRecurrence with initial values 0 and 1
fibonacci = fibRecurrence 0 1

-- describe action to print the 10th element of the fibonacci list
main = print (fibonacci !! 10)

The imperative style describes the intermediate steps involved in calculating fibonacci(N), and places those steps inside a loop statement. In contrast, the functional implementation shown here states the mathematical recurrence relation that defines the entire Fibonacci sequence, then selects an element from the sequence (see also recursion). This example relies on Haskell's lazy evaluation to create an "infinite" list of which only as much as needed (the first 10 elements in this case) will actually be computed. That computation happens when the runtime system carries out the action described by "main".

1 comment:

  1. Thanks for sharing such a useful information, I will be checking your blog for further updates.

    loan modifications

    ReplyDelete