Erik Frøkjær
Copenhagen University

Edda Sveinsdottir
Roskilde University

This book is a selection of Peter Naur’s writings about computing, covering many scientific, technical, philosophical, and social aspects of the subject highly relevant to the situation of computing of today.
The selection contains those parts of Naur's work which we in our experience have found of greatest interest to our students, colleagues, managers of system development projects, and authorities responsible for education, research and public administration. The book also contains previously unpublished material, both completely new writings and writings of historical interest.
The idea to establish a collection came in connection with the 60th birthday of Peter Naur when we had occasion to make a detailed review of his work in computer science. Again, the viability of his ideas and the inner coherence of his diligent work over many years on essential aspects of the computing field were striking. Let us try to summarize:

First Peter Naur’s contribution to the development of the ALGOL language should be emphasized. The importance of the ALGOL 60 development in the history of computer science is indisputable, ALGOL 60 being a milestone in the development of programming languages, both by its new concepts and by the use of a formal notation for syntax, now known as the Backus-Naur-Form (BNF), introduced by J. W. Backus and given a final form in the Report on the Algorithmic Language ALGOL 60 [Naur et al., 1960, see section 2.1]. Most theoretical and much practical language and compiler work since 1960 has been based on ALGOL 60. Let us call Peter Naur’s special contribution to this development to mind through John Backus’s expression at a conference in 1978 on the history of programming languages: ‘One last thing I’d like to add is that Peter Naur’s conduct of the ALGOL–Bulletin and his incredible preparation for that Paris meeting in which ALGOL was all written down already in his notebook—he changed it a little bit in accordance with the wishes of the committee, but it was that stuff that really made ALGOL the language that it is, and it wouldn’t have even come about, I don’t think, had he not done that’. [Wexelblat, 1981, p. 162]
When ALGOL 60 was produced Peter Naur was a computer-oriented astronomer, recently switched fully to computing. The design of ALGOL 60 was followed immediately by his participation at Regnecentralen—at that time an independent institute of research and development of computers under the Danish Academy of Technical Sciences—in the development of compilers, for ALGOL 60, in several versions, for several computers, during the years 1960 to 1967, and for Cobol during 1963-65. Also this work is of a pioneering character. The GIER ALGOL compiler—called a masterpiece by Edsger W. Dijkstra—was based on viable ideas, such as automatic storage allocation during program execution (later known as paging), multipass translation, and pseudoevaluation of expressions [Naur, 1963a, in section 3.1]. A number of brilliant programmers and scientists were brought up at this outstanding programming milieu at Regnecentralen, among others Charles Simonyi and Per Brinch Hansen [see Lammers, 1986, and Brinch Hansen, 1970].
Building upon this experience, from about 1965 Naur saw the solutions developed by the group at Regnecentralen as examples of methods of wider applicability. Hence originated the text, written in 1966, of Outline of a Course of Datalogy and Datamatics [Naur, 1966a, in section 4.2], a paper given at IFIP 1968 [Naur, 1968, in section 4.4], repeated by invitation at The ACM’68 National Conference, and the book, from 1974, Concise Survey of Computer Methods [Naur, 1974]. Naur’s notion of computer science, understood as the science of the nature and use of data, more properly denoted datalogy, was original and contemporary with other early attempts to identify the new field. Thus George Forsythe [1967] was in line with Naur when emphasizing the importance of extracting and teaching the essence of computer science. Naur’s ideas became directly effective when an independent curriculum of datalogy was established at Copenhagen University, where, in 1969, the first chair of datalogy in Denmark was set up for Peter Naur. This tradition of computer science education is characteristic, first and foremost, by its maintenance of close connection with applications and other fields of knowledge. Comprehensive project activity is an integral part of the curriculum, thus presenting theory as an aspect of realistic solutions known primarily through actual experience obtained under active guidance from researchers and more advanced students. Under sometimes hard conditions a vigorous and effective computer science educational milieu with obvious professional qualities has been created. An account of the ideas behind datalogy as it has been practised at the Copenhagen University Institute of Datalogy is given in [Sveinsdottir and Frøkjær, 1988].
However, in Naur’s view this approach to computer science can be difficult to maintain. Though highly problematic, a widening split between the more academic, pure computer science oriented study of programming languages and the world of practical programming can be expected to persist indefinitely. Such problems among others are closely treated in Programming Languages, Natural Languages, and Mathematics [Naur, 1975, in section 1.3]. Here Naur gives a suggestive illumination of some social aspects of programming, drawing on similar historical experiences within natural languages and mathematics, the two closest relatives to programming among the intellectual disciplines.
For Naur an all-pervasive theme has been the study of programming and system development conceived as a human activity. This orientation is visible in his early contributions to the understanding of problems and techniques in program construction. A fine example is The Place of Programming in a World of Problems, Tools and People, presented at the IFIP Congress 1965 [Naur, 1965, in section 1.1]. Again we find original views from Peter Naur. In 1963, before anybody else, he wrote about a number of unfavourable effects of the unrestricted use of go to statements [Naur, 1963b, in section 5.1]. Donald E. Knuth tells the story in his paper Structured Programming With go to Statements [Knuth, 1974]. Naur was among the first to realize the need for more reliable and maintainable programming. In the paper Proof of Algorithms by General Snapshots [Naur, 1966b, in section 5.2] the fundamental technique of invariants in program verification was discussed under Naur’s term general snapshots; according to David Gries actually the first article on proving programs correct [Gries, 1981, p. 297]. In close relation to the proof problem, the problem of program construction gave rise to the suggestion by Naur that in order to establish the connection between the requirements to be satisfied by the program and the program itself, it should be possible to join logically related statements together to form action clusters [Naur, 1969, in section 5.3]. For this to be done effectively, the programming language should include special clauses for delimiting the clusters. This is a line of work that David L. Parnas and Niklaus Wirth have developed through their ideas on modular programming.
Peter Naur has also contributed to a deeper understanding of the serious and varied problems connected to design, production and service of large software systems, now treated under the term software engineering—a term coined at the Conference on Software Engineering in Garmisch Partenkirchen, October 1968 [Naur and Randell, 1969]. This conference created a sensation by the first open admission of the software crisis, as mentioned by Dijkstra [1972].
Still to day our profession has serious problems in meeting the demands for more and better software systems. According to Naur we shall not expect these difficulties to be overcome mainly through new methods in software development. This is one of the conclusions in the paper Programming as Theory Building [Naur, 1985b, in section 1.4], where a thorough treatment of programming viewed as a human activity is given. Instead the key issue in programming ‘... is to have the programmers build a theory of the way the matters at hand may be supported by the execution of a program. Such a view leads to a notion of program life that depends on the continued support of the program by programmers having its theory. Further, on this view the notion of a programming method, understood as a set of rules of procedure to be followed by the programmer, is based on invalid assumptions and so has to be rejected. As further consequences of the view, programmers have to be accorded the status of responsible, permanent developers and managers of the activity of which the computer is a part, and their education has to emphasize the exercise of theory building, side by side with the acquisition of knowledge of data processing and notations’. [Naur, 1985b, in section 1.4]
It is on this fundamental view of programming, founded in a number of empirical studies of programmers [Naur, 1972, 1981, 1983, in sections 6.1 to 6.3], that Peter Naur has based his penetrating critique of central topics within computer science. Here we emphasize the following:

• The ideas of structured programming as they were originally put forward by Dijkstra and Wirth in 1970 and 1971. To Naur the ideas didn’t seem right as a guidance for the programmer during problem solving. Program development styles should allow for personality factors and Naur urged for more empirical studies [Naur, 1972, in section 6.1]. In 1976 Peter J. Denning was able to give the subject a more complete treatment [Denning, 1976].
• The different proposals of software life-cycle models. As an alternative Naur points to an approach where the development problems of large data systems are regarded primarily as questions of overall design, to be established through experiments [Naur, 1974, in section 5.5].
• The widespread expectations in the scientific community that formal methods are an answer to the continued problems in software development. Naur emphasizes that only formal specifications which contribute by supporting the intuitive understanding of the matter at hand can be recommended [Naur, 1982, 1985a, 1989, in sections 7.1, 7.2, and 7.5].
• The notion often found within artificial intelligence research or cognitive science that the human mind works in a rule governed manner like an information processor. This leads to naive expectations of the possibilities to control or replace human activity by computers [Naur, 1985c, 1986, 1988, in sections 8.3, 8.2, 8.7].

So far, many of Naur’s writings have been difficult to locate and to access, and moreover many of them have been available only in Danish. We—and, we are sure, many others who have worked with Peter Naur—are very pleased that, with the present publication by ACM Press and Addison-Wesley Publishing Company, his work is in one stroke made available to a wide readership. We trust that the readers of the book will share our pleasure.

