Edsger W. Dijkstra


Edsger Wybe Dijkstra was a Dutch computer scientist, programmer, software engineer, systems scientist, science essayist, and pioneer in computing science. A theoretical physicist by training, he worked as a programmer at the Mathematisch Centrum from 1952 to 1962. A university professor for much of his life, Dijkstra held the Schlumberger Centennial Chair in Computer Sciences at the University of Texas at Austin from 1984 until his retirement in 1999. He was a professor of mathematics at the Eindhoven University of Technology and a research fellow at the Burroughs Corporation.
One of the most influential figures of computing science's founding generation, Dijkstra helped shape the new discipline from both an engineering and a theoretical perspective. His fundamental contributions cover diverse areas of computing science, including compiler construction, operating systems, distributed systems, sequential and concurrent programming, programming paradigm and methodology, programming language research, program design, program development, program verification, software engineering principles, graph algorithms, and philosophical foundations of computer programming and computer science. Many of his papers are the source of new research areas. Several concepts and problems that are now standard in computer science were first identified by Dijkstra and/or bear names coined by him. As a foremost opponent of the mechanizing view of computing science, he refuted the use of the concepts of 'computer science' and 'software engineering' as umbrella terms for academic disciplines.
Until the mid-1960s computer programming was considered more an art than a scientific discipline. In Harlan Mills's words, "programming was regarded as a private, puzzle-solving activity of writing computer instructions to work as a program". In the late 1960s, computer programming was in a state of crisis. Dijkstra was one of a small group of academics and industrial programmers who advocated a new programming style to improve the quality of programs. Dijkstra, who had a background in mathematics and physics, was one of the driving forces behind the acceptance of computer programming as a scientific discipline. He coined the phrase "structured programming" and during the 1970s this became the new programming orthodoxy. His ideas about structured programming helped lay the foundations for the birth and development of the professional discipline of software engineering, enabling programmers to organize and manage increasingly complex software projects. As Bertrand Meyer noted, "The revolution in views of programming started by Dijkstra's iconoclasm led to a movement known as structured programming, which advocated a systematic, rational approach to program construction. Structured programming is the basis for all that has been done since in programming methodology, including object-oriented programming."
The academic study of concurrent computing started in the 1960s, with Dijkstra credited with being the first paper in this field, identifying and solving the mutual exclusion problem. He was also one of the early pioneers of the research on principles of distributed computing. His foundational work on concurrency, semaphores, mutual exclusion, deadlock, finding shortest paths in graphs, fault-tolerance, self-stabilization, among many other contributions comprises many of the pillars upon which the field of distributed computing is built. Shortly before his death in 2002, he received the ACM PODC Influential-Paper Award in distributed computing for his work on self-stabilization of program computation. This annual award was renamed the Dijkstra Prize the following year. As the prize, sponsored jointly by the ACM Symposium on Principles of Distributed Computing and the EATCS International Symposium on Distributed Computing, recognizes that "No other individual has had a larger influence on research in principles of distributed computing".

Biography

Early years

Edsger W. Dijkstra was born in Rotterdam. His father was a chemist who was president of the Dutch Chemical Society; he taught chemistry at a secondary school and was later its superintendent. His mother was a mathematician, but never had a formal job.
Dijkstra had considered a career in law and had hoped to represent the Netherlands in the United Nations. However, after graduating from school in 1948, at his parents' suggestion he studied mathematics and physics and then theoretical physics at the University of Leiden.
In the early 1950s, electronic computers were a novelty. Dijkstra stumbled on his career quite by accident, and through his supervisor, Professor A. Haantjes, he met Adriaan van Wijngaarden, the director of the Computation Department at the Mathematical Center in Amsterdam, who offered Dijkstra a job; he officially became the Netherlands' first "programmer" in March 1952.
For some time Dijkstra remained committed to physics, working on it in Leiden three days out of each week. With increasing exposure to computing, however, his focus began to shift. As he recalled:
When Dijkstra married Maria C. Debets in 1957, he was required as a part of the marriage rites to state his profession. He stated that he was a programmer, which was unacceptable to the authorities, there being no such profession then in The Netherlands.
In 1959, he received his PhD from the University of Amsterdam for a thesis entitled 'Communication with an Automatic Computer', devoted to a description of the assembly language designed for the first commercial computer developed in the Netherlands, the X1. His thesis supervisor was Van Wijngaarden.

Mathematisch Centrum, Amsterdam

