Click to learn more about author Thomas Frisendal.

I started at the University of Copenhagen in 1969. My professor was Peter Naur. He was in many ways an unusual man and a deep thinker. It is only now in recent years that I realize how much he influenced my thinking. 1969 was his second year as professor. He had met computing pioneers such as Howard Aiken at Harvard University and John von Neumann at Princeton, but his original field was Astronomy. Peter Naur is best known for things like:

• Co-author with Edsger Dijkstra et al on the Algol-60 programming language
• The “N” in BNF, the Backus-Naur-Form used in a lot of language definitions
• He did not want to be called a “computer scientist,” he preferred “Datalogy” instead of “Computer Science” – the reason being that the two domains (computers and human knowing) are very different and his interest was in data, which is created and described by us as humans
• In his book “Computing: A Human Activity” (1992), a collection of his contributions to computer science, he rejected the school of programming that views programming as a branch of mathematics
• Computer Pioneer Award of the IEEE Computer Society (1986)
• 2005 Turing Award winner, the title of his award lecture was “Computing Versus Human Thinking.”

In his later years he focused on finding better ways of understanding human thinking, based on psychology, not mathematics.

This post is an essay about Peter Naur, profiling his views on formalism versus human cognition,  mostly in his own words. It is essential to think about these issues as the world moves in the direction of automated reasoning.

Background

During my years at university (interlaced with work for money as a programmer in ADP – automated data processing) it became clear to me that I fancied databases much more than logic, not least because of the human factor in Data Modeling.

Born in Denmark, I merrily participate in nurturing the narrative about the uniqueness of Danish design. My father was an architect, which explains that fascination of not only Danish design but also architecture. Just a few reminders about what it is about:

Here is a quote:

“Denmark has a long history of quality design, mainly focused on functionalism and simplicity. Combining different industrial technologies, Danish designers have managed to radically change public perception of design from something seen as reserved only for artists and professionals to something enhancing everyday life.”

So, functionalism and simplicity at the forefront. Need some evidence? What about Bang & Olufsen? The Carlsberg logo? The Egg (chair) by Arne Jacobsen? The Margrethe bowl by Jacob Jensen? The Stelton Vacuum Jug by Erik Magnussen? The Sydney Opera house by Jørn Utzon? OK, enough is enough, but here is a nice picture of the Stelton Vacuum Jug:

One of my first exposures to functionalism in computing was that of learning programming languages. The dominating ones, when I started, were FORTRAN, RPG, and assembly language. However, my boy scout troop assistant (an astronomer, like Peter Naur) showed me Algol on an early, transistor-based computer. And Algol is indeed the place to go to explore structures of programs and algorithms (as the name implies):

Compare that to FORTRAN or RPG, for example, and you will realize how big a step forward Algol was. The practice of “coding pseudo-code” looks a lot like sketching out Algol program. In fact, Algol was used as the standard method for algorithm description used by the Association for Computing Machinery (ACM) in textbooks and academic sources for more than 30 years.

Another of the early, but very big, contributions to programming systems was the so-called Backus-Naur format for metasyntax descriptions. Here is an example (from Wikipedia) of a possible BNF for a U.S. postal address:

BNF was introduced around 1958 by John Backus (of IBM).

Functional, simple representations was what I learned to expect. As it happened, I did get disappointed at times. And so did Peter Naur. Here, follow some of his observations.

Formal Logic vs. Deep Understanding of Human Cognition

Sue Gee wrote an excellent obituary of Peter Naur in 2016. The article is available on the “WayBackMachine” and I have condensed it into the following four paragraphs:

In 1970 Peter Naur opposed Edsger Dijkstra’s and Niklaus Wirth’s Structured Programming proposals. Dijkstra and Wirth were, forcefully, focused on how programming should ideally be done. But Peter Naur conducted empirical investigations trying to find out how people actually go about programming.

In 2005 Peter Naur was given the prestigious ACM Turing Award:

“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.”

In his award talk, he comments that it is ironic that he is talking under the auspices of the Turing Award because one of his works is a critique of the concept of the “Turing test.” Peter Naur explained how his early work focused on description as a core issue of science and scholarship. Science is a not a matter of causes. He points out that description was key to his contribution with John Backus to his work on the Algol 60 language. In his work on establishing programming as an academic subject his formulation of “datalogy” was a reaction against the idea of computer science, a concept that he finds misleading, suggesting instead that data is a matter of human understanding.

After his retirement in 2000, his interests shifted to more philosophical and psychological questions, and his 2004 paper “A Synapse-State Theory of Mental Life” explains his thinking.

