Edsger Dijkstra: In Search of the “Shortest Way” to Conscious Programming

Image from abv24.com

One of the people whose name is associated with the transformation of programming from shamanism to science is Edsger Dijkstra. He unsuccessfully argued that programming is high art and intellectual creativity.

In all his studies, Dijkstra attaches great importance to the simplicity and grace of mathematical reasoning. When writing his works, he created a new style of scientific and technical communications, which can be described as something between journal publications and friendly correspondence.

Programming is not a set of passes and spells, not shamanism, not dancing with a tambourine, but mathematical discipline. And any discipline, if it claims to be more than an external effect, should be built on a solid foundation. Such a foundation for Dijkstra is mathematical logic, or rather, predicate calculus.

Now this does not seem unusual, but in the 50s it sounded like a revelation. Dijkstra understood and convincingly showed how theory can and should help practice.

For the gifted

Edsger Vyb Dijkstra was born in Rotterdam (Holland) in 1930. His parents were well-educated people: his father was a chemist, and his mother was a mathematician. In 1942, at the age of 12, Dijkstra entered the Erasminium Gymnasium - a school for especially gifted children, where a number of various subjects were taught, including Greek, Latin, French, German and English, biology, mathematics and chemistry.


Image from balto-slavica.com

In 1945, Dijkstra thought that he could study law and possibly work as the representative of the Netherlands at the UN. However, due to his successes in the study of chemistry, mathematics and physics, he entered the University of Leiden, where he decided to study theoretical physics. In 1951, he attended the Summer School of Programming at Cambridge University.

Dilemma

A year before graduating, Dijkstra faced a dilemma: to pursue a scientific career in the main specialty - theoretical physics or still continue to do programming:

I had to make a choice - either stop programming and become a real respectable theoretical physicist, or somehow formally complete my training in theoretical physics with minimal effort and become ... who? Programmer? But is this a respectable profession? After all, what is programming? What should be the solid amount of knowledge that would allow programming to be considered a scientific discipline?

One day, Dijkstra knocked on the study door of his supervisor van Weingaarden. Having patiently listened to what Dijkstra was concerned about, van Weingaarden agreed that there aren’t so many things that could be attributed to the programming discipline, but then he calmly continued to explain that automatic machine computing is not a short-term fashion, and the future lies with them that we are at the very beginning and - who knows? - maybe Dijkstra is called to turn programming into an honorable scientific discipline. This was a turning point in the life of Edsger Dijkstra, and as soon as possible he passed all the courses required to obtain a diploma in theoretical physics, and began to engage in programming.

Dijkstra officially became a "programmer" on March 1, 1952 and was the first Dutchman to start doing this in his own country. He began working as a part-time job at the Mathematics Center in Amsterdam.

Misty future

I must say that Dijkstra really risked choosing such an exotic profession at that time. There were few programmers, and computers were counted at all in two or three dozen. The future of computer science as a science was vague - many considered (and it must be admitted not without reason) computer science as a branch of applied mathematics.

However, the next few years showed that van Weingaarden did not make a mistake, suggesting to his talented student, and later a graduate student, to choose programming: from the end of the 50s, IBM began producing computers with transistors, which significantly reduced their energy consumption, weight and cost at the same time. holding up memory and performance. Other companies instantly pulled themselves up and computers from military and scientific laboratories became available to banks, manufacturing enterprises, educational institutions, hospitals, and public utilities.

Dijkstra's Algorithm

Dijkstra is known to many programmers as the creator of the “shortest path” algorithm, proposed by him back in 1952, which appeared as a result of his work on the task of evaluating the performance of the ARCMAC computer installed in the Mathematical Center. This algorithm allows you to find the best path to move between two points.

The scientist also used this algorithm to solve the problem “On finding the optimal transmission path of electric current to all the essential elements of the circuit, while minimizing the consumption of copper,” which engineers developing ARCMAC faced. He called this method "the tree algorithm with the shortest branches."


Image from urban-sanjoo.narod.ru

Dijkstra’s algorithm is still widely used today (for example, when planning automobile and air routes, when wiring electronic boards, in routing protocols). It refers to "greedy" algorithms, that is, it is effective enough to search for paths in relatively small graphs.

ALGOL-60

Having come to terms at the beginning of his programming career with machine codes and with the fact that the same algorithm had to be rewritten from scratch for different computer models, Edsger Dijkstra could not help but grasp at high-level programming languages.

FORTRAN, which appeared in the late 1950s, did not attract Dijkstra very much: in FOTRAN, much was sacrificed to the main goal - at all costs, to implement a high-level language and save the programmer from the “curse” of binary codes. If FORTRAN appeared today, its chances to hold on, I think, would be very doubtful. But then, of course, FORTRAN was a great step forward. However, Dijkstra did not like FORTRAN anyway - in this language, apparently, he lacked the grace and logic of the constructions that Dijkstra used to see in mathematics and logic.

