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.
Further reading:
The Functional programming reference in Wikipedia
This article is based loosely on notes I made at ACCU 2008 from attending the following talks:
- “Caging the Effects Monster: the next decade’s big challenge”, Simon Peyton-Jones
- “Functional Programming Matters”, Russel Winder
- “Grafting Functional Support on Top of an Imperative Language”, Andrei Alexandrescu
Any mistakes are almost certainly mine.
Successful Software 
I don’t know what you meant by that three equation examples, but it surely was not what you wrote (or at least I hope so)…
Peter,
There was a mistake. I have fixed it now. Thanks.
I hope that the fixed version still includes a mistake (or I’m really missing the point). Is the operator in the first equation correct?
I think with:
y = f(x) * f(x);
You really mean:
y = f(x) + f(x);
Else the other stuff underneath it isn’t quite true. Either than or you mean:
y = z * z;
(I love scheme, I really do…)
It’s inaccurate to say “the Perl 6 compiler is being written in Haskell.” Perl 6 is a specification, and there may well be multiple implementations, just like C or Java.
There is an implementation of Perl 6 being written in Haskell called Pugs, and there is also an implementation of Perl 6 being written in Parrot called Rakudo. For more information about Rakudo, see http://www.rakudo.org/
I think I have got the example right now. Doh! I’ve been up most of the night with a sick child. Thats my excuse and I’m sticking to it.
Andy,
I didn’t realise there were multiple implementation. Thanks for the clarification. It would be interesting to compare the two implementations for performance and number of lines of code.
“We can classify programming languages into a simple taxonomy”
Not so. It’s trivially easy to show that programming languages can’t be sorted into four neat little piles. The piles overlap. Like anthills built too close together, they share both outer surface and inner features. Prolog has functional features. CAML and Java have procedural features. Common LISP has a bit of everything. In fact, I believe your point is that functional features can be injected into the language of your choice.
Not only do the categories dissolve at the edges, they aren’t sufficiently bifurcated. Following Colmerauer, Prolog is a special case of constraint programming. To “fix” the diagram, CP should be pushed to the top and Prolog down a level, with its peers added. There are “pure” OOP languages like Smalltalk and impure ones like Java. This may be worthy of an additional level.
But this node-splitting produces increasingly disturbing results. For example, suppose instead of splitting on the attributes “pure” and “impure” one chose to split OOP on “(not) suitable for concurrent programs”. This would surely put Java in a separate pile from C++ and both rather far from the pile that contains Erlang. If instead one split OOP on “(non) contractual”, Eiffel would be king of its own hill while all the others would find themselves roomies.
The notion that programming languages can be sorted into a simple taxonomy is one of the persistent errors of computer science, as is the notion that issues with one branch of the tree can be resolved (or at least greatly improved) by an infusion of ideas from another branch. It is too bad that the 80’s fumblings of the Microelectronics Computer Consortium (MCC) are not more widely publicized. Then everyone would know that you can’t make a great leap forward by crossing functional and logic (FOOL) or all three of the not discredited paradigms (FLOOP). Instead, you get a mess.
Any useful sort on programming languages must be multi-dimensional, in terms of the attributes that give each language a reason to exist. Phrasing the debate in terms of four tired categories is a habit we all must break.
Memory plays tricks. Actually FOOL was the MCC hybrid of all three paradigms. Functional. Object-Oriented. Logic. More fool I, I blew the punch line. ;-}
Bob,
Obviously any classification of languages is going to be simplification of the reality. All sorts of other classifications are also possible. I think it usefully illustrates a point for this article nonetheless.
For anyone interested in functional programming, we are organising the First International Erlang eXchange in London on June 26th-27th.
http://www.erlang-exchange.com
With over 30 speakers, including Erlang Creator Joe Armstrong, Dennis Byrne (JInterface creator) and other experts, presenting talks, practical workshops and leading discussions on Erlang, concurrent programming and functional programming, this 2 day event in London will be the ultimate platform to learn, network and exchange ideas!
Tickets go at GBP 300, but if you register on or before May 1st, they are just 250. Tickets are limited to just 200 people and, particularly the last 2 weeks, tickets are going very very fast, so if you fancy coming, get your skates on!
More information and registration: http://www.erlang-exchange.com