From “Pluralism in Software Engineering”

Such is the title of a discussion book between Edgar G. Daylight and Peter Naur (Lonely Scholar, 2011).

The booklet is mostly about Peter Naur’s discussions with Dijkstra and others, and there are a number of characteristic findings:

“… advocating a universal formal specification language is troubling, because in practice we use several different forms of notation. … Design is all about choosing your representations and that’s precisely what is ignored by the formalists in computing. … The formalists assume that reliability is highly dependent of the forms of expressions used in interfacing with those who develop the program, while it is independent of the forms used in interfacing with the eventual users of the programs. Clearly such a view on program development leaves important reliability issues uncovered. … My later paper called ‘Intuition in Software Development’ (Lecture notes in Computer Science 186, Springer Verlag 1985) delves more into these matters. We have to rely on Intuition, we have nothing better. It’s not a question of eliminating intuition, it’s a question of using it in the best way we know.”

I (Thomas F.) just love this Albert Einstein quote: “As far as the propositions of mathematics refer to reality, they are not certain; and as far as they are certain, they do not refer to reality” (quote used by Peter Naur in a workshop on Programming Logic, Chalmers University of Technology, 1989).

The following sections are based on Peter Naur’s 1992 collected writings book, called “Computing: A Human Activity” (ACM Press/Addison Wesley, 1992).

On Programming Languages, Natural Languages, and Mathematics

“Several of the social aspects of mathematics and natural languages show a meaningful analogy with similar aspects of programming languages. It therefore makes sense to extrapolate the analogy to further such aspects. On this basis the following conclusions may be drawn: the split between the more academic, pure computer science oriented study of programming languages and the world of practical programming will persist indefinitely; the area of influential programming language construction is past.” (Comm. Of the ACM 18 (12), 1975).

This is still very much true. The divide between algebraic thinking and semantics is still a serious issue. Well, at best, more optimistically, still being attempted to be built.

On Computing and the So-Called Foundations of the So-Called Sciences

Presented at Informatics Curricula for the 1990s, IFIP WG 3.2, 1990:

“Computing is seen as the activity of constructing models of aspects of the world from the data processes. Computing involves both formal and informal issues, either of which can be taken up for scientific investigation. Very general theorems of computing are not the basis of the insight into computing, but consequences of such insight.”

“In approaching the question of the most proper way to teach computing, the first issue is already presented by the use of the word computing rather than computer science. Indeed, the very designation computer science carries with it the suggestion that there is something definite, perhaps a substance of insight or suchlike, that might be presented to students. … The decisive activity will be for the students to experience how significant aspects of the world can be modeled by the processing of data in computers.”

I agree. Whichever way we are being persuaded to look at solutions, even today, it is all about modeling significant aspects of the world. The rest is tooling. It is the data that rule!

On Formalization in Program Development

BIT 22 (4), 1982 (Now Springer):

“Lisskov and Zilles (in Modular Program Construction Using Abstractions, 1977) state that … ‘specifications should be written in a notation which is mathematically sound’ and that ‘the syntax and semantics of the language in which the specifications are written must be fully defined.’”

After a lengthy discussion Peter Naur tries to wrap up a conclusion about specifications: “When specification cannot be avoided they should be designed to bridge the gap between the user’s intuitive understanding of each aspect of his or her problem and its solution on the one hand and the programmed solution on the other. … the overriding concern in producing this documentation being clarity to the people, who have to deal with it.”

On the Data Modeling side, formalisms have been tried over and over again. Not least the relational database discussion of normalization is a good example of good intentions mistakenly applied to users and developers as mathematical theory. Algebra doesn’t do the job of communication between humans.

On Intuition in Software Development

In “Formal Methods and Software Development,” vol. 2, Lecture Notes in Computer Science, Springer, 1985.

We are now in the mid ’80s and Peter Naur, after a discussion of intuition and texts, is explicitly addressing data models:

“Software is developed with the purpose of supporting human beings in their activity. Although the manner of support may take many forms and be concerned with many different aspects of human life, a common underlying principle of software solutions is the use of a model of the human activity in the form of data and data processes.”

Using a “household stocking procedure” as an example, Peter Naur observes that:

“One may want to claim that the procedure can be derived systematically from one single, overall requirement, such that the household at no time run out of supply of any kind of goods. In establishing the principles of the procedure to be applied at each shopping trip we depend on an intuitive understanding of the consumption of the goods in a household and the relevance of the formal concept of average consumption.”