From 1952 until 1962, Dijkstra worked at the Mathematisch Centrum in Amsterdam, where he worked closely with Bram Jan Loopstra and Carel S. Scholten, who had been hired to build a computer. Their mode of interaction was disciplined: They would first decide upon the interface between the hardware and the software, by writing a programming manual. Then the hardware designers would have to be faithful to their part of the contract, while Dijkstra, the programmer, would write software for the nonexistent machine. Two of the lessons he learned from this experience were the importance of clear documentation, and that program debugging can be largely avoided through careful design.
Dijkstra formulated and solved the shortest path problem for a demonstration at the official inauguration of the ARMAC computer in 1956. Because of the absence of journals dedicated to automatic computing, he did not publish the result until 1959.
At the Mathematical Center, Dijkstra and his colleague developed the first compiler for the programming language ALGOL 60 by August 1960, more than a year before a compiler was produced by another group. It had a profound influence on his later thinking on programming as a scientific activity.

Eindhoven University of Technology

In 1962, Dijkstra moved to Eindhoven, and later to Nuenen, in the south of the Netherlands, where he became a professor in the Mathematics Department at the Eindhoven University of Technology. The university did not have a separate computer science department and the culture of the mathematics department did not particularly suit him. Dijkstra tried to build a group of computer scientists who could collaborate on solving problems. This was an unusual model of research for the Mathematics Department. In the late 1960s he built the THE operating system, which has influenced the designs of subsequent operating systems through its use of software based paged virtual memory.

Burroughs Corporation

Dijkstra joined Burroughs Corporation, a company known then for producing computers based on an innovative hardware architecture, as its research fellow in August 1973. His duties consisted of visiting some of the firm's research centers a few times a year and carrying on his own research, which he did in the smallest Burroughs research facility, namely, his study on the second floor of his house in Nuenen. In fact, Dijkstra was the only research fellow of Burroughs and worked for it from home, occasionally travelling to its branches in the United States. As a result, he reduced his appointment at the university to one day a week. That day, Tuesday, soon became known as the day of the famous 'Tuesday Afternoon Club', a seminar during which he discussed with his colleagues scientific articles, looking at all aspects: notation, organisation, presentation, language, content, etc. Shortly after he moved in 1984 to the University of Texas at Austin, a new 'branch' of the Tuesday Afternoon Club emerged in Austin, Texas.
The Burroughs years saw him at his most prolific in output of research articles. He wrote nearly 500 documents in the EWD series, most of them technical reports, for private circulation within a select group.

The University of Texas at Austin

Dijkstra accepted the Schlumberger Centennial Chair in the Computer Science Department at the University of Texas at Austin in 1984.

Last years

Dijkstra worked in Austin until his retirement in November 1999. To mark the occasion and to celebrate his forty-plus years of seminal contributions to computing science, the Department of Computer Sciences organized a symposium, which took place on his 70th birthday in May 2000.
Dijkstra and his wife returned from Austin to his original house in Nuenen where he found that he had only months to live. He said that he wanted to retire in Austin, Texas, but to die in the Netherlands. Dijkstra died on 6 August 2002 after a long struggle with cancer. He and his wife Maria Debets were survived by their three children: Marcus, Femke, and the computer scientist Rutger M. Dijkstra.

Pioneering contributions and impact on computing science

As an early pioneer in many research areas of computing science, Dijkstra helped shape the new discipline from both an engineering and an academic perspective. Many of his papers are the source of new research areas. Many concepts that are now standard in computer science were first identified by Dijkstra and/or bear names coined by him. Several important problems were also first formulated and solved by him. A 1994 survey of over a thousand professors of computer science was conducted to obtain a list of 38 most influential scholarly papers in the field, and Dijkstra is the author of five papers.
During his forty-plus years as a computing scientist, which included positions in both academia and industry, Dijkstra made numerous seminal contributions to many areas of computing science, including compiler construction, operating systems, concurrent programming, distributed programming, programming paradigm and methodology, programming language research, program design, program development, program verification, software engineering principles, algorithm design, and philosophical foundations of computer programming and computer science. In addition, Dijkstra was intensely interested in teaching computer science, and in the relationships between academic computing science and the software industry.

Algorithmic work

