悼念偉大的計算機科學家Edsger Wybe Dijkstra

悼念偉大的計算機科學家Edsger Wybe Dijkstra

2002年8月8日，我象往常一樣查看自己在extremeprogramming電子小組上訂閱的newsletter。突然看到這個小組上的稀客、OO教父Grady Booch的發言，題目是Dijkstra。我以為大家在討論Dijkstra教授提出的什么難題，定睛一看，才知道是一篇類似生平介紹式的訃告——在與癌癥進行了多年的斗爭之后，偉大的荷蘭計算機科學家Edsger Wybe Dijkstra已經于2002年8月6日在荷蘭Nuenen自己的家中與世長辭！終年72歲。

原來如此！

這個Dijkstra，就是那個提出“goto有害論”的Dijkstra，就是那個提出信號量和PV原語，解決了有趣的“哲學家聚餐”問題的Dijkstra，那個Dijkstra最短路徑算法的創造者，第一個Algol 60編譯器的設計者和實現者，THE操作系統的設計者和開發者，那個與D. E. Knuth并稱為我們這個時代最偉大的計算機科學家的人。

阿蘭圖靈的自殺是在辦個世紀之前，馮諾依曼去世也已經多年，作為這個相對新興的行當中的從業者，我們似乎已經很習慣于從相信，從書上讀到的每個名字都是仍然在世的活生生的人，都是我們這個時代的驕傲。無論是仍然健碩的D. E. Knuth，Fred Brooks，Dennis Ritchie, Ken Thompson, Brian Kernighan, 還是正當盛年的Bjarne Stroustrup，Grady Booch，Steve McConnell, Andy Koenig, Robert Martin, Kent Becker, Martin Fowler, James Gosling, 再或者是青春年少，意氣風發的Linus Trovalds，Andrei Alexandrescu，我們似乎都習慣于認為，只要一封email，這些書本上的名字就會立刻成為你的朋友。Internet把地球變成了一個大村莊，每個人的距離都那么的近。

但是可惜，Internet卻無法縮短跨越生與死的冥界。今天，一顆真正的巨星在我們的眼前隕落！作為一名普通的程序員，我從內心感到惋惜和悲痛。這種悲痛，兩年半前在我最初得知Richard Stevens的逝世時，也曾感受過，然而卻不如今天來得這么強烈。畢竟，當我對編程還是懵懵懂懂的時候，就知道有個叫Dijkstra的人勸告大家不要濫用goto，而在那之前，goto在我看來就是編程的全部奧秘所在。之后我在學習算法、數據結構、操作系統等課程的時候，Dijkstra這個名字一次又一次從書里跳出來，我對于這個名字的崇敬也越來越深。我知道他晚年瘋狂的迷戀C++，這也幾乎是我這個C++ Fan所能感受到的最大榮幸。我曾想過，有朝一日，我會給他寫一封email，什么也不說，只想表達我個人對他的感謝和敬意。沒想到，如今連這個機會也沒有了！

Dijkstra引導了并且將繼續引導這個星球上所有的程序員，他的貢獻和影響將與世長存，讓我們祝他安息！

【附】Grady Booch對Dijkstra的介紹

