Code Read 9 - John Backus and Functional Programming

The 1977 Turing Award went to John Backus, and in his Turing Lecture, "Can Programming Be Liberated from the von Neumann Style?", he made a vigorous case against traditional "von Neumann" programming (VNP), and for functional programming (FP). Unfortunately, the vigorous rhetorical style of this paper has infused the discussion of FP, resulting in countless flame wars over the last 30 years. The overly broad and weakly supported statements that make up the bulk of the discussion often boil down to these:

"Traditional programming languages are clumsy. FP will solve all your problems, if only you are smart enough to use it."

versus

"FP is a toy. Nobody has done any real work with it, so it must be useless."

Both sides are throwing out the baby with the bathwater, and the good ideas of FP are tainted by their association with their more problematic brethren.

Backus's Paper

Let's start with Backus's paper. From the beginning, he clearly has an ax to grind - he describes conventional programming languages foundations as "complex, bulky, not useful", and conventional programs, while "moderately clear, are not very useful conceptually". Whereas, he says later in his paper, FP programs "can accommodate a great range of changeable parts, parts whose power and flexibility exceed that of any von Neumann language so far." Yet he makes very few points to support these statements.

Expressive Power and Simplicity

One of his recurrent themes is the superior "expressive power" of FP. When he does defines "expressive power", it is not clear that even under his definition FP is any more expressive than VNP. His definition revolves around on having functions that are expressible in one language and not in another, yet he offers no supporting example.

He also asserts that VNP languages are necessarily complex, requiring new features to be added to the language itself, rather than implemented using existing language features. As one of the creators of many VNP languages, he's more than entitled to make such statements. But newer languages (like C, and many OO languages) have reversed this trend by simplifying the underlying language and making it easier to define new functions. They do this without using using FP, so this argument also falls apart.

An Algebra of Programs

The most coherent argument in the paper, and also longest, is that FP allows a relatively straightforward mathematical theory of programming, which is much more difficult in VNP. This is true, but I'm not convinced it is that important. He proves the equivalence of two algorithms for matrix multiplication, and also discusses using this algebra of programs to optimize algorithms safely.

However, formal proofs of programs are only marginally useful, usually taking far longer to do well than to write an algorithm, and are just a prone to misunderstanding of the problem to be addresses. So while it may be easier to prove an FP algorithm does what it tires to do, it is just as hard to prove that what it tries to do correctly solves the underlying problem.

Optimization is important, but as I've argued before, the most effective optimizations involve using an newer algorithm that is not equivalent in a formal way, but only by virtue of a deeper understanding of the problem. For example I once had to optimize an algorithm which had to go through a list doing pairwise operations on each element and all previous elements (e.g. f(1,2), f(1,3), f(2,3), f(1,4), f(2,4), f(3,4),...) This approach takes big-O n-squared operations, so the implementation ran in seconds for n = 100, but took hours for n = 1000, and days for n = 10000. No amount of code optimization was going to improve that. But when I realized that there was a way to run it operating on the elements of the list and only a few previous elements, the program went from needing big-O n-squared operations to big-O n operations, which meant a run time of a few minutes even for n = 100000. No formal manipulations of the algorithm would ever have gotten me there, only the insight that most of the operations were unnecessary by virtue of the problem itself, not by virtue of the comparison algorithm.

Oddly, enough, when talking about this algebra of programs, Backus himself says that "severely restricted FP systems" are easier to analyze, "as compared with the much more powerful classical systems." He seems to be implying that the ease of analyzing FP systems justifies their restrictions, but I think the consensus view today is the other way. Outside of academic circles, formal analysis has never caught on.

Rethinking Computers from the Ground Up

