This is the ninth edition of Code Reads, a series of discussions of some of the central essays, documents and texts in the history of software. You can go straight to the comments and post something if you like. Here’s the full Code Reads archive.
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]
Post Revisions:
There are no revisions for this post.
This was pretty fun and I’m glad you came up with it. Despite having done a short course ‘Foundations of Software Science’ as part of my BSc degree about 18 years ago, I had no idea of Backus’ contribution to FP. Reading this paper now made me realise that Backus must have been an influence on my lecturer.
I loved the idea of FP at uni, but I’m a little ashamed to say I’ve never seriously applied it since entering industry. (It’s gratifying to hear that others also find Backus’ paper a bit befuddling and illegible.)
A few months earlier I’d heard someone talking of their use of Ocaml, and so reading this paper made me feel it’s time to look into this corner again.
To answer your questions, the simple answers I think are yes and yes. Yes FP has been a dead end, but yes, aspects of Backus’ ideas have filtered into real-world programming. The latter, however, has been very slow. But a recent surf of (say) Ocaml users’ discussions is encouraging.
It seems to me that one thing that’s changed since I studied FP is that there are more people prepared to try working with unusual languages. This I suppose is partly a result of the explosion of the internet, Moore’s Law, and other factors. This has transformed a lot of other dead ends.
Another thing that’s changed is the wide adoption of Unix and related operating systems. When working with Unix it is very hard to escape the von Neumann bottleneck, since the successful Unix abstractions are things like processes, shells, and filters — all elaborations of von Neumann machines. Unix has allowed us to work with the von Neumann bottleneck very effectively, and discouraged us from thinking in other terms.
You shouldn’t feel better about your own befuddlement because of Vorlath… he’s always ranting about how he doesn’t understand functional programming. :-)
“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.”
I realize you’re working from a Judeocentric weltanschauung, but psychology goes back at least to Aristotle; and Newton is as much physics’ founder (if not more so) than Einstein.
Shalom, JR
Good point — I think there was an implicit “modern” modifying “psychology” and “physics” as I wrote. Similarly, of course, one could look well beyond Von Neumann to Babbage, Lovelace and so on. For every “founder” there’s always another pair of shoulders being stood upon…
I think it’s fair to say that the leading edge of academic research in programming languages is pretty much entirely dominated by functional languages, and has been for ages. Their semantics are much simpler, and they are more powerful and more fun to program in. Ideas first found in functional languages — garbage collection, type inference, parametric polymorphism (aka Java generics), first-class functions, list comprehensions, and so on — are trickling very slowly into the mainstream.
The rate of adoption has picked up recently, which is nice. It used to be that we were thirty to forty years of the mainstream, and now the lag ranges from ten to twenty years.
Neel makes a very interesting point – many of the ideas first found in functional languages have made it into the mainstream. But strict adherence to the core idea of functional programming – everything being a function, and the complete elimination of side-effects – make 90% of programming much harder.
Because FP languages are easy to create and implement, they provide a great experimental sandbox for the development of new ideas. I think this explains the number of innovative academic languages based on FP. They will continue to be a source of good ideas which will trickle out to the rest of the programming world. But I outside of a few algorithmically intense areas of programming, I don’t see FP taking off.
P.S. I also reviewed the paper: http://upayasoftware.blogspot.com/2007/04/code-read-9-john-backus-and-functional.html
There are efforts to get functional languages into the mainstream of commercial programming. Microsoft has developed a functional language, F#, that is being folded into the .NET environment. I haven’t followed their progress too closely, but I plan on looking at the language over the summer. Apress Publishing already has two books coming out on the language.
Being a bit of a devil’s advocate, where are the FP proponents? Although I feel that most of the time FP makes things more complicated, there are some times when it works really well.
Since nobody else is bringing it up, I guess I’ll be the first. Google’s MapReduce (Google it… my last link was very ugly) clearly and effectively solves a hard problem by organizing Von Neumann code using a distinctly FP approach. A lot of telecommunications software is written using functional languages (presumably the problems are primarily mathematically transforming lots of data in parallel, and thus are well suited to FP solutions), or so I’ve read. Does anyone have better examples? Has anyone built a commercial website, or desktop application using an FP language? How did it go?
Being a bit of a devil’s advocate, where are the FP proponents?
OK, I’ll bite. First of all, I must note: I am an academic, so my experience is not indicative of software engineering “in the trenches.”
I love FP. I program almost every day in OCaml, a primarily-functional mixed-paradigm language descended from ML. The nice thing about OCaml is it gives you access to the things about FP that make it nice and fun, while giving you recourse to imperative features (mutable variables) and an object system where necessary.
But of course it is exactly its these features that make OCaml non-“functional”, in the sense that Backus is advocating. What he seems primarily concerned with is “equational reasoning” and “referential transparency“: the desire to reason about and manipulate a program definition as if it were an algebraic entity. The only significant language I know of that supports “pure” FP in this sense is Haskell and its industrial adoption is close to (if not precisely) nil.
The main complaints I hear about FP in practice are not that it is impenetrable (it can be, but the combinatory style that Backus uses is discouraged; it is possible to give intermediate values names without introducing mutable variables!), but that:
(1) It is too abstract, in the sense that it can be hard to imagine the performance characteristics of the generated code from looking at the source. E.g., in OCaml, it is important to understand tail recursion if you don’t want your algorithms to crap out on large data structures. In Haskell, due to lazy evaluation, there are subtle ways to make the memory usage of a program explode (and one of those ways, it seems, is to use tail recursion!). In contrast, even in Java, the translation from source code to bytecode is straight-forward enough for the programmer to understand and reason about directly.
(2) Massaging a program through the type system is challenging. For one, the inferring type systems give bizarre and unhelpful error messages. For another, the subtle ways that modules and objects (in OCaml), type classes and monads (in Haskell), and parametric polymorphism (in both) interact is very difficult to learn and master. The payoff is you completely eliminate a broad class of runtime type errors (anything to do with pointers, or downcasting in Java).
The features that Neel listed as having trickled from FP to the mainstream—”garbage collection, type inference, parametric polymorphism (aka Java generics), first-class functions, list comprehensions”—none of these have much or anything to do with functional programming at all! (First-class functions are necessary, but not sufficient, to make a language “functional”.) These are just advanced language features that appeared first in the FP community for exactly the reason Neel cited: FP is where cutting edge language research happens.
P.S. For an even more dramatic example of the migration of PL ideas into practice, see Microsoft’s LINQ language. Its creator spent more than a decade hacking on Haskell. See also here for an article on OCaml’s use in the finance industry.
P.P.S. What’s with the no comment preview? I’m pretty sure this is going to be typo-rific.
Andrew said: strict adherence to the core idea of functional programming – everything being a function, and the complete elimination of side-effects – make 90% of programming much harder.
The consensus of the FP community is pretty much the opposite: that “pure” FP makes 90% of your work easier (and safer), while making things like I/O much harder. If your project is 90% I/O (and many projects are!), your experience will differ.
There seems to be a divide between academic, algorithmically-oriented programming and “real world” programming, where it seems most development effort is spent writing “glue” between pre-existing systems. The assumption seems to be that this “glue” is always ugly and non-algorithmic, and consistently resists any attempts at generalization and elegance.
I have no idea if this is true and I’m not going to wave my hands and pretend otherwise. But I suspect there will always be a place for C programming (at the systems level) and Perl programming (at the shell level), even as more and more programmers move to higher-level and FP-ish languages.
The paper does have relevance. The thing that I find strange is that no one seems to understand the core properties that makes FP possible. For example, above, you see someone mentioning Map/Reduce as if it’s something that has to do with FP. It does not. Map/Reduce is a flow based concept, not functional. The version used in FP is a limited version of it. Unfortunately, because the term ‘function’ has never been properly defined, the FP community saw it fit to associate anything under the sun to FP. Sad, but true.
And to John: I have never said I did not understand FP. There’s nothing in that paper or about FP that is even remotely foreign to me. What I’ve said about FP is that it’s an inconsistant system that cannot interact with external systems without breaking its own rules. For that reason, FP has serious limitations and is useless for the future of multiprocessing. This is the ‘glue’ code that most real life programmers need. FP doesn’t provide it. And it’s simple to see why if you understand the underlying principles… of these, none are taught in any school or university.
For something that is supposed to be simple, the terminology is left open-ended so that credit can be taken when it’s not appropriate to do so. Map/Reduce being the biggest example.
I’m not saying these things to be contentious either. It’s because there are too many programmers attached to a certain PL or programming system. Why is this? I do not care what I use just as long as it works. So I’m pointing out what’s really going on. On my blog, I get too many that think I’m emotionally caught up. I have no idea where this comes from because I dislike all languages equally. I use what works. Show me that it works regardless of terminology and I’ll use it. Otherwise, in /dev/null it goes. Guess where FP is.
Chris – thank you for a very cogent and balanced assessment of FP. I’ve been looking for something this clear for a while.
And your comment There seems to be a divide between academic, algorithmically-oriented programming and “real world” programming sparked an idea. I was thinking that the distinction between “real world” and “academic” carries a lot of unnecessary baggage, and despite being somewhat convenient, obscures deeper issues. Perhaps one cloud classify programming into three broad modes (bear with me a moment, please):
1) algorithmic – the raw manipulation of data is mathematical ways
2) conversational – the storage, retrieval, and transmission of data involving only basic manipulation
3) arbitrary – modeling external processes which where never designed to be algorithmic
In my daily work (I build “enterprise” applications, typically for large companies) 90% of what I face is conversational and arbitrary – moving data between systems with essentially straightforward syntax transformations, and following business processes which were never meant to be rational (as an engineer or mathematician understands “rational”).
“Academic” software probably tends to be more algorithmic and conversational, since there is little that is intellectually interesting and rewarding in arbitrary software. Yet many other “real world” programmers also build software which is at its core highly algorithmic, and merely wrapped in arbitrary or conversational wrapper. So Google’s MapReduce would fall into this case, as would Photoshop plugins, industrial optimization software, and so on. This sounds like what your work involves as well.
Anyhow, I may have to take a look at OCaml. It sounds like it might allow you to use FP approach for the algorithmic portions of your code, while using more imperative techniques for the rest.
Cleo, I’m curious about your assertion that MapReduce is not FP, but rather flow based. I think this is along the lines of your earlier comments about eliminating the execution point. This also seems to be quite consistent with the more pure strains of FP. Can you say more about the difference?
Also, have you ever heard of a language called Prograph. Instead of writing code, a program was specified as a dataflow diagram, with data flowing along directed edges between nodes representing operations. Operations could execute whenever all of their data was available, and execution order was unspecified – the whole thing was inherently parallelizable (provided you had a suitable algorithm), and once you got the hang of it, programmers could be very productive. Sadly, there are no current interpreters/compilers, but back in the day Prograph CPX was a fantastic development environment to work with.
Andrew, I suspect we may be sailing right past the real divides between the “academic” and the “real” worlds, which are: (a) performance, and (b) what Joel Spolksy calls the language ecosystem, the giant stack of libraries and development tools that make it possible to develop modern, web-enabled, Unicode-aware, blah blah blah, software. I think that language developers are painfully aware of both of these issues.
As regards (a), things are Not That Bad. Take a look at the language shootout numbers (grain of salt and all that), which show that OCaml, SML, and Haskell are all in the “reasonable” range between C and Java. If you go functional, you pay a small price in performance and a moderate price in coping with the static type system (and, in Haskell, a steep price in learning how to use monads to manage side effects) which yields a large savings in not having to debug crazy runtime errors (memory leaks, use-after-free, null pointers, etc.)
(b) is really a chicken-egg problem which won’t get solved until a big corporation steps up and wills the ecosystem into existence. This may be happening right now with F#, which is a first-class citizen of the .NET kingdom. (Although the monarch of .NET is OOP, so F# may, in the end, gain the ecosystem, but lose its (functional) soul.)
Andrew: I’m not familiar with Prograph. I went on wikipedia to see what was there and it appears to be a dataflow environment that works exactly as you specify. Your statement “Operations could execute whenever all of their data was available” is right on target as to how dataflow can be made distributed. I think there’s power there (and I personally want to expand on the ideas of FBP) and many languages are starting to have their own version of this. I believe ‘arrows’ are what they are called in Haskell for example. This is yet another case of a data flow concept being called FP when it is far from being so.
As to the differences, FP does have an execution point while data flow does not. It’s just that it’s very difficult to see because ALL data ALWAYS has an execution point in FP. Because there is a one to one relationship between data and their transformation, you can control execution via its associated data relationships. If one does not know better, they would think there’s no execution and that this is the best you can get. Unfortunately, the way functions are used, it cannot send data and leave it there for another ‘entity’ to do something with it. I call this a side-effect, but there are some that believe otherwise because it only affects an external system. A view I cannot agree with. Yet, this leaving behind of data is the prime requirement for distributed computing. Note that FP is fine for distributed delegation though.
So what is the difference in Map/Reduce? With the data flow mechanism, you can input data at any time from any source. The data flow network cares not where the data comes from. To be pure FP, you cannot do this. You need all the data before you can map it. So that’s why you have lazy lists and monads and all sorts of extensions to make these things fit more closely to the FP paradigm. Some people believe that these things are in fact FP. I do not because you have internal state changes. In any case, no matter what you call it, there are things going on that are no different than imperative or data flow when it comes to communicating with the external world.
An interesting example of functional languages used in the telecommunication industry is Erlang. It was first developed at and is mostly used by Ericsson.
Erlang white paper: http://www.erlang.org/white_paper.html
It is based around the concept of processes that communicate by passing messages to each-other. So while each process acts like a program in a functional language, there is some overall system state defined by the message queues of the processes.
It includes a lot of other features to support fault-tolerance, transparently accessing processes on distributed nodes, and dynamic code updates. Mostly features that are useful in distributed systems that must respond to many parallel queries.
In response to the comment by Cleo Saulnier above, Erlang is well-adapted to multi-core programming. Program logic is defined in a functional style, and the interpreter provides the “glue” that is necessary to communicate data between different CPUs, perform load-balancing, etc.
I am also surprised by Cleo’s comment that, “none [of the FP principals] are taught in any school or university.” I know at least two universities, Waterloo and MIT, that offer introductory CS courses in Scheme and provide an overview of FP in the process.