> Professor Edsger Wybe Dijkstra, a noted pioneer of the science and
> industry of computing, died after a long struggle with cancer on 6
> August 2002 at his home in Nuenen, the Netherlands.
>
> Dijkstra was born in 1930 in Rotterdam, The Netherlands, the son of a
> chemist father and a mathematician mother. He graduated from the
> Gymnasium Erasmianum in Rotterdam and obtained degrees in mathematics
> and theoretical physics from the University of Leyden and a Ph.D. in
> computing science from the University of Amsterdam. He worked as a
> programmer at the Mathematisch Centrum, Amsterdam, 1952-62; was
> professor of mathematics, Eindhoven University of Technology,
> 1962-1984; and was a Burroughs Corporation research fellow, 1973-1984.
> He held the Schlumberger Centennial Chair in Computing Sciences at the
> University of Texas at Austin, 1984-1999, and retired as Professor
> Emeritus in 1999.
>
> Dijkstra is survived by his wife of over forty years, Maria (Ria) C.
> Dijkstra Debets, by three children, Marcus J., Femke E., and computer
> scientist Rutger M. Dijkstra, and by two grandchildren.
>
> Dijkstra was the 1972 recipient of the ACM Turing Award, often viewed
> as the Nobel Prize for computing. He was a member of the Netherlands
> Royal Academy of Arts and Sciences, a member of the American Academy
> of Arts and Sciences, and a Distinguished Fellow of the British
> Computer Society. He received the 1974 AFIPS Harry Goode Award, the
> 1982 IEEE Computer Pioneer Award, and the 1989 ACM SIGCSE Award for
> Outstanding Contributions to Computer Science Education. Athens
> University of Economics awarded him an honorary doctorate in 2001. 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 is renowned for the insight that mathematical logic is and
> must be the basis for sensible computer program construction and for
> his contributions to mathematical methodology. He is responsible for
> the idea of building operating systems as explicitly synchronized
> sequential processes, for the formal development of computer programs,
> and for the intellectual foundations for the disciplined control of
> nondeterminacy. He is well known for his amazingly efficient shortest
> path algorithm and for having designed and coded the first Algol 60
> compiler. He was famously the leader in the abolition of the GOTO
> statement from programming.
>
> Dijkstra was a prodigious writer. His entire collection of over
> thirteen hundred written works was digitally scanned and is accessible
> at http://www.cs./users/EWD. He also corresponded regularly
> with hundreds of friends and colleagues over the years --not by email
> but by conventional post. He strenuously preferred the fountain pen to
> the computer in producing his scholarly output and letters.
>
> Dijkstra was notorious for his wit, eloquence, and way with words,
> such as in his remark "The question of whether computers can think is
> like the question of whether submarines can swim"; his advice to a
> promising researcher, who asked how to select a topic for research:
> "Do only what only you can do"; and his remark in his Turing Award
> lecture "In their capacity as a tool, computers will be but a ripple
> on the surface of our culture. In their capacity as intellectual
> challenge, they are without precedent in the cultural history of
> mankind."
>
> Dijkstra enriched the language of computing with many concepts and
> phrases, such as structured programming, separation of concerns,
> synchronization, deadly embrace, dining philosophers, weakest
> precondition, guarded command, the excluded miracle, and the famous
> "semaphores" for controlling computer processes. The Oxford English
> Dictionary cites his use of the words "vector" and "stack" in a
> computing context.
>
> Dijkstra enjoyed playing Mozart for his friends on his Boesendorfer
> piano. He and his wife had a fondness for exploring state and national
> parks in their Volkswagen bus, dubbed the Touring Machine, in which he
> wrote many technical papers.
>
> Throughout his scientific career, Dijkstra formulated and pursued the
> highest academic ideals of scientific rigour untainted by commercial,
> managerial, or political considerations. Simplicity, beauty, and
> eloquence were his hallmarks, and his uncompromising insistence on
> elegance in programming and mathematics was an inspiration to
> thousands. He judged his own work by the highest standards and set a
> continuing challenge to his many friends to do the same. For the rest,
> he willingly undertook the role of Socrates, that of a gadfly to
> society, repeatedly goading his native and his adoptive country by
> remarking on the mistakes inherent in fashionable ideas and the
> dangers of time-serving compromises. Like Socrates, his most
> significant legacy is to those who engaged with him in small group
> discussions or scientific correspondence about half-formulated ideas
> and emerging discoveries. Particularly privileged are those who
> attended his reading groups in Eindhoven and Austin, known as the
> "Tuesday Afternoon Clubs".
>
> At Dijkstra's passage, let us recall Phaedo's parting remark about
> Socrates: "we may truly say that of all the men of his time whom we
> have known, he was the wisest and justest and best."

Edsger Dijkstra經典言論

 

1. 編程的藝術就是處理復雜性的藝術。