Dijkstra's algorithmic work plays an important role in many areas of computing science. According to Leslie Lamport, Dijkstra "started the field of concurrent and distributed algorithms with his 1965 CACM paper "Solution of a Problem in Concurrent Programming Control", in which he first stated and solved the mutual exclusion problem." As Lamport explains, "that paper is probably why PODC exists. It remains to this day the most influential paper in the field. That it did not win a PODC Influential Paper Award reflects an artificial separation between concurrent and distributed algorithms–a separation that has never existed in Dijkstra's work."
In 1959 Dijkstra published in a 3-page article 'A note on two problems in connexion with graphs' the algorithm to find the shortest path in a graph between any two given nodes, now called Dijkstra's algorithm. Its impact over the next 40 years is summarised from the article of Mikkel Thorup, 'Undirected Single Source Shortest Paths with Positive Integer Weights in Linear Time' : "Since 1959, all theoretical developments in SSSP for general directed and undirected graphs have been based on Dijkstra's algorithm." Dijkstra's algorithm is used in SPF, Shortest Path First, which is used in the routing protocols OSPF and IS-IS. Various modifications to Dijkstra's algorithm have been proposed by many authors using heuristics to reduce the run time of shortest path search. One of the most used heuristic algorithms is the A* search algorithm, the main goal is to reduce the run time by reducing the search space. Dijkstra thought about the shortest path problem when working at the Mathematical Center in Amsterdam in 1956 as a programmer to demonstrate capabilities of a new computer named ARMAC. His objective was to choose both a problem as well as an answer that non-computing people could understand. He designed the shortest path algorithm in about 20 minutes without aid of paper and pen and later implemented it for ARMAC for a slightly simplified transportation map of 64 cities in the Netherlands. As he recalled, in an interview published in 2001:
A year later, he came across another problem from hardware engineers working on the institute's next computer: minimize the amount of wire needed to connect the pins on the back panel of the machine. As a solution, he rediscovered the algorithm known as Prim's minimal spanning tree algorithm. The Prim's algorithm was originally developed in 1930 by Czech mathematician Vojtěch Jarník. and later independently rediscovered and republished by Robert C. Prim in 1957, and Dijkstra in 1959. Therefore, it is also sometimes called the DJP algorithm.
In 1961 Dijkstra first described the shunting-yard algorithm, a method for parsing mathematical expressions specified in infix notation, in the Mathematisch Centrum report. It can be used to produce output in Reverse Polish notation or as an abstract syntax tree. The algorithm was named the "shunting yard" algorithm because its operation resembles that of a railroad shunting yard. The shunting-yard algorithm is commonly used to implement operator-precedence parsers.
In 1962 or 1963 Dijkstra proposed the semaphore mechanism for mutual exclusion algorithm for n processes, which was probably the first published concurrent algorithm and which introduced a new area of algorithmic research. He also identified the deadlock problem and proposed the banker's algorithm that prevents deadlock.
In 1974 Dijkstra presented three self-stabilizing algorithms for mutual exclusion on a ring. Dijkstra's work is considered to be the first to introduce and demonstrate the self-stabilization concept.
In the mid-1970s Dijkstra introduced two useful abstractions to the study of garbage collection. The mutator abstracts the process that performs the computation, including allocation of a new storage cell. The collector is the process that automatically reclaims garbage. Furthermore, this paper gives a formalization of "tri-color marking" that is basic to incremental garbage collection.
In the early 1980s Dijkstra and Carel S. Scholten proposed the Dijkstra–Scholten algorithm for detecting termination in distributed systems.
In 1981 Dijkstra developed smoothsort, a comparison-based sorting algorithm and a variation of heapsort.

Compiler construction and programming language research

Dijkstra was known to be a fan of the programming language ALGOL, and worked on the team that implemented the first compiler for ALGOL 60, which he was closely involved in developing, realising, and popularising. As discussed by Peter Naur in the article 'The European side of the last phase of the development of ALGOL 60', in the Proceedings of the First ACM SIGPLAN Conference on History of Programming Languages, January 1978, Dijkstra took part in the period 1958–1959 in a number of meetings that culminated in the publication of the report defining the ALGOL 60 language. Dijkstra's name does not appear in the list of 13 authors of the final report, but he was an official member of the International Federation for Information Processing IFIP Working Group 2.1 on Algorithmic Languages and Calculi, which supports and maintains ALGOL 60 and ALGOL 68. He eventually left the committee, apparently because he could not agree with the majority opinions. Still, while at the Mathematisch Centrum, he wrote jointly with Jaap Zonneveld the first ALGOL 60 compiler. Dijkstra and Zonneveld, who collaborated on the compiler, agreed not to shave until the project was completed. Zonneveld shaved shortly thereafter, but Dijkstra kept his beard for the rest of his life.
ALGOL was the result of a collaboration of American and European committees. ALGOL 60 is a member of the ALGOL family of computer programming languages. It followed on from ALGOL 58 and inspired many languages that followed it. It gave rise to many other languages, including BCPL, B, Pascal, Simula, and C. Algol 60 was a sophisticatedly designed computer language and it provided a large number of hitherto unknown implementation challenges. As Bjarne Stroustrup notes, "one problem with Algol60 was that no one knew how to implement it." A major new challenge in Algol 60 implementation was the run-time allocation and management of data. In 1960, Dijkstra and Zonneveld showed how recursive procedures could be executed using a run-time stack of activation records, and how to efficiently access identifiers from statically enclosing scopes using the so-called display. The ALGOL 60 compiler was one of the first to support recursion employing a novel method to do so. Dijkstra's short book Primer of Algol 60 Programming, originally published in 1962, was the standard reference for the language for several years.

Programming paradigm and methodology

in the 1950s to 1960s was not recognized as an academic discipline and unlike mature sciences there were no theoretical concepts or coding systems. Programming as a professional activity was poorly understood in those years.
In the late 1960s computer programming was in state of crisis. Software crisis is a term used in the early days of computing science for the difficulty of writing useful and efficient computer programs in the required time. The software crisis was due to the rapid increases in computer power and the complexity of the problems that could be tackled. With the increase in the complexity of the software, many software problems arose because existing methods were insufficient. The term "software crisis" was coined by some attendees at the first NATO Software Engineering Conference in 1968 at Garmisch, Germany. His 1972 ACM Turing Award Lecture makes reference to this same problem: "The major cause of the software crisis is that the machines have become several orders of magnitude more powerful! To put it quite bluntly: as long as there were no machines, programming was no problem at all; when we had a few weak computers, programming became a mild problem, and now we have gigantic computers, programming has become an equally gigantic problem."
While Dijkstra had programmed extensively in machine code in the 1950s, he came to the conclusion that in high-level languages frequent use of the GOTO statement was usually symptomatic of poor structure. In 1968 he wrote a private paper "A Case against the GO TO Statement", which was then published as a letter in CACM. Editor Niklaus Wirth gave this letter the heading "Go To Statement Considered Harmful", which introduced the phrase "considered harmful" into computing.
Dijkstra argued that the programming statement GOTO, found in many high-level programming languages, is a major source of errors, and should therefore be eliminated. This letter caused a huge debate in the programming community. Some went to the length of equating good programming with the elimination of GO TO. Dijkstra refused to mention the debate, or even the GO TO statement, in his article "Notes on Structured Programming". The debate has long since died down; programming languages provide alternatives to the GO TO, few programmers today use it liberally, and most never use it at all.
Dijkstra's thesis was that departures from linear control flow were clearer if allowed only in disciplined higher-level structures such as the if-then-else statement and the while loop. This methodology was developed into structured programming movement, the title of his 1972 book, coauthored with C.A.R. Hoare and Ole-Johan Dahl. Considered by many as the first significant movement in history of computer programming, structured programming became the new programming orthodoxy during the 1970s. Bertrand Meyer remarked that, "The revolution in views of programming started by Dijkstra's iconoclasm led to a movement known as structured programming, which advocated a systematic, rational approach to program construction. Structured programming is the basis for all that has been done since in programming methodology, including object-oriented programming."
Structured programming is often regarded as "goto-less programming". But as Bertrand Meyer notes, "As the first book on the topic shows, structured programming is about much more than control structures and the goto. Its principal message is that programming should be considered a scientific discipline based on mathematical rigor." :Category:Structured programming languages|As a programming paradigm, structured programming – especially in the 1970s and 1980s – significantly influenced the birth of many modern programming languages such as Pascal, C, Modula-2, and Ada. The Fortran 77 version which incorporates the concepts of structured programming, was released in 1978. The C++ language was a considerably extended and enhanced version of the popular :Category:Structured programming languages|structured programming language C. Since C++ was developed from a more traditional :Category:Structured programming languages|structured language, it is a 'hybrid language', rather than a pure object-oriented programming language.
In his article Structured Programming: Retrospect and Prospect, Harlan Mills writes, "Edsger W. Dijkstra's 1969 Structured Programming article precipitated a decade of intense focus on programming techniques that has fundamentally altered human expectations and achievements in software development. Before this decade of intense focus, programming was regarded as a private, puzzle-solving activity of writing computer instructions to work as a program. After this decade, programming could be regarded as a public, mathematics-based activity of restructuring specifications into programs. Before, the challenge was in getting programs to run at all, and then in getting them further debugged to do the right things. After, programs could be expected to both run and do the right things with little or no debugging. Before, it was common wisdom that no sizable program could be error-free. After, many sizable programs have run a year or more with no errors detected. These expectations and achievements are not universal because of the inertia of industrial practices. But they are well-enough established to herald fundamental change in software development."
The book Concise Encyclopedia of Computer Science, edited by Edwin D. Reilly, notes that "the major contributions of structured programming have been twofold—the elevation of programming technique to something less of an art and more of a science, and the demonstration that carefully structured programs can be creative works of sufficient literary merit to deserve being read by humans and not just by computer."

