Edsger W. Dijkstra

From Wikipedia, the free encyclopedia
  (Redirected from Edsger Dijkstra)
Jump to: navigation, search
Edsger Wybe Dijkstra
Edsger Wybe Dijkstra.jpg
Edsger Wybe Dijkstra in 2002
Born (1930-05-11)11 May 1930
Rotterdam, Netherlands
Died 6 August 2002(2002-08-06) (aged 72)
Nuenen, Netherlands
Fields Computer science
Institutions
Doctoral advisor Adriaan van Wijngaarden
Doctoral students
Known for
Notable awards

Edsger Wybe Dijkstra (Dutch: [ˈɛtsxər ˈʋibə ˈdɛikstra]; 11 May 1930 – 6 August 2002) was a Dutch computer scientist.[1] He received the 1972 Turing Award for fundamental contributions to developing programming languages, and was the Schlumberger Centennial Chair of Computer Sciences at The University of Texas at Austin from 1984 until 2000.

Dijkstra was one of the most influential members of computing science’s founding generation. Through his fundamental contributions Edsger Dijkstra helped shape the field of computer science. His contributions ranged from the engineering side of computer science to the theoretical one and covered several areas including compiler construction, operating systems, distributed systems, sequential and concurrent programming, software engineering, and graph algorithms. Many of his papers are the source of new research areas. Several concepts that are now standard in computer science were first identified by Dijkstra and/or bear names coined by him.[2][3] A 1994 survey of over a thousand professors of computer science was conducted to obtain a list of 36 scholarly papers considered to be the most important in terms of contributions to the field, and Dijkstra authored five of them.[4][5]

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.[6] 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.[7]

The academic study of concurrent programming started in the 1960s, with Dijkstra (1965) credited with being the first paper in this field, identifying and solving mutual exclusion.[8] As Per Brinch Hansen, a pioneer in the field of concurrent computing notes, ‘Dijkstra lays the conceptual foundation for abstract concurrent programming.’[9] Dijkstra was one of the very 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.[10][11]

Life and work[edit]

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.[12][13] Dijkstra studied theoretical physics at Leiden University, but quickly realized he was more interested in computer science. Originally employed by the Mathematisch Centrum in Amsterdam, he held a professorship at the Eindhoven University of Technology, worked as a research fellow for Burroughs Corporation in the early 1980s, and later held the Schlumberger Centennial Chair in Computer Sciences at the University of Texas at Austin, in the United States. He retired in 2000.

Among his contributions to computer science are a shortest path algorithm, known as Dijkstra's algorithm; the Shunting yard algorithm; the THE multiprogramming system, an important early example of structuring a system as a set of layers; the Banker's algorithm; and the semaphore construct for coordinating multiple processors and programs. Another concept due to Dijkstra in the field of distributed computing is that of self-stabilization – an alternative way to ensure the reliability of the system. 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)[14] is an extension of Dijkstra's 1959 algorithm. The Prim's algorithm was originally developed in 1930 by Czech mathematician Vojtěch Jarník[15] and later independently rediscovered and republished by Robert C. Prim in 1957[16] and Dijkstra in 1959.[17] Therefore, it is also sometimes called the DJP algorithm.[18]

Dijkstra's algorithm. It picks the unvisited vertex with the lowest-distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if smaller. Mark visited (set to red) when done with neighbors.

While he 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",[19] which was then published as a letter in CACM.[20] Editor Niklaus Wirth gave this letter the heading "Go To Statement Considered Harmful", which introduced the phrase "considered harmful" into computing. 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, the title of his 1972 book, coauthored with C.A.R. Hoare and Ole-Johan Dahl. Dijkstra also strongly opposed the teaching of BASIC.[21]

Dijkstra was known to be a fan of ALGOL 60, and worked on the team that implemented the first compiler for that language. Dijkstra and Jaap 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.[22] The ALGOL 60 compiler was one of the first to support recursion.[23]

Dijkstra wrote two important papers in 1968, devoted to the structure of a multiprogramming operating system called THE, and to Cooperating Sequential Processes.[24]

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 a 2001 interview,[25] 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.

