Computer Science

Dijkstra’s Most Powerful Lessons


Edsger Wybe Dijkstra was one of the pioneers and one of the most influential members in the field of computer science.
Dijkstra had contributed in many domains such as algorithm design, operating system, distributed processing, and the list goes on.

If you are a computer science student in the past or present, you probably encountered Dijkstra’s work in your Algorithms course where you studied the algorithm for the shortest path between two nodes in a graph — known as Dijkstra’s Algorithm, or the Dining philosophers problem presented in Operating System course to illustrate synchronization issues and techniques for resolving them.


While researching Dijkstra’s work, I have found out that Dijkstra had composed more than a thousand manuscripts (1318 precisely), called EWDs, that he distributed to his colleagues.
The manuscripts topics were computer science and mathematics and included Dijkstra’s trip reports, letters, and speeches.

Around a week ago, I stumbled upon a specific EWD that seemed to be quite intriguing judging from the table of contents, it was EWD249, and after reading it, I wish to share with you a few insights that resonated with me.


In August 1969 Dijkstra wrote EWD249 — Notes on Structured Programming and declared programming as a discipline in contrast to a craft, which became one of his most famous manuscripts till this day.

Lesson #1 — Know And Respect Your Limitations

In the second section called “On our inability to do much”, Dijkstra is discussing the difficulties of scalability in programming.

“It would be very nice if I could illustrate the various techniques with small demonstration programs and could conclude with ‘… and when faced with a program a thousand times as large, you compose it in the same way.’ “

In other words, Dijkstra is claiming that the size of a program doesn’t scale linearly with the complexity of its composition and that we cannot apply induction thinking to the problem of scalability.

“We tell ourselves that what we can do once, we can also do twice and by induction we fool ourselves into believing that we can do it as many times as needed, but this is just not true!”

Dijkstra argues that difficulties in scalability are one of the major underlying causes of software failure, and his advised solution is to treat these problems as explicitly as possible.

Dijkstra finishes off this section with quite a strong statement that I truly resonated with.

“as a slow-witted human being I have a very small head and I had better learn to live with it and to respect my limitations and give them full credit, rather than to try to ignore them, for the latter vain effort will be punished by failure.”

Although Dijkstra is comparing himself to a machine when saying he’s “a slow-witted human”, I think that his statement could be applicable to life in general, as we all have our inherent limitations.

Lesson #2 — Program Testing Limitations

In the third section called “On the reliability of mechanisms”, Dijkstra is discussing reliable software and hardware while making an argument that testing methodologies are limited and are not enough to completely verify the software/hardware functionality.

“Present-day computers are amazing pieces of equipment, but most amazing of all are the uncertain ground on account of which we attach any validity to their output. It starts already with our belief that the hardware functions properly.”

Dijkstra is mentioning an example of a circuit board that performs a fixed-point multiplication of two 27-bit integers and asks “Is this multiplier correct, is it performing according to the specifications?”.
Theoretically, the circuit functionality can be tested thoroughly. there is a finite number of different calculations it will need to do — 2^54, so we can try and test them all.
Although this test might seem reasonable, if a single multiplication took only a single microsecond, to test all 2⁵⁴ it will take more than 500 years (571.2).

“We must conclude that exhaustive testing, even of a single component such as a multiplier, is entirely out of the question.”

As for software testing, given that the probability of an individual software component to be correct is p, the probability of the entire program to be correct is pⁿ where n is the number of components.
Hence, the probability that a program is not entirely correct is 1-pⁿ, which approaches 1 as n grows — large programs have a higher probability to fail.

“My conclusion is that it is becoming most urgent to stop to consider programming primarily as the minimization of a cost/performance ratio. We should recognize that already now programming is much more an intellectual challenge: the art of programming is the art of organizing complexity, of mastering multitude and avoiding its bastard chaos as effectively as possible”

Dijkstra seals off this section with a concise statement that concludes our second lesson

“Program testing can be used to show the presence of bugs, but never to show their absence!”


This concludes the 2 most powerful lessons from Dijkstra — at least from the ones that I encountered — feel free to share yours in the comments


References

[1] https://www.cs.utexas.edu/users/EWD/ewd02xx/EWD249.PDF

0 comments on “Dijkstra’s Most Powerful Lessons

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: