Edsger Wybe Dijkstra

Phoenix Dagny Moorman

CSCI 300

Fall 2000

September 7, 2000

Dijkstra: An Overview

Perhaps one of the most influential figures in post-WWII computing, Dr. Edsger Wybe Dijkstra was born in Rotterdam, Netherlands in 1930, and as a young man, studied theoretical physics at the University of Leiden. During his studies at Leiden, Dijkstra spent a summer at Cambridge University, studying the field of computer programming. Fascinated by such studies, and especially frustrated by the copious number of bugs and problems in computing at the time, Dijkstra continued his research into the field during the rest of his academic career, during which he made many fundamental contributions to the field. In 1972, Dijkstra was awarded the notable Turing Award for his contributions to the creation of the ALGOL-60 language. Dijkstra currently teaches at the University of Texas and continues his quest for structure, correctness, and mathematical elegance in computer science today.

Why We Care About Dijkstra

Edsger Dijkstra was the primary figure responsible for the concept of structured programming, a style in which emphasizes clean flow and design, little possibility for error, and modularity. In 1962, Dijkstra made the fundamental observation that a programming statement was in essence a string of mathematical operations, which should be able to be proven without running the program. Although his attempts at proving statements to be correct without running them was more oft then not unsuccessful, Dijkstra did however begin a revolution in the ways that programmers view statements and structure their code. In his book, Structured Programming, Dijkstra poses the following query:

"The leading question was if it was conceivable to increase our programming ability by an order of magnitude and what techniques (mental, organizational, or mechanical) could be applied in the process of program composition to produce this increase."

Dijkstra also highly stressed the concept of error prevention instead of error recovery, by which problems simply never exist within code rather then trying to handle exceptions as they occur. During the sixties, in which Dijkstra began to heavily emphasize and promote structure in programming styles, the fairly primitive nature of the hardware being used by computer scientists demanded that fewer errors in code be made to compensate for the likely possibility of a hardware problem or failure. However, even today, Dijkstra's methods of structure and style are no less valid, contributing to the ease by which programmers in an enormous company may take another person's code and understand it, allowing for updating and modification by a programmer who had no influence on the creation of the original code. His work remains the basis of computer scientists sharing and reusing code during the current "Freeware Revolution" and the basis by which Linux users may modify application and OS code with relative ease and simplicity.

Dijkstra's passion for "program correctness, algorithms, and systems" led him to heavily contribute to the creation of the ALGOL-60 programming language, a language heralded as being thorough, small, and of elegant style. It was designed to have nested, recursive, and free form properties that allowed for superior structure within the language, an extension of Dijkstra's goal for fluidly readable style within programming. ALGOL-60 was originally designed for scientific programming, and is a language steeped in mathematical rigor and distinct clarity.

During his work on the ALGOL-60 language, Dijkstra found himself intrigued by the use of the GO TO statement in programming languages and how they affect the readability and structure of a program. After much thought, Dijkstra wrote a letter to the ACM warning of the potential dangers and general messiness of using the GO TO statement in a language other than the most simplistic machine code. In the letter, Dijkstra explains that "if-else"-type statements allow for a value-count at any given time during the program (for example, if we say:

if (numberofpeople = = 20) then (ShutDoor())

we can, at any point in which the program is running, examine the variable numberofpeople to determine how close we are to calling the function ShutDoor(). However, with the GO TO statement, we cannot examine at any point in time the progression of the program towards that statement. For example

goto ShutDoor()

would not allow us to examine when this procedure will be called, except by counting against a standardized clock. The statement is problematic as such, and in fact, the ALGOL-60 language contains a Switch statement capability that allows for much more graceful handling of GO TO-type situations rather than using a GO TO statement itself.

While working for the Mathematical Centre at Amsterdam, Dijkstra made quite a name for himself by solving the problem involving the centre's ARMAC computer. Engineers at the centre tried to discover the best way to "convey electricity to all essential circuits using as little wire as possible." The solution that Dijkstra formulated is now known as the famous Dijkstra's Algorithm, which finds the shortest path between a point on a graph and a destination.

Bibliography

Berard, Edward. "What is a Methodology?" The Object Agency Website. http://www.toa.com/pub/methodology_article.txt

Dijkstra, Edsger. "Edsger Wybe Dijkstra." Faculty Home Page - University of Texas. http://www.cs.utexas.edu/users/UTCS/report/1994/profiles/dijkstra.html

Dijkstra, Edsger. A Discipline of Programming. New Jersey: Prentice-Hall, 1976.

Dijkstra, Edsger. "GO TO Statement Considered Harmful." Association for Computing Machinery Website. http://www.acm.org/classics/oct95/

"Edsger W. Dijkstra". Association for Computing Machinery Turing Award Recipients. http://www.acm.org/awards/turing_citations/dijkstra.html

Morris, John. "Dijkstra's Algorithm." University of Western Australia Website. http://henson.cc.kzoo.edu/~k98mn01/dijkstra.html

Nusdorfer, Mike. "Edsger Dijkstra: Contributions to Computer Science." Kalamazoo College Website. http://henson.cc.kzoo/edu/~k98mn01/dijkstra.html

Perrolle, Judith. "Computers and Social Change: Web Edition." Northeastern University Website. http://www.ccs.neu.edu/home/perrolle/book/chapter8.html

Ulogov, Vladimir. "Encyclopedia of Programming Languages." OOPsworld Website. http://oop.rosweb.ru/Other/77.html