Dijkstra was one of the early pioneers in the field of distributed computing. In particular, his paper "Self-stabilizing Systems in Spite of Distributed Control" (1974) started the sub-field of self-stabilization. Dijkstra's work was not widely noticed until Leslie Lamport's invited talk at the ACM Symposium on Principles of Distributed Computing in 1983. In his report on Dijkstra's work on self-stabilizing distributed systems, Lamport regard it to be 'a milestone in work on fault-tolerance' and 'a very fertile field for research'.[26]

Many of his opinions on computer science and programming have become widespread. For example, he coined the programming phrase "two or more, use a for",[citation needed] alluding to the rule of thumb that when you find yourself processing more than one instance of a data structure, it is time to consider encapsulating that logic inside a loop. 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. When expressing the abstract nature of computer science, he wrote

The job [of operating or using a computer] 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"].[28]

He died in Nuenen on 6 August 2002 after a long struggle with cancer.[29] The following year, the ACM (Association for Computing Machinery) PODC Influential Paper Award in distributed computing was renamed the Dijkstra Prize in his honor.

EWDs and writing by hand[edit]

Dijkstra was 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. Looking closely at himself he realized that if he wrote about things they would appreciate at the MC in Amsterdam his colleagues in Eindhoven would not understand; if he wrote about things they would like in Eindhoven, his former colleagues in Amsterdam would look down on him. He then decided to write only for himself, and in this way the EWDs were born. Dijkstra would distribute 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. 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.[31]

One of Dijkstra's sidelines was serving as chairman of the board of the fictional 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.[32] 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.[33] A more successful effort was the Standard Proof for Pythagoras' Theorem, that replaced the more than 100 incompatible existing proofs.[34] Dijkstra described Mathematics Inc. as "the most exciting and most miserable business ever conceived".[32] EWD 443 (1974) describes his fictional company as having over 75 percent of the world's market share.[35][36]

Dijkstra at the blackboard during a conference at ETH Zurich in 1994

Despite having invented much of the technology of software, Dijkstra eschewed the use of computers in his own work for many decades. Almost all EWDs appearing after 1972 were hand-written. When lecturing, he would write proofs in chalk on a blackboard rather than using overhead foils. Even after he acquired an Apple Macintosh computer, he used it only for email and for browsing the World Wide Web.[37]

Awards and honors[edit]

Among Dijkstra's awards and honors are:[37]

See also[edit]

Bibliography[edit]

  • 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.: 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])
  • Daylight, Edgar G.: The Dawn of Software Engineering: from Turing to Dijkstra. (Lonely Scholar, 2012, 248pp)
  • Dijkstra, Edsger W.; Hoare, C. A. R.; Dahl, Ole-Johan: Structured Programming (A.P.I.C. studies in data processing, no. 8). (Academic Press, 1972, 418pp)
  • 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)
  • 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)
  • 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)
  • 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)
  • 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)
  • 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)
  • Sniedovich, Moshe (2006). Dijkstra’s Algorithm Revisited: The Dynamic Programming Connexion. (Journal of Control and Cybernetics, Vol.35, No.3, p.599–620)
  • Tel, Gerard: Introduction to Distributed Algorithms, 2nd edition. (Cambridge University Press, 2000, 512pp)

