Algorithm 版 (精华区)

发信人: Lerry (坐壮:望苗:思汉@贵族 与猫族斗争到底), 信区: Algorithm
标  题: Edsger W. Dijkstra(1972) 
发信站: 哈工大紫丁香 (2002年04月26日07:59:47 星期五), 站内信件

Edsger W. Dijkstra
Also known as: Edsger W(ybe) Dijkstra, Edsger Wybe Dijkstra
Born: 1930
Nationality: Dutch
Occupation: computer scientist
Source: Notable Twentieth-Century Scientists. Gale Research, 1995.
Table of Contents
Biographical Essay
Further Readings
Works
BIOGRAPHICAL ESSAY
Edsger W. Dijkstra has highly influenced the manner in which computer progra
ms, the sets of instructions that tell computers what to do, are constructed
. His persuasive support for the concept and practice of structured programm
ing permanently changed the way computer programs are written. It was once a
ssumed that bugs or program errors were inevitably introduced into programs
during their development and that, as a consequence, programs had to be debu
gged in order to work properly. Dijkstra argued that this was not necessaril
y so; he convinced the scientific community that computer program s could be
 correctly constructed from the initial stages of design.
Dijkstra was born in Rotterdam, The Netherlands, on May 11, 1930. He was the
 third of four children. His father, Douwe W. Dijkstra, was a chemist and in
ventor who had been president of the Dutch Chemical Society, and his mother,
 Brechtje Cornelia Kluyver, was a mathematician. Dijkstra originally intende
d to study law, but his scientific talents came to light following his final
 exams at the gymnasium in 1948. His exam grades were better than most of hi
s teachers had ever seen, and he was convinced, as he recalled in a written
interview with contributor Frank Hertle, "that it would be a pity if I did n
ot devote myself to science." Dijkstra enrolled at Leyden University to stud
y mathematics and physics. It was during his early years at Leyden that Dijk
stra was introduced to computers. As a reward for his academic performance,
in 1951 his father offered him the opportunity to attend a three-week comput
er programming course (for the Electronic Delay Storage Automatic Calculator
, or EDSAC) in Cambridge, England. Dijkstra, who then had plans to become a
theoretical physicist, thought it would be a good idea to learn more about c
omputers. When A. van Wijngaarden, the director of the computation departmen
t at the Mathematical Centre in Amsterdam, heard by chance of Dijkstra's pla
ns to attend this course, he interviewed him and offered him a job. Dijkstra
 began working part-time at the Mathematical Centre in 1952 and took a full-
time position there in 1956. In 1957, Dijkstra married Maria Cornelia Debets
; they would eventually have three children together.
While at the Mathematical Centre, Dijkstra worked with Bram J. Loopstra and
Carel S. Scholten on the design and construction of a computer, known as the
 ARMAC. He was primarily responsible for the software, and they for the hard
ware, and his involvement included writing the programming manual that was t
o contain a complete functional description of the machine. The document ser
ved as a "contract" between Dijkstra and the two other men: they knew what t
hey had to build and Dijkstra knew what he would build upon. This project ha
d an important influence on the course of his career. Dijkstra already sense
d that computers would be a permanent and important part of the modern world
 and had become convinced of the need to program them accurately. From this
point forward, he felt personally challenged to develop a methodology for co
nstructing programs that could be proven correct before being run on a compu
ter.
During this period, Dijkstra designed some of his first computer algorithms-
-sequences of instructions designed to perform specific mathematical tasks.
Dijkstra developed one of his most famous algorithms--the Shortest Path (to
find the shortest distance between two cities on a map)--over coffee on a ca
fe terrace in Amsterdam, and without paper and pencil.
When Loopstra and Scholten set out to design their next machine, they wanted
 it to be able to respond to what is known as a real-time interrupt. A real-
time interrupt is a spontaneous event originating outside the computer that
influences the action that the program running in the computer will take. Di
jkstra devised a solution to this problem; he called it a real-time interrup
t handler , and it became his doctoral thesis. In 1959 he received a Ph.D. f
rom the University of Amsterdam, but he remained at the Mathematical Centre,
 where he worked with J. A. Zonneveld designing an ALGOL 60 compiler. The pr