2. 優秀的程序員很清楚自己的能力是有限的，所以他對待編程任務的態度是完全謙卑的，特別是，他們會象逃避瘟疫那樣逃避 “聰明的技巧”。——1972年圖靈獎演講

3. 計算機科學是應用數學最難的一個分支，所以如果你是一個蹩腳的數學家，最好留在原地，繼續當你的數學家。

4. 我們所使用的工具深刻地影響我們的思考習慣，從而也影響了我們的思考能力。

5. 實際上如果一個程序員先學了BASIC，那就很難教會他好的編程技術了：作為一個可能的程序員，他們的神經已經錯亂了，而且無法康復。

6. 就語言的使用問題：根本不可能用一把鈍斧子削好鉛筆，而換成十把鈍斧子會是事情變成大災難。

7. 簡單是可靠的先決條件。

下面是Dijkstra遺孀和子女發出的通告：

>Grateful for most that has befallen him, has peacefully passed away,
>    Edsger Wybe Dijkstra,
>our husband and father.
>
>We hold him very dear.
>
>The cremation will take place on
>
>Saterday, August 10th, 12:30 PM at
>Somerenseweg 120
>Heeze
>the Netherlands
>
>Maria C. Dijkstra Debets
>Marcus J. Dijkstra
>Femke E. Dijkstra
>Rutger M. Dijktra
>
>Please forward this message to whomever you feel missing in the
>recipient list.

最后，請重溫Dijkstra在1968年發表的那篇短文：

Go To Statement Considered Harmful

For a number of years I have been familiar with the observation that the quality of programmers is a decreasing function of the density of go to statements in the programs they produce. More recently I discovered why the use of the go to statement has such disastrous effects, and I became convinced that the go to statement should be abolished from all "higher level" programming languages (i.e. everything except, perhaps, plain machine code). At that time I did not attach too much importance to this discovery; I now submit my considerations for publication because in very recent discussions in which the subject turned up, I have been urged to do so.

My first remark is that, although the programmer's activity ends when he has constructed a correct program, the process taking place under control of his program is the true subject matter of his activity, for it is this process that has to accomplish the desired effect; it is this process that in its dynamic behavior has to satisfy the desired specifications. Yet, once the program has been made, the "making' of the corresponding process is delegated to the machine.

My second remark is that our intellectual powers are rather geared to master static relations and that our powers to visualize processes evolving in time are relatively poorly developed. For that reason we should do (as wise programmers aware of our limitations) our utmost to shorten the conceptual gap between the static program and the dynamic process, to make the correspondence between the program (spread out in text space) and the process (spread out in time) as trivial as possible.

Let us now consider how we can characterize the progress of a process. (You may think about this question in a very concrete manner: suppose that a process, considered as a time succession of actions, is stopped after an arbitrary action, what data do we have to fix in order that we can redo the process until the very same point?) If the program text is a pure concatenation of, say, assignment statements (for the purpose of this discussion regarded as the descriptions of single actions) it is sufficient to point in the program text to a point between two successive action descriptions. (In the absence of go to statements I can permit myself the syntactic ambiguity in the last three words of the previous sentence: if we parse them as "successive (action descriptions)" we mean successive in text space; if we parse as "(successive action) descriptions" we mean successive in time.) Let us call such a pointer to a suitable place in the text a "textual index."

When we include conditional clauses (if B then A), alternative clauses (if B then A1 else A2), choice clauses as introduced by C. A. R. Hoare (case[i] of (A1, A2,···, An)),or conditional expressions as introduced by J. McCarthy (B1 -> E1, B2 -> E2, ···, Bn -> En), the fact remains that the progress of the process remains characterized by a single textual index.

As soon as we include in our language procedures we must admit that a single textual index is no longer sufficient. In the case that a textual index points to the interior of a procedure body the dynamic progress is only characterized when we also give to which call of the procedure we refer. With the inclusion of procedures we can characterize the progress of the process via a sequence of textual indices, the length of this sequence being equal to the dynamic depth of procedure calling.