Program design and development (software engineering research)

Dijkstra's ideas about programming methodology helped lay the foundations for the birth and development of the professional discipline of software engineering, enabling programmers to organize and manage increasingly complex software projects. In the late 1960s Dijkstra discussed the concept of program families. And in the mid 1970s David Parnas and others clarified the idea and showed how to apply it in software engineering principles.
The rise of the structured programming movement led to many other structured approaches applied to software design. The techniques of structured analysis and structured design are outgrowths of structured programming concepts and techniques, and of the early ideas about modular design. Principles of modularity were strengthened by Larry Constantine's concepts of coupling and cohesion, by David Parnas's techniques of information hiding, and by abstract data types. A number of tools and methods employing structured concepts were developed, such as Structured Design, Jackson's Structured Programming, Ross' Structured Analysis and Design Technique, Yourdon's Structured Method, Structured Systems Analysis and Design Method, and James Martin's information technology engineering. The field of software metrics is often considered as a direct influence of the structured programming movement on software engineering in the 1970s.
Separation of concerns, one of the basic principles in software engineering, is a design principle for separating a computer program into distinct sections, such that each section addresses a separate concern. The term separation of concerns was coined by Dijkstra in his 1974 paper "On the role of scientific thought".

Operating system research

In the 1960s Dijkstra and his colleagues in Eindhoven designed and implemented THE operating system, which was organised into clearly identified abstraction layers. His 1968 article on this subject provided the foundation for subsequent designs of the operating systems. The IEEE Computer Society's David Alan Grier writes, "We generally trace the idea of building computer systems in layers back to a 1967 paper that the Dutch computer scientist Edsger Dijkstra gave to a joint IEEE Computer Society/ACM conference. Prior to this paper, engineers had struggled with the problem of how to organize software. If you look at early examples of programs, and you can find many in the electronic library of the Computer Society, you will find that most code of that era is complicated, difficult to read, hard to modify, and challenging to reuse. In his 1967 paper, Dijkstra described how software could be constructed in layers and gave an example of a simple operating system that used five layers. He admitted that this system might not be a realistic test of his ideas but he argued that the "larger the project, the more essential the structuring!" The idea of using layers to control complexity has become a mainstay of software architecture. We see it in many forms and apply it to many problems. We see it in the hierarchy of classes in object-oriented programming and in the structure of service-oriented architecture operational systems, 2) service components, 3) services, 4) business processes, 5) consumer actions, 6) system integration, 7) quality control and assurance, 8) information architecture, and 9) system governance and policies."
Dijkstra organized the design of the system in layers in order to reduce the overall complexity of the software. Though the term 'architecture' had not yet been used to describe software design, this was certainly considered the first glimpse of software architecture. It introduced a number of design principles which have become part of the working vocabulary of every professional programmer: levels of abstraction, programming in layers, the semaphore, and cooperating sequential processes. His original paper on the THE operating system was reprinted in the 25th Anniversary issue of Communications of the ACM, in January 1983. By way of introduction, the Editor-in-Chief says, "This project initiated a long line of research in multilevel systems architecture — a line that continues to the present day because hierarchical modularity is a powerful approach to organizing large systems."

Concurrent computing and programming

