Edsger W. Dijkstra

Edsger Wybe Dijkstra ( ; ; 11 May 1930 – 6 August 2002) was a Dutch computer scientist, programmer, mathematician, and science essayist.

Born in Rotterdam in the Netherlands, Dijkstra studied mathematics and physics and then theoretical physics at the University of Leiden. Adriaan van Wijngaarden offered him a job as the first computer programmer in the Netherlands at the Mathematical Centre in Amsterdam, where he worked from 1952 until 1962. He formulated and solved the shortest path problem in 1956, and in 1960 developed the first compiler for the programming language ALGOL 60 in conjunction with colleague Jaap A. Zonneveld. In 1962 he moved to Eindhoven, and later to Nuenen, where he became a professor in the Mathematics Department at the Technische Hogeschool Eindhoven. In the late 1960s, he built the THE multiprogramming system, which influenced the designs of subsequent systems through its use of software-based paged virtual memory. Dijkstra joined Burroughs Corporation as its sole research fellow in August 1973. The Burroughs years saw him at his most prolific in output of research articles. He wrote nearly 500 documents in the "EWD" series, most of them technical reports, for private circulation within a select group.

Dijkstra accepted the Schlumberger Centennial Chair in the Computer Science Department at the University of Texas at Austin in 1984, working in Austin, USA, until his retirement in November 1999. He and his wife returned from Austin to his original house in Nuenen, where he died on 6 August 2002 after a long struggle with cancer.

He received the 1972 ACM Turing Award for fundamental contributions to developing structured programming languages. Shortly before his death, he received the ACM PODC Influential Paper Award in distributed computing for his work on self-stabilization of program computation. This annual award was renamed the Dijkstra Prize the following year, in his honor.

Life and works

Early years Dijkstra was born in Rotterdam. His father Douwe Wybe Dijkstra (1898–1970) was a chemist who studied with Frans Maurits Jaeger and was president of the Rotterdamsche Chemische Kring, the Rotterdam branch of the Royal Netherlands Chemical Society; he taught chemistry at a secondary school and was later its superintendent. His mother Brechtje Cornelia Kluijver (1900–1994) was a mathematician but never had a formal job.

Dijkstra had considered a career in law and had hoped to represent the Netherlands in the United Nations. However, after graduating from Gymnasium Erasmianum in 1948, at his parents' suggestion he studied mathematics and physics and then theoretical physics at the University of Leiden.

In the early 1950s, electronic computers were a novelty. Dijkstra stumbled on his career by accident, and through his supervisor, Professor , he met Adriaan van Wijngaarden, the director of the Computation Department at the Mathematical Centre in Amsterdam, who offered Dijkstra a job; he officially became the Netherlands' first "programmer" in March 1952.

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 then in The Netherlands.

In 1959, he received his PhD from the University of Amsterdam for a thesis entitled 'Communication with an Automatic Computer', devoted to a description of the assembly language designed for the first commercial computer developed in the Netherlands, the Electrologica X1. His thesis supervisor was Van Wijngaarden.

Mathematisch Centrum, Amsterdam From 1952 until 1962, Dijkstra worked at the Mathematisch Centrum in Amsterdam,

Burroughs Corporation Dijkstra joined the Burroughs Corporation—a company known then for producing computers based on an innovative hardware architecture—as its research fellow in August 1973. His duties consisted of visiting some of the firm's research centers a few times a year and carrying on his own research, which he did in the smallest Burroughs research facility, namely, his study on the second floor of his house in Nuenen. In fact, Dijkstra was the only research fellow of Burroughs and worked for it from home, occasionally travelling to its branches in the United States. As a result, he reduced his appointment at the university to one day a week. That day, Tuesday, soon became known as the day of the famous 'Tuesday Afternoon Club', a seminar during which he discussed with his colleagues scientific articles, looking at all aspects: notation, organisation, presentation, language, content, etc. Shortly after, he moved in 1984 to the University of Texas at Austin (USA), a new 'branch' of the Tuesday Afternoon Club emerged in Austin, Texas. He and his wife were survived by their three children: Marcus, Femke, and the computer scientist Rutger M. Dijkstra.

Personality Dijkstra at the blackboard during a conference at ETH Zurich in 1994. He once remarked, "A picture may be worth a thousand words, a formula is worth a thousand pictures."

Character

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.

As a university professor for much of his life, Dijkstra saw teaching not just as a required activity but as a serious research endeavour. 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.

Personal life Dijkstra led a modest lifestyle to the point of "being spartan".

Simplicity and elegance

Dijkstra thought simplicity and elegance were important in computer science and in mathematics. His interest in 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, further, if he required more than five lines to prove something, he was on the wrong track.

He thought that in large programs, where there was a potential for messiness, it was vital to seek elegance. With deliberate hyperbole, he wrote that "in the practice of computing, where we have so much latitude for making a mess of it, mathematical elegance is not a dispensable luxury, but a matter of life and death".

Writing style

Dijkstra was famous for his wit, eloquence, rudeness, abruptness and often cruelty to fellow professionals, and way with words, such as in his remark, "The question of whether Machines Can Think (…) is about as relevant as the question of whether Submarines Can Swim." His advice to a promising researcher, who asked how to select a topic for research, was the phrase: "Do only what only you can do".

Recurring themes In many of his more witty 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".

Legacy Dijkstra won the Turing award in 1972 for his advocacy of structured programming, a programming paradigm that makes use of structured control flow as opposed to unstructured jumps to different sections in a program using Goto statements. His 1968 letter to the editor of Communications of ACM, "Go To statement considered harmful", caused a major debate. Modern programmers generally adhere to the paradigm of structured programming.

Among his most famous contributions to computer science is Dijkstra's algorithm, for finding the shortest path through a network, which is widely taught in modern computer science undergraduate courses, and is used in the computer network routing protocols OSPF and IS-IS.

Other important work included the Shunting yard algorithm for parsing; the "THE" operating system, an early example of structuring an operating system as a set of layers; the Banker's algorithm for resource allocation; and the semaphore construct for coordinating multiple processes. Another concept formulated by Dijkstra in the field of distributed computing is that of self-stabilization, a method of ensuring fault-tolerance.

Font Luca Cardelli designed a Dijkstra font to mimic Dijkstra's writing style which had become so recognizable among computer scientists in the 1980s.

Awards and honors Among Dijkstra's awards and honors are: 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).

In 1969, the British Computer Society (BCS) received approval for an award and fellowship, Distinguished Fellow of the British Computer Society (DFBCS), to be awarded under bylaw 7 of their royal charter. In 1971, the first election was made, to Dijkstra.

In 1990, on occasion of Dijkstra's 60th birthday, 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 Edsger W. Dijkstra. Beginning in 2005, this award recognizes the top academic performance by a graduating computer science major. Selection is based on GPA in all major courses and election by department faculty.

The Department of Computer Science (UTCS) at the University of Texas at Austin hosted the inaugural Edsger W. Dijkstra Memorial Lecture on 12 October 2010. Tony Hoare, Emeritus Professor at Oxford and Principal Researcher at Microsoft Research, was the speaker for the event. This lecture series was made possible by a generous grant from Schlumberger to honor the memory of Dijkstra.

Selected publications Books

Selected articles

Reprinted in Published as