Let us now consider repetition clauses (like, while B repeat A or repeat A until B). Logically speaking, such clauses are now superfluous, because we can express repetition with the aid of recursive procedures. For reasons of realism I don't wish to exclude them: on the one hand, repetition clauses can be implemented quite comfortably with present day finite equipment; on the other hand, the reasoning pattern known as "induction" makes us well equipped to retain our intellectual grasp on the processes generated by repetition clauses. With the inclusion of the repetition clauses textual indices are no longer sufficient to describe the dynamic progress of the process. With each entry into a repetition clause, however, we can associate a so-called "dynamic index," inexorably counting the ordinal number of the corresponding current repetition. As repetition clauses (just as procedure calls) may be applied nestedly, we find that now the progress of the process can always be uniquely characterized by a (mixed) sequence of textual and/or dynamic indices.

The main point is that the values of these indices are outside programmer's control; they are generated (either by the write-up of his program or by the dynamic evolution of the process) whether he wishes or not. They provide independent coordinates in which to describe the progress of the process.

Why do we need such independent coordinates? The reason is - and this seems to be inherent to sequential processes - that we can interpret the value of a variable only with respect to the progress of the process. If we wish to count the number, n say, of people in an initially empty room, we can achieve this by increasing n by one whenever we see someone entering the room. In the in-between moment that we have observed someone entering the room but have not yet performed the subsequent increase of n, its value equals the number of people in the room minus one!

The unbridled use of the go to statement has an immediate consequence that it becomes terribly hard to find a meaningful set of coordinates in which to describe the process progress. Usually, people take into account as well the values of some well chosen variables, but this is out of the question because it is relative to the progress that the meaning of these values is to be understood! With the go to statement one can, of course, still describe the progress uniquely by a counter counting the number of actions performed since program start (viz. a kind of normalized clock). The difficulty is that such a coordinate, although unique, is utterly unhelpful. In such a coordinate system it becomes an extremely complicated affair to define all those points of progress where, say, n equals the number of persons in the room minus one!

The go to statement as it stands is just too primitive; it is too much an invitation to make a mess of one's program. One can regard and appreciate the clauses considered as bridling its use. I do not claim that the clauses mentioned are exhaustive in the sense that they will satisfy all needs, but whatever clauses are suggested (e.g. abortion clauses) they should satisfy the requirement that a programmer independent coordinate system can be maintained to describe the process in a helpful and manageable way.

It is hard to end this with a fair acknowledgment. Am I to judge by whom my thinking has been influenced? It is fairly obvious that I am not uninfluenced by Peter Landin and Christopher Strachey. Finally I should like to record (as I remember it quite distinctly) how Heinz Zemanek at the pre-ALGOL meeting in early 1959 in Copenhagen quite explicitly expressed his doubts whether the go to statement should be treated on equal syntactic footing with the assignment statement. To a modest extent I blame myself for not having then drawn the consequences of his remark

The remark about the undesirability of the go to statement is far from new. I remember having read the explicit recommendation to restrict the use of the go to statement to alarm exits, but I have not been able to trace it; presumably, it has been made by C. A. R. Hoare. In [1, Sec. 3.2.1.] Wirth and Hoare together make a remark in the same direction in motivating the case construction: "Like the conditional, it mirrors the dynamic structure of a program more clearly than go to statements and switches, and it eliminates the need for introducing a large number of labels in the program."

In [2] Guiseppe Jacopini seems to have proved the (logical) superfluousness of the go to statement. The exercise to translate an arbitrary flow diagram more or less mechanically into a jump-less one, however, is not to be recommended. Then the resulting flow diagram cannot be expected to be more transparent than the original one.

References:
Wirth, Niklaus, and Hoare C. A. R. A contribution to the development of ALGOL. Comm. ACM 9 (June 1966), 413-432. BÖhm, Corrado, and Jacopini Guiseppe. Flow diagrams, Turing machines and languages with only two formation rules. Comm. ACM 9 (May 1966), 366-371.
 
Edsger W. Dijkstra
Technological University
Eindhoven, The Netherlands

本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/szelsie/archive/2006/12/28/1465153.aspx