“No Silver Bullet” and Functional Programming

(((This was originally posted on December 6th 2006 on Blogthing. It is reposted here because Blogthing seems to be permanently down. The original was posted to Programming Reddit and extensively discussed at the time, so please do not resubmit this version.)))

-----

This post is about No Silver Bullet by Fred Brooks. If you haven’t already read this paper then trust me, you really should. It says a lot, and it says it far better than I ever could.

In this post I’m going to look at this paper in the context of functional programming. Brooks thesis is that there will be no technology that brings an order-of-magnitude improvement in software productivity “in the next ten years” (i.e. in the years 1987 - 97). This is because most of what makes software difficult to write is “essential” complexity (i.e. inherent to the problem) rather than “accidental” complexity (i.e. bought in by the implementation technology).

Brooks’ career had in fact spanned the adoption of a silver bullet. High level languages had replaced assembler, and led to an order of magnitude improvement in productivity. Brooks argued that assembler has a very high accidental complexity, but high level languages like C and Ada had already disposed of most of this, leaving only the essential complexity. Therefore the big wins had all been achieved, and only small incremental improvements were left.

In fact Brooks has already been proved right. It is now almost 20 years after he wrote, and no order-of-magnitude step has occured in mainstream software. Things have certainly gotten better, and some application domains have improved by an order of magnitude thanks to application frameworks. Ruby On Rails is certainly that much better for writing web apps than raw C on top of sockets. But outside of these niches software is still not much easier to write than in 1987. OO helped, but not by an order of magnitude. Garbage collection also helped, but again not by an order of magnitude.

Brooks argument that only essential complexity was left is founded in the size of the
state space of software. As the data and necessary processing increases, so the number of possible states grows. The data and processing are inherent to the problem, and so are therefore essential
rather than accidental: any technology must grapple with the same complexity.

But now lets look at this argument in the context of functional programming. Back in 1993 the US Navy ran a little test of prototyping languages: experts in several different languages were given a simplified spec
taken from a real problem and asked to implement it. Some results:

• Ada 83: 767 lines

• Ada 95: 800 lines

• C++: 1195 lines

• Haskell: 85 lines

So on that particular problem Haskell really was an order of magnitude better than conventional languages. Other studies have confirmed this result, although usually with somewhat lower degrees of improvement. Ulf Wiger wrote a paper called Four-fold Increase in Productivity and Quality about the use of Erlang in an ATM switch, although in the paper Wiger claimed to have seen as much as a 10-fold reduction in line count when C++ code was rewritten in Erlang. The Haskell implementation of getOpt took a mere 13% of the line count of the GNU C version. However you slice it, it looks like functional programming can deliver between 4 and 10-fold reduction in line count.

But is this truly a reduction in complexity, or is it just packing that the same into fewer lines? I believe the former, for two reasons.

First, Wiger reports that defect count fell in proportion to line count (i.e. defects per thousand lines of code was constant, but with fewer lines the Erlang code had proportionately fewer bugs). This strongly suggests
that Erlang was indeed hiding accidental complexity from the developers.

Second, “pure” functional code has no side effects and stores no state. Thus it completely evades two kinds of accidental complexity that are inherent to any conventional “imperative” code:

• If the program lacks state, then there is no way that the number of states can become a problem.

• The order in which statements are executed, and hence the execution trace of the program, is completely irrelevant. Thus execution order is revealed as a major source of accidental complexity which Brooks mistook for essential complexity, but which is eliminated in pure functional programs.

Of course not everything can be pure functional. Erlang has functions with side effects, and so the order of execution matters for those. But they are only used when necessary e.g. for I/O). If the bulk of the code employs only pure functions then it gains these benefits in proportion.

Haskell goes even further than Erlang. Stateful code is fenced off by the type system using a mathematical construct called a monad, and fragments of monadic code can be passed around and stitched together without the side effects escaping to mess up the pure code. Within a monad most of the usual vices of imperative programming are possible (although an uninitialised variable takes real effort). But like Erlang the bulk of Haskell code does not in fact have side effects, and the resulting lack of state makes Haskell programs easy to understand and safe to modify.

There is one more source of complexity that Brooks did not in fact tackle in his paper: concurrency. In 1987 concurrency was not a major problem in most systems. But today it is becoming a serious headache. Today applications are increasingly distributed and concurrent, and the urrent trend towards multi-core CPUs will make concurrent programming a real imperative for high performance applications. But concurrency is very hard to get right first time, and very hard to debug when you get it wrong. In other words it is a huge source of accidental complexity.

Both Erlang and Haskell tackle concurrency. Erlang was designed for telecom applications, which require both concurrency and reliability in large amounts. Erlang implements a simple message passing model of
concurrency with light weight threads based on Hoare’s CSP formalism. This represented the state of the art when it was designed in the late 1980s and is still far more robust than the Java model of object-as-monitor.

Haskell, on the other hand, has recently introduced “software transactional memory” (STM), which provides transactional semantics for ordinary variables. This was originally tried during the 1990s, but the overhead of tracking every access to every variable made it too slow for practical use. But the Haskell
implementation cleverly exploits both the rarity of state in Haskell programs and the way the type system fences it in. Side effects can occur within a transaction, but only to special STM variables. The type checker guarantees that these side effects cannot escape from the transaction until it is committed. Thus a transaction can be tried, rolled back, and retried as often as necessary without any change in
the behaviour of the program.

Both of these systems are very effective at removing the accidental complexity of concurrency. Erlang
programmers think in terms of concurrent servers and clients exchanging information, where each individual server acts as a transactional machine and no client can ever see the server state half way through a transaction. Haskell provides much more direct transactional semantics, but the overall result is the same: the programmer can ignore the concurrency on their own bit of program without having to worry about the rest of the system.

So: is functional programming an actual bona-fide silver bullet as defined by Brooks? I believe it is.
Functional programming is based on a sound theory of scalable software engineering, and the empirical evidence clearly and consistently supports the theory.

So if its so good, why isn’t the whole world using it? That will be the subject of my next blog.