Edsger W. Dijkstra
Edsger Wybe Dijkstra (Dutch: [ˈɛtsxər ˈʋibə ˈdɛikstra] ( listen); 11 May 1930 – 6 August 2002) was a Dutch computer scientist. A theoretical physicist by training, he worked as a programmer at the Mathematisch Centrum (Amsterdam) from 1952 to 1962. He was a professor of mathematics at the Eindhoven University of Technology (1962–1984) and a research fellow at the Burroughs Corporation (1973–1984). He held the Schlumberger Centennial Chair in Computer Sciences at the University of Texas at Austin from 1984 until 1999, and retired as Professor Emeritus in 1999.
One of the most influential members 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 science and computer programming. 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.
Computer programming in the 1950s to 1960s was not recognized as an academic discipline and unlike physics there were no theoretical concepts or coding systems. Dijkstra was one of the moving forces behind the acceptance of computer programming as a scientific discipline. A training background in mathematics and physics led to his applying similar disciplines of mathematical logic and methodology to computer programming. In 1968, 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 coined the phrase "structured programming" and during the 1970s this became the new programming orthodoxy. Dijkstra's 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.
Dijkstra was an early theoretical pioneer in many research areas of computing science, including algorithm design, programming methodology, and software architecture. The academic study of concurrent computing and concurrent programming started in the 1960s, with Dijkstra (1965) 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 (mutex), deadlock (deadly embrace), 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 (Edsger W. Dijkstra Prize in Distributed Computing) the following year, in his honor.
- 1 Biography
- 2 Scientific contributions and impacts
- 2.1 Algorithmic work
- 2.2 Compiler construction and programming language research
- 2.3 Programming paradigm and methodology
- 2.4 Program design and development (software engineering research)
- 2.5 Operating system research
- 2.6 Concurrent computing and programming
- 2.7 Distributed computing
- 2.8 Formal specification and verification
- 2.9 On the nature of computer science and computer programming
- 3 Personality and working style
- 4 EWDs
- 5 Personal life
- 6 Quotes
- 7 Influence and recognition
- 8 Awards and honors
- 9 See also
- 10 Bibliography
- 11 References
- 12 External links
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 during his last years in high school. He had hoped to represent the Netherlands in the United Nations. He graduated in 1948 with the highest possible marks in mathematics, physics, chemistry, and biology. So his teachers and parents counseled him to seek a career in the sciences. He decided to join the University of Leiden, to study mathematics and physics during the first years, and theoretical physics later on.
In the early 1950s, electronic computers were a novelty. Dijkstra stumbled on his career quite by accident. His father had seen an advertisement for a three-week course in programming for the electronic computer EDSAC, to be given at Cambridge University, and he advised his son to attend the course. Dijkstra felt that computers might become an important tool for theoretical physicists, and he decided to attend this course in September 1951. When he asked his supervisor, Professor dr. A. Haantjes, for a letter of recommendation, it turned out that Professor Haantjes knew Adriaan van Wijngaarden, the director of the Computation Department at the Mathematical Center in Amsterdam, and he knew that van Wijngaarden had taken the same course in 1950. Professor Haantjes phoned van Wijngaarden who invited Dijkstra to visit the Mathematical Center and wrote the letter of recommendation. Van Wijngaarden also offered Dijkstra a job, which he accepted, becoming officially the Netherlands' first "programmer" in March 1952.
In 1956 he graduated from the Leiden University in mathematics and theoretical physics. In 1959 he received his PhD from the University of Amsterdam for his 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. It also dealt with the concept of an interrupt, a novelty at that time. His PhD thesis supervisor was van Wijngaarden.
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:
After having programmed for some three years, I had a discussion with A. van Wijngaarden, who was then my boss at the Mathematical Center in Amsterdam, a discussion for which I shall remain grateful to him as long as I live. The point was that I was supposed to study theoretical physics at the University of Leiden simultaneously, and as I found the two activities harder and harder to combine, I had to make up my mind, either to stop programming and become a real, respectable theoretical physicist, or to carry my study of physics to a formal completion only, with a minimum of effort, and to become....., yes what? A programmer? But was that a respectable profession? For after all, what was programming? Where was the sound body of knowledge that could support it as an intellectually respectable discipline? I remember quite vividly how I envied my hardware colleagues, who, when asked about their professional competence, could at least point out that they knew everything about vacuum tubes, amplifiers and the rest, whereas I felt that, when faced with that question, I would stand empty-handed. Full of misgivings I knocked on van Wijngaarden's office door, asking him whether I could "speak to him for a moment"; when I left his office a number of hours later, I was another person. For after having listened to my problems patiently, he agreed that up till that moment there was not much of a programming discipline, but then he went on to explain quietly that automatic computers were here to stay, that we were just at the beginning and could not I be one of the persons called to make programming a respectable discipline in the years to come? This was a turning point in my life and I completed my study of physics formally as quickly as I could.— Edsger Dijkstra, The Humble Programmer (EWD340)
When Dijkstra married Maria (Ria) 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 at that time in The Netherlands.
Mathematisch Centrum, Amsterdam
From 1952 until 1962 Dijkstra worked at the Mathematisch Centrum in Amsterdam. The early computers were built out of vacuum tubes. They occupied large amounts of space, consumed power voraciously, and failed regularly. As Dijkstra recalls, "In retrospect one can only wonder that those first machines worked at all, at least sometimes. The overwhelming problem was to get and keep the machine in working order."
He worked closely with Bram Jan Loopstra and Carel S. Scholten, who had been hired to build a computer. Their mode of interaction remains a model of disciplined engineering: 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, but —because of the absence of journals dedicated to automatic computing— did not publish the result until 1959.
At the Mathematical Center, Dijkstra and his colleague J. A. Zonneveld developed a compiler for the programming language ALGOL 60; it had a profound influence on his later thinking on programming as a scientific activity. He and Zonneveld had completed the implementation of the first ALGOL 60 compiler by August 1960, more than a year before a compiler was produced by another group.
Eindhoven University of Technology
In 1962 Dijkstra moved to Eindhoven in the south of the Netherlands, where he became a professor in the Mathematics Department at the Eindhoven University of Technology. Then in 1964 Dijkstra and his family moved to a newly built house in Nuenen, a small town/village on the outskirts of Eindhoven.
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.
Dijkstra joined Burroughs Corporation, a company known at that time for the production of computers based on an innovative hardware architecture, as its Research Fellow in August 1973. His duties consisted of visiting some of the company'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 Corporation 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 (USA), a new 'branch' of the Tuesday Afternoon Club emerged in Austin.
He was already famous by that time, and he received a large number of invitations to lecture throughout the world. He used these visits to interact with other computer scientists, mentor younger scientists, and sharpen his skills as an English speaker.
The Burroughs years saw him at his most prolific in output of research articles. He wrote nearly 500 documents in the EWD series (described below), 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. He had been visiting the Burroughs Research Center in Austin since the late 1970s and had become quite familiar with the Department of Computer Science and its faculty. As he says in an autobiographical note, "...when The University of Texas at Austin offered me the Schlumberger Centennial Chair in Computer Sciences, the offer was actually welcome. The offer was not so surprising, nor my acceptance, for I knew Austin, I knew UT and they knew me. All through my years at Burroughs I had made it a rule to visit, wherever I went, the local university and since the late 70s Burroughs had had an Austin Research Center, a visit to which was included in most of my trips to the USA." Dijkstra remained prolific in research during his years at Austin. He had embarked on a long-term project on "Streamlining Mathematical Arguments".
The years in Austin saw Dijkstra at his best as a teacher and mentor for a generation of students, both undergraduate and graduate. From his days in the Eindhoven University of Technology, he had thought deeply about how computer science should be taught. He had sharpened his thinking on education over a number of years, and Austin provided him the opportunity for trying out his ideas.
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 (Netherlands) 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 (Ria) Debets were survived by their three children: Marcus, Femke and the computer scientist Rutger M. Dijkstra.
Scientific contributions and impacts
As an early theoretical 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/concurrent computing, distributed computing/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 science and computer programming. In addition, Dijkstra was intensely interested in teaching computer science, and in the relationships between academic computing science and the software industry.
Dijkstra's algorithmic work (especially graph algorithms, concurrent algorithms, and distributed algorithms) plays an important role in many areas of computing science. According to Leslie Lamport (2002), 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, 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' (1999): "Since 1959, all theoretical developments in SSSP [Single-Source Shortest Paths] 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. A* search algorithm (first described by Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute in 1968) is an extension of Dijkstra's 1959 algorithm. 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 called ARMAC. His objective was to choose both a problem as well as an answer (that would be produced by computer) 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 Netherland (64 cities, so that 6 bits would suffice to represent the city in the algorithm).
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 re-discovered 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 (RPN) or as an abstract syntax tree (AST). 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 (a generalization of Dekker's algorithm), 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 (together with other authors) introduced two useful abstractions (mutator and collector) 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.
Compiler construction and programming language research
Dijkstra was known to be a fan of ALGOL 60, and worked on the team that implemented the first compiler for that language. He was closely involved in the ALGOL 60 development, realisation and popularisation. 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. Apparently, he eventually left the committee because he could not agree with the majority opinions. Still, while at the Mathematisch Centrum (Amsterdam), 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; while Zonneveld shaved shortly thereafter, Dijkstra kept his beard for the rest of his life.
ALGOL was the result of a collaboration of American and European committees. ALGOL 60 (short for ALGOrithmic Language 1960) 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 programming 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
Computer programming 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 Dijkstra's own words:
What about the poor programmer? Well, to tell the honest truth: he was hardly noticed. For one thing, the first machines were so bulky that you could hardly move them and besides that, they required such extensive maintenance that it was quite natural that the place where people tried to use the machine was the same laboratory where the machine had been developed. Secondly, his somewhat invisible work was without any glamour: you could show the machine to visitors and that was several orders of magnitude more spectacular than some sheets of coding. But most important of all, the programmer himself had a very modest view of his own work: his work derived all its significance from the existence of that wonderful machine. Because that was a unique machine, he knew only too well that his programs had only local significance and also, because it was patently obvious that this machine would have a limited lifetime, he knew that very little of his work would have a lasting value.
In the late 1960s computer programming was in a 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 neither sufficient nor up to the mark. The term software crisis" was coined by some attendees at the first NATO Software Engineering Conference in 1968 at Garmisch, Germany. Edsger Dijkstra's 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 seminal 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. Fortran introduced structured programming constructs in 1978 and in successive revisions the relatively loose semantic rules governing the allowable use of goto were tightened; the "extended range" in which a programmer could use a GOTO to enter and leave a still-executing DO loop was removed from the language in 1978, and by 1995 several forms of Fortran GOTO, including the Computed GOTO and the Assigned GOTO, had been deleted from the language. Some widely used modern programming languages, such as Java and Python lack the GOTO statement, though most provide some means of breaking out of a selection, or either breaking out of or moving on to the next step of an iteration.
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: "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 [Structured Programming by Dijkstra, Dahl, and Hoare] 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." 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 structured programming language C (see also: list of C-based programming languages). Since C++ was developed from a more traditional structured language, it is a 'hybrid language', rather than a pure object-oriented programming language.
Dijkstra was particularly impressed by the dimension of the software problem when he attended the famous 1968 NATO Conference on Software Engineering, which was the first conference devoted to the problem. He claimed that programming as a discipline in contrast to a craft, that programming must no longer be an ad hoc activity, and that programming methodology should become a scientific discipline. Dijkstra formulated some of his early ideas about programming as a mathematical discipline starting around the time of publication of his letter ("Go To Statement Considered Harmful"). He continued to point out that software productivity is closely related to rigor in design, which eliminates software bugs at an early stage.
Program design and development (software engineering research)
Dijkstra's ideas about programming methodology (especially the structured programming movement) helped lay the foundations for the birth and development of the professional discipline of software engineering (in particular the software design and development), 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.
Dijkstra sent "Notes on Structured Programming", later to be one of his seminal works, to a few friends soliciting their comments. This note became a sensation, and major corporations initiated programs based on his ideas to integrate rigorous practices into their programming projects. Dijkstra had advocated certain design principles, which have now become completely accepted in the computer science community: Large systems should be constructed out of many 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. This work has had far-reaching impact on all areas of computer science, from teaching of the very first course in programming to the designs of complex software. Mathematical analysis of designs and specifications have become central activities in computer science research.
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 (to be minimized between modules) and cohesion (to be maximized within modules), 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 (SADT), Yourdon's Structured Method, Structured Systems Analysis and Design Method (SSADM), and James Martin's Information 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 (SoC), 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".
Let me try to explain to you, what to my taste is characteristic for all intelligent thinking. It is, that one is willing to study in depth an aspect of one's subject matter in isolation for the sake of its own consistency, all the time knowing that one is occupying oneself only with one of the aspects. We know that a program must be correct and we can study it from that viewpoint only; we also know that it should be efficient and we can study its efficiency on another day, so to speak. In another mood we may ask ourselves whether, and if so: why, the program is desirable. But nothing is gained —on the contrary!— by tackling these various aspects simultaneously. It is what I sometimes have called "the separation of concerns", which, even if not perfectly possible, is yet the only available technique for effective ordering of one's thoughts, that I know of. This is what I mean by "focusing one's attention upon some aspect": it does not mean ignoring the other aspects, it is just doing justice to the fact that from this aspect's point of view, the other is irrelevant. It is being one- and multiple-track minded simultaneously.
Operating system research
In the 1960s Dijkstra and his colleagues in Eindhoven designed and implemented THE (standing for 'Technische Hogeschool Eindhoven') operating system, which was organised into clearly identified layers. His 1968 article on this subject provided the foundation for subsequent designs of the operating systems.
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 (1965) 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.
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 (mutex) 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' (called there 'the problem of the deadly embrace') 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. Several years after Dijkstra posed the problem, he was surprised to find that the Massachusetts Institute of Technology designers of the sophisticated MULTICS operating system had not thought about deadlock at all, and the system would, on occasion, abruptly stop – like so many philosophers each holding a single chopstick. With gentle irony, he recalled: "You can hardly blame M.I.T. for not taking notice of an obscure computer scientist in a small town (Nuenen) in the Netherlands." The sleeping barber problem, a classic inter-process communication and synchronization problem between multiple operating system processes, is often attributed to Dijkstra.
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" (1974) 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 (PODC) 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', as can be seen by studying the book Self-stabilization (2000) of Shlomi Dolev and by browsing through the proceedings of the annual workshops on self-stabilizing systems. Self-stabilization is related to autonomic computing, which entails several "self-*" attributes: self-management, self-configuration, self-healing, self-optimization, and self-protection.
In the early 1980s he published two small papers on the problem of detecting termination in distributed systems. The first one, four pages long, was written with Carel Scholten; the second, three pages long, with Wim Feijen and Netty van Gasteren.
Formal specification and verification
From the 1970s, Dijkstra's chief interest was formal verification. The prevailing opinion at the time was that one should first write a program and then provide a mathematical proof of correctness. Dijkstra objected, noting that the resulting proofs are long and cumbersome and give no insight on how the program was developed. An alternative method is program derivation, to "develop proof and program hand in hand". One starts with a mathematical specification of what a program is supposed to do and applies mathematical transformations to the specification until it is turned into a program that can be executed. The resulting program is then known to be correct by construction. Much of Dijkstra's later work concerns ways to streamline mathematical argument.
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.
Then in 1990 Dijkstra published his book Predicate Calculus and Program Semantics with Carel S. Scholten. The book was devoted to logical and mathematical analysis of his weakest precondition semantics with a long prelude concerning predicate calculus.
On the nature of computer science and computer programming
Dijkstra wrote a large number of essays on the nature of computer science research and education, on its relationship to the industry and society, and even on the manner in which scientific articles should be written and presented.
In his 1988 paper On the Cruelty of Really Teaching Computer Science, Dijkstra argues that computer programming should be understood as a branch of mathematics, and that the formal provability of a program is a major criterion for correctness.
In a 2001 interview, he stated a desire for "elegance", whereby the correct approach would be to process thoughts mentally, rather than attempt to render them until they are complete. The analogy he made was to contrast the compositional approaches of Mozart and Beethoven.
Many of his opinions on computer science and programming have become widespread. For example, the programming phrase "two or more, use a for" (a rule of thumb when to use a loop) 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 dislikes 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,
- A confusion of even longer standing came from the fact that the unprepared included the electronic engineers that were supposed to design, build and maintain the machines. The job was actually beyond the electronic technology of the day, and, as a result, the question of how to get and keep the physical equipment more or less in working condition became in the early days the all-overriding concern. As a result, the topic became – primarily in the USA – prematurely known as 'computer science' – which, actually, is like referring to surgery as 'knife science' – and it was firmly implanted in people's minds that computing science is about machines and their peripheral equipment. Quod non [Latin: "Which is not true"]. We now know that electronic technology has no more to contribute to computing than the physical equipment. We now know that programmable computer is no more and no less than an extremely handy device for realizing any conceivable mechanism without changing a single wire, and that the core challenge for computing science is hence a conceptual one, viz., what (abstract) mechanisms we can conceive without getting lost in the complexities of our own making.
In The Humble Programmer (1972), Dijkstra wrote: "We must not forget that it is not our [computing scientists'] 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 (1976) 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 (especially as an essayist), 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, 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. 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 (1974) describes his fictional company as having over 75 percent of the world's market share.
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 (then Technische Hogeschool Eindhoven). 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.
Dijkstra's self-confidence went together with a remarkably modest lifestyle, to the point of being 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.
||This section contains too many or too-lengthy quotations for an encyclopedic entry. (December 2015)|
The question of whether Machines Can Think (…) is about as relevant as the question of whether Submarines Can Swim.
|— Dijkstra (1984), The threats to computing science (EWD898)|
- "Automatic computers have now been with us for a quarter of a century. They have had a great impact on our society in their capacity of tools, but in that capacity their influence will be but a ripple on the surface of our culture, compared with the much more profound influence they will have in their capacity of intellectual challenge without precedent in the cultural history of mankind."
- "Programming is one of the most difficult branches of applied mathematics; the poorer mathematicians had better remain pure mathematicians."
- "The tools we use have a profound (and devious!) influence on our thinking habits, and, therefore, on our thinking abilities."
- "Brainpower is by far our scarcest resource."
- "The competent programmer is fully aware of the strictly limited size of his own skull; therefore he approaches the programming task in full humility, and among other things he avoids clever tricks like the plague."
- "I see no meaningful difference between programming methodology and mathematical methodology in general."
- "Program testing can be used to show the presence of bugs, but never to show their absence!"
- "It is not the task of the University to offer what society asks for, but to give what society needs."
- "We must give industry not what it wants, but what it needs." (Dijkstra quoted in the program of his birthday symposium, Austin, Texas, 2000)
- "Simplicity is prerequisite for reliability." (Handwritten annotation)
- "A picture may be worth a thousand words, a formula is worth a thousand pictures."
- "Do only what only you can do." (Dijkstra's advice to a promising researcher, who asked how to select a topic for research.)
Influence and recognition
The difference between a computer programmer and a computer scientist is a job-title thing. Edsgar Dijkstra wants proudly to be called a "computer programmer," although he hasn't touched a computer now for some years. (...) His great strength is that he is uncompromising. It would make him physically ill to think of programming in C++.
|— Donald Knuth (1996), an interview with Donald Knuth by Jack Woehr of Dr. Dobb's Journal.|
Edsger Dijkstra was a principal contributor in the late 1950's to the development of the ALGOL, a high level programming language which has become a model of clarity and mathematical rigor. He is one of the principal exponents of the science and art of programming languages in general, and has greatly contributed to our understanding of their structure, representation, and implementation. His fifteen years of publications extend from theoretical articles on graph theory to basic manuals, expository texts, and philosophical contemplations in the field of programming languages.
The introduction given at the awards ceremony is a tribute to Dijkstra:
The working vocabulary of programmers everywhere 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. (…) 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.
Edsger is widely recognized as a man who has thought deeply about many deep questions; and among the deepest questions is that of traditional moral philosophy: How is it that a person should live their life? Edsger found his answer to this question early in his life: He decided he would live as an academic scientist, conducting research into a new branch of science, the science of computing. He would lay the foundations that would establish computing as a rigorous scientific discipline; and in his research and in his teaching and in his writing, he would pursue perfection to the exclusion of all other concerns. From these commitments he never deviated, and that is how he has made to his chosen subject of study the greatest contribution that any one person could make in any one lifetime.
This is to announce that the award formerly known as the "PODC Influential-Paper Award" has been renamed the "Edsger W. Dijkstra Prize in Distributed Computing" after the late Edsger W. Dijkstra, a pioneer in the area of distributed computing. His foundational work on concurrency primitives (such as the semaphore), concurrency problems (such as mutual exclusion and deadlock), reasoning about concurrent systems, and self-stabilization comprises one of the most important supports upon which the field of distributed computing is built. No other individual has had a larger influence on research in principles of distributed computing.
Edsger Dijkstra, one of the giants of our field and a passionate believer in the mathematical view of programs and programming (...) Over the previous quarter-century, he had formulated many of the great intellectual challenges of the field as programming—the goto statement, structured programming, concurrent processes, semaphores, deadlocks, recursive programming in Algol, and deriving correct programs.
Awards and honors
Among Dijkstra's awards and honors are:
- Member of the Royal Netherlands Academy of Arts and Sciences (1971)
- Distinguished Fellow of the British Computer Society (1971)
- The Association for Computing Machinery's A.M. Turing Award (1972)
- Harry H. Goode Memorial Award from the IEEE Computer Society (1974).
- Foreign Honorary Member of the American Academy of Arts and Sciences (1975)
- Doctor of Science Honoris Causa from the Queen's University Belfast (1976)
- Computer Pioneer Charter Recipient from the IEEE Computer Society (1982)
- ACM/SIGCSE Award for Outstanding Contributions to Computer Science Education (1989)
- Fellow of the Association for Computing Machinery (1994)
- Honorary doctorate from the Athens University of Economics & Business, Greece (2001).
The Distinguished Fellowship of the British Computer Society (BCS) 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 (UTCS) 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 (Edsger W. Dijkstra Prize in Distributed Computing) the following year, in his honor.
The Dijkstra Award for Outstanding Academic Achievement in Computer Science (Loyola University Chicago, Department of Computer Science) is named for Edger 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 (UTCS) at the University of Texas at Austin hosted the inaugural Edsger W. Dijkstra Memorial Lecture on October 12, 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.
- Dijkstra's algorithm
- Dining philosophers problem
- Guarded Command Language
- Predicate transformer semantics
- Weakest precondition calculus
- Go To Statement Considered Harmful
- On the Cruelty of Really Teaching Computer Science
- List of pioneers in computer science
- List of important publications in computer science
- List of important publications in theoretical computer science
- List of important publications in concurrent, parallel, and distributed computing
- Dijkstra, Edsger W.: A Primer of ALGOL 60 Programming: Together with Report on the Algorithmic Language ALGOL 60. (New York: Academic Press, 1962)
- Dijkstra, Edsger W.; Dahl, Ole-Johan; Hoare, C. A. R. (1972). Structured Programming. Academic Press. ISBN 0-12-200550-3.
- Dijkstra, Edsger W.: A Discipline of Programming. (Prentice Hall, 1976, 217pp)
- Dijkstra, Edsger W.: Selected Writings on Computing: A Personal Perspective (Monographs in Computer Science). (Springer, 1982, 362pp)
- Dijkstra, Edsger W.; Feijen, W. H. J.; Sterringa, Joke: A Method of Programming. (Addison-Wesley, 1988, 198pp)
- Dijkstra, Edsger W.; Scholten, Carel S.: Predicate Calculus and Program Semantics (Texts and Monographs in Computer Science). New York: Springer-Verlag, 1990, 220pp
Articles, a selection:
- Dijkstra, Edsger W. (1959). "A Note on Two Problems in Connexion with Graphs". Numerische Mathematik 23 (3): 269–271. doi:10.1007/BF01386390.
- Dijkstra, Edsger W. (1962). "Some Meditations on Advanced Programming," Proc. IFIP Congress, North-Holland, Amsterdam, pp. 535–538.
- Dijkstra, Edsger W. (1965). Cooperating Sequential Processes (Technische Hogeschool Eindhoven). Reprinted in F. Genuys (ed.), Programming Languages, Academic Press, Orlando, Florida, 1968, pp. 43–112
- Dijkstra, Edsger W. (1965). "Solution of a Problem in Concurrent Programming Control". Communications of the ACM 8 (9): 569.
- Dijkstra, Edsger W. (1965). "Programming Considered as a Human Activity," Proc. IFIP Congress, pp. 213–217.
- Dijkstra, Edsger W. (1968). Letters to the editor: Go To Statement Considered Harmful. Commun. ACM 11(3): 147-148
- Dijkstra, Edsger W. (1968). A Constructive Approach to the Problem of Program Correctness. BIT Numerical Mathematics 8(1968): pp. 174–186.
- Dijkstra, Edsger W. (1968). "The Structure of the 'THE'-Multiprogramming System," ACM Symp. on Operating Systems, Comm. ACM, Vol. 11, No. 5, May 1968, pp. 341–346.
- Dijkstra, Edsger W. (1971). A Short Introduction to the Art of Computer Programming. (Technische Hogeschool, Eindhoven)
- Dijkstra, Edsger W. (1971). Hierarchical Ordering of Sequential Processes. Acta Inf. 1: 115-138
- Dijkstra, Edsger W. (1972). The Humble Programmer. Communications of the ACM 15(10): pp. 859-866.
- Dijkstra, Edsger W. (1972). Notes on Structured Programming, in Structured Programming, by O.-J. Dahl, E. W. Dijkstra, and C. A. R. Hoare, New York: Academic Press
- Dijkstra, Edsger W. (1974). Programming as a Discipline of Mathematical Nature. American Mathematical Monthly 81(JuneJuly): pp. 608-612.
- Dijkstra, Edsger W. (1974). On the role of scientific thought (EWD447). (E.W. Dijkstra Archive, Center for American History, University of Texas at Austin)
- Dijkstra, Edsger W. (1974). Self-stabilizing Systems in Spite of Distributed Control. Commun. ACM 17(11): 643-644
- Dijkstra, Edsger W. (1975). How do we tell truths that might hurt?. In Dijkstra, Edsger W. (1982): "Selected Writings on Computing: A Personal Perspective": pp. 129-131.
- Dijkstra, Edsger W. (1975). Craftsman or Scientist. ACM Pacific 1975: 217-223
- Dijkstra, Edsger W. (1975). On the teaching of programming, i. e. on the teaching of thinking. Language Hierarchies and Interfaces 1975: 1-10
- Dijkstra, Edsger W. (1977). Programming: From Craft to Scientific Discipline. International Computing Symposium 1977: 23-30
- Dijkstra, Edsger W. (1978). On the Interplay between Mathematics and Programming. Program Construction 1978: 35-46
- Dijkstra, Edsger W. (1975). Correctness Concerns And, Among Other Things, Why They Are Resented. (ACM) Proceedings of the international conference on Reliable software. April 21–23, 1975, Los Angeles, California, USA: pp. 546-550.
- Dijkstra, Edsger W. (1975). Guarded Commands, Nondeterminacy and Formal Derivation of Programs. Commun. ACM 18(8): 453-457
- Dijkstra, Edsger W. (1978). Finding the Correctness Proof of a Concurrent Program. Program Construction 1978: 24-34
- Dijkstra, Edsger W. (1984). The threats to computing science (EWD898). (E.W. Dijkstra Archive, Center for American History, University of Texas at Austin)
- Dijkstra, Edsger W. (1986). On a Cultural Gap. The Mathematical Intelligencer 8(1): pp. 48-52.
- Dijkstra, Edsger W. (1987). Mathematicians and Computing Scientists: The Cultural Gap. Abacus 4(4): pp. 26-31.
- Dijkstra, Edsger W. (1989). On the Cruelty of Really Teaching Computer Science. Communications of the ACM 32(12): pp.1398-1404.
- Dijkstra, Edsger W. (1999). Computing Science: Achievements and Challenges. ACM SIGAPP Applied Computing Review 7(2): pp. 2-9.
- Dijkstra, Edsger W. (2001). The End of Computing Science?. Communications of the ACM 44(3): pp. 92.
- Dijkstra, Edsger W. (2001). "What led to Notes on Structured Programming". (E.W. Dijkstra Archive, Center for American History, University of Texas at Austin)
- Brinch Hansen, Per: The Origin of Concurrent Programming: From Semaphores to Remote Procedure Calls. (Springer, 2002, 534pp)
- Ben-Ari, Mordechai: Principles of Concurrent and Distributed Programming, 2nd edition. (Pearson Education Limited, 2006, 384 pp)
- Broy, Manfred; Denert, Ernst (eds.): Software Pioneers: Contributions to Software Engineering. (Springer, 2002, 728pp)
- Daylight, Edgar G.: The Dawn of Software Engineering: from Turing to Dijkstra. (Lonely Scholar, 2012, 248pp)
- Demetrescu, Camil; Goldberg, Andrew V.; Johnson, David S. (eds.): The Shortest Path Problem: Ninth DIMACS Implementation Challenge (DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, Vol. 74). (American Mathematical Society, 2009, 319 pp)
- Dolev, Shlomi: Self-stabilization. (MIT Press, 2000, 207pp)
- Downey, Allen B.: The Little Book of Semaphores, 2nd edition. (CreateSpace Independent Publishing Platform, 2009, 294pp)
- Feijen, W.; van Gasteren, A.J.M.; Gries, D.; Misra, J. (eds.): Beauty Is Our Business: A Birthday Salute to Edsger W. Dijkstra. (Springer, 1990, 455pp)
- Ghosh, Sukumar: Distributed Systems: An Algorithmic Approach, Second Edition (Chapman & Hall/CRC Computer and Information Science Series). (Taylor & Francis Group: CRC Press, 2014, 554pp, ISBN 978-1-4665-5297-5)
- Herman, Ted; Ghosh, Sukumar (eds.): Self-Stabilizing Systems: 3rd Workshop, WSS '97, Santa Barbara, California, August 1997 Proceedings. (Carleton University Press, 1997, ISBN 0-88629-333-2)
- Herman, Ted; Datta, Ajoy K. (eds.): Self-Stabilizing Systems: 5th International Workshop, WSS 2001, Lisbon, Portugal, October 1–2, 2001 Proceedings. (Springer, 2001, 229pp)
- Herman, Ted; Huang, Shing-Tsaan (eds.): Self-Stabilizing Systems: 6th International Symposium, SSS 2003, San Francisco, CA, USA, June 2003 Proceedings (Lecture Notes in Computer Science). (Springer, 2003, 215pp)
- Herman, Ted; Tixeuil, Sébastien (eds.): Self-Stabilizing Systems: 7th International Symposium, SSS 2005, Barcelona, Spain, October 2005 Proceedings (Lecture Notes in Computer Science). (Springer, 2005, 229pp)
- Kshemkalyani, Ajay D.; Singhal, Mukesh: Distributed Computing: Principles, Algorithms, and Systems. (Cambridge University Press, 2011, 756pp)
- Laplante, Phillip (ed.): Great Papers in Computer Science. (Minneapolis-St. Paul: West Publishing Company, 1996, 600pp)
- Lynch, Nancy A. (1996). Distributed Algorithms. (San Francisco, CA: Morgan Kaufmann Publishers, 1996, 904pp)
- O'Regan, Gerard: Giants of Computing: A Compendium of Select, Pivotal Pioneers. (Springer, 2013, 306pp)
- Raynal, Michel: Algorithms for Mutual Exclusion. (Cambridge, MA: MIT Press, 1986, 107pp)
- Raynal, Michel: Concurrent Programming: Algorithms, Principles, and Foundations. (Springer, 2013, 516pp)
- Shasha, Dennis; Lazere, Cathy: Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists. (Copernicus, 1998, 291pp)
- Tel, Gerard: Introduction to Distributed Algorithms, 2nd edition. (Cambridge University Press, 2000, 512pp)
- Apt, Krzysztof R. (2002). "Edsger Wybe Dijkstra (1930-2002): A Portrait of a Genius". Formal Aspects of Computing, Volume 14, Issue 2, pp. 92–98
- Daylight, Edgar G.: Dijkstra's Rallying Cry for Generalization: The Advent of the Recursive Procedure, Late 1950s–Early 1960s. (The Computer Journal (2011) 54 (11): 1756-1772.[doi: 10.1093/comjnl/bxr002])
- Haigh, Thomas (2010). Dijkstra's Crisis: The End of Algol and Beginning of Software Engineering, 1968-72. (Workshop on the History of Software, European Styles. The Netherlands, Lorentz Center, University of Leiden)
- Haigh, Thomas (2010). Crisis, What Crisis?: Reconsidering the Software Crisis of the 1960s and the Origins of Software Engineering. (Paper presented at the Second Inventing Europe / Tensions Of Europe Conference, Sofia, Bulgaria)
- Istrail, Sorin (2008). Storytelling About Lighthouses: Criticizing Professor Dijkstra Considered Harmless. Conduit, Brown University Department of Computer Science Alumni Magazine, Vol. 17, No. 2, 2008
- Istrail, Sorin (2010). Storytelling About Lighthouses: When Professor Dijkstra Slapped Me in the Quest for Beautiful Code. Conduit, Brown University Department of Computer Science Alumni Magazine, Vol. 19, No. 1, 2010
- Lee, J.A.N. (1991). Frontiers of Computing: A Tribute to Edsger W. Dijkstra on the Occasion of his 60th Birthday,. (Ann. Hist. Comp., Vol. 13, No. 1, 1991, pp. 91–96.)
- Payette, Sandy (2014). Hopper and Dijkstra: Crisis, Revolution, and the Future of Programming. (IEEE Annals of the History of Computing, Issue Vol. 36 No.04, pp: 64-73)
- Schrijver, Alexander (2012). On the History of the Shortest Path Problem. Documenta Mathematica, Extra Volume ISMP, p. 155–167
- Sniedovich, Moshe (2006). Dijkstra's Algorithm Revisited: The Dynamic Programming Connexion. (Journal of Control and Cybernetics, Vol.35, No.3, p. 599–620)
- Marateck, Samuel L. (1977). FORTRAN (Academic Press), p. 488
- Courtois, Pierre-Jacques (2008). Justifying the Dependability of Computer-based Systems: With Applications in Nuclear Engineering (Springer), p. 112
- Denning, Peter J.; Martell, Craig H. (2015). Great Principles of Computing (MIT Press), p. 157
- Birrell, N. D.; Ould, M. A. (1985). A Practical Handbook for Software Development (Cambridge University Press), p.181
- Haigh, Thomas (2010)
- Albin, Stephen T. (2003). The Art of Software Architecture: Design Methods and Techniques (Wiley Publishing, Inc.), p. 3
- Hoare, C. A. R. (12 October 2010). "The 2010 Edsger W. Dijkstra Memorial Lecture: What Can We Learn from Edsger W. Dijkstra?". Department of Computer Science, The University of Texas at Austin. Retrieved 12 August 2015.
- Ryder, Barbara G.; Soffa, Mary Lou; Burnett, Margaret (2005). Impact of Software Engineering Research on Modern Programming Languages. ACM Transactions on Software Engineering and Methodology, Vol. 14, No. 4, October 2005, p. 431-477. "Of great influence to Pascal was Structured Programming, put forth by E. W. Dijkstra. This method of proceeding in a design would obliviously be greatly encouraged by the use of a Structured Language, a language with a set of constructs that could freely be combined and nested. The textual structure of a program should directly reflect its flow of control."
- Wirth, Niklaus (2008). A Brief History of Software Engineering. IEEE Annals of the History of Computing, vol.30, no. 3, July–September 2008, pp. 32–39. "In 1965 Dijkstra wrote his famous Notes on Structured Programming and declared programming as a discipline in contrast to a craft. Also in 1965 Hoare published an important paper about data structuring. These ideas had a profound influence on new programming language, in particular Pascal. Languages are the vehicles in which these ideas were to be expressed. Structured programming became supported by a structured programming language."
- In his 2004 memoir, "A Programmer's Story: The Life of a Computer Pioneer", Brinch Hansen wrote that he used "Cooperating Sequential Processes" to guide his work implementing multiprogramming on the RC 4000, and described it saying, "One of the great works in computer programming, this masterpiece laid the conceptual foundation for concurrent programming."
- As Lamport (2002) wrote, "Edsger W. 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. That paper is probably why PODC exists; it certainly inspired most of my work."
- Lamport, Leslie. "Turing Lecture: The Computer Science of Concurrency: The Early Years (Communications of the ACM, Vol. 58 No. 6, June 2015)". ACM. Retrieved 22 September 2015.
While concurrent program execution had been considered for years, the computer science of concurrency began with Edsger Dijkstra's seminal 1965 paper that introduced the mutual exclusion problem. (...) The first scientific examination of fault tolerance was Dijkstra's seminal 1974 paper on self-stabilization. (...) The ensuing decades have seen a huge growth of interest in concurrency—particularly in distributed systems. Looking back at the origins of the field, what stands out is the fundamental role played by Edsger Dijkstra, to whom this history is dedicated.
- Lo Russo, Graziano (1997). "An Interview with A. Stepanov (Edizioni Infomedia srl.)". STLport. Retrieved 30 August 2015.
Alexander Stepanov: "...I also discovered books of two great computer scientists from whose work I learned the scientific foundation of my trade: Donald Knuth and Edsger Dijkstra. Knuth taught me the answers. Dijkstra taught me the questions. Time and time again I come back to their works for new insights."
- Hoare, Tony (March 2003). "Obituary: Edsger Wybe Dijkstra". Physics Today 56 (3): 96–98. doi:10.1063/1.1570789.
- Faulkner, Larry R.; Durbin, John R. (19 August 2013). "In Memoriam: Edsger Wybe Dijkstra". The University of Texas at Austin. Retrieved 20 August 2015.
- O'Regan, Gerard (2013). Giants of Computing: A Compendium of Select, Pivotal Pioneers. (London: Springer Verlag), pp. 91–92
- Apt, Krzysztof R. (2002)
- Gries, David (1978). Programming Methodology: A Collection of Articles by Members of IFIP WG2.3 (New York: Springer Verlag), p. 7. "The working vocabulary of programmers everywhere 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."
- Markoff, John (10 August 2002). "Edsger Dijkstra: Physicist Who Shaped Computer Era". NYTimes.com. Retrieved 10 April 2015.
- Schofield, Jack (19 August 2002). "Edsger Dijkstra: Pioneering computer programmer who made his subject intellectually respectable". The Guardian. Retrieved 19 April 2015.
- Knuth, Donald (1974). Structured Programming with Go To Statements. Computing Surveys 6 (4): 261–301. doi:10.1145/356635.356640. "A revolution is taking place in the way we write programs and teach programming, because we are beginning to understand the associated mental processes more deeply. It is impossible to read the recent [E. W. Dijkstra, O.-J. Dahl, and C. A. R. Hoare] book Structured Programming, without having it change your life. The reason for this revolution and its future prospects have been aptly described by E.W. Dijkstra in his 1972 Turing Award Lecture, The Humble Programmer."
- Broy, Manfred; Denert, Ernst (eds.) (2002). Software Pioneers: Contributions to Software Engineering, p. 19. (Springer)
- Nakagawa, Toru (18 July 2005). "Software Engineering And TRIZ (1) - Structured Programming Reviewed With TRIZ". TRIZ Journal. Retrieved 18 August 2015.
- Hashagen, Ulf; Keil-Slawik, Reinhard; Norberg, A. (eds.) (2002). History of Computing: Software Issues (International Conference on the History of Computing, ICHC 2000 April 5–7, 2000 Heinz Nixdorf MuseumsForum Paderborn, Germany). (Springer), p. 106. "Structured programming is a topic which links the histories of software as science, software as engineering, software dependability, and, perhaps above all, software as labour process."
- Henderson, Harry (2009). Encyclopedia of Computer Science and Technology, revised edition. (Facts on File, Inc.), p. 150
- "PODC Influential Paper Award: 2002", ACM Symposium on Principles of Distributed Computing, retrieved 2009-08-24
- Edsger W. Dijkstra Prize in Distributed Computing (Symposium on Principles of Distributed Computing – PODC), retrieved 2015-08-01
- Edsger W. Dijkstra Prize in Distributed Computing (European Association for Theoretical Computer Science – EATCS), retrieved 2015-08-01
- Edsger W. Dijkstra Prize in Distributed Computing (International Symposium on Distributed Computing – DISC)
- "Edsger Wybe Dijkstra". Stichting Digidome. 3 September 2003. Archived from the original on 6 December 2004.
- O'Connor, J J; Robertson, E F (July 2008). "Dijkstra biography". The MacTutor History of Mathematics, School of Mathematics and Statistics, University of St Andrews, Scotland. Archived from the original on 11 October 2013. Retrieved 18 January 2014.
- E. W. Dijkstra Archive
- E. W. Dijkstra Archive. "Another two years later, in 1957, I married and Dutch marriage rites require you to state your profession and I stated that I was a programmer. But the municipal authorities of the town of Amsterdam did not accept it on the grounds that there was no such profession. And, believe it or not, but under the heading "profession" my marriage act shows the ridiculous entry "theoretical physicist"!"
- James, Mike (1 May 2013). "Edsger Dijkstra - The Poetry of Programming". i-programmer.info. Retrieved 12 August 2015.
- Edsger W. Dijkstra Archive
- Edsger W. Dijkstra Archive
- Irfan Hyder, Syed (25 March 2013). "Learning and Life: Beauty is Our Business - Mathematics, Excellence and the Great Dijkstra". syedirfanhyder.blogspot.com. Retrieved 12 August 2015.
- Irfan Hyder, Syed (12 December 2013). "Learning and Life: Fairness in Grading: A Lesson by the Great Dijkstra". syedirfanhyder.blogspot.com. Retrieved 12 August 2015.
- Goodwins, Rupert (8 August 2002). "Computer science pioneer Dijkstra dies". Retrieved 22 December 2010.
- Laplante, Phillip A. (ed.) (1996). Great Papers in Computer Science. (Minneapolis-St. Paul: West Publishing Company)
- Chen, Peter P. (2002). From Goto-less to Structured Programming: The Legacy of Edsger W. Dijkstra. (IEEE Software, 19: 21)
- Laplante, Phillip A. (2008). Great Papers in Computer Science: A Retrospective. (Journal of Scientific and Practical Computing, Vol. 2, No. 1, December 2008, pp. 31–35)
- 2002 PODC Influential Paper Award (ACM Symposium on Principles of Distributed Computing). The following is a description of the winning paper's contribution, written by Leslie Lamport: "Edsger W. 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. That paper is probably why PODC exists; it certainly inspired most of my work. It remains to this day the most influential paper in the field."
- Hart, P. E.; Nilsson, N. J.; Raphael, B. (1968). "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". IEEE Transactions on Systems Science and Cybernetics SSC4 4 (2): 100–107. doi:10.1109/TSSC.1968.300136.
- Frana, Philip L. (2001). "An Interview with Edsger W. Dijkstra (OH 330)". Communications of the ACM 53 (8): 41–47. doi:10.1145/1787234.1787249. "What is the shortest way to travel from Rotterdam to Groningen, in general: from given city to given city. It is the algorithm for the shortest path, which I designed in about twenty minutes. One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a twenty-minute invention. In fact, it was published in '59, three years late. The publication is still readable, it is, in fact, quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. I learned later that one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities. Eventually that algorithm became, to my great amazement, one of the cornerstones of my fame."
- Dijkstra biography
- Jarník, V. (1930), "O jistém problému minimálním" [About a certain minimal problem], Práce Moravské Přírodovědecké Společnosti (in Czech) 6: 57–63.
- Prim, R. C. (November 1957), "Shortest connection networks And some generalizations", Bell System Technical Journal 36 (6): 1389–1401, doi:10.1002/j.1538-7305.1957.tb01515.x.
- Dijkstra, E. W. (1959), "A note on two problems in connexion with graphs" (PDF), Numerische Mathematik 1: 269–271, doi:10.1007/BF01386390.
- Pettie, Seth; Ramachandran, Vijaya (2002), "An optimal minimum spanning tree algorithm", Journal of the ACM 49 (1): 16–34, doi:10.1145/505241.505243, MR 2148431.
- MR 34/61
- Dolev, Shlomi (2000). Self-stabilization. (MIT Press), p. 16
- "People Behind Informatics: Dijkstra-Breakthroughs, Glossary (Garbage Collection)". University of Klagenfurt. Retrieved 12 August 2015.
- Hudson, Richard (31 August 2015). "Go GC: Prioritizing low latency and simplicity". The Go Programming Language Blog. Retrieved 21 September 2015.
Go is building a garbage collection (GC) not only for 2015 but for 2025 and beyond: A GC that supports today's software development and scales along with new software and hardware throughout the next decade.
To create a garbage collector for the next decade, we turned to an algorithm from decades ago. Go's new garbage collector is a concurrent, tri-color, mark-sweep collector, an idea first proposed by Dijkstra in 1978. This is a deliberate divergence from most "enterprise" grade garbage collectors of today, and one that we believe is well suited to the properties of modern hardware and the latency requirements of modern software.
- van Emden, Maarten (6 May 2008). "I remember Edsger Dijkstra (1930–2002)". Retrieved 22 December 2010.
- Hoare, C.A.R. (December 1973). "Hints on Programming Language Design" (PDF). p. 27.
Here is a language so far ahead of its time that it was not only an improvement on its predecessors but also on nearly all its successors.
- Stroustrup, Bjarne (2014). Programming: Principles and Practice Using C++, 2nd Edition. (Addison-Wesley Professional), p. 827
- Gram, Christian; Rasmussen, Per; Østergaard, Søren Duus (eds.) (2015). History of Nordic Computing 4 4th IFIP WG 9.7 Conference, HiNC 4, Copenhagen, Denmark, August 13–15, 2014, Revised Selected Papers. (Springer), p. 358
- Daylight, E. G. (2011). "Dijkstra's Rallying Cry for Generalization: the Advent of the Recursive Procedure, late 1950s – early 1960s". The Computer Journal. doi:10.1093/comjnl/bxr002.
- Report about the NATO Software Engineering Conference dealing with the software crisis
- Report on a conference sponsored by the NATO SCIENCE COMMITTEE Garmisch, Germany, 7th to 11th October 1968
- Dijkstra, Edsger W. A Case against the GO TO Statement (EWD-215). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (original; transcription)
- Dijkstra, E. W. (March 1968). "Letters to the editor: go to statement considered harmful". Communications of the ACM 11 (3): 147–148. doi:10.1145/362929.362947. ISSN 0001-0782.
- Knuth, Donald (1974)
- Mills, Harlan D. (1986). Structured Programming: Retrospect and Prospect. (IEEE Software 3(6): 58-66, November 1986). "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."
- Reilly, Edwin D. (2004). Concise Encyclopedia of Computer Science. (John Wiley & Sons, Ltd.), p. 734. "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."
- Nakagawa, Toru (TRIZ Journal, 2005)
- Meyer, Bertrand (2009). Touch of Class: Learning to Program Well with Objects and Contracts. (Springer), p. 188.
- Meyer, Bertrand (2009), p. 188
- Reilly, Edwin D. (2004), p. 734. "The first significant SP [Structured Programming] language was Algol 60 (q.v.). Subsequently developed SP languages in current use are Ada, C (q.v.), C++ (q.v.), Pascal, and Java (q.v.)."
- Graba, Jan (1998). Up and Running with C++. (Springer), p. 1
- Broy, Manfred; Denert, Ernst (2002)
- Henderson, Harry (Facts on File, Inc., 2009)
- Selby, Richard W. (2007). Software Engineering: Barry W. Boehm's Lifetime Contributions to Software Development, Management, and Research. (IEEE Computer Society), pp. 701–702
- Dijkstra, Edsger W (1982). "On the role of scientific thought". Selected writings on Computing: A Personal Perspective. New York, NY, USA: Springer-Verlag. pp. 60–66. ISBN 0-387-90652-5.
- Brown, Kyle; Craig, Gary; Hester, Greg (2003). Enterprise Java Programming with IBM WebSphere, 2nd Edition (IBM Press), p. 5. "Most experienced IT professionals will agree that developing and adhering to a standard architecture is key to the success of large-scale software development. Computer pioneer Edsger Dijkstra validated this notion when he developed THE operating system in 1968. Since then, layered architectures have proved their viability in technological domains, such as hardware and networking.
Layering has proved itself in the operating system domain; however, the same benefits are available when applied to e-commerce or to thin client–oriented applications. Layered architectures have become essential in supporting the iterative development process by promoting reusability, scalability, and maintainability."
- Grier, David Alan. "Closer Than You Might Think: Layers upon Layers". IEEE Computer Society. Retrieved 12 August 2015.
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.
- Albin, Stephen T. (Wiley Publishing, Inc., 2003), p. 3
- Dijkstra, Edsger W. Over seinpalen (EWD-74). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (original; transcription)
- Brinch Hansen, Per (2002). The Origin of Concurrent Programming: From Semaphores to Remote Procedure Calls. (Springer)., p. 8
- McCormick, John W.; Singhoff, Frank; Hugues, Jérôme (2011). Building Parallel, Embedded, and Real-Time Applications with Ada (Cambridge University Press), p. 5. "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 (1968). Moti Ben-Ari (1982) 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 (hardware and software) 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.'"
- Anderson, J.H.; Kim, Y.-J.; Herman, T. (2003). Shared-Memory Mutual Exclusion: Major Research Trends Since 1986. (Distributed Computing 16(2-3), 75-110)
- Alagarsamy, K. (2003). Some Myths About Famous Mutual Exclusion Algorithms. (ACM SIGACT News, 34(3): 94-103)
- Raynal, Michel (2013). Concurrent Programming: Algorithms, Principles, and Foundations (Springer), p. vi. "Since the early work of E.W. Dijkstra (1965), who introduced the mutual exclusion problem, the concept of a process, the semaphore object, the notion of a weakest precondition, and guarded commands (among many other contributions), 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."
- James, Mike (1 May 2013). "Edsger Dijkstra - The Poetry of Programming". i-programmer.info. Retrieved 12 August 2015.
Although Dijkstra will always be remembered for structured programming, and for his style and approach, he also invented many other of the standard ideas of programming. If you are struggling with multi-threaded programming you may have encountered the semaphore, and the idea of the "deadly embrace". These, and more, are the result of Dijkstra's work on concurrent programming. He showed how this particularly difficult area of programming could be made relatively safe.
- Hoare, C. A. R. (2004). "Communicating Sequential Processes" (PDF). usingcsp.com (originally published in 1985 by Prentice Hall International). External link in
- Shasha, Dennis; Lazere, Cathy (1998). Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists. (Copernicus), p. 64
- Edsger W. Dijkstra Prize in Distributed Computing (ACM Symposium on Principles of Distributed Computing). The citation for the prize reads: "The Edsger W. Dijkstra Prize in Distributed Computing is named for Edsger Wybe Dijkstra (1930–2002), a pioneer in the area of distributed computing. His foundational work on concurrency primitives (such as the semaphore), concurrency problems (such as mutual exclusion and deadlock), reasoning about concurrent systems, and self-stabilization comprises one of the most important supports upon which the field of distributed computing is built. No other individual has had a larger influence on research in principles of distributed computing."
- Edsger W. Dijkstra Prize in Distributed Computing (EATCS International Symposium on Distributed Computing)
- 2002 PODC Influential Paper Award (ACM Symposium on Principles of Distributed Computing)
- Dolev, Shlomi (2000). Self-stabilization. (MIT Press), p. 3
- Self-Stabilization Home Page
- Back, Ralph-Johan; Wright, Joakim (1998). Refinement Calculus A Systematic Introduction (Texts in Computer Science). (Springer)
- Morgan, Carroll; Vickers, Trevor (1992). On the Refinement Calculus. (Springer)
- Back, Ralph-Johan; Wright, Joakim (1998), p. v
- "Edsger Dijkstra – Discipline in Thought (visit www.catonmat.net for notes)". Video.google.com. Retrieved 20 April 2012.
- Stabler, Edward P. (2014-01-01). Roeper, Tom; Speas, Margaret, eds. Recursion in Grammar and Performance. Studies in Theoretical Psycholinguistics. Springer International Publishing. pp. 159–177. doi:10.1007/978-3-319-05086-7_8. ISBN 978-3-319-05085-0.
- Dijkstra, Edsger W. On a cultural gap (EWD-924). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (original; transcription)Dijkstra, E.W. (1986). "On a cultural gap". The Mathematical Intelligencer 8 (1): 48–52. doi:10.1007/bf03023921.
- Dijkstra, Edsger W. On the cruelty of really teaching computer science (EWD-1036). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (original; transcription)
- Irfan Hyder, Syed (2013)
- In Memoriam Edsger Wybe Dijkstra (memorial), University of Texas.
- Istrail, Sorin (Brown Univesirty Department of Computer Science Alumni Magazine, Vol 17.2, 2008)
- Dijkstra, Edsger. "Denken als Discipline". VPRO. Noorderlicht. Retrieved 21 June 2016.
- Dijkstra, Edsger W. How do we tell truths that might hurt? (EWD-498). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (original; transcription)
- Dijkstra, Edsger W. EWD-475. E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (original; transcription)
- Dijkstra, Edsger W. EWD-539. E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (original; transcription)
- Dijkstra, Edsger W. EWD-427. E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (original; transcription)
- Dijkstra, Edsger W. EWD-443. E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (original; transcription)
- Dijkstra, Edsger W (1982). Selected Writings on Computing: A Personal Perspective. Berlin: Springer-Verlag. ISBN 978-0-387-90652-2.
- Online EWD archive, University of Texas.
- Dijkstra, Edsger W. The threats to computing science (EWD898). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (original; transcription)
- Dijkstra, Edsger W. Why American Computing Science seems incurable (EWD-1209). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (original; transcription)
- Dijkstra, Edsger W. Structured programming (EWD-268). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (original; transcription)
- Dijkstra, Edsger W. Answers to questions from students of Software Engineering (EWD-1305). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (original; transcription)
- Edsger Dijkstra - How do we tell truths that might hurt?
- Dijkstra, Edsger W. A first exploration of effective reasoning (EWD-1239). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (original; transcription)
- Irfan Hyder, Syed (9 February 2015). "Learning and Life: A Formula is Worth a Thousand Pictures: Dijkstra vs Buzan's Mind-Maps". syedirfanhyder.blogspot.com. Retrieved 12 August 2015.
- Woehr, Jack (1 April 1996). "An interview with Donald Knuth". Dr. Dobb's Journal. Retrieved 12 August 2015.
- Edsger W. Dijkstra - Award Winner - ACM Awards (Extract from the Turing award Citation ready by M. Doug McIlroy, chairman of the ACM Turing Award Committee, at the presentation of his lecture on August 14, 1972, at the ACM Annual Conference in Boston.)
- Dale, Nell; Lewis, John (2011). Computer Science Illuminated, 4th Edition (Jones and Barlett Publishers, LLC.), p. 313
- Denning, Peter J. (2004). The Field of Programmers Myth. (Communications of the ACM, 47 (7) pp. 15–20)
- "Edsger Wybe Dijkstra (1930 - 2002)". Royal Netherlands Academy of Arts and Sciences. Retrieved 17 July 2015.
- "A. M. Turing Award". Association for Computing Machinery. Retrieved 5 February 2011.
- "Edsger W. Dijkstra 1974 Harry H. Goode Memorial Award Recipient". IEEE Computer Society. Retrieved 17 January 2014.
- "ACM Fellows – D". Association for Computing Machinery. Retrieved 15 February 2011.
- "Roll of Distinguished Fellows". British Computer Society. Retrieved 2014-09-10.
- Feijen, W.; van Gasteren, A.J.M.; Gries, D.; Misra, J. (eds.): Beauty Is Our Business: A Birthday Salute to Edsger W. Dijkstra. (Springer)
- Awards: Loyola University Chicago
|Wikimedia Commons has media related to Edsger Wybe Dijkstra.|
|Wikiquote has quotations related to: Edsger W. Dijkstra|
- E.W. Dijkstra Archive (Center for American History, University of Texas at Austin)
- Computer Pioneers - Edsger W. Dijkstra - History Committee archive - IEEE Computer Society
- Edsger W. Dijkstra Additional Materials - A.M. Turing Award Winner
- Edsger Dijkstra - The Centre for Computing History
- Edsger W. Dijkstra - University of Pittsburgh - School of Information Science - Hall of Fame
- An Interview with Edsger W. Dijkstra OH 330 (2001) by Philip L. Frana
- Edsger Wybe Dijkstra (1930–2002): A Portrait of a Genius (2002) by Krzysztof R. Apt
- In Memoriam Edsger Wybe Dijkstra (1930-2002) (2002) by Mario Szegedy
- From Goto-less to Structured Programming: The Legacy of Edsger W. Dijkstra (2002) by Peter P. Chen
- Dijkstra's Dream: Internal Iterators as Software Theorems (2002) by Jan Dockx, Marko van Dooren, and Eric Steegmans, KU Leuven, Belgium
- Edsger Wybe Dijkstra (Эдсгер Дейкстра), photos of Edsger Wybe Dijkstra
- How can we explain Edsger W. Dijkstra to those who didn't know him? (2002) by David Gries
- People behind Informatics: Dijkstra - Breakthroughs by Laszlo Böszörmenyi and Stefan Podlipnig, University of Klagenfurt, Austria
- People behind Informatics: Dijkstra - Legacy by Laszlo Böszörmenyi and Stefan Podlipnig, University of Klagenfurt, Austria
- Demonic Nondeterminacy: A Tribute to Edsger Wybe Dijkstra (Jayadev Misra, 2003)
- E. W. Dijkstra, una vita da informatico (Lorenzo Milone, Mondo Digitale, 2009)
- Storytelling About Lighthouses: Criticizing Professor Dijkstra Considered Harmless by Sorin Istrail (Conduit, Brown University Department of Computer Science Alumni Magazine, Vol. 17, No. 2, 2008)
- Storytelling About Lighthouses: When Professor Dijkstra Slapped Me in the Quest for Beautiful Code by Sorin Istrail (Conduit, Brown University Department of Computer Science Alumni Magazine, Vol. 19, No. 1, 2010)
- What can we learn from Edsger W. Dijkstra? by Tony Hoare (Edsger W. Dijkstra Memorial Lecture, The University of Texas at Austin, 2010)
- Dijkstra's Crisis: The End of Algol and Beginning of Software Engineering, 1968-72 (2010) by Thomas Haigh
- Edsger Dijkstra - The Poetry of Programming by Mike James (i-programmer.info, 1 May 2013)
- Learning and Life: Beauty is Our Business - Mathematics, Excellence and the Great Dijkstra by Dr. Syed Irfan Hyder (25 March 2013)
- Learning and Life: Fairness in Grading: A Lesson by the Great Dijkstra by Dr. Syed Irfan Hyder (12 December 2013)
- Learning and Life: A Formula is Worth a Thousand Pictures: Dijkstra vs Buzan's Mind-Maps by Dr. Syed Irfan Hyder (9 February 2015)
- Discipline in Thought A website dedicated to disciplined thinking, calculational mathematics, and mathematical methodology. The members of this site are markedly influenced by the works of E. W. Dijkstra.
- Dijkstra's Rallying Cry for Generalization A blog devoted to Dijkstra's works and thoughts, created and maintained by the historian of computing Edgar G. Daylight.