In a one-page paper from 1965 Dijkstra introduced the 'mutual exclusion problem' for n processes and discussed a solution to it. It was probably the first published concurrent algorithm. The notion, standard by now, of a 'critical section' was also introduced in this paper. Per Brinch Hansen, a pioneer in the field of concurrent computing, considers Dijkstra's Cooperating Sequential Processes to be the first classic paper in concurrent programming. As Brinch Hansen notes, 'Dijkstra lays the conceptual foundation for abstract concurrent programming' with that paper.
was first identified and solved by Dijkstra in his seminal 1965 paper titled Solution of a problem in concurrent programming control, and is credited as the first topic in the study of concurrent algorithms.
In 1968 Dijkstra published his seminal paper 'Cooperating sequential processes', a 70-page essay that originated the field of concurrent programming. He discussed in it the notion of mutual exclusion and the criteria a satisfactory solution should satisfy. He also redressed the historical perspective left out of his 1965 paper by including the first known correct solution to the mutual exclusion problem, for two processes, due to Theodorus Dekker. Dijkstra subsequently generalized Dekker's solution to n processes. Further, he proposed the first synchronisation mechanism for concurrent processes, the semaphore with its two operations, P and V. He also identified the 'deadlock problem' and proposed an elegant 'Banker's algorithm' that prevents deadlock. The deadlock detection and prevention became perennial research problems in the field of concurrent programming.
The dining philosophers problem is an example problem often used in concurrent algorithm design to illustrate synchronization issues and techniques for resolving them. It was originally formulated in 1965 by Dijkstra as a student exam exercise, presented in terms of computers competing for access to tape drive peripherals. Soon after, Tony Hoare gave the problem its present formulation. The sleeping barber problem is also attributed to Dijkstra.
In his book Concurrent Programming: Algorithms, Principles, and Foundations Michel Raynal writes, "Since the early work of E.W. Dijkstra, who introduced the mutual exclusion problem, the concept of a process, the semaphore object, the notion of a weakest precondition, and guarded commands, synchronization is no longer a catalog of tricks but a domain of computing science with its own concepts, mechanisms, and techniques whose results can be applied in many domains. This means that process synchronization has to be a major topic of any computer science curriculum."
John W. McCormick et al. notes, "The notion of the concurrent program as a means for writing parallel programs without regard for the underlying hardware was first introduced by Edsger Dijkstra. Moti Ben-Ari elegantly summed up Dijkstra's idea in three sentences: ‘Concurrent programming is the name given to programming notation and techniques for expressing potential parallelism and solving the resulting synchronization and communication problems. Implementation of parallelism is a topic in computer systems that is essentially independent of concurrent programming. Concurrent programming is important because it provides an abstract setting in which to study parallelism without getting bogged down in the implementation details.’"

Distributed computing

Dijkstra was one of the very early pioneers of the research on principles of distributed computing. As the citation for the Dijkstra Prize recognizes, "no other individual has had a larger influence on research in principles of distributed computing." Some of his papers are even considered to be those that established the field. Dijkstra's 1965 paper, Solution of a Problem in Concurrent Programming Control was the first to present the correct solution to the mutual exclusion problem. Leslie Lamport writes that this work "is probably why PODC exists" and it "started the field of concurrent and distributed algorithms".
In particular, his paper "Self-stabilizing Systems in Spite of Distributed Control" started the sub-field of self-stabilization. It is also considered as the first scientific examination of fault-tolerant systems. Dijkstra's paper was not widely noticed until Leslie Lamport's invited talk at the ACM Symposium on Principles of Distributed Computing in 1983. In his report on Dijkstra's work on self-stabilizing distributed systems, Lamport regard it to be 'a milestone in work on fault tolerance' and 'a very fertile field for research'.

Formal specification and verification

From the 1970s, Dijkstra's chief interest was formal verification. In 1976 Dijkstra published a seminal book, A Discipline of Programming, which put forward his method of systematic development of programs together with their correctness proofs. In his exposition he used his 'Guarded Command Language'. The language, with its reliance on non-determinism, the adopted weakest precondition semantics and the proposed development method has had a considerable impact on the field to this day. The refinement calculus, originally proposed by Ralph-Johan Back and developed by Carroll Morgan, is an extension of Dijkstra's weakest precondition calculus, where program statements are modeled as predicate transformers.
In 1984, to add further support to this approach to programming, he published jointly with Wim Feijen an introductory textbook for first-year students of computer science. The book, first published in Dutch, was entitled Een methode van programmeren. The English edition appeared in 1988 as A Method of Programming.

On the nature of computer science and computer programming