One of the most visionary themes in his paper is the proposal that we change the way we relate to state (aka history, or storage). VNP relies on making many small, incremental, changes to the stored data in a computer. Thus the overall state of that data is consistent and meaningful only rarely - usually it represents a job half done. Moreover, subsequent, or concurrent execution runs the risk of operating on that inconsistent data, resulting in what is called "side-effects". Instead of operating piecewise on small bits of data, leaving the overall state inconsistent during the calculation, Backus proposed not just a programming style but a change in hardware that prevents these side-effects. Not only does this make it easier to analyze the code, it becomes trivial to split larger programs into smaller pieces of work, and run those pieces in parallel. Indeed, this idea seems to be the root of many the "FP" successes - for instance its use in telecommunications software, and in Google's MapReduce. However, I put FP in quotes, because this idea is a fringe benefit of FP, and can easily be implemented in traditional languages (in the right context), and even Ericssons's Erlang projects make extensive use of C libraries. Ironically, the most successful idea of FP - a formalized way to eliminate side-effects - seems to be a side effect itself.

Conclusions

Since Turing and Church proved that "Turning Machine Computable" and "Lambda Calculus Computable" are the same thing, and thus FP and VNP can perform exactly the same computations (with suitable extensions to FP), there are two basic questions. Is either one inherently better than the other in:
1) simplicity/ease of writing code (fewer bugs, easier to understand, better at expressing underlying problem space, easier to fix bugs)
2) speed of execution?

I do not find FP to be any more "expressive" or easier to understand than VNP (and my first programming language was LISP). If anything, the restrictions of FP make it harder to model some problems in code, and thus make it harder to understand that code. It is easier to optimize FP in some cases, and thus optimizations bugs are less likely. But these bugs are a small fraction of all bugs, and among the easier to fix once identified.

As for speed of execution, on existing hardware FP programs tend to be slower, whereas they may be faster on purpose build hardware. This is because of the elimination of side-effects. On conventional hardware, eliminating side-effects often requires duplicating data. On purpose-built hardware, eliminating side-effects allows automatic parallelization. So FP programs may be faster in cases where both problem and the hardware support simple parallelization. But parallelization is notoriously difficult, and automatic parallelization technique are only modestly successful on general problems. The marginal payoff of adding more processors quickly diminishes. Instead, special parallel algorithms need to be built which carefully manage data movement in the system, minimize duplication, and so on. These techniques are equally suited to FP and VNP.

So in the end, I think FP will fade away, except for leaving its name attached to extensions to VNP languages which encourage side-effect free programming for easier application to distributed systems. These extensions will prove to be very useful, especially as programming for the web, and programming for multicore processors becomes more and more common.

Hopefully the dogmatic proponents of FP will be satisfied by this, and the dogmatic detractors will be satisfied, so we can all move on to more productive discussions.

Read more...

Code Read 8 - Eric S Raymond's Cathedral and Bazaar

The ever evolving "The Cathedral and the Bazaar" by Eric S Raymond (aka CatB) has become something of a lengthy read. Scott Rosenberg's Code Read 8 dives on in, and rightly describes it as a "classic essay" and says it "has proved its importance" in the literature of software development. I first read it several years ago, it was considerably pithier then. However, it is still full of important ideas.

Cathedrals and Bazaars

The most important idea is its title track - two different ways to build software. In the "cathedral" style, a master architect and a small group of hand-picked skilled craftsmen work toward a grand vision with lots of direction and coordination. This is the traditional model of software development. The "bazaar" model, which is common to many open-source projects, particularly Linux, is one in which there are no hand-selected craftsmen, and no master plan. Instead the people in power select the best contributions from those people interested and able enough to contribute something worthwhile. The direction in which the project evolves is determined by the availability of volunteers willing to push it in that direction, as well as an entity, often an elected committee, which acts as an editor.

CatB presents a strong case that high quality software can be produced quickly and efficiently using the bazaar approach. Actually, to many people who just came into the software world in the last five years or so, this seems self-evident - Linux, Apache, MySQL, PHP, and Mozilla are just a few of the high-quality, feature rich, and reliable projects built in the bazaar mode. They are part of the landscape of the Internet which many take for granted. Yet less than 10 years ago there were many thoughtful, intelligent people who had serious concerns about the utility of any of these. Today, of course, the only people who seriously argue that open source development can not produce good software are those who have a stake in commercial alternatives. So while CatB's argument is convincing, it has already been won.

