FP | Successful Software

We can classify programming languages into a simple taxonomy:

Commercial programmers have overwhelmingly developed software using imperative languages, with a strong shift from procedural languages to object oriented languages over time. While declarative style programming has had some successes (most notably SQL), functional programming (FP) has been traditionally seen as a play-thing for academics.

FP is defined in Wikipedia as:

A programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data.

Whereas an imperative language allows you to specify a sequence of actions (‘do this, do that’), a functional language is written in terms of functions that transform data from one form to another. There is no explicit flow of control in a functional language.

In an imperative language variables generally refer to an address in memory, the contents of which can change (i.e. is ‘mutable’). For example the rather unmathematical looking “x=x+1” is a valid expression. In FP there are no mutable variables and no state.

In an imperative language a function can return different values for the same input, either because of stored state (e.g. global or static variables) or because it is interfacing with an external device (e.g. a file, database, network or system clock). But a pure functional language always returns the same value from a function given the same input. This ‘referential integrity’ means an FP function call has no ‘side-effects’ and consequently can’t interface with external devices. In other words it can’t actually do anything useful – it can’t even display the result of a computation to your VDU. The standard joke is that you only know a pure functional program is running because your CPU gets warmer.

The functional language Haskell works around the side-effects issue by allowing some functions to access external devices in a controlled way through ‘monads’. These ‘impure’ functions can call ‘pure’ functions, but can never be called by them. This clearly separates out the pure parts of the program (without side-effects) from the impure ones (with side-effects). This means that it is possible to get many of the advantages of FP and still perform useful tasks.

FP is much closer to mathematics than imperative programming. This means that some types of problems (particularly algorithmic ones) can be expressed much more elegantly and easily as functional programs. The fact that a function has no side effects also means that it’s structure is much easier to analyse automatically. Consequently there is greater potential for a computer to optimise a functional program than an imperative program. For example in FP:

y = f(x) + f(x);

Can always be rewritten as:

z = f(x);

y = 2 * z;

Saving a function call. This is more difficult to do in an imperative language, because you need to show that second call to f(x) won’t return a different value to the first.

Functional programs are also inherently much easier to parallelise, due to the lack of side-effects. We can let the FP interpreter/compiler take care of parallelism. No need to worry about threads, locks, critical sections, mutexes and deadlocks. This could be very useful as processors get ever more cores. However imperative languages, with their flow of control and mutable variables, map more easily than functional languages onto the machine instruction of current (von Neumann architecture) computer. Consequently writing efficient FP interpreters and compilers is hard and still a work in progress.

Elements of FP are steadily making their way into mainstream commercial software:

Erlang is being used in commercial systems, including telecoms switching systems.
Microsoft Research has implemented F#, a .Net language that includes FP elements based on ML.
Work is underway to add elements of FP to version 2.0 of the D programming language.
Google’s MapReduce is based on ideas from FP.
The Mathematica programming language has support for FP.
The K programming language is used in financial applications.
The Perl 6 compiler is being written in Haskell. <insert your own sarcastic comment here>.

I recently attended ACCU 2008 which had a whole stream of talks on FP. All the FP talks I attended were packed out. That is quite something given that the audience is primarily hardcore C++ programmers. There seemed to be quite a consensus in these talks that:

FP is starting to move out of academia and into commercial use.
FP is more suitable than imperative style programming for some classes of problem.
FP is not going to replace imperative programming. The bulk of commercial development will still be done in an imperative style, but with FP mixed in where appropriate.
Hybrid languages that mix OO and FP will become more common.

I don’t see Haskell replacing C++ any time soon. But I can definitely see the benefits of using FP to tackle some types of problems.