The Short Story1
Spreadsheets and SQL are both fairly specialized languages. Functional programming languages take the same ideas and move them into the realm of general-purpose programming. To get an idea of what a functional program is like, and the expressiveness of functional languages, look at the following quicksort programs. They both sort a sequence of numbers into ascending order using a standard method called "quicksort".
Whereas the C program describes the particular steps the machine must make to perform a sort — with most code dealing with the low-level details of data manipulation — the functional program encodes the sorting algorithm at a much higher level, with improved brevity and clarity as a result.
Quicksort in C
void qsort(int a[], int lo, int hi) {
{
int h, l, p, t;
if (lo < hi) {
l = lo;
h = hi;
p = a[hi];
do {
while ((l < h) && (a[l] <= p))
l = l+1;
while ((h > l) && (a[h] >= p))
h = h-1;
if (l < h) {
t = a[l];
a[l] = a[h];
a[h] = t;
}
} while (l < h);
a[hi] = a[l];
a[l] = p;
qsort( a, lo, l-1 );
qsort( a, l+1, hi );
}
}
Quicksort in Clojure
(defn qsort [[head & tail]]
(when head
(lazy-cat (qsort (filter #(< % head) tail))
[head]
(qsort (remove #(< % head) tail)))))
Quicksort in Erlang
qsort([]) -> [];
qsort([X|Xs]) -> qsort([ Y || Y <- Xs, Y < X]) ++ [X] ++ qsort([ Y || Y <- Xs, Y >= X]).
Quicksort in Haskell
qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
Brevity
Functional programs tend to be much more concise than their imperative counterparts. Quicksort is a rather extreme case, but in general functional programs are much shorter (by a factor of two to ten).
Ease of Understanding
Functional programs are often easier to understand. You should be able to understand the program without any previous knowledge of Clojure/Erlang/Haskell (or qsort).
Powerful Abstractions
One powerful abstraction mechanism available in functional languages is the higher order function. In a functional programming language, a function is a first-class citizen; it can freely be passed to other functions, returned as the result of a function, stored in a data structure, and so on. It turns out that the judicious use of higher order functions can substantially improve the structure and modularity of many programs.
The Long Story
In his paper Why Functional Programming Matters (written in 1984) John Hughes tells us that:
The special characteristics and advantages of functional programming are often summed up more or less as follows. Functional programs contain no assignment statements, so variables, once given a value, never change. More generally, functional programs contain no side-effects at all. A function call can have no effect other than to compute its result. This eliminates a major source of bugs, and also makes the order of execution irrelevant - since no side-effect can change the value of an expression, it can be evaluated at any time. This relieves the programmer of the burden of prescribing the flow of control. Since expressions can be evaluated at any time, one can freely replace variables by their values and vice versa - that is, programs are “referentially transparent”. This freedom helps make functional programs more tractable mathematically than their conventional counterparts.
We are not experts in this field, so we will continue by quoting from another paper written by someone who is. Beautiful Concurrency begins:
The free lunch is over. We have grown used to the idea that our programs will go faster when we buy a next-generation processor, but that time has passed. While that next-generation chip will have more CPUs, each individual CPU will be no faster than the previous year’s model. If we want our programs to run faster, we must learn to write parallel programs. Parallel programs execute in a non-deterministic way, so they are hard to test and bugs can be almost impossible to reproduce. For me, a beautiful program is one that is so simple and elegant that it obviously has no mistakes, rather than merely having no obvious mistakes.
And then continues:
To make a long story short, today’s dominant technology for concurrent programming – locks and condition variables – is fundamentally flawed. Here are some standard difficulties, some of which we have seen above:
- Taking too few locks. It is easy to forget to take a lock and thereby end up with two threads that modify the same variable simultaneously.
- Taking too many locks. It is easy to take too many locks and thereby inhibit concurrency (at best) or cause deadlock (at worst).
- Taking the wrong locks. In lock-based programming, the connection between a lock and the data it protects often exists only in the mind of the programmer, and is not explicit in the program. As a result, it is all too easy to take or hold the wrong locks.
- Taking locks in the wrong order. In lock-based programming, one must be careful to take locks in the “right” order. Avoiding the deadlock that can otherwise occur is always tiresome and error-prone, and sometimes extremely difficult.
Error recovery can be very hard, because the programmer must guarantee that no error can leave the system in a state that is inconsistent, or in which locks are held indefinitely. Lost wake-ups and erroneous retries. It is easy to forget to signal a condition variable on which a thread is waiting; or to re-test a condition after a wake-up. But the fundamental shortcoming of lock-based programming is that locks and condition variables do not support modular programming. By “modular programming” I mean the process of building large programs by gluing together smaller programs. Locks make this impossible.
And we would like to end with a few words from another expert in his field:
An imperative program manipulates its world (e.g. memory) directly. It is founded on a now-unsustainable single-threaded premise - that the world is stopped while you look at or change it. You say "do this" and it happens, "change that" and it changes. Imperative programming languages are oriented around saying do this/do that, and changing memory locations.
This was never a great idea, even before multithreading. Add concurrency and you have a real problem, because "the world is stopped" premise is simply no longer true, and restoring that illusion is extremely difficult and error-prone. Multiple participants, each of which acts as though they were omnipotent, must somehow avoid destroying the presumptions and effects of the others. This requires mutexes and locks, to cordon off areas for each participant to manipulate, and a lot of overhead to propagate changes to shared memory so they are seen by other cores. It doesn't work very well.
Functional programming takes a more mathematical view of the world, and sees programs as functions that take certain values and produce others. Functional programs eschew the external 'effects' of imperative programs, and thus become easier to understand, reason about, and test, since the activity of functions is completely local. To the extent a portion of a program is purely functional, concurrency is a non-issue, as there is simply no change to coordinate.