“Relating, finally, flaws of intuition to the third area of concern of methods, ordering of activities, it seems likely that imposed orderings will not help to avoid flaws and may in fact contribute to them. Indeed, the task of software development involves the programmer’s dealing with complicated patterns of interconnected restrictions and concerns and deriving new relevant conclusions from them, intuitively.”

Alas, the importance of relatedness, interconnected restrictions, and concern is surfacing here. Ironically, the weakest part of the relational model is the “relational” bit. Relations are thought of as just functional dependencies between attributes of an entity. And, oh, yes, there are relations between entities, but they are not important. To the extent that they get a name at all, in practice the names are not business-inspired.

This is in contrast with the observation that in understanding data structures, relationships are of utmost importance and the details about the assertions that they represent further strengthen the intuitive qualities of visual representations of relationships:

On Human Knowing, Language, and Discrete Structures

Talk given by Peter Naur at his 60th birthday in 1988:

“I will talk about knowing language and discrete structures … they crop up when one tries to understand such topics as computers – programming – applications of computers – user interfaces – principles of program development – computer science – natural science – foundations of fields and more of this kind. … It is a peculiar pattern in which several fields appear just to pass on the ball to one another – the computer scientists make use of views that have a certain currency among psychologists … and then the same psychologists in return say – the computer scientists say so and so, don’t they – and in this way one just goes on and on without ever getting sufficiently down to analyzing the core of the issues.”

“… indeed it will not work to believe that we may acquire the understanding of a phenomenon by copying a strictly defined model into the box of our knowledge … this shows itself time and time again in practice … only through concrete experience may we make this type of understanding our own … it will be a support in synthesizing and understanding an insight into concrete relationships.”

“ … on the contrary, in my opinion, the notion that a person’s consciousness and mental activity should be like that of a computer makes for a derailment of the understanding … that the computers are useful – they will do things for us that we do very badly – but they are painfully poor at doing that which human beings are good at …”

The Dilemma as Seen from the Data Modeling Side

Are we good at dealing with structured data? The relational model as defined by Dr. Codd is positioned as an algebra. And many people see relational as set algebra. However, there have been several mathematical critiques of the completeness of the relational model and not least SQL. See for example this Wikipedia page for some details.

SQL turned out to be a not-so-good idea from a mathematical purity perspective. C.J. Date, who has been evangelizing relational since the mid ’80s, wrote an article titled “A Critique of the SQL Database Language” in 1984 (ACM SIGMOD Record Vol. 14 No. 3). His criticisms are on the level of not being a “well-formed” and complete (in the mathematical sense) computer language. Not least the concept of NULLs to represent the missing/unknown has been criticized heavily by C.J. Date and others until this very day.

Most recently (2015) a mathematical incompleteness claim came from a company called Algebraix Data. They had a mathematician, Prof. Gary Sherman, working for them on “The Algebra of Data.” One of the findings of that work is that the relational model as defined by Dr. Codd is not really a consistent model, since it cannot support sets of sets (which their patented Algebra of Data can).

The schisma started in 1970 (when Dr. Codd first published his relational theory). It is that of formal mathematical foundations versus human psychology – exactly what Prof. Peter Naur was concerned about.

Using the “sets of sets” requirement as an example, we humans intuitively grasp what sets containing other sets are. However, that does not mean that we all can write recursive algorithms for traversal of hierarchies of inherited structures and properties. Most people find that very difficult and, in fact, uncomfortably so.

The rise of functional programming is partly enabled by mathematically complete algebras, by the way. It goes for full functional support like Haskell as well as functional support in nonfunctional languages such as Python. Yes, maths are good for algorithms, but not so good for describing data.

On Computers and Society, the Datalogical Way

From a Danish book based on a series of radio lectures in 1967:

Following a historical overview Peter Naur introduces “Datalogy – the Science of Data” (yes, indeed!). Talking about data and art, symbols and models as data. And data as tools. So, Data Science was introduced in 1967! (But pretty much forgotten until the present.)

“The importance of data models to society can hardly be exaggerated. … In each of these areas the work with data makes it possible to obtain insight about how the real world will behave under various circumstances. … First, datalogy will make us free of prejudices that the work with a certain, definite kind of problem is tied to a certain data representation. … The second value of datalogy for the model builder lies in the building of a data model and in the description of all details of the processes involved in its use. The careful formulation of a data model acts as a strong stimulus to the understanding … It will be clear from these considerations that datalogy is not strictly dependent on computers and that the datalogical way of looking at things comprises much of what has been known for a long time, but that has not so far been collected under one point of view.”

That is why my little company is called TF Informatics, not TF Computing!