Much of CatB is also devoted to describing how successful open source projects work. If you are planning on running an open source project, these are must-read sections. But even if you are not, the idea of project leader as editor instead of architect is a very interesting one, and reflects a common gem of an idea in leadership theory that is subtle and often misunderstood: some of the best leaders do not lead by inspiring others to follow the leader's ideas, but rather the leader finds and supports the best ideas of the people they are leading. What makes Linus Torvalds (the creator and benevolent-dictator-for-life of Linux) such a genius is not his ability to write code or convince others of the correctness of his ideas (which both are probably impressive), but rather his ability to pick and choose the best from among the many contributions to Linux. There is a great deal that goes along with that style of leadership that is difficult for a type-A ego, and CatB delves into all of it with great insight.

The Twainian Passing of Closed Source Software

The second main thrust of CatB is that traditional management styles and closed-source software will ultimately be washed away under the coming wave of high-quality open source software and its management processes. This is a bit more controversial - and in some cases I think it is just plain wrong. Certainly it is possible that Apache may become the only web server anybody uses. It is also possible, although a bit more of a stretch, that open-source databases will replace commercial databases, or that Linux will become the dominant operating system, or that OpenOffice will become the only office productivity suite. But it unlikely that anybody but E-Bay will ever see the software that runs eBay, or that Google will ever open-source their search software. Sometimes, software is so tied to the fundamental service a business provides that there is just not enough interest in an open-source equivalent. We would all like to be making money like eBay, but how many of us are actually trying to write on-line auction software to match eBay's? There are simply to few developers to support it - especially since any E-Bay competitors needs to distinguish itself, which will probably require substantially different software. So there are some markets in which there is simply not enough demand for open-source software to make it viable.

Another example is corporate web sites, which will always be paid for in the traditional sense, even if they are built using entirely open-source software, simply because nobody but Acme Widgets needs an Acme Widgets web site.

This is one of the things I think Cat B misses in its open-source evangelism. Open-source projects work well when many programmers need the same thing to support the businesses they work for - so we see web servers, operating systems, programming languages and tools, web-site management software, a shopping cart or two, image and photo editing software, an office productivity suite, and so on. But the success of an open-source project depends on having a legion of programmers who need it. Yet CatB argues that commercial software is going away, along with all of the management processes that come with it.

I just do not buy it. Instead, I see the comercial software market becoming smaller, and more individualized. Nobody buys compilers anymore. GCC, gmake, Ant, Eclipise, and dozens of other free products all work fine. Moreover, support for open source products is often better than support for commercial equivalents. (I speak from personal experience.) A lot of software is going open source. But there will always be a market for software to support the specific business processes of individual organizations, which will require one-off construction - even if it does use off-the-shelf open-source components.

The Corporate Embrace of Open-Source

Indeed, many open-source projects are now significantly supported by companies (like IBM, RedHat, and others) that make money building exactly that kind of custom software. The underlying components are no longer something that distinguishes one competitor from another in the marketplace, so companies that compete against each other are joining forces to make everyone's job easier. Companies like IBM, RedHat, Oracle, and countless others are paying programmers to write code which the company will then give to its competitors.

This is one of the most interesting facets of the open-source revolution - the evolution of business strategy and corporate intellectual property policy in the face of the commodification of software infrastructure. In some ways, the software market has become an interesting experiment in altruism. More and more technology companies are realizing that despite superficial appearances, their software is not the core value they provide. And in that case, it makes financial sense to cooperate with their competitors (and anyone else who is interested) to build and maintain that software, while they focus on the what real value that they do provide.

P.S.

One final note - people can be slow to accept change. Some managers and programmers are still protective of "their" code against people in their own organization. This seems to me to be doubly backward, and I hope that as more and more open-source software succeeds, IT departments will learn let more open-source software practices through their cathedral doors. It can only make our lives easier.
Read more...