Skip to content

Peter Naur

Abstract

Peter Naur (1928–2016) was an astronomer who became the editor of the ALGOL 60 report, the document that taught the computing world how to define a programming language precisely. His name is the N in Backus-Naur Form, an attribution he spent decades trying to decline. He built Denmark’s first compiler group at Regnecentralen, founded computer science as an academic subject in Denmark under a name he preferred (“datalogi”), and then spent the second half of his career arguing that the formalists had it backwards: that a program is not a text or a mathematical object but a theory held in a programmer’s head, and that when the people leave, the theory dies and no amount of documentation brings it back. He won the 2005 Turing Award for the work he had done by 1963 and used the platform to attack most of what the field had done since.

Nemausa

Naur was born in Frederiksberg, Denmark on October 25, 1928. His subject was astronomy, and he was good at it early: he was writing the comet column in Nordisk astronomisk tidsskrift from 1944, at fifteen, and entered the University of Copenhagen in 1947, taking his astronomy degree in 1949. He spent 1950 and 1951 as a research student at King’s College, Cambridge, where he wrote an EDSAC program for the perturbed motions of minor planets: twenty seconds of machine time for what took two hours by hand. He earned his doctorate from the University of Copenhagen in 1957 with a thesis on the minor planet 51 Nemausa and the fundamental system of declinations.

Celestial mechanics is arithmetic performed at length, and it pulled a generation of astronomers into computing. Naur was one of them. By the late 1950s he had stopped doing astronomy.

The Report

In 1959 he joined Regnecentralen, Denmark’s first computer company, where he worked in the compiler group until 1969. He also joined the international committee assembling a successor to ALGOL 58.

ALGOL 58’s specification was written in prose, and prose left gaps. Implementations diverged wherever the wording was loose. At the Paris meeting in January 1960 the committee agreed the language needed a definition with no room to interpret, and Naur was made editor of the resulting Report on the Algorithmic Language ALGOL 60.

He did two things that mattered. He took the syntax notation John Backus had proposed for ALGOL 58, tightened it, and used it to define the whole language in a few pages of rules. And he edited ruthlessly, producing a specification short enough to read in an afternoon and exact enough to implement from. The notation became Backus-Naur Form, and it is still how programming languages, internet protocols, and data formats are specified. The language and the notation are covered in ALGOL and the ALGOL Family, The Compiler, and The History of Parsing.

Naur objected to the name. Donald Knuth proposed calling it Backus-Naur Form in a 1964 letter to the ACM; Naur’s position was that the notation was Backus’s and that “Backus normal form” was the correct term. He lost that argument permanently. He also pushed successfully for recursion in ALGOL 60, which several committee members thought was an unnecessary complication, and which turned out to be one of the features the language is remembered for.

Back in Copenhagen he led the team that wrote GIER ALGOL, a full ALGOL 60 compiler for Regnecentralen’s GIER machine. Work started on January 5, 1962; a running version existed that August and the final one was distributed in February 1963. The constraint was the machine: 1,024 words of core store and 12,800 words on a drum, which forced a compiler organised as a chain of passes swapped in from the drum one at a time. It was among the first complete implementations of ALGOL 60 anywhere. He also co-edited, with Brian Randell, the report of the 1968 NATO conference in Garmisch that named the software crisis.

Datalogi

In 1966 he renamed the courses he was teaching datalogi, the study of data and its use, refusing “computer science” on the grounds that it names the machine rather than the subject. Copenhagen set up a chair of datalogi in 1969 with Naur as its first holder, and he built the institute around it; he held the chair until 1998. Denmark and Sweden adopted the word; the rest of the world did not. The department at Copenhagen is still called Datalogisk Institut.

The objection was not pedantry. Naur’s view was that the discipline’s proper object is what people do with data and what programs mean to the humans who write and maintain them, and that a field named after its hardware would keep mistaking the machine for the problem.

Against Formalism

Through the 1970s the field’s centre of gravity moved toward proving programs correct. Edsger Dijkstra, Tony Hoare, and Niklaus Wirth argued that programming should become a branch of mathematics: derive the program from the specification, prove it meets the specification, and the bugs have nowhere to hide.

Naur, who had written one of the tightest formal specifications in the field’s history, disagreed. His argument was empirical: he studied how programmers actually worked, ran experiments on program comprehension, and concluded that formal proof addressed a small and not especially dangerous class of errors while consuming the effort that should go into understanding the problem. He was blunt about it, and the dispute with Dijkstra was personal as well as technical.

His clearest statement is the 1985 paper Programming as Theory Building. The argument: the valuable product of programming is not the source code but the theory the programmers hold, their grasp of why the program is shaped as it is, which parts of the world it models, and how it would have to change if the world did. Source code and documentation are shadows of that theory and cannot reconstitute it. It follows that a program whose original team has dispersed is effectively dead even though it still compiles; that maintenance by people who never held the theory produces decay; and that program lifetime is bounded by the lifetime of the group, not the code. The paper is short, went almost unnoticed for twenty years, and now circulates among working programmers more widely than anything he wrote apart from the ALGOL report.

His later work went further from computing, into psychology and philosophy of mind. He proposed a “synapse-state theory of mental life”, rejected the idea that the nervous system resembles a computer, and dismissed the Turing test as resting on a bad analogy.

The Award

ACM gave Naur the Turing Award for 2005, cited for contributions to programming language design and the definition of ALGOL 60, to compiler design, and to the art and practice of computer programming. He was 77, and the work being honoured was more than forty years old.

He used the lecture, “Computing versus Human Thinking”, to say that most of what the field had built on top of that work was mistaken. He opened by naming his theory of the nervous system as the fulfilment of his career, restated his rejection of computer science as a name and a self-conception, dismissed the Turing test, and said he expected to offend part of the audience. It was not the retrospective they came for. It was consistent with everything he had said since 1970.

Naur died on January 3, 2016, aged 87, after a short illness.

📚 Sources