The Full Wiki

Edsger W. Dijkstra: Wikis

Advertisements
  
  

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Encyclopedia

From Wikipedia, the free encyclopedia

Edsger Wybe Dijkstra

Born May 11, 1930(1930-05-11)
Rotterdam, Netherlands
Died August 6, 2002 (aged 72)
Nuenen, Netherlands
Fields Computer science
Institutions Mathematisch Centrum
Eindhoven University of Technology
The University of Texas at Austin
Doctoral advisor Adriaan van Wijngaarden
Doctoral students Nico Habermann
Martin Rem
David Naumann
Cornelis Hemerik
Jan Tijmen Udding
Johannes van de Snepscheut
Antonetta van Gasteren
Known for Dijkstra's algorithm
Structured programming
THE multiprogramming system
Semaphore
Notable awards Turing Award
Association for Computing Machinery

Edsger Wybe Dijkstra (May 11, 1930 – August 6, 2002; Dutch pronunciation: [ˈɛtsxər ˈwibə ˈdɛɪkstra]  ( listen)) was a Dutch computer scientist. 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.

Shortly before his death in 2002, he received the ACM PODC Influential Paper Award in distributed computing for his work on self-stabilization of program computation. This annual award was renamed the Dijkstra Prize the following year, in his honour.

Contents

Life and work

Born in Rotterdam, Netherlands, 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 1970s, 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 the shortest path-algorithm, also known as Dijkstra's algorithm; Reverse Polish Notation and related Shunting yard algorithm; the THE multiprogramming system, an important early example of structuring a system as a set of layers; 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 protocol OSPF, Open Shortest Path First.

While he had programmed extensively in machine code in the 1950s, he was known for his low opinion of the GOTO statement in computer programming, writing a paper in 1965, and culminating in the 1968 article "A Case against the GO TO Statement" (EWD215), regarded as a major step towards the widespread deprecation of the GOTO statement and its effective replacement by structured control constructs, such as the while loop. This methodology was also called structured programming, the title of his 1972 book, coauthored with C.A.R. Hoare and Ole-Johan Dahl. The March 1968 ACM letter's famous title, "Go To Statement Considered Harmful",[1] was not the work of Dijkstra, but of Niklaus Wirth, then editor of Communications of the ACM. Dijskra also strongly opposed the teaching of BASIC,[2] a language whose programs are typically GOTO-laden.

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.

Dijkstra wrote two important papers in 1968, devoted to the structure of a multiprogramming operating system called THE, and to Co-operating Sequential Processes.

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 that the proof gives 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,[3] 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" started the sub-field of self-stabilization.

Many of his opinions on computer science and programming have become widespread. For example, he is famed for coining the popular programming phrase "two or more, use a for," 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 once said, "computer science is no more about computers than astronomy is about telescopes."

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

EWDs and writing by hand

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 Technological University (then TH) Eindhoven. After going to the TUE 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 EWD's were born. Dijkstra would distribute photocopies of a new EWD among his colleagues; as many recipients photocopied and forwarded their copy, 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 since been scanned, with a growing number transcribed to facilitate search, and are available online at the Dijkstra archive of the University of Texas.[4]

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 (EWD 475). 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 (EWD 539). A more successful effort was the Standard Proof for Pythagoras' Theorem, that replaced the more than 100 incompatible existing proofs (EWD427). Dijkstra described Mathematics Inc. as "the most exciting and most miserable business ever conceived" (EWD475). He claimed that by 1974 his fictional company was the world's leading mathematical industry with more than 75 percent of the world market (EWD443).[5]

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, let alone Powerpoint slides. 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.[6]

Awards and honors

Among Dijkstra's awards and honours are:[6]

See also

Footnotes

  1. ^ "Go To Statement Considered Harmful", Communications of the ACM, Vol. 11, No. 3, March 1968, pp. 147-148.
  2. ^ How do we tell truths that might hurt?, 18 June 1975, http://www.cs.virginia.edu/~evans/cs655-S00/readings/ewd498.html 
  3. ^ http://video.google.com/videoplay?docid=-6873628658308030363
  4. ^ University of Texas online EWD archive.
  5. ^ Dijkstra, Edsger W. (1982). Selected Writings on Computing: A Personal Perspective. Berlin: Springer-Verlag. ISBN 9780387906522. 
  6. ^ a b University of Texas, "In Memoriam Edsger Wybe Dijkstra."