Many of his opinions on computer science and programming have become widespread. For example, the programming phrase "two or more, use a for" is sometimes attributed to him.
He was the first to make the claim that programming is so inherently complex that, in order to manage it successfully, programmers need to harness every trick and abstraction possible.
Dijkstra was one of the most famous opponents of the engineering view of computing science. Like Peter Naur and Kristen Nygaard, Dijkstra disliked the very term 'computer science'. Computer science, as Dijkstra pointed out, deserves a better name. He suggests it can be called 'computing science'. Instead of the computer, or computing technology, Dijkstra wanted to emphasize the abstract mechanisms that computing science uses to master complexity. When expressing the abstract nature of computing science, he wrote,
In The Humble Programmer, Dijkstra wrote: "We must not forget that it is not our business to make programs, it is our business to design classes of computations that will display a desired behaviour."
Dijkstra also opposed the inclusion of software engineering under the umbrella of academic computer science. He wrote that, "As economics is known as "The Miserable Science", software engineering should be known as "The Doomed Discipline", doomed because it cannot even approach its goal since its goal is self-contradictory." And "software engineering has accepted as its charter "How to program if you cannot."."

Personality and working style

In the world of computing science, Dijkstra is well known as a "character". In the preface of his book A Discipline of Programming he stated the following: "For the absence of a bibliography I offer neither explanation nor apology." In fact, most of his articles and books have no references at all. This approach to references was deplored by some researchers. But Dijkstra chose this way of working to preserve his self-reliance.
As a university professor for much of his life, Dijkstra saw teaching not just as a required activity but as a serious research endeavor. His approach to teaching was unconventional. His lecturing style has been described as idiosyncratic. When lecturing, the long pauses between sentences have often been attributed to the fact that English is not Dijkstra's first language. However the pauses also served as a way for him to think on his feet and he was regarded as a quick and deep thinker while engaged in the act of lecturing. His courses for students in Austin had little to do with computer science but they dealt with the presentation of mathematical proofs. At the beginning of each semester he would take a photo of each of the students, in order to memorize their names. He never followed a textbook, with the possible exception of his own while it was under preparation. When lecturing, he would write proofs in chalk on a blackboard rather than using overhead foils. He invited the students to suggest ideas, which he then explored, or refused to explore because they violated some of his tenets. He assigned challenging homework problems, and would study his students' solutions thoroughly. He conducted his final examinations orally, over a whole week. Each student was examined in Dijkstra's office or home, and an exam lasted several hours.
He was also highly original in his way of assessing people's capacity for a job. When Vladimir Lifschitz came to Austin in 1990 for a job interview, Dijkstra gave him a puzzle. Vladimir solved it and has been working in Austin since then.
Despite having invented much of the technology of software, Dijkstra eschewed the use of computers in his own work for many decades. Even after he succumbed to his UT colleagues' encouragement and acquired a Macintosh computer, he used it only for e-mail and for browsing the World Wide Web. Dijkstra never wrote his articles using a computer. He preferred to rely on his typewriter and later on his Montblanc pen. Dijkstra's favorite writing instrument was the Montblanc Meisterstück fountain pen. He repeatedly tried other pens, but none ever displaced the Montblanc.
He had no use for word processors, believing that one should be able to write a letter or article without rough drafts, rewriting, or any significant editing. He would work it all out in his head before putting pen to paper, and once mentioned that when he was a physics student he would solve his homework problems in his head while walking the streets of Leiden.
Most of Dijkstra's publications were written by him alone. He never had a secretary and took care of all his correspondence alone. When colleagues prepared a Festschrift for his sixtieth birthday, published by Springer-Verlag, he took the trouble to thank each of the 61 contributors separately, in a hand-written letter.
Throughout Dijkstra's career, his work was characterized by elegance and economy. A prolific writer, Dijkstra authored more than 1,300 papers, many written by hand in his precise script. They were essays and parables; fairy tales and warnings; comprehensive explanation and pedagogical pretext. Most were about mathematics and computer science; others were trip reports that are more revealing about their author than about the people and places visited. It was his habit to copy each paper and circulate it to a small group of colleagues who would copy and forward the papers to another limited group of scientists. His love affair with simplicity came at an early age and under his mother's guidance. He once said he had asked his mother whether trigonometry was a difficult topic. She replied that he must learn all the formulas and that furthermore if he required more than five lines to prove something, he was on the wrong track.
Dijkstra was famous for his wit, eloquence, rudeness, abruptness and often cruelty to fellow professionals, and way with words, such as in his remark, "The question of whether Machines Can Think is about as relevant as the question of whether Submarines Can Swim."; his advice to a promising researcher, who asked how to select a topic for research, "Do only what only you can do". Dijkstra was also known for his vocal criticism and absence of social skills when interacting with colleagues. As an outspoken and critical visionary, he strongly opposed the teaching of BASIC.
In many of his more humorous essays, Dijkstra described a fictional company of which he served as chairman. The company was called Mathematics, Inc., a company that he imagined having commercialized the production of mathematical theorems in the same way that software companies had commercialized the production of computer programs. He invented a number of activities and challenges of Mathematics Inc. and documented them in several papers in the EWD series. The imaginary company had produced a proof of the Riemann Hypothesis but then had great difficulties collecting royalties from mathematicians who had proved results assuming the Riemann Hypothesis. The proof itself was a trade secret. Many of the company's proofs were rushed out the door and then much of the company's effort had to be spent on maintenance. A more successful effort was the Standard Proof for Pythagoras' Theorem, that replaced the more than 100 incompatible existing proofs. Dijkstra described Mathematics Inc. as "the most exciting and most miserable business ever conceived". EWD 443 describes his fictional company as having over 75 percent of the world's market share.

