The annals of programming include a small but significant number of radical thinkers who propose total overhauls of our basic techniques for making computers perform useful tasks. One of them is the late John Backus. Backus was the central figure in the creation of FORTRAN — the archetypal first-generation “higher level” programming language — and the devising of the BNF (“Backus Naur Form” or “Backus Normal Form”), a formal method for specifying programming-language syntax.
In his 1977 Turing Award lecture, however, Backus stepped away from the world he’d helped shape and asked, “Can Programming Be Liberated from the Von Neumann Style?” It’s a question that gets at fundamentals, at breaking free of founding constraints. It’s like asking whether psychology could be liberated from Freud, or physics from Einstein.
Backus describes the prevalent Von Neumann paradigm of computing:
In its simplest form a von Neumann computer has three parts: a central processing unit (or CPU), a store, and a connecting tube that can tramsit a single word between the CPU and the store (and send an address to the store). I propose to call this tube the von Neumann bottleneck. The task of a program is to change the contents of the store in some major way; when one considers that this task must be accomplished entirely by pumping single words back and forth through the von Neumann bottleneck, the reason for its name becomes clear….
Surely there must be a less primitive way of making big changes in the store than by pushing vast numbers of words nback and forth through the von Neumann bottleneck. Not only is this tube a literal bottleneck for the data traffic of a problem, but, more importantly, it is an intellectual bottleneck that has kept us tied to word-at-a-time thinking instead of encouraging us to think in terms of the larger conceptual units of the task at hand.
(I will pause here to note the presence of that word “tube.” Perhaps Senator Ted Stevens, far from being a techno-rube, was actually a student of Backus.)
Taking off from the subtitle of his paper — “A Functional Style and Its Algebra of Programs” — Backus proposes a different approach from the Von Neumann standard: a “functional programming style” that, as far as I can tell, involves putting aside the whole concept of variables and data as separate from procedures, and instead concentrating on small functions that can be transformed through algebra-style techniques.
This is where the going gets hairy. I freely confess that I felt way over my head through much of Backus’s detailed description of the functional programming approach. I can’t tell whether this is because he is doing a poor job of explaining it, or because, despite my immersion in programming lore, I’m not much of a programmer and even less a mathematician — I’m reasonably willing to examine chunks of program code, but when I see a page full of formulas, my eyes get blurry and my mind wanders. (That is at least part of the explanation for why this installment of Code Reads is so absurdly tardy; the rest is just the usual overload.)
My question to you, my self-selecting think-tank and co-Code-Readers, is: Backus’s paper is 30 years old now. Was it a total dead end? Did some aspects of his idea eventually filter into real-world programming?
Since I took so long to write this piece I have the opportunity of pointing to some other thoughtful responses to Backus: Google’s Mark Chu-Carroll offers an in-depth review of the paper and suggests that, ironically, even though Backus’s functional programming solves many of the problems that distured him, “it’s just totally illegible in textual form” — which defeats one of Backus’s original purposes, of exposing in readable form the important actions of a program that, in traditional code, get hidden deep in the internals of repetitive loops.
Chu-Carroll also identifies the programming language Haskell’s concept of monads as a “reinvention” of one of Backus’s concepts.
Cleo Saulnier is even harder on Backus’s effort to outline a functional programming system: “The abrupt transition into hieroglyphs that only serve to confuse is rather curious considering the extensive sections devoted to how simple pure functional programming is supposed to be.” (I feel a little better now about my own befuddlement!)
There is also this review by Edsger Dijsktra (pointed out in a comment on the Mark Chu-Carroll post), who says, “the article is a progress report on a valid research effort but suffers badly from aggressive overselling of its significance, long before convincing results have been reached.”
It seems that my effort to honor the recently deceased and give a closer read to a paper I’d always found intriguing ended up backfiring to a large extent, and what should have been a two-week turnaround ended up taking two months.
Next time we’ll come up with something more fun — I promise!
UPDATE: I failed to include, in my roundup of other commenters on Backus’s paper, this entry by Andrew Sacamano, which concludes: “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.”
[tags]code reads, programming, john backus, functional programming[/tags]
There are no revisions for this post.