Brinch Hansen, P. The nucleus of a multiprogramming system. Comm. ACM 13 (4): 238-241, 250, 1970.
Denning, P. J. A hard look at structured programming. Pp. 183–202 in Structured Programming, Infotech State of the Art Report, 1976.
Dijkstra, E. W. The humble programmer. Comm. ACM 15 (10): 859–866, 1972. Also in ACM Turing Award Lectures. ACM Press anthology series, 1987.
Forsythe, G. A university's educational program in computer science, Comm. ACM 10 (1): 3–11, 1967.
Gries, D. The Science of Programming. Springer-Verlag, p. 297, 1981.
Knuth, D. E. Structured programming with go to statements. Computing Surveys 6 (4): 261—301, 1974. Also pp. 140–194 in R. T. Yeh (ed.). Current Trends in Programming Methodology, Vol. I, Software specification and design, Prentice Hall, 1977.
Lammers, S. Programmers at Work—Interviews. Pp. 6—24, Charles Simonyi. Microsoft Press, 1986.
Naur, P. (ed.), J. W. Backus, F. L. Bauer, J. Green, C. Katz, J. McCarthy, A. J. Perlis, H. Rutishauser, K. Samelson, B. Vauquois, J. H. Wegstein, A. van Wijngaarden, M. Woodger. Report on the algorithmic language ALGOL 60. Comm. ACM 3 (6): 299-314, 1960.
Naur, P. The design of the GIER ALGOL compiler. BIT 3: 124-140 and 145-166, 1963a. This selection section 3.1.
Naur, P. Goto statements and good ALGOL style. BIT 3: 204-208, 1963b. This selection section 5.1.
Naur, P. The place of programming in a world of problems, tools and people. Pp. 195–199 in Proc. IFIP Congress 65, Vol. I, 1965. This selection section 1.1.
Naur, P. Outline of a Course of Datalogy and Datamatics. A/S Regnecentralen, København, March 1966a. This selection section 4.2.
Naur, P. Proof of algorithms by general snapshoots. BIT 6(4): 310-316, 1966b. This selection section 5.2.
Naur, P. Datalogy, the science of data and data processes and its place in education. Pp. 1383–1387 in Proc. IFIP Congress 68, Vol. II, 1968. This selection section 4.4.
Naur, P. Programming by action clusters. BIT 9(3): 250-258, 1969. This selection section 5.3.
Naur P., and B. Randell (eds.), Software Engineering. Nato Science Committee, Brussels, 1969. Reprinted in Naur, P., B. Randell, and J.N. Buxton, eds., Software Engineering: Concepts and Techniques, Petrocelli/Charter, New York, 1976.
Naur, P. An experiment on program development. BIT 12(3): 347-365, 1972. This selection section 6.1.
Naur, P. Concise Survey of Computer Methods. Studentlitteratur, Sweden, and Petrocelli/Charter, New York, N.Y., 1974. Chapter 1 in this selection section 1.2, chapter 18 in section 5.5.
Naur, P. Programming languages, natural languages, and mathematics. Comm. ACM18 (12): 676-683, 1975. This selection section 1.3.
Naur, P. An empirical approach to program analysis and construction. Pp. 265–272 in Systems Architecture, Proc. 6th ACM European Regional Conference. ICS 81, 1981. This selection section 6.2
Naur, P. Formalization in program development. BIT 22: 437-453, 1982. This selection section 7.1.
Naur, P. Program development studies based on diaries. Pp. 159–170 in T. R. G. Green, S. J. Payne, G. C. van der Veer (eds.): Psychology of Computer Use. Academic Press, London, 1983. This selection section 6.3..
Naur, P. Intuition in software development. Pp. 60–79 in Formal Methods and Software Development, Vol. 2: Colloquium on software engineering, ed. H. Ehrig, C. Floyd, M. Nivat, and J. Thatcher. Lecture Notes in Computer Science 186, Springer-Verlag, Berlin, 1985a. This selection section 7.2.
Naur, P. Programming as theory building. Microprocessing and Microprogramming, 15: 253-261, 1985b. This selection section 1.4.
Naur, P. Review 8502-0062 of D. Michie: Machine intelligence and related topics. Computing Reviews 26 (2): 101-104, 1985c. This selection section 8.3.
Naur, P. Thinking and Turing's Test. BIT. 26:. 175-187, 1986. This selection section 8.2.
Naur, P. Human knowing, language, and discrete structures. Talk on Peter Naur’s 60th birthday, at the Institute of Datalogy, Copenhagen University, 1988. This selection section 8.7.
Naur, P. The place of strictly defined notation in human insight. Pp. 429-443 in Proc. of the Workshop on Programming Logic, ed. P. Dybjer, L. Hallnäs, B. Nordström, K. Petersson, and J. M.Smith. Göteborg, Sweden, Report 54, Programming Methodology Group, Univ. of Göteborg and Chalmers Univ. of Technology, May 1989. This selection section 7.5.
Sveinsdottir, E., and Frøkjær, E. Datalogy—the Copenhagen tradition of computer science. BIT 28 (3): 450—472, 1988.
Wexelblat, R. L.(ed.) Proc. History of Programming Languages Conference, 1978. Academic Press, New York, 1981.