EWD manuscripts

Dijkstra was well known for his habit of carefully composing manuscripts with his fountain pen. The manuscripts are called EWDs, since Dijkstra numbered them with EWD, his initials, as a prefix. According to Dijkstra himself, the EWDs started when he moved from the Mathematical Centre in Amsterdam to the Eindhoven University of Technology. After going to Eindhoven, Dijkstra experienced a writer's block for more than a year. Dijkstra distributed photocopies of a new EWD among his colleagues. Many recipients photocopied and forwarded their copies, so the EWDs spread throughout the international computer science community. The topics were computer science and mathematics, and included trip reports, letters, and speeches. These short articles span a period of 40 years. Almost all EWDs appearing after 1972 were hand-written. They are rarely longer than 15 pages and are consecutively numbered. The last one, No. 1318, is from 14 April 2002. Within computer science they are known as the EWD reports, or, simply the EWDs. More than 1300 EWDs have been scanned, with a growing number transcribed to facilitate search, and are available online at the Dijkstra archive of the University of Texas.

Personal life

Dijkstra's self-confidence went together with a remarkably modest lifestyle, to the point of being :wikt:spartan|spartan. His and his wife's house in Nuenen was simple, small and unassuming. He did not own a TV, a VCR or a mobile telephone, and did not go to the movies. In contrast, he played the piano well and, while in Austin, liked to go to concerts. An enthusiastic listener of classical music, Dijkstra's favorite composer was Mozart.

Death

Dijkstra died on 6 August 2002. According to officials at the University of Texas, the cause of death was cancer.

Influence and recognition

In 1972 the Association for Computing Machinery acknowledged Dijkstra's seminal contributions to the field by awarding him the distinguished Turing Award. The citation for the award reads:
The introduction given at the awards ceremony is a tribute to Dijkstra:
In the words of Sir Tony Hoare, FRS, delivered by him at Dijkstra's funeral:
In March 2003, the following email was sent to the distributed computing community:
Former ACM President Peter J. Denning wrote about Dijkstra:

Awards and honors

Among Dijkstra's awards and honors are:
The Distinguished Fellowship of the British Computer Society is awarded under bylaw 7 of the BCS's Royal Charter. The award was first approved in 1969 and the first election was made in 1971 to Dijkstra.
On the occasion of Dijkstra's 60th birthday in 1990, The Department of Computer Science at the University of Texas at Austin organized a two-day seminar in his honor. Speakers came from all over the United States and Europe, and a group of computer scientists contributed research articles which were edited into a book.
In 2002, the C&C Foundation of Japan recognized Dijkstra "for his pioneering contributions to the establishment of the scientific basis for computer software through creative research in basic software theory, algorithm theory, structured programming, and semaphores." Dijkstra was alive to receive notice of the award, but it was accepted by his family in an award ceremony after his death.
Shortly before his death in 2002, Dijkstra received the ACM PODC Influential-Paper Award in distributed computing for his work on self-stabilization of program computation. This annual award was renamed the Dijkstra Prize the following year, in his honor.
The Dijkstra Award for Outstanding Academic Achievement in Computer Science is named for Edsger W. Dijkstra. Beginning in 2005, this award recognizes the top academic performance by a graduating computer science major. Selection is based on GPA in all major courses and election by department faculty.
The Department of Computer Science at the University of Texas at Austin hosted the inaugural Edsger W. Dijkstra Memorial Lecture on 12 October 2010. Tony Hoare, Emeritus Professor at Oxford and Principal Researcher at Microsoft Research, was the speaker for the event. This lecture series was made possible by a generous grant from Schlumberger to honor the memory of Dijkstra.

Selected publications

; Books
; Selected articles