References[edit]

  1. ^ Hoare, Tony (March 2003). "Obituary: Edsger Wybe Dijkstra". Physics Today 56 (3): 96–98. doi:10.1063/1.1570789. 
  2. ^ Markoff, John (10 August 2002). "Edsger Dijkstra: Physicist Who Shaped Computer Era". NYTimes.com. Retrieved 10 April 2015. 
  3. ^ Schofield, Jack (19 August 2002). "Edsger Dijkstra: Pioneering computer programmer who made his subject intellectually respectable". The Guardian. Retrieved 19 April 2015. 
  4. ^ Chen, Peter P. (2002). From Goto-less to Structured Programming: The Legacy of Edsger W. Dijkstra. (IEEE Software, 19[5]: 21)
  5. ^ Laplante, Phillip (2008). Great Papers in Computer Science: A Retrospective. (Journal of Scientific and Practical Computing, Vol. 2, No. 1, December 2008, pp. 31–35)
  6. ^ Broy, Manfred; Denert, Ernst (eds.) (2002). Software Pioneers: Contributions to Software Engineering, p. 19. (Springer)
  7. ^ Henderson, Harry (2009). Encyclopedia of Computer Science and Technology, revised edition. (Facts on File, Inc.), p. 150
  8. ^ "PODC Influential Paper Award: 2002", ACM Symposium on Principles of Distributed Computing, retrieved 2009-08-24 
  9. ^ Brinch Hansen, Per (2002). The Origin of Concurrent Programming: From Semaphores to Remote Procedure Calls. (Springer)., p. 8
  10. ^ Edsger W. Dijkstra Prize in Distributed Computing (ACM Symposium on Principles of Distributed Computing), retrieved 2015-08-01 
  11. ^ Edsger W. Dijkstra Prize in Distributed Computing (EATCS International Symposium on Distributed Computing), retrieved 2015-08-01 
  12. ^ "Edsger Wybe Dijkstra". Stichting Digidome. 3 September 2003. Archived from the original on 6 December 2004. 
  13. ^ 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. 
  14. ^ 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. 
  15. ^ 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 .
  16. ^ 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 .
  17. ^ Dijkstra, E. W. (1959), "A note on two problems in connexion with graphs" (PDF), Numerische Mathematik 1: 269–271, doi:10.1007/BF01386390 .
  18. ^ 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 .
  19. ^ 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)
  20. ^ 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. 
  21. ^ 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)
  22. ^ van Emden, Maarten (6 May 2008). "I remember Edsger Dijkstra (1930–2002)". Retrieved 22 December 2010. 
  23. ^ 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. 
  24. ^ Dijkstra, Edsger (1968). "Cooperating Sequential Processes". Retrieved 29 May 2013. 
  25. ^ "Edsger Dijkstra – Discipline in Thought (visit www.catonmat.net for notes)". Video.google.com. Retrieved 20 April 2012. 
  26. ^ Dolev, Shlomi (2000). Self-stabilization. (MIT Press), p. 3
  27. ^ Dijkstra, Edsger W. How do we tell truths that might hurt? (EWD498). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin.  (original; transcription)
  28. ^ 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. 
  29. ^ Goodwins, Rupert (8 August 2002). "Computer science pioneer Dijkstra dies". Retrieved 22 December 2010. 
  30. ^ Dijkstra, Edsger W. The threats to computing science (EWD898). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin.  (original; transcription)
  31. ^ Online EWD archive, University of Texas .
  32. ^ a b Dijkstra, Edsger W. EWD-475. E.W. Dijkstra Archive. Center for American History, University of Texas at Austin.  (original; transcription)
  33. ^ Dijkstra, Edsger W. EWD-539. E.W. Dijkstra Archive. Center for American History, University of Texas at Austin.  (original; transcription)
  34. ^ Dijkstra, Edsger W. EWD-427. E.W. Dijkstra Archive. Center for American History, University of Texas at Austin.  (original; transcription)
  35. ^ Dijkstra, Edsger W. EWD-443. E.W. Dijkstra Archive. Center for American History, University of Texas at Austin.  (original; transcription)
  36. ^ Dijkstra, Edsger W (1982). Selected Writings on Computing: A Personal Perspective. Berlin: Springer-Verlag. ISBN 978-0-387-90652-2. 
  37. ^ a b In Memoriam Edsger Wybe Dijkstra (memorial), University of Texas .
  38. ^ "Edsger Wybe Dijkstra (1930 - 2002)". Royal Netherlands Academy of Arts and Sciences. Retrieved 17 July 2015. 
  39. ^ "A. M. Turing Award". Association for Computing Machinery. Retrieved 5 February 2011. 
  40. ^ "Edsger W. Dijkstra 1974 Harry H. Goode Memorial Award Recipient". IEEE Computer Society. Retrieved 17 January 2014. 
  41. ^ "ACM Fellows – D". Association for Computing Machinery. Retrieved 15 February 2011. 

External links[edit]