Peter Naur’s passing

Danish computer science pioneer, Peter Naur, died on January 3 2016 after a short illness, aged 87.

peter_naur source


Peter Naur received the ACM Turing award in 2005 for “…fundamental contributions to programming language design and the definition of Algol 60, to compiler design, and to the art and practice of computer programming”.

He is best known as the original editor of the Algol 60 Report, and as the “N” in BNF or Backus-Naur Form (with John Backus of Fortran, and other, fame), first used to describe the syntax of Algol 60. He objected to this and thought BNF should denote Backus-Normal Form instead. Nevertheless, MacLennan (1983), in Principles of Programming Languages: Evaluation and Implementation), notes the following about the connection between BNF and Naur:

Peter Naur, then the editor of the Algol Bulletin, was surprised because Backus’s definition of Algol-58 did not agree with his interpretation of the Algol-58 report. He took this as an indication that a more precise method of describing syntax was required and prepared some samples of a variant of the Backus notation. As a result, this notation was adopted for the Algol-60 report…

I gave examples of BNF from the Report along with Algol code fragments in a talk I gave to the Australian Computer Society about the 50th anniversary of Algol 60. Compiler construction tools like lex & yacc arose from the creation of BNF and variations such as EBNF (with which I have spent more time) led to more expressive and concise programming language grammars and still more powerful tools.

Alan Perlis commented in 1978, with a pun on the begin and end keywords used to delimit code blocks, that:

Algol’s is the linguistic form most widely used in describing the new exotic algorithms…Where important new linguistic inventions have occurred, they have been imbedded usually within an Algol framework, e.g. records, classes, definitions of types and their operations,…, modules. Algol has become so ingrained in our thinking about programming that we almost automatically base investigations in abstract programming on an Algol representation to isolate, define, and explicate our ideas…It was a noble begin but never intended to be a satisfactory end.

Others have remarked upon the contribution of Algol:

Here is a language so far ahead of its time that it was not only an improvement on its predecessors but also on nearly all its successors. (1980 Turing Award Lecture, C.A.R. Hoare)

Lisp and Algol, are built around a kernel that  seems as natural as a branch of mathematics. (Metamagical Themas, Douglas Hofstadter)

Algol 60 lives on in the genes of Scheme and Pascal. (SICP, Abelson & Sussman)

Block structure, lexical scope, and recursion are just a few features that no Pascal, C/C++, Python, Java, C# or  programmer would find surprising. Naur and his collaborators played a large part in shaping the programming languages we think and code in today. Scheme is a dialect of Lisp — Lisp predating Algol — that was ultimately influenced by it, e.g. lexical scope and by the “language report” document approach (see Revised Report on the Algorithmic language Scheme).

As Perlis alludes to above, many of the beneficiaries of the descendants of Algol are unaware of how their language constrains the way in which they think about programs and programming, the Sapir-Whorf hypothesis in action.

The late Dutch computer scientist, Edsger Dijkstra remarked:

Several friends of mine, when asked to suggest a date of birth for Computing Science, came up with January 1960, precisely because it was Algol 60 that showed the first ways in which automatic computing could and should and did become a topic of academic concern.

Naur started his career as an astronomer, but changed his profession after encountering computers. He was not fond of the idea of programming as a branch of mathematics and saw it as very much a human activity, the sub-title of a 1992 book (Computing: A Human Activity) by Naur. Section 1.4 entitled Programming as Theory Building challenges the simplistic Agile mantra that source code is all that matters, whereas in fact, like JPEG image files, it can be seen as a lossy format, a distillation of a programmer’s thoughts with lost context, mitigated only in part by appropriate comments (an art form in itself).



In Programming as Theory Building, Naur outlines scenarios relating to writing a compiler for similar languages and the development of a large real-time industrial monitoring system. In his words:

The conclusion seems inescapable that at least with certain kinds of large programs, the continued adaption, modification, and correction of errors in them, is essentially dependent on a certain kind of knowledge possessed by a group of programmers who are closely and continuously connected with them.

Naur was offered a professorship in computer science at the University of Copenhagen in 1969. He thought that computer science was fundamentally about the nature and use of data, didn’t much like the phrase and coined the term datology, which he thought had a more human orientation, giving rise to what has been called the Copenhagen interpretation of computer science (as opposed to quantum physics).

Later in his career, Peter Naur was critical of contemporary conceptions of science and philosophy, developed a theory of human thinking called Synapse-State Theory of Mental Life, contrasted human vs computer thinking (see this video) and rejected the possibility of strong AI. I may not agree with all of Naur’s ideas in this area, but consider them worth hearing.

As an aside, this Y-Combinator post about Naur’s passing makes the interesting observation that a number of widely used programming languages other than Algol 60 have Danish origins, e.g.

  • PHP (Rasmus Lerdorrf)
  • Turbo Pascal, Delphi, C# (Anders Hejlsberg)
  • C++ (Bjarne Stroustrup)

It has occurred to me increasingly in the last few years that many of our field’s pioneers are reaching the end of their lives. Even confining oneself to those associated with programming language design and implementation, since 2010, at least the following have died:

  • Denis Ritchie: C
  • John McCarthy: Lisp
  • Robin Milner: ML
  • Peter Naur: Algol

Before I started writing this post, I knew about Naur’s association with Algol 60 and BNF, but that’s about all. Now I’ve discovered that, like so many pioneers, he had depths I have only just started to explore, even if confining myself to his work Computing: A Human Activity.


Leave a Reply