Edsger Wybe Dijkstra

Oral Interviews

In August of 2001 Philip L. Frana conducted an oral interview with Edsger Dijkstra for the Charles Babbage Institute. As described by the CBI: ....Dijkstra recounts his early education and training as a theoretical physicist and as a ‘programmer’. Dijkstra describes his work developing software for the Mathematical Centre in Amsterdam, the completion of his Ph.D. thesis, and his activities at several early information processing conferences. Dijkstra also discourses on the development of ALGOL 60 and the origins of computing science in Europe and America. The transcript of this interview is available here.
 

compiler

A compiler is a program which translates programs written in a notation suitable for humans into code suitable for execution by a computer.

calculational proof style

A proof based on representing the theorem as a predicate and calculating that its value is true.

deadlock

Deadlock is a possibility whenever each of two concurrently running processes requires exclusive access to both of two resources R1 and R2. For example, suppose R1 and R2 are files, and each process copies from one file to the other.

A process gets exclusive access to resource X by executing the operation acquire X, executing release X when it no longer needs X. A process executing acquire X at a time when some other process has exclusive access to it simply pauses until it is released by the other process.

To see how deadlock occurs, consider these two processes:p

P1: ... acquire R1 ... acquire R2 ... perform operation ... release R1; release R2 ...
P2: ... acquire R2 ... acquire R1 ... perform operation ... release R2; release R1 ...

If process P1 executes acquire R1, but fails to execute acquire R2 before process P2 executes acquire R2, then neither process can proceed. Each waits forever for the other, in a situation Dijkstra called “deadly embrace.”

In the example, deadlock could be prevented by ensuring that both processes acquire the resources they need in the same order. In real systems, however, both processes and resources number in the hundreds or thousands, and more general methods are required [1].

design principles

In his landmark article on the THE operating system [2], Dijkstra considered his group’s main contribution to system design to be the decision, inspired by his extensive experience in making basic software dealing with real time interrupts, “to be as careful as possible and to try to prevent bugs from entering the construction.” They found that “it is possible to design a refined multiprogramming system in such a way that its logical soundness can be proved a priori.”

The system was constructed in layers, each of which constituted an abstraction, providing only the features needed by the layer above it. This hierarchical structure not only facilitated the system’s design and construction, it also kept the number of cases to be tested small enough that the testing could be exhaustive and that it was clear that no cases had been overlooked.

The whole system was arranged as a society of sequential processes regulated by explicit mutual synchronization statements. The fundamental consequence of this approach was that the processes’ harmonious cooperation could be established by discrete reasoning.

 

EWD series

The EWD (“Edsger W. Dijkstra”) series began in 1959 when Dijkstra was working on four or five manuscripts simultaneously and mixed up pages between manuscripts. He decided that not only the pages needed numbers, but also the manuscripts: EWD0, EWD1, EWD2, etc. Some of the EWDs were later published as conference papers, journal articles, or book chapters, but the majority were written not for publication, only for their author and for circulation among a small group of friends. Even so, many of his “small” ideas, such as deadlock, on-the-fly garbage collection, and self-stabilizing systems have started new subareas of computer science.

Since EWD numbers were assigned to manuscripts when they were begun and not all were completed, the number of the last EWD —1317— exceeds the number of actual documents (1126) in the series.

In EWD1000 [7] Dijkstra relates the series’ origin and evolution, reflecting that

If there is one "scientific" discovery I am proud of, it is the discovery of the habit of writing without publication in mind. I experience it as a liberating habit: without it, doing the work becomes one thing and writing it down becomes another one, which is often viewed as an unpleasant burden. When working and writing have merged, that burden has been taken away.

Dijkstra distributed photocopies of the EWDs in batches to friends and colleagues, who in turn often extended the distribution.

The fate of EWD249 (“Notes on Structured Programming”) revealed that the suddenly ubiquitous copying machine had profoundly changed the pattern of scientific communication. He mailed only 20 copies to friends in Europe and the USA, but it spread around the world like wildfire to the extent that only a few years later IBM felt comfortable adopting the term “structured programming”. People from far-away places later said that in, say, 1971 they had a 6th- or 7th-generation copy!

Sixty-six of the EWDs were collected, edited, and published in 1982 [8]. These include not only technical notes but also several entertaining trip reports, and several communications from the Chairman of Mathematics, Inc., a fictitious company which was a faithful contributor to Austin’s classical-music FM station, KMFA.

The entire series has been scanned and put on line by the Department of Computer Sciences of The University of Texas at Austin as the Edsger W. Dijkstra Archive. Roughly half of the manuscripts have been transcribed by an ever-changing team of volunteers into html, which makes them searchable, and accessible to readers who are visually handicapped.

GO TO