The ALGOL-60 language was described by a harmonious and quite strict notation (the so-called “Backus-Naur form”), its development was carried out almost in an academic environment with the latest requirements for clarity, clarity and provability. The criteria were strict and the language therefore turned out to be elegant (it is no coincidence that programming languages ​​such as PL / 1, PASCAL and ADA bear obvious traces of the influence of ALGOL).

Without hesitation, Dijkstra began to implement the compiler and success in this direction confirmed his long-standing idea - it is necessary to program in "normal" languages, adapted, as far as possible, to human psychology. And the machine code - well, since without it you still can’t get anywhere - it can and should be left to the machines.

One of the most difficult tasks in translating programming languages ​​in those years was the task of compiling arithmetic expressions taking into account the priorities of operations and brackets. Dijkstra convincingly substantiated and simplified the algorithm proposed in 1957 by F. Brauer and K. Zamelzon to use two stacks for this purpose (then they usually said “store” by analogy with a weapon store). Arithmetic expressions were effectively translated into reverse (or "inverse") Polish notation very convenient for generating object code.


Example of reverse Polish notation

The greatest inventions of the past according to Dijkstra

One of the greatest inventions, he believed, is a closed routine that embodies one of the fundamental abstractions.

Dijkstra called the birth of FORTRAN the second major achievement in software. It was an extremely bold project, which should be evaluated as a successful programming technique, but with a very limited number of means of supporting the basic concept. These days, this language is considered obsolete. The tragic fate of FORTRAN is a consequence of its widespread recognition, which chained the thinking of thousands and thousands of programmers to past mistakes.

The third project that Dijkstra mentions is LISP. LISP is based on many, in a sense, the most sophisticated software products. Jokingly, LISP was described as "the most intelligent way to abuse a computer." Dijkstra believed that such a characteristic is a great compliment, since it conveys the fullness of liberation: LISP helps many of the most gifted programmers to think about things that were previously considered unthinkable.

The fourth project was ALGOL-60. While the definition of LISP still remains a bizarre mishmash of what the language means and how it works, the famous ALGOL-60 Algorithmic Language Message is the result of genuine efforts to move to the next level of abstractness and define a programming language in a way independent of its implementation.

Five dining philosophers

The developers of the first operating systems, which can be called operating systems with a stretch, worked in batch mode (when all tasks of the computer “completely” belonged to one task) almost did not encounter a task that by the mid-60s of the last century had become extremely urgent - providing access of several processes to shared resources and sharing these resources between processes. Without this, it was impossible to solve the most important task - the simultaneous execution of several processes on one computer. In operating systems using these algorithms, it was impossible to avoid blocking each other's processes.

Of course, such instability and unpredictability of the behavior of the main program - the operating system - could not suit anyone.

Dijkstra most fully expressed his thoughts on this subject in the article “Interaction of sequential processes”. To solve this problem Dijkstra proposed the concept of “semaphore” - special integer common variables and two primitives “P-operation” and “V-operation”. Here's how Dijkstra himself describes these primitives:

These last two operations are always performed on semaphores and represent the only way to access semaphores from simultaneously acting processes. Semaphores are essentially non-negative integers. If they are used only to solve the problem of mutual exclusion, then the range of their values ​​is only “0” and “1”.

A V-operation consists in increasing the value of the argument (which is a semaphore) by 1. Such an increase must be an indivisible operation. The P-operation, on the contrary, being applied to the semaphore, decreases (also indivisibly) the value of the latter by 1. Since the semaphore, by definition, is a non-negative number, sooner or later the P-operation will reduce its value to 0. The process that initiated the P-operation will be forced to wait (that is, it will actually be in the delayed execution mode) until another process “shifts” the value of this semaphore to a positive region, i.e. unlocks the semaphore.

These concepts and their further development - for example, mutexes - are still used today in the design and implementation of operating systems.

During the same years, Edsger Dijkstra led the creation of the THE operating system (from the Technische Hogeschool Eindhoven) with support for multitasking. The operating system was built in a hierarchy of 6 levels; at the same time, lower levels (starting from 0) served as the basis for higher (up to 5). At the initial levels, an interrupt handling system, semaphores, process context switching, a memory management system, and a dispatcher were implemented. At intermediate levels, interaction with the console, input / output, and interaction with devices were implemented; the highest level was intended for user programs. Subsequently, such an operating system organization model was widely adopted.

To illustrate the problem of sharing / blocking resources and the interaction of processes Dijkstra proposed a simple and witty model; later this model was named the “problem of the five dining philosophers”. In the statement of Charles Hoare, it sounds like this:

In ancient times, one rich philanthropist donated his capital to found a boarding house to give shelter to five famous philosophers. Each philosopher had his own room where he could indulge in thought. They also had a common dining room with a round table, around which there were five chairs, each labeled with the name of the philosopher to whom it was intended ... To the left of each philosopher lay a golden fork, and in the center there was a large bowl of spaghetti, the contents of which were constantly replenished.