oject frequently took him outside of The Netherlands and gave him the opport
unity to begin polishing his English. The ALGOL implementation took eight mo
nths to complete and was done in August of 1960, more than a year before the
ir nearest competitor. This work helped establish Dijkstra's reputation amon
g computer scientists in America.
Challenges a Common Programming Technique
In 1962, Dijkstra became professor of mathematics at the Technical Universit
y in Eindhoven, The Netherlands. His work there included a collaboration tha
t produced a multiprogramming operating system (called "THE Multiprogramming
 System") for the university's computer, an Electrologica X8. THE Multiprogr
amming System was to influence the design of nearly all later operating syst
ems. It was while at Eindhoven that Dijkstra challenged one of the most basi
c techniques of programming at that time: the abrupt transfer of control fro
m one point in a flow of computer instructions to some other point in the pr
ogram. This technique was called a GOTO statement, and programmers were usin
g them to interrupt sequences of computer instructions in order to perform a
 different instruction or set of instructions. GOTO is a generic term for an
 instruction that causes a program to "go to" some location within itself fo
r its next instruction. GOTO statements, also called "branches" or "transfer
s," were commonly used in early computer program designs.
In a famous 1968 letter to the editor of Communications of the ACM, Dijkstra
 argued that the ability of programmers to read and understand programs writ
ten in high-level languages was severely compromised by the number of GOTO s
tatements in these programs. High-level languages (meant to resemble written
 English or mathematical statements) are to a certain degree self-documentin
g; this means that the reader should be able to understand the flow of opera
tions simply by reading the programming statements. The use of GOTO statemen
ts interrupts the logical flow, and the composition and interpretation of a
program (especially a large one) becomes more difficult as the number of GOT
O statements increases. In his letter, entitled by the ACM editors "Go To St
atement Considered Harmful," Dijkstra termed the statements as "primitive" i
n high-level programming languages, calling them "too much an invitation to
make a mess of one's program."
The alternative Dijkstra offered he called structured programming. It is a s
tyle, or methodology, of programming in which a program is put together by c
onnecting a number of smaller structured programs or program segments. It is
 easiest to understand structured programming if one thinks of an English se
ntence containing several difficult words; these words are like GOTO stateme
nts. The reader must look up these words in order to understand the sentence
, but taking the time to find a word in the dictionary is an interruption, a
nd one tends to lose track of the meaning of the original sentence. If the s
ame sentence were written in a structured fashion, each difficult word would
 be replaced by an expression that defined it, thus ending the need to look
elsewhere for clarification. While it is generally agreed that the idea of s
tructuring programs had supporters before Dijkstra's letter, there is no que
stion that his arguments brought everyone's attention to the issue and led t
he way to the wide implementation of structured programming.
In 1972 Dijkstra contributed to the book Notes on Structured Programming, in
 which he wrote that "program testing can be used to show the presence of bu
gs, but never to show their absence!" He advanced the idea that "it is not o
nly the programmer's task to produce a correct program but also to demonstra
te its correctness in a convincing manner." In order to provide the proof, t
he program must be "usefully structured." In Dijkstra's view, every effort m
ust always be made to design programs to be as error-free as possible from t
he beginning; he believed that this method of design made programs easier to
 construct and understand. The easier it was to write and comprehend a progr
am, he argued, the easier it was to avoid introducing errors or bugs into it
.
Dijkstra left Eindhoven in August of 1973 to accept a position as a research
 fellow with the Burroughs Corporation. Even though the company was headquar
tered in Detroit, Michigan, Dijkstra's position allowed him to continue to w
ork and live in his home in Nuenen, a village near Eindhoven in The Netherla
nds. Burroughs gave Dijkstra great latitude in the use of his time, and he t
raveled widely during his years with the company, lecturing all over the wor
ld and frequently visiting the United States.
In the early 1980s, the intellectual climate at Burroughs changed: the compa
ny became more concerned with short-term profits and Dijkstra's colleagues b
ecame disenchanted and began to leave. Additionally, Dijkstra's interests we
re shifting from computers and programming to mathematical methodology in ge
neral. He felt it appropriate to return to a university environment, and the
 University of Texas offered him the Schlumberger Centennial chair in Comput
er Science.
The vocabulary of computer programmers is far richer for the influence of Di
jkstra. He introduced and popularized a number of terms including go-to-less
 programming, structured programming, semaphore, guarded command, and deadly
 embrace. Semaphores are elements used to coordinate the activities of two o
r more simultaneously running programs that share data. Guarded commands are
 those that execute conditionally, that is, only when some condition that ca
n be tested for is satisfied. A deadly embrace (also called a deadlock) occu
rs when a program cannot continue because it is waiting for some event that
will never happen.
Dijkstra's philosophy can perhaps best be summarized by a passage from Notes
 on Structured Programming: "My point is that a program is never a goal in i
tself; the purpose of a program is to evoke computations and the purpose of
the computations is to establish a desired effect." He goes on to say that "
although the program is the final product made by the programmer, the possib
le computations evoked by it ... are the true subject matter of his trade."
Programs, in other words, are not ends in themselves but rather means to end
s, those ends being correct computations and outcomes. The elegance of a pro
gram should increase the ease with which the program can be comprehended and
 maintained.
In 1972 Dijkstra was presented with the Turing Award. This award is made eac
h year by the Association for Computing Machinery (ACM) as a memorial to A.
M. Turing . The award recognized Dijkstra's tremendous influence on programm
ing methodology. In 1974, Dijkstra received the Harry Goode Memorial Award a
s recognition of his achievements in the field of information processing.
WORKS
Notes on Structured Programming, Academic Press, 1972.
A Discipline of Programming, Prentice Hall, 1976.
Selected Writings on Computing: A Personal Perspective, Springer-Verlag, 198
2.
Development of Programs and Proofs, Addison-Wesley, 1990.
Communications of the ACM, Go To Statements Considered Harmful,, Volume 11,
1968, pp. 147148.
FURTHER READINGS
, Encyclopedia of Computer Science and Engineering, Van Nostrand Reinhold, 1
983, pp. 508, 877878, 1311, 1348.
, Macmillan Encyclopedia of Computers, Macmillan, 1992, pp. 100101.
, Macmillan Encyclopedia of Computers, Dijkstra, E. W., written response to
interview questions from Frank Hertle on December 7, 1993. 
--
当一个女孩儿觉得她不太容易了解那个男人的时候，她会爱他。

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 218.7.32.75]