The paradigms of programming Floyd, CACM 1979

(Also available in )

A couple of weeks ago we looked at Dan Bernstein’s very topical “thoughts on security after ten years of qmail 1.0.” From the general reaction I can tell that lots of you enjoyed reading that paper, but in the discussions that I saw, no-one was picking up on what I see as the real underlying secret to Bernstein’s success and progression as a software engineer. (Perhaps because it is one level of indirection away from the main topic of security in that paper). Here is my favourite extract again:

For many years I have been systematically identifying error-prone programming habits — by reviewing the literature, analyzing other people’s mistakes, and analyzing my own mistakes — and redesigning my programming environment to eliminate those habits.

In today’s paper choice we’ll be looking at some other ways of systematically improving your skills over time (along with quite a few other gems). In 1978 Professor Robert Floyd was presented with the ACM Turing Award for “helping to found the following important subfields of computer science: the theory of parsing, the semantics of programming languages, automatic program verification, automatic program synthesis, and analysis of algorithms.” Not a bad list! “The paradigms of programming” is his acceptance speech.

Today I want to talk about the paradigms of programming, how they affect our success as designers of computer programs, how they should be taught, and how they should be embodied in our programming languages.

Dominant at the time was the idea of structured programming (whose ideas are still very much with us today of course). The notion of starting with a top-down, stepwise refinement of the problem, and then building upwards from the primitives of the underlying machine to ‘meet in the middle’ with a set of more abstract modules and functions to be used by the top-down design. See e.g. ‘Program development by stepwise refinement’, and ‘On the criteria to be used in decomposing systems into modules’.

The structured programming paradigm is useful, says Floyd, but it’s not the only one. Programming paradigms are at the heart of this paper – and a reasonable interpretation of what Floyd means by paradigm here is, I think, ‘a strategy or tactic for solving a class of problems.’ That sounds a bit like a design pattern when I say it that way, but the examples Floyd gives us are at a slightly more fundamental level than those the phrase ‘design patterns’ conjures in my mind. Far more powerful than how many languages you know (in terms of syntax), is how many paradigms you are fluent with.

I believe that the current state of the art of computer programming reflects inadequacies in our stock of paradigms, and in the way our programming languages support, or fail to support, the paradigms of their user communities.

Computer science quickly breaks down into communities each with its own languages and dominant paradigms. The problem of falling into one of these and not escaping is that it becomes hard to see the fundamentals afresh and discover new approaches. Quoting from Kuhn in ‘The Structure of Scientific Revolutions’ :

The study of paradigms, including many that are far more specialized than those named illustratively above, is what mainly prepares the student for membership in the particular scientific community with which he will later practice. Because he there joins men who learned the bases of their field from the same concrete models, his subsequent practice will seldom evoke overt disagreement over fundamentals.

John Cocke invented the dynamic programming paradigm to solve a problem with the efficient parsing of context-free languages. Floyd discovered recursive coroutines as a structure while building hierarchical top-down parsers.

John Cocke’s experience and mine illustrate the likelihood that continued advance in programming will require the continuing invention, elaboration, and communication of new paradigms.

On developing as a programmer

So much for the advancement of the field, what about developing your own skills?

If the advancement of the general art of programming requires the continuing invention and elaboration of paradigms, advancement of the art of the individual programming requires that he expand his repertory of paradigms.

Here’s the technique that Floyd used to expand his own capabilities.

After solving a challenging problem, I solve it again from scratch, retracing only the insight of the earlier solution. I repeat this until the solution is as clean and direct as I can hope for. Then I look for a general rule for attacking similar problems, that would have led me to approach the given problem in the most efficient way the first time. Often, such a rule is of permanent value.

It can be hard to gain exposure to new paradigms from within your own immediate environment, because it’s likely your colleagues are all working within the same local paradigm set — witness job advertisements that specify the desired programming language (“The rules of Fortran can be learned within a few hours; the associated paradigms take much longer, both to learn and unlearn.”).

Floyd writes of an eye-opening experience of visiting MIT and seeing the power of Lisp first-hand (as someone grown up more in the tradition of Algol-like languages).

… my message to the serious programmer is to spend a part of your working day examining and refining your own methods. Even though programmers are always struggling to meet some future or past deadline, methodological abstraction is a wise long term investment.

On designing (and evaluating) programming languages

Everyone wants to design a new programming language. Bah! Floyd doesn’t find much satisfaction in the incremental extensions to existing languages (example: adding variant records to Pascal). Instead, it’s far more important to look at the paradigms a language supports.

I believe that the continued advance of programming as a craft requires the development and dissemination of languages which support the major paradigms of their user’s communities. The design of a language should be preceded by enumeration of those paradigms, including a study of the deficiencies in programming caused by discouragement of unsupported paradigms… If there is ever a science of programming language design, it will probably consist largely of matching languages to the design methods they support.

It’s not just the programming language itself of course, “the entire environment in which we program, diagnostic systems, files systems, editors, and all, can be analyzed as supporting or failing to support the spectrum of methods for design of programs.”

To persuade me of the merit of your language, you must show me how to construct programs in it. I don’t want to discourage the design of new languages; I want to encourage the language designer to become a serious student of the details of the design process.

On teaching programming

We have an unfortunate obsession with form over content (Floyd is speaking in 1978 remember, not a lot has changed in the intervening 40 years!). You can feel Floyd’s heart sink in the following exchange:

If I ask another professor what he teaches in the introductory programming course, whether he answers proudly “Pascal” or diffidently “FORTRAN,” I know that he is teaching a grammar, a set of semantic rules, and some finished algorithms, leaving the students to discover, on their own, some process of design.

We would do better to explicitly teach a set of systematic methods for all levels of program design. Students trained this way “have a large head start over those conventionally taught.”

To the teacher of programming… I say: identify the paradigms you use, as fully as you can, then teach them explicitly. They will serve your students when Fortran has replaced Latin and Sanskrit as the archetypal dead language.

How many paradigms do you have in your toolbox?