References

Advertisements

Writings by E.W. Dijkstra

  • From My Life (EWD1166)
  • Dijkstra, E.W. (August 1975), Guarded commands, nondeterminacy and formal derivation of program. Communications of the ACM, 18(8):453–457. [1]
  • Dijkstra, E.W. (1976), A Discipline of Programming, Prentice-Hall Series in Automatic Computation, ISBN 0-13-215871-X — A systematic introduction to a version of the guarded command language with many worked examples
  • Selected Writings on Computing: A Personal Perspective, Texts and Monographs in Computer Science, Springer-Verlag, 1982, ISBN 0-387-90652-5
  • A Method of Programming, E.W. Dijkstra, W.H.J. Feijen, J. Sterringa, Addison Wesley 1988, ISBN 0-201-17536-3
  • E. W. Dijkstra and Carel S. Scholten (1990). Predicate Calculus and Program Semantics. Springer-Verlag ISBN 0-387-96957-8 — An abstract, formal treatment of Predicate transformer semantics
  • O.-J. Dahl, Edsger W. Dijkstra, C. A. R. Hoare Structured Programming, Academic Press, London, 1972 ISBN 0-12-200550-3

Others about Dijkstra, eulogies

External links


Quotes

Up to date as of January 14, 2010

From Wikiquote

Simplicity is prerequisite for reliability.

Edsger W. Dijkstra (1930-05-112002-08-06) was a Dutch computer scientist, and winner of the 1972 Turing Award. He was an early and influential proponent of "structured programming."

Contents

Sourced

  • I think of the company advertising "Thought Processors" or the college pretending that learning BASIC suffices or at least helps, whereas the teaching of BASIC should be rated as a criminal offence: it mutilates the mind beyond recovery.
  • Testing shows the presence, not the absence of bugs
    • Source: J.N. Buxton and B. Randell, eds, Software Engineering Techniques, April 1970, p. 21. Report on a conference sponsored by the NATO Science Committee, Rome, Italy, 27–31 October 1969. Possibly the earliest documented use of the famous quote.
  • Program testing can be used to show the presence of bugs, but never to show their absence!
    • Source: Notes On Structured Programming, 1972, at the end of section 3, On The Reliability of Mechanisms. EWD249 (1970).
  • There are many different styles of composition. I characterize them always as Mozart versus Beethoven. When Mozart began to write at that time he had the composition ready in his mind. He wrote the manuscript and it was 'aus einem Guss' (casted as one). And it was also written very beautiful. Beethoven was an indecisive and a tinkerer and wrote down before he had the composition ready and plastered parts over to change them. There was a certain place where he plastered over nine times and one did remove that carefully to see what happened and it turned out the last version was the same as the first one.
  • The competent programmer is fully aware of the limited size of his own skull. He therefore approaches his task with full humility, and avoids clever tricks like the plague.
    • Source: EWD340
  • Elegance is not a dispensable luxury but a quality that decides between success and failure.
    • Source: EWD1284
  • How do we convince people that in programming simplicity and clarity —in short: what mathematicians call "elegance"— are not a dispensable luxury, but a crucial matter that decides between success and failure?
    • Source: EWD648
  • Write a paper promising salvation, make it a 'structured' something or a 'virtual' something, or 'abstract', 'distributed' or 'higher-order' or 'applicative' and you can almost be certain of having started a new cult.
  • For me, the first challenge for computing science is to discover how to maintain order in a finite, but very large, discrete universe that is intricately intertwined. And a second, but not less important challenge is how to mould what you have achieved in solving the first problem, into a teachable discipline: it does not suffice to hone your own intellect (that will join you in your grave), you must teach others how to hone theirs. The more you concentrate on these two challenges, the clearer you will see that they are only two sides of the same coin: teaching yourself is discovering what is teachable.
  • When we had no computers, we had no programming problem either. When we had a few computers, we had a mild programming problem. Confronted with machines a million times as powerful, we are faced with a gigantic programming problem.
  • The required techniques of effective reasoning are pretty formal, but as long as programming is done by people that don't master them, the software crisis will remain with us and will be considered an incurable disease. And you know what incurable diseases do: they invite the quacks and charlatans in, who in this case take the form of Software Engineering gurus.
  • When I came back from Munich, it was September, and I was Professor of Mathematics at the Eindhoven University of Technology. Later I learned that I had been the Department's third choice, after two numerical analysts had turned the invitation down; the decision to invite me had not been an easy one, on the one hand because I had not really studied mathematics, and on the other hand because of my sandals, my beard and my "arrogance" (whatever that may be).
  • I mean, if 10 years from now, when you are doing something quick and dirty, you suddenly visualize that I am looking over your shoulders and say to yourself "Dijkstra would not have liked this", well, that would be enough immortality for me.
  • On Our Inability To Do Much.
    • Source: Chapter title in "Structured Programming", O.J. Dahl, E.W. Dijkstra, and C.A.R. Hoare. Academic Press, 1972 ISBN 0122005503
  • Thank goodness we don't have only serious problems, but ridiculous ones as well.
    • Source: EWD475, "A Letter to My Old Friend Jonathan"; p. 101 in Dijkstra, Edsger (1982). Selected Writings on Computing. Berlin: Springer-Verlag. ISBN 9780387906522.  

