Functional programming

Functional programming, as opposed to imperative programming, is a programming paradigm that emphasizes the evaluation of functional expressions, rather than execution of commands. The expressions in these languages are formed by using functions to combine basic values.

The functions alluded to in the title are mathematical functions. Mathematical functions have great strengths in terms of flexibility and in terms of analysis. For example if a function is known to be idempotent, then a call to a function which has itself as its argument, and which is known to have no side-effects, may be efficiently computed without multiple calls.

A functional programming language is a programming language that supports and encourages programming in a functional style. The oldest example is Lisp. More recent examples include Scheme, ML, Haskell, Erlang, Clean. Pure functional programs need no variables and side-effects, and are therefore automatically thread-safe, automatically verifiable (as long as any recursive cycle eventually stops) and have more such nice properties. Nested functions just pass their results back to the main function. Implementations of these languages usually make quite sophisticated use of stack manipulation, since it is used so commonly.

Functional programming often depends heavily on recursion. The Scheme programming language even requires certain types of recursion (tail recursion) to be recognized and automatically optimized by a compiler.

Furthermore, functional programming languages are likely to enforce referential transparency, which is the familiar notion that 'equals can be substituted for equals': if two expressions are defined to have equal values, then one can be substituted for the other in any larger expression without affecting the result of the computation. For example, in

 	z = f(sqrt(2), sqrt(2));

we can factor out sqrt(2) and write

 	s = sqrt(2);
 	z = f(s, s);

thus eliminating the extra evaluation of the square-root function.

As intuitive as it sounds, this is not always the case with imperative languages. A case in point is the C programming language's getchar() "function", which is strictly a function not of its arguments but of the contents of the input stream stdin and how much has already been read. Following the example above:

 	z = f(getchar(), getchar());

we cannot eliminate getchar() as we did for sqrt(2), because in C, "getchar()" might return two different values the two times it is called.

Hidden side-effects are in general the rule, rather than the exception, of traditional programming languages. Whenever a procedure reads a value from or writes a value to a global or shared variable, the potential exists for hidden side effects. This leakage of information across procedure boundaries in ways that are not explictly represented by function calls and definitions greatly increases the hidden complexity of programs written in conventional non-functional languages.

By removing these hidden information leaks, functional programming languages offer the possibility of much cleaner programs which are easier to design and debug. However, they also offer other benefits.

Many programmers accustomed to the imperative paradigm find it difficult to learn functional programming, which encompasses a whole different way of composing programs. This difficulty, along with the fact that functional programming environments do not have the extensive tools and libraries available for traditional programming languages, are among the main reasons that functional programming has received little use in the software industry. Functional languages have remained largely the domain of academics and hobbyists, and what little inroads have been made are due to impure functional languages such as Erlang and Scheme. It could be argued that the largest influence of functional programming on the software industry has been by those academically trained programmers who have gone on to apply the impure functional programming style to their work in traditional imperative languages.

Greater expressiveness: "new forms of glue"

A powerful mechanism sometimes used in functional programming is the notion of higher-order functions. Functions are higher-order when they can take other functions as arguments, and/or return functions as results. (The derivative in calculus is a common example of a function that maps a function to a function). Higher-order functions were studied long before the notion of functional programming existed, in the lambda calculus, a formalism which has influenced the design of several functional programming languages, especially the Haskell programming language.

Chapter 4 - Functional Programming - of Raphael Finkel's Advanced Programming Language Design is an excellent introduction to and explanation of functional programming. Here's a link to the chapter (ftp://ftp.aw.com/cseng/authors/finkel/apld/finkel04.pdf), and here's AddisonWesley's page for the book (http://cseng.aw.com/book/related/0,3833,0805311912+20,00)

See also:

• lazy evaluation
• eager evaluation

Offsite Link

Why Functional Programming Matters (http://www.math.chalmers.se/~rjmh/Papers/whyfp)