Edsger Wybe Dijkstra (May
11, 1930 – August 6, 2002; ) 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 in the subtopic
of
selfstabilization of program
computation. This annual award was renamed the
Dijkstra Prize the following year, in his
honour.
Life and work
Born in
Rotterdam,
Netherlands, Dijkstra studied theoretical physics at Leiden University, but he 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 in the Netherlands, 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 is the
shortest pathalgorithm, also known as
Dijkstra's algorithm;
Reverse Polish Notation and
related
Shunting yard
algorithm; the
THE
multiprogramming system;
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
selfstabilization – 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
OleJohan
Dahl. The March 1968 ACM letter's famous title, "Go To
Statement
Considered Harmful",was
not the work of Dijkstra, but of
Niklaus
Wirth, then editor of
Communications of the
ACM.
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
Cooperating Sequential
Processes.
He is famed for coining the popular programming phrase "2 or more,
use a for", alluding to the fact that when you find yourself
processing more than one instance of a data structure, it is time
to encapsulate that logic inside a loop.
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 as to 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 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 very early pioneers of the research on
distributed computing. Some people even consider some of his papers
to be those that established the field. In particular, his paper
"Selfstabilizing Systems in Spite of Distributed Control" started
the subfield of
selfstabilization.
Dijkstra was known for his essays on programming; he was the first
to make the claim that programming is so inherently difficult and
complex that programmers need to harness every trick and
abstraction possible in hopes of managing the complexity of it
successfully.
Dijkstra believed that computer science was more abstract than
programming; he once said, "Computer Science is no more about
computers than astronomy is about telescopes."
He died in
Nuenen, The
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 as 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 experieced 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 collaegues in Eindhoven would not understand;
if he wrote about things they would like in Eindhoven, his former
collaegues 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.
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).
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 handwritten. 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
email and for browsing the World Wide Web.
Awards and honors
Among Dijkstra's awards and honours are:
See also
Footnotes
 "Go To Statement Considered Harmful", Communications
of the ACM, Vol. 11, No. 3, March 1968, pp. 147148.

http://video.google.com/videoplay?docid=6873628658308030363
 University of Texas online EWD
archive.
 University of Texas, "In Memoriam Edsger Wybe Dijkstra."
References
Writings by E.W. Dijkstra
 From My Life (EWD1166)
 A Discipline of Programming, PrenticeHall Series in
Automatic Computation, 1976, ISBN 013215871X
 Selected Writings on Computing: A Personal
Perspective, Texts and Monographs in Computer Science,
SpringerVerlag, 1982, ISBN 0387906525
 A Method of Programming, E.W. Dijkstra, W.H.J. Feijen,
J. Sterringa, Addison Wesley 1988, ISBN 0201175363
 O.J. Dahl, E.
W. Dijkstra, C.
A. R.
Hoare Structured
Programming, Academic Press, London, 1972 ISBN 0122005503
Others about Dijkstra, eulogies
External links