Edsger Dijkstra: in search of the “shortest path” to conscious programming

Image from abv24.com

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

In all his research, Dijkstra attaches great importance to the simplicity and elegance of mathematical reasoning. When writing his works, he created a new style of scientific and technical communications, which can be described as a cross between journal publications and friendly correspondence.
')
Programming is not a set of passes and spells, not shamanism, not dancing with a tambourine, but a 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 it does not seem something 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 Waib Dijkstra was born in Rotterdam (Holland) in 1930. His parents were well-educated people: his father was a chemist, and his mother a mathematician. In 1942, at the age of 12, Dijkstra enrolled at the Erasiminium Gymnasium, a school for especially gifted children, where a variety of 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 a representative of the Netherlands at the UN. However, due to his success in the study of chemistry, mathematics and physics, he entered the University of Leiden, where he decided to take up theoretical physics. In 1951, he attended the Summer Programming School at Cambridge University.

Dilemma

A year before graduation, Dijkstra was faced with a dilemma: continue his scientific career in the main field of study - theoretical physics or, nevertheless, continue programming:

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

One day Dijkstra knocked on the door of the office of his supervisor van Weingaarden. After listening patiently to what concerns Dijkstra, van Weingaarden agreed that at present there are not too many things that could be applied to the programming discipline, but then he calmly went on to explain that automatic computing of the machine is not a short-term fashion, the future is for them that we are at the very beginning and - how to know? - maybe it was Dijkstra who was supposed to turn programming into an honorary scientific discipline. This was the turning point of Edsger Dijkstra’s whole life, and as soon as possible he completed all the courses required for obtaining a diploma in theoretical physics, and began to study 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 worker at the Mathematical Center in Amsterdam.

Foggy future

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

However, the next few years showed that Van Wayngaarden was right in proposing to his talented student, and then to a graduate student, to choose programming: from the end of the 50s, IBM began producing computers on transistors, which significantly reduced their energy intensity, mass and cost. raising memory and performance. Instantly, other companies and computers from military and scientific laboratories became accessible to banks, industrial enterprises, educational institutions, hospitals, and public utilities.

Dijkstra's Algorithm

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

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


Image from urban-sanjoo.narod.ru

Dijkstra's algorithm is widely used today (for example, when planning road and air routes, when routing electronic boards, in routing protocols). Refers to the "greedy" algorithms, that is, sufficiently effective to search for paths on relatively small graphs.

ALGOL-60

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

FORTRAN, which appeared in the late 50s, didn’t attract very much: in FOTRAN, much was sacrificed to the main goal - to realize the high-level language at all and save the programmer from the “curse” of binary codes. Appear FORTRAN today, I think its chances of holding out would be very doubtful. But then, of course, FORTRAN was a great step forward. However, FORTRAN was not impressed by Dakstra anyway - in this language, apparently, he lacked the grace and logic of the structures that Dijkstra used to see in mathematics and logic.

The language ALGOL-60 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 inherent clarity, clarity and provability inherent in the latter requirements. The criteria were strict and the language therefore turned out to be elegant (it is not by chance that such programming languages ​​as PL / 1, PASCAL and ADA bear obvious traces of the influence of ALGOL).

Without delay, 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, there’s no way to go 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 with regard to the priorities of operations and parentheses. Dijkstra convincingly substantiated and simplified the algorithm proposed in 1957 by F. Brauer and K. Zamelzon for using two stacks for this purpose (at that time they usually said “shop” by analogy with a weapon shop). Arithmetic expressions were effectively translated into inverse (or "inverse") Polish notation very convenient for generating object code.


Example of reverse polish notation

Dijkstra's greatest inventions of the past

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

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

The third project that Dijkstra mentions is LISP. Many, in a sense, most sophisticated software products are based on the use of LISP. In a joke, LISP was described as "the most intelligent way to abuse a computer." Dijkstra thought that this feature is a great compliment, because it conveys the fullness of the release: LISP helps many of the most gifted programmers to think about things previously thought unthinkable.

The fourth project was ALGOL-60. While the definition of LISP is still a bizarre jumble of what language means and how it works, the famous “ALGOL-60 Algorithmic Language Report” is the fruit of genuine effort to move to the next level of abstractness and define the programming language , independent of its implementation.

Five dining philosophers

The developers of the first operating systems, which can be called a big stretch of operating systems in batch mode (when all the computer’s resources completely “belonged” to one task) almost didn’t come up with a task that by the mid-60s of the last century had become extremely relevant providing access of several processes to shared resources and the separation of 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 the operating systems using these algorithms, they could not avoid blocking each other by 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 a “semaphore” - special integer common variables and two primitives “P-operation” and “V-operation”. Here is how Dijkstra describes these primitives:

These two last operations are always performed on semaphores and represent the only way to access semaphores from simultaneous processes. Semaphores are essentially non-negative integers. If they are used only for solving 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 an argument (which is a semaphore) by 1. Such an increase must be an indivisible operation. P-operation, on the contrary, being applied to the semaphore, reduces (also indivisibly) the value of the latter by 1. Since the semaphore, by definition, is non-negative, sooner or later the P-operation reduces its value to 0. The process that initiated the P-operation will have to wait (ie, actually be in the execution delay mode) until another process “shifts” the value of this semaphore into a positive area, 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 these years, Edsger Dijkstra led the creation of the THE operating system (from 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 levels (up to 5). At the initial levels, the interrupt handling system, semaphores, process context switching, memory management system, dispatcher were implemented. At the middle levels, interaction with the console, I / O, interaction with devices were implemented; the top level was meant for user programs. In the future, this model of organization of the operating system has become widespread.

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

In ancient times, a wealthy philanthropist donated his capital on the basis of a certain guesthouse to provide shelter for five famous philosophers. Each philosopher had his own room where he could indulge in thinking. They had a common dining room with a round table, around which there were five chairs, each labeled with the name of the philosopher for whom it was intended ... To the left of each philosopher lay a golden fork, and in the center stood 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, but when he felt hungry, he went to the dining room, sat down on his chair, took the fork to his left and started eating. 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 and to the right of himself ... If the plug was needed by another philosopher, he had to wait until it was free.

Structured programming

The penetration of computers in all branches of industry, business, education, as well as the increase in the volume of developed software accompanying this penetration caused the concern of leading experts: the programs became more and more complex and more diverse. All this could not affect their quality - it is rapidly falling.

It is a shame if the mistake was in the payroll program, but this is finally reparable. It is terrible if a software error was detected in the air traffic control system. And a mistake in the program for controlling the operation of a nuclear reactor would be quite disastrous.

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

I believe that a program is never an end in itself; the program is meant to cause calculations, and the purpose of calculations is to get the desired result ... I affirm (although I cannot prove) that the ease and flexibility of such our judgments essentially depends on the simplicity of the relationships between the program and the calculations ... Roughly speaking, it can be considered desirable so that the structure of the program is reflected in the structure of calculations.

He helped the software industry to become much more disciplined by putting forward the thesis that the “go to” operator is harmful. This meant that the more go to operators in the program, the harder it is to understand the source code of the program.

To ensure these ease and flexibility, Dijkstra proposes to design and code programs in accordance with a particular discipline, which he called structured programming. It is known (this is a mathematical fact known as the Bem-Yakopini theorem) that any program can be constructed using three constructs: follow, branch and loop.


Image from itandlife.ru

Dijkstra proposed (at the same time, though independently with Niklaus Wirth ) to present the program as a hierarchical structure of blocks, each of which performs a small but completed task. This is achieved through the mechanism of procedures and functions.

The ideas of structured programming, initially met with distrust, soon won recognition (especially after the creation of the PASCAL programming language by Niklaus Wirth). Moreover, this technique remains relevant today (it suffices to recall such popular programming languages ​​C, PASCAL or BASIC).

About the benefits and harm Goto

One of the articles on Habré was devoted to this issue.
Vs:

1. Using GOTO - bad form.
2. The worst tone - back with a label 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 cancels many of the compiler's optimization capabilities of control structures, which makes the code slower and more complex.

Behind:

1. Group of mutually exclusive conditions.
2. The principle of universal causality - if somewhere there is a GOTO, then it is needed there.
3. Exit from multiple cycles simultaneously.
4. State machines (sample code).

Memory

Dijkstra was an active writer, his pen (he preferred the pen to the keyboard) owned many books and articles, the most famous of which are the books “Programming Discipline” and “Notes on Structured Programming”, and the article “GOTO considered harmful” - classic books on the theory of structured programming.

Dijkstra continued to work at the Mathematical Center until, in the early 1970s, he went to work as a researcher at Burroughs Corporation in the United States. In 1972, ACM awarded Dijkstra a Turing Award (ACM Turing Award).

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

Edsger Vaib Dijkstra is an Honorary Foreign Member of the American Academy of Humanities, Natural and Technical Sciences. He is also a member of the Royal Dutch Academy of Sciences, a full member of the British Computer Society and, finally, a doctor of sciences at the Royal University in 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 in when registering a marriage, he wrote “programmer” - he was forced to rewrite documents, stating that such a profession does not exist. As a result, as Dijkstra wrote: “Believe it - believe it or not, but in the“ profession ”column of my marriage certificate there is an amusing“ theoretical physicist ”!”

In ordinary life, Dijkstra was in an amusing way "eccentric": he preferred a simple pen to a computer, there was no TV in his house, he did not use a mobile phone, 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 (which is, by the way, 61 recipients). A secretary relied on a scientist of his level and status, but Dijkstra refused this privilege and preferred to do everything himself.

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