The Humble Programmer (1972)

1972 Turing Award Lecture[1], Communications of the ACM 15 (10), October 1972: pp. 859–866

  • We must be very careful when we give advice to younger people: sometimes they follow it!
  • 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. In this sense the electronic industry has not solved a single problem, it has only created them, it has created the problem of using its products.
  • FORTRAN's tragic fate has been its wide acceptance, mentally chaining thousands and thousands of programmers to our past mistakes.
  • LISP has been jokingly described as "the most intelligent way to misuse a computer". I think that description a great compliment because it transmits the full flavor of liberation: it has assisted a number of our most gifted fellow humans in thinking previously impossible thoughts.
  • When FORTRAN has been called an infantile disorder, full PL/1, with its growth characteristics of a dangerous tumor, could turn out to be a fatal disease.
  • If you want more effective programmers, you will discover that they should not waste their time debugging, they should not introduce the bugs to start with.
  • Program testing can be a very effective way to show the presence of bugs, but it is hopelessly inadequate for showing their absence.
    • Compare more succinct phrasings cited above.
  • The effective exploitation of his powers of abstraction must be regarded as one of the most vital activities of a competent programmer.

How do we tell truths that might hurt? (1975)

How do we tell truths that might hurt? (numbered EWD498, written 1975) was written as a series of aphorisms, and is the source of several popular quotations. It was also published in Selected Writings on Computing:A Personal Perspective.

  • The use of COBOL cripples the mind; its teaching should, therefore, be regarded as a criminal offense.
  • APL is a mistake, carried through to perfection. It is the language of the future for the programming techniques of the past: it creates a new generation of coding bums.
  • FORTRAN, 'the infantile disorder', by now nearly 20 years old, is hopelessly inadequate for whatever computer application you have in mind today: it is now too clumsy, too risky, and too expensive to use.
  • In the good old days physicists repeated each other's experiments, just to be sure. Today they stick to FORTRAN, so that they can share each other's programs, bugs included.
  • It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration.
  • Besides a mathematical inclination, an exceptionally good mastery of one's native tongue is the most vital asset of a competent programmer.
  • Simplicity is prerequisite for reliability.
  • Programming is one of the most difficult branches of applied mathematics; the poorer mathematicians had better remain pure mathematicians.
  • We can found no scientific discipline, nor a hearty profession, on the technical mistakes of the Department of Defense and, mainly, one computer manufacturer.

Unsourced

  • Computer Science is no more about computers than astronomy is about telescopes.
  • 2 or more, use a for

Misattributed

  • Go To statement considered harmful

About E.W. Dijkstra

  • You probably know that arrogance, in computer science, is measured in nanodijkstras.

External links

Wikipedia
Wikipedia has an article about:

Advertisements






Got something to say? Make a comment.
Your name
Your email address
Message