Now I’m in a post-Masters state (see earlier), I’m spending some time reading formative computer science papers, starting with lists from Michael Feathers and Mike “Fogus” (is that a pseudonym? I couldn’t tell) outlined here:

• 10 papers every programmer should read at least twice
• 10 technical papers every programmer should read at least twice

I’ve read a bunch of these now, and yesterday’s menu included John Backus’ Turing award paper “Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs”. I didn’t know much about Backus coming to this work, but I was familiar with the Backus-Naur form of notation. I learnt he led a team that created Fortran, and given that context the rest of the paper became more revealing. Essentially he says that the Von Neumann style is sub optimal because it relies on the assignment statement, and the management of state:

“The assignment statement is the von Neumann bottleneck of programming languages and keeps us thinking in word-at-a-time terms in much the same way the computer’s bottleneck does.” p615

This programming model, Backus argues, leads to defects and large rigid frameworks because it turns out to be much harder to reason about. He seems particularly heated considering assignment:

“The second world of conventional programming languages is the world of statements. The primary statement in that world is the assignment statement itself. All the other statements of the language exist in order to make it possible to perform a computation that must be based on this primitive construct: the assignment statement.” p616

Given this groundwork, Backus goes on to establish his vision for a better mode of programming, essentially functional programming without variables, a coherent algebra, precise definitions, and applicative state transition properties (where a subsystem has a state that is transformed via transition rules).

The paper continues with outlines of the algebra behind functional programming systems, and to be honest, I glossed over this section. I’m relatively weak on formal proofs, but I’ve read enough of them to realise I get to the end having been thoroughly convinced they are right, while also knowing that I’ll never get that time back. In this case, I’ve just taken them as proven. I want the big picture here, not the nitty gritty.

The next area of interest regarding this paper was not around the paper itself, but centering on the discussions I found. Firstly, over at C2, the discussion starts around whether FP really provides the benefits claimed, and that the Von Neumann style might be more approachable to begin with. There is the important point made that the issue is mutable state, not state per se. The last point worth noting from C2 is the highlighting of the context of the time is relevant: Backus was writing in a time where programming was dominated by Fortran, COBOL and Algol. This prompts us to consider his perspective if it were argued today.

Next, I visited the discussion at Lambda the Ultimate, where the discussion was a lot more detailed. One commenter there said: “I worked with Backus at IBM Research during 1974-1975, and I found his dedication to exploring a ‘variable-free’ approach to programming both inspiring and frustrating.” Other commenters say that Backus’s approach is most closely revealed in the J programming language.

The final discussion I reviewed was at Hacker News, where several commenters made the case that the flaw in the thinking is not taking into account the reality of time. State happens because of time, and that is the easiest reality for most people to relate to. Functional programming is thus harder to understand since it takes programs out of the context of time and into theory. Another take away from this discussion was being introduced to “dataflow” architecture, an architecture that contrasts with the typical Von Neumann control flow architecture, which was new for me. Finally, one commenter at Hacker News mentioned Dijkstra’s review of Backus’ paper. This was particularly interesting, Djikstra has some good points, effectively saying that Backus is claiming too much too soon.

Michael Feathers concluded his summary of this paper by saying “His arguments were convincing and they helped to set a research agenda which is just now starting to make some waves in the mainstream.” Functional programming seems to have been constantly gaining steam the last few years, and more and more mainstream relevancy, but considering this paper was written over thirty years ago, it seems it could be a long time till we’re all taking advantage of the FP paradigm in our professional lives.

My concluding thoughts and questions:

• If Backus was right 34 years ago, why are we not all living in a functional world now?
• What factors are holding back functional programming from mainstream acceptance?
• Could functional programming still need a critical insight to move it from theoretically better to practically better?
• Is there a perspective missing? While the Von Neumann style is not as elegant as functional programming, it is more approachable.