Image from dic.academic.ru

It was assumed that the philosopher spent most of his time thinking, and, feeling hunger, went to the dining room, sat down in his chair, took a fork to his left, and proceeded to eat. But such is the complex nature of spaghetti that they cannot be brought to the mouth without the help of a second fork. Therefore, the philosopher had to take the plug to his right ... If the plug was required by another philosopher, he had to wait until it was released.

Structural programming

The penetration of computers in all sectors of industry, business, education, as well as the growth in the volume of software being developed concomitantly with this penetration caused concern of leading experts: programs became more and more, more and more complex, more and more diverse. All this could not affect their quality - it was rapidly falling.

It’s annoying if the error was in the payroll program, but this is, in the end, a fixable thing. It is scary if a software error was detected in the air transport control system. And an absolutely catastrophic mistake would have been in the program for controlling the operation of an atomic reactor.

Dijkstra saw the causes of errors in the confusing structure of programs:

I believe that a program is never an end in itself; the program is intended to invoke calculations, and the purpose of the calculations is to obtain the desired result ... I affirm (although I can not prove) that the ease and flexibility of our judgments substantially depends on the simplicity of the relationship between the program and calculations ... Roughly speaking, it can be considered desirable so that the structure of the program is reflected in the structure of the calculations.

He helped the software industry become much more disciplined, putting forward the thesis that the go to operator is harmful. This meant that the more go to statements in a program, the more difficult it was to understand the source code of the program.

To ensure the indicated ease and flexibility, Dijkstra proposes to design and code programs in accordance with a certain discipline, which he called structural programming. It is known (this is a mathematical fact known as the Böhm-Jacopini theorem) that any program can be constructed using three constructions: follow, branch, and loop.


An image from the itandlife.ru site

Dijkstra suggested (at the same time, albeit independently, with Nicklaus Wirth) represent the program as a hierarchical structure of blocks, each of which performs a small but complete task. This is achieved through a mechanism of procedures and functions.

Structural programming ideas, initially met with distrust, quickly gained recognition (especially after Nicklaus Wirth created the PASCAL programming language). Moreover, this technique remains relevant today (it is enough to recall such popular programming languages ​​as C, PASCAL or BASIC).

About the benefits and harms of Goto

One of articles on "Habr" was devoted to this question .
Against:

1. Using GOTO is a bad tone.
2. The worst tone is returning with a mark back.
3. GOTO - redundant operator. It can easily be replaced by cycles and conditions.
4. Wirth and Dijkstra say that GOTO is bad.
5. GOTO nullifies many of the compiler's options for optimizing control structures, which makes the code slower and more voluminous.

Behind:

1. A group of mutually exclusive conditions.
2. The principle of universal causality - if somewhere there is GOTO, then it is needed there.
3. Exiting multiple cycles at the same time.
4. Finite state machines (code example).

Memory

Dijkstra was an active writer, many books and articles belong to his pen (he preferred a fountain pen to a keyboard), the most famous of which are the books “Discipline of programming” and “Notes on structural programming”, and the article “On the dangers of the GOTO operator” (GOTO considered harmful) - classic books on the theory of structural programming.

Dijkstra continued to work at the Mathematics Center until, in the early 70s, transferred to work as a researcher at Burroughs Corporation in the United States. In 1972, the ACM awarded the Dijkstra the Turing Award.

In 1974, AFIPS honored him with the Harry Goode Memorial Award. In the early 1980s, Dijkstra moved to Austin, Texas. In 1984, he was appointed Dean of the Department of Computer Science at the University of Texas.

Edsger Vyb Dijkstra is an Honorary Foreign Member of the American Academy of Humanities, Science, and Technology. He is also a member of the Royal Dutch Academy of Sciences, a full member of the British Computer Society, and finally a Ph.D. at Queen's University Belfast.
Image from abv24.com

Not of this world

In 1957 he got married. In the column “profession” of the questionnaire, which is supposed to be filled out during the registration of marriage, he wrote “programmer” - he was forced to rewrite documents, stating that such a profession does not exist. As a result, as Dijkstra wrote: “If you want - believe it or not - but in the column“ profession ”of my marriage certificate there is a funny entry“ theoretical physicist ”!”

In ordinary life, Dijkstra was “eccentric” in a good way: he preferred a simple pen to a computer, he did not have a TV in his house, he did not use a mobile phone, he did not watch a movie. He also loved music and was a good pianist.

When his colleagues prepared and published a special collection for the 60th anniversary, Dijkstra answered each of them with a personal thank-you letter written by hand (and this, by the way - 61 recipients). The secretary was supposed to be a scientist of his level and position, but Dijkstra refused this privilege and preferred to do everything himself.

In August 2002, Edsger Weebe Dijkstra died at his home in the Netherlands.