In conventional programming languages, a program is a sequence of statements which are executed one after another in the order in which they are written. Constructs that provide for alternation and repetition of groups of statements are a powerful mechanism for abstraction, enabling groups of statements to be considered for control-flow purposes as single statements. The GO TO statement, which allows control to be transferred to an arbitrary point in a program, can cripple the power of that abstraction. As Dijkstra wrote, “The go to statement as it stands is just too primitive, it is too much an invitation to make a mess of one’s program.”

nondeterminacy

The earliest and simplest model of machine computation is deterministic: A processor executing a given program starting in a given initial condition always performs the same process (i.e., the same sequence of operations), and therefore always produces the same results.

Nondeterminacy arises when two different runs of a program can give different results. For example, a processor may respond to a signal from a keyboard by suspending its execution of the current process, executing a process that deals with the keyboard signal, and then returning to the original process. The instant at which transfer of control from the original process to the keyboard handler takes place is likely to be different from one run to the next, and hence the actual sequence of operations is also different from one run to the next.

The computing science challenge that Dijkstra attacked was to develop methods for ensuring that the results produced by nondeterministic computations always meet their specifications.

Notes on Structured Programming

“Notes” [3] advocates certain design principles which are now generally accepted in the computer science community: Large systems should be constructed out of smaller components; each component should be defined only by its interface and not by its implementation; smaller components may be designed following a similar process of decomposition, thus leading to a top-down style of design; the design should start by enumerating the “separable concerns” and by considering each group of concerns independently of the others; and mathematical logic is and must be the basis for software design.

on-the-fly garbage collection

The typical program’s needs for random-access storage vary as its data structures are built, modified, and discarded. Because storage is finite, it needs to be recycled, identifying the storage locations occupied by discarded structures and making them available for building new structures. Storage recycling is known as garbage collection.

In early systems, garbage collection was performed whenever available storage was exhausted, so that the computation and garbage collection were performed alternately. The resulting pauses in the computation proper could be awkward, and in systems required to respond promptly to external events it could be lethal (a favorite example is the robot tennis player halting in mid-serve for garbage collection).

An on-the-fly garbage collector eliminates the awkward pauses by running concurrently with the “useful” computation. The cooperation required is intricate, and the solution and its correctness proof went through several iterations (EWD 492, 496A, EWD 496B, EWD 520, EWD 595, EWD 630, [6]).

predicate calculus

Predicate calculus is, informally speaking, an algebra of mathematical expressions whose values are logical rather than numerical.

predicate transformers

The most obvious way to understand the meaning of a statement in a conventional programming language is to specify its effects on the program’s variables. For example, the statement x := x + 5 (a so-called assignment statement) updates the value of the variable x with the value of the expression x + 5.

For purposes of proving programs’ correctness, however, it turns out to be more useful to understand statements’ meanings in terms of their effects not on variables themselves, but on logical expressions involving variables, i.e., on predicates. For example, suppose that we want to know what needs to be true before the execution of the statement x := x + 5 in order for x’s value afterwards to be at least 9. We write this as a formula

{ ? } x := x + 5 { x ≥ 9 }

where x ≥ 9 is the statement’s postcondition, and we wish to derive a precondition which guarantees that the statement’s execution establishes the postcondition.

We reason that x + 5 needs to be at least 9 before the statement is executed, i.e.,

{ x + 5 ≥ 9 } x := x + 5 { x ≥ 9 }

which simplifies to

{ x ≥ 4 } x := x + 5 { x ≥ 9 }

The statement is thus viewed as transforming the postcondition x ≥ 9 into the precondition x ≥ 4.

Generalizing, the meaning of any assignment statement, which has the form x := e where x is a variable and e is an expression, is defined by the relationship between its pre- and postconditions:

{ R in which each occurrence of x is replaced by e } x := e { R }

That is, given an assignment statement’s postcondition, the precondition necessary for the postcondition to hold after the statement’s execution is derived by calculation.

It would be equally feasible to calculate statements’ postconditions from their preconditions, but since programming is generally aimed at some known goal, which can be formulated as the postcondition of the entire program, it is more useful to begin with statements’ postconditions and work backwards towards their preconditions.

real-time interrupt

Ubiquitous in the design of modern operating systems, the problem of real-time interrupts arises when several computing devices operate asynchronously and one device may affect the behavior of another by interrupting the latter’s execution sequence. This was Dijkstra’s first experience with non-determinacy, which he formalized in a landmark paper [5] in 1975.

recursion

Recursion is the invocation of a subprogram within its own definition. For example, a program to calculate the sum of a sequence of numbers can be defined recursively as follows:

If the sequence is empty, the sum is 0.

Otherwise, the sum is calculated by adding the sequence’s first element to the sum of the sequence of the remaining elements.

 

self-stabilizing systems

Wikipedia puts it well: “A distributed algorithm is self-stabilizing if, starting from an arbitrary state, it is guaranteed to converge to a legitimate state and remain in a legitimate set of states thereafter. ... The property of self-stabilization enables a distributed algorithm to recover from a transient fault regardless of its nature.” [4]

stack

A stack is a sequence of elements subject to the restriction that elements can be added or removed at one end only. The name stack is suggested by the behavior of a stack of dishes, where dishes can be added or removed only at the top.

streamlining mathematical arguments

Dijkstra explains this area of research:

As a matter of fact, the challenges of designing high-quality programs and of designing high-quality proofs are very similar, so similar that I am no longer able to distinguish between the two: I see no meaningful difference between programming methodology and mathematical methodology in general. The long and short of it is that the computer’s ubiquity has made the ability to apply mathematical method[s] more important than ever. [11]

teaching

“Teaching to unsuspecting youngsters the effective use of formal methods is one of the joys of life because it is so extremely rewarding. Within a few months, they find their way in a new world with a justified degree of confidence that is radically novel for them; within a few months, their concept of intellectual culture has acquired a radically novel dimension. To my taste and style, that is what education is about. Universities should not be afraid of teaching radical novelties; on the contrary, it is their calling to welcome the opportunity to do so. Their willingness to do so is our main safeguard against dictatorships, be they of the proletariat, of the scientific establishment, or of the corporate elite.” [9]

the THE Multiprogramming System

Dijkstra remarks in a later note: “It was the first operating system conceived (or partitioned) as a number of loosely coupled, explicitly synchronized, co-operating sequential processes, a structure that made proofs of absence of the danger of deadlock and proofs of other correctness properties feasible.”[10]

Turing Award

The introduction given at the awards ceremony in 1972 is a tribute worth repeating:

The working vocabulary of programmers is studded with words originated or forcefully promulgated by E. W. Dijkstra: display, deadly embrace, semaphore, go-to-less programming, structured programming. But his influence on programming is more pervasive than any glossary can possibly indicate. The precious gift that this Turing Award acknowledges is Dijkstra’s style: his approach to programming as a high, intellectual challenge; his eloquent insistence and practical demonstration that programs should be composed correctly, not just debugged into correctness; and his illuminating perception of problems at the foundations of program design. He has published about a dozen papers, both technical and reflective, among which are especially to be noted his philosophical address at IFIP, his already classic papers on cooperating sequential processes, and his memorable indictment of the go-to statement. An influential series of letters by Dijkstra have recently surfaced as a polished monograph on the art of composing programs. We have come to value good programs in much the same way as we value good literature. And at the center of this movement, creating and reflecting patterns no less beautiful than useful, stands E. W. Dijkstra.

vector

In this context, a vector is a sequence of consecutive locations in a computer’s memory. Dijkstra was the first to apply this mathematical term to computer data structures.

 

References

1. Edsger W. Dijkstra. Cooperating sequential processes. In F. Genuys, editor, Programming Languages, 43–112. Academic Press, 1968 . Also http://www.cs.utexas.edu/users/EWD/ewd01xx/EWD123.PDF.
2. Edsger W. Dijkstra. The structure of the “THE”-multiprogramming system. Communications of the ACM 11, 5 (1968), 341–346. Also http://www.cs.utexas.edu/users/EWD/ewd01xx/EWD196.PDF.
3. Edsger W. Dijkstra. Notes on Structured Programming. T.H.-Report 70–WSK–03, Second edition, April 1970. Also http://www.cs.utexas.edu/users/EWD/ewd02xx/EWD249.PDF.
4. Edsger W. Dijkstra. Self-stabilizing systems in spite of distributed control. Communications of the ACM 17, 11 (1974), 643–644.
5. Edsger W. Dijkstra. Guarded commands, nondeterminacy, and the formal derivation of programs. Communications of the ACM 18, 8 (1975), 453–457.
6. Edsger W. Dijkstra et al. On-the-fly garbage collection: An exercise in cooperation. Communications of the ACM 21, 11 (1978), 966–975.
7. Edsger W. Dijkstra. Twenty-eight years, EWD 1000. http://www.cs.utexas.edu/users/EWD/transcriptions/EWD10xx/EWD1000.html. 1987. Circulated privately.
8. Edsger W. Dijkstra. Selected Writings on Computing: A Personal Perspective. Springer-Verlag, 1982.
9. Edsger W. Dijkstra. On the cruelty of really teaching computing science. Communications of the ACM 32, 1 (1989), 398–414. Also http://www.cs.utexas.edu/users/EWD/ewd10xx/EWD1036.PDF.
10. Edsger W. Dijkstra. From my life, EWD 1166. http://www.cs.utexas.edu/users/EWD/ewd11xx/EWD1166.PDF, 1993. Circulated privately.
11. Edsger W. Dijkstra. Why American Computing Science seems incurable, EWD 1209. http://www.cs.utexas.edu/users/EWD/ewd12xx/EWD1209.PDF, 1995. Circulated privately.