The Man Who Carried Laptop Science on His Shoulders | Krzysztof Apt

As it turned out, the practice I had taken from Nijmegen to Eindhoven arrived late. To make issues worse, I used to be then unable to seek out the proper workplace within the college constructing. Once I finally arrived for my appointment, I used to be greater than half an hour delayed. The professor utterly ignored my profuse apologies and proceeded to take a full hour for the assembly. It was the primary time I met Edsger Wybe Dijkstra.

On the time of our assembly in 1975, Dijkstra was 45 years previous. Probably the most prestigious award in pc science, the ACM Turing Award, had been conferred on him three years earlier. Virtually twenty years his junior, I knew little or no in regards to the discipline—I had solely realized what a flowchart was a few weeks earlier. I used to be a postdoc newly arrived from communist Poland with a background in mathematical logic and a plan to remain within the West. I left the assembly with two e book suggestions and a replica of a current analysis article Dijkstra had written. He additionally steered that I be taught the programming language Pascal.

Dijkstra handed away in 2002. In the course of the Seventies and Nineteen Eighties, on the top of his profession, he was in all probability probably the most mentioned scientist in his discipline. He was a pioneer and a genius whose work and concepts formed the rising discipline of pc science like few others. It was over the course of his profession that pc science grew to become a decent and established self-discipline.

There’s a permanent rigidity between the engineering view of pc science, which is concentrated on constructing software program techniques and {hardware} parts, and the mathematical and logical view, which goals to supply rigorous foundations for areas reminiscent of programming. Dijkstra tried to reconcile each views. Consequently, he contributed to either side of the divide in quite a few elementary methods.

Dijkstra was additionally a most putting and weird particular person. He was admired and criticized, in equal measure, and commented upon by nearly everybody he got here into contact with. But, regardless of his achievements, Dijkstra has all the time remained largely unknown outdoors pc science. Eighteen years after his dying, few individuals have heard of him, even in his personal nation.

Biography

Edsger Dijkstra was born in Rotterdam in 1930. He described his father, at one time the president of the Dutch Chemical Society, as “a superb chemist,” and his mom as “an excellent mathematician who had no job.” In 1948, Dijkstra achieved outstanding outcomes when he accomplished secondary faculty on the well-known Erasmiaans Gymnasium in Rotterdam. His faculty diploma reveals that he earned the best attainable grade in at least six out of 13 topics. He then enrolled on the College of Leiden to check physics.

In September 1951, Dijkstra’s father steered he attend a three-week course on programming in Cambridge. It turned out to be an thought with far-reaching penalties. It was in Cambridge that Dijkstra met the mathematician and pc scientist Adriaan van Wijngaarden, who subsequently supplied him a job on the Mathematisch Centrum (Mathematical Centre) in Amsterdam, which he joined the next yr. Dijkstra grew to become, in his personal phrases, “the primary Dutchman with the qualification ‘programmer’ on the payroll.” In 1956, he completed his research in Leiden. Three years later, he defended his PhD thesis, “Communication with an Automated Laptop.” His supervisor was van Wijngaarden.

Dijkstra labored on the Mathematisch Centrum till 1962, when he moved to Eindhoven to imagine the place of professor within the arithmetic division of the Eindhoven College of Expertise. In 1973, he lowered his employment to at some point per week and for the remaining 4 days labored as a analysis fellow on the Burroughs Company, at the moment an revolutionary American pc producer. His solely duties for Burroughs concerned enterprise analysis and touring to the US a number of occasions annually to go to the corporate headquarters.

In Dijkstra’s experiences, he listed the deal with Plataanstraat 5, Nuenen 4565, The Netherlands. This led some to imagine that the Burroughs Company had opened a brand new workplace. The deal with was, in truth, that of Dijkstra’s house, a modest home located in a village close to the outskirts of Eindhoven. His workplace consisted of a small room on the second ground, which was geared up with an “elegant transportable Olivetti typewriter” and “two telephones … certainly one of which he may use to name anyplace on the planet, with the payments going direct to Burroughs.”

In 1984, disenchanted with a change of path on the Burroughs Company and an absence of help for pc science at his college, Dijkstra left the Netherlands and took up a prestigious chair in pc science on the College of Texas at Austin. “Whereas Burroughs’s mental horizon was shrinking,” he later wrote, “my very own was widening.” He retired in 1999.

In early 2002, Dijkstra realized that he was terminally unwell and moved again to Nuenen along with his spouse, Ria. He handed away in August, just some months after returning. Ria died ten years later. The couple are survived by three kids: Femke, Marcus, and Rutger.

Over the course of his profession, Dijkstra wrote round 40 journal publications and 30 convention publications. He’s listed as the only writer for nearly all of those works. A number of of his journal papers had been simply a few pages lengthy, whereas most of his convention publications had been nonrefereed manuscripts that he offered in the course of the Annual Worldwide Marktoberdorf Summer season Faculty and printed within the faculty proceedings. He additionally wrote a handful of e book chapters and some books.

Considered from this angle, Dijkstra’s analysis output seems respectable, however in any other case unremarkable by present requirements. On this case, appearances are certainly misleading. Judging his physique of labor on this method misses the mark utterly. Dijkstra was, in truth, a extremely prolific author, albeit in an uncommon manner.

EWDs

In 1959, Dijkstra started writing a sequence of personal experiences. Consecutively numbered and along with his initials as a prefix, they grew to become referred to as EWDs. He continued writing these experiences for greater than forty years. The ultimate EWD, number one,318, is dated April 14, 2002. In whole, the EWDs quantity to over 7,700 pages. Every report was photocopied by Dijkstra himself and mailed to different pc scientists. The recipients different relying on the topic. Round 20 copies of every EWD had been distributed on this method.

The EWDs had been initially written in Dutch utilizing a typewriter. In 1972, Dijkstra switched to writing solely in English, and in 1979 he started writing them largely by hand. The EWDs consisted of analysis papers, proofs of recent or current theorems, feedback or opinions on the scientific work of others (normally essential and infrequently titled “A considerably open letter to…”), place papers, transcripts of speeches, strategies on how one can conduct analysis (“Do solely what solely you are able to do”), opinions on the function of training and universities (“It isn’t the duty of the College to supply what society asks for, however to provide what society wants”), and authentic options to puzzles. Later experiences additionally included occasional accounts of Dijkstra’s life and work. Quite a lot of EWDs are titled “Journey Report” and supply detailed descriptions of his travels to conferences (“I managed to go to Moscow with out being dragged to the Kremlin”), summer time colleges, or trip locations. These experiences are a wealthy supply of details about Dijkstra’s habits, views, pondering, and (hand)writing. Solely a small portion of the EWDs involved with analysis ever appeared in scientific journals or books.

This fashion of reporting analysis was, in truth, widespread in the course of the eighteenth century. Within the twentieth century it was a disarming anachronism. However, it labored. In EWD1000, dated January 11, 1987, Dijkstra recounts being instructed by readers that they possessed a sixth or seventh era copy of EWD249.

Whether or not written utilizing a fountain pen or typewriter, Dijkstra’s technical experiences had been composed at a pace of round three phrases per minute. “The remainder of the time,” he remarked, “is taken up by pondering.” For Dijkstra, writing and pondering blended into one exercise. When making ready a brand new EWD, he all the time sought to supply the ultimate model from the outset.

Round 1999, Hamilton Richards, a former colleague of Dijkstra’s in Austin, created a web site to protect all of the out there EWDs and their bibliographic entries. The E. W.  Dijkstra Archive, as the location is understood, additionally gives an abundance of further materials about Dijkstra, together with hyperlinks to scans of his early technical experiences, interviews, movies, obituaries, articles, and a weblog.

Regardless of a worldwide search, quite a few EWDs from the interval previous to 1968 have by no means been discovered. Different lacking entries within the numbering scheme had been, by Dijkstra’s personal admission, “occupied by paperwork that I failed to finish.”

Early Contributions

Dijkstra was a real pioneer in his discipline. This sometimes brought on him issues in on a regular basis life. In his Turing Award lecture he recalled:

[I]n 1957, I married, and Dutch marriage rites require you to state your career and I acknowledged that I used to be a programmer. However the municipal authorities of the city of Amsterdam didn’t settle for it on the grounds that there was no such career.

Within the mid-Nineteen Fifties, Dijkstra conceived a sublime shortest path algorithm. There have been only a few pc science journals on the time and discovering someplace to publish his three-page report proved removed from simple. Finally, three years later, he settled on the newly established Numerische Mathematik. “A Be aware on Two Issues in Connexion with Graphs” stays one of the extremely cited papers in pc science, whereas Dijkstra’s algorithm has turn out to be indispensable in GPS navigation techniques for computing the shortest route between two areas.

Over a interval of eight months starting in December 1959, Dijkstra wrote an ALGOL 60 compiler with Jaap Zonneveld. Theirs was the primary compiler for this new and extremely revolutionary programming language. It was a outstanding achievement. To be able to write the compiler, a number of challenges needed to be overcome. The obvious downside the pair confronted was that the machine designated to run the software program, the Dutch Electrologica X1 pc, had a reminiscence of solely 4,096 phrases. By comparability, the reminiscence of a present-day laptop computer is bigger by an element of one million.

The programming language itself was not with out its personal challenges. ALGOL 60 included a sequence of novel options, reminiscent of recursion, which was supported in a way more complicated method than logicians had ever envisaged. One of many concepts steered by Dijkstra, termed a show, addressed the implementation of recursive procedures and has since turn out to be a normal approach in compiler writing.

ALGOL 60 was designed by a world committee. Though Dijkstra attended a number of conferences in the course of the design course of, his identify doesn’t seem among the many 13 editors of the ultimate report. Apparently, he disagreed with quite a few majority opinions and withdrew from the committee. This was maybe the primary public signal of his fiercely held independence.

Throughout his employment on the Eindhoven College of Expertise, Dijkstra and his group wrote an working system for the Electrologica X8, the successor to the X1. The system they created, referred to as the THE multiprogramming system (THE is an abbreviation of Technische Hogeschool Eindhoven), had an revolutionary layered purposeful construction, wherein the upper layers depended solely on the decrease ones.

It was throughout his work on this method that Dijkstra’s pursuits started shifting to parallel packages, of which THE is an early instance. These packages include a set of parts, every of which is a standard program, executed in parallel. Such packages are notoriously tough to jot down and analyze as a result of they should work appropriately regardless of the execution speeds of their parts. Parallel packages additionally have to synchronize their actions to make sure unique entry to assets. If a number of print jobs are dispatched on the similar time by the customers of a shared pc community, this could not result in pages from the totally different print jobs turning into interspersed. Including to the complexity, the parts of parallel packages shouldn’t turn out to be deadlocked, ready indefinitely for each other.

Within the early Nineteen Sixties, these issues had not but been correctly examined or analyzed, nor had any methods been developed to confirm potential options. Dijkstra recognized an important synchronization downside, which he named the mutual exclusion downside, and printed his answer in a single-page paper. This work was taken from EWD123, an intensive 87-page report titled “Cooperating Sequential Processes.” In the identical report, he launched the primary recognized synchronization primitive, which he termed a semaphore, that led to a a lot less complicated answer to the mutual exclusion downside. He additionally recognized the impasse downside, which he named the lethal embrace, and proposed a sublime answer, the banker’s algorithm. The mutual exclusion downside, together with impasse detection and prevention, are actually obligatory subjects in programs on working techniques and parallel programming.

In 1968, Dijkstra printed a two-page letter addressed to the editor of the Communications of the ACM, wherein he critiqued the goto programming assertion. Entitled “Go To Assertion Thought of Dangerous,” the letter was extensively criticized and generated appreciable debate. Ultimately, Dijkstra’s views prevailed. Each programmer is now conscious that utilizing the goto assertion results in so-called spaghetti code. Java, at present one of the extensively used programming languages, was initially launched in 1996 and doesn’t have the goto assertion. The phrase “thought-about dangerous” continues to be used usually in pc science and stays inextricably related to Dijkstra.

In 1968, Dijkstra suffered an extended, deep despair that persevered for nearly half a yr. He later made point out of being hospitalized throughout this era. One purpose for Dijkstra’s torment was that his division didn’t take into account pc science vital and disbanded his group. He additionally needed to resolve what to work on subsequent. Dijkstra’s main software program tasks, the ALGOL 60 compiler and the THE multiprogramming system, had given him a way that programming was an exercise with its personal guidelines. He then tried to find these guidelines and current them in a significant manner. Above all, he strove to rework programming right into a mathematical self-discipline, an endeavor that saved him busy for a number of years to return. On the time, these had been utterly uncharted waters. No one else gave the impression to be devoting their consideration to such issues.

A yr later, the looks of the 87-page EWD249, “Notes on Structured Programming,” marked the tip of Dijkstra’s despair. The topic of the EWD was so novel, the writing so partaking, and the brand new time period “structured programming” so convincing that the report grew to become an enormous success. However, in Dijkstra’s view, “IBM … stole the time period ‘Structured Programming’ and … trivialized the unique idea to the abolishment of the goto assertion.” The declare was unsurprising to these conscious of Dijkstra’s long-held and largely detrimental views towards IBM computer systems and software program. These days it isn’t unusual to see related criticisms of enormous firms, however within the Seventies and Nineteen Eighties few lecturers had been ready to take a public stand in opposition to pc producers.

In 1972, Dijkstra acquired the ACM Turing Award, extensively thought-about crucial prize in pc science. He was acknowledged for

elementary contributions to programming as a excessive, mental problem; for eloquent insistence and sensible demonstration that packages must be composed appropriately, not simply debugged into correctness; for illuminating notion of issues on the foundations of program design.

Additional elementary contributions had been to comply with. In 1974, Dijkstra printed a two-page article wherein he launched a brand new idea: self-stabilization. Within the paper, he posed the issue of how a system of speaking machines would possibly restore itself when a brief fault arises in one of many machines. He offered new protocols that assured right functioning of the system would finally be restored. “Self-stabilization,” he remarked, “…could possibly be of relevance on a scale starting from a worldwide community [emphasis added] to widespread bus management.” This can be a putting statement when one considers that the World Extensive Internet was developed simply 15 years later. Because it turned out, the paper was utterly ignored till 1983, when Leslie Lamport confused its significance in an invited discuss. In time, the concepts outlined by Dijkstra would result in the emergence of an entire new space in distributed computing with its personal annual workshops and conferences. In 2002, the paper gained an award that was posthumously renamed the Edsger W. Dijkstra Prize in Distributed Computing.

The notion that some occasions can’t be deterministically predicted, normally known as indeterminism, has saved philosophers, and later physicists, occupied for hundreds of years. Laptop scientists enter the story extra not too long ago, learning the concept below the identify nondeterminism—not a reference, it must be famous, to any probabilistic interpretation of occasions. In 1963, John McCarthy launched nondeterminism within the context of programming languages. A few years later, Robert Floyd confirmed how this idea, now referred to as angelic nondeterminism, can considerably simplify programming duties requiring a search. When decisions come up there may be some computation that delivers the specified end result—although it isn’t sure which one.

Dijkstra’s view of nondeterminism was possible influenced by the inherently nondeterministic habits of the real-time interrupt handler he developed in his PhD thesis. In a 1975 paper, he launched a small programming language that he known as guarded instructions; it encapsulated what’s now termed demonic nondeterminism. This was, in truth, the paper he handed me the primary time I met him. In distinction to the angelic variant, all computations need to ship the specified end result. This extra demanding view of nondeterminism—known as nondeterminacy by Dijkstra—typically yields less complicated packages, however for causes apart from angelic nondeterminism. The programmer is free to go away some choices unspecified.

The programming notation launched by Dijkstra sometimes results in elegant packages. He illustrated this level by reconsidering Euclid’s 2,300-year-old algorithm for computing the best widespread divisor of two pure numbers. The algorithm will be acknowledged as follows: so long as the 2 numbers differ, hold subtracting the smaller quantity from the larger one. In Dijkstra’s language this algorithm will be written in a easy method that isn’t far faraway from its description in English. His language additionally launched the essential notion of a guard, which has since turn out to be a pure idea in varied programming formalisms. Equally, weakest precondition semantics, an idea Dijkstra launched to explain program semantics, marked a late however extremely vital entry into the sphere of program verification. A few years later, the language was generalized by Tony Hoare to create a extremely influential programming language proposal for distributed computing that he named CSP.

Dijkstra’s landmark e book A Self-discipline of Programming was printed in 1976. It launched a novel method to programming wherein Dijkstra mixed weakest precondition semantics with quite a few heuristics to develop a number of pc packages, hand in hand with their correctness proofs. In distinction with EWD249, “Notes on Structured Programming,” he was now arguing about program correctness in a proper manner. This improvement marked a brand new stage in Dijkstra’s analysis. He now considered the event of an accurate program as the event of a mathematical proof, one thing to which he first alluded in 1973 as a part of EWD361, “Programming as a Self-discipline of Mathematical Nature.” This system was quickly employed by Dijkstra and a gaggle of researchers to systematically derive varied, normally small, nontrivial packages. In distinction to a few of his different improvements, it by no means actually caught on.

Eighties

In the early Nineteen Eighties, Dijkstra cowrote two brief however influential papers wherein he utilized his methodology to the systematic improvement of distributed packages. He additionally sought to have this method to programming taught to first-year college students, and, with this purpose in thoughts, put collectively a sublime introductory textbook with Wim Feijen.

Dijkstra’s realization that programming could possibly be considered as a mathematical exercise led to his curiosity in analyzing mathematical reasoning. He tried to give you tips and heuristics that facilitated the invention of proofs. In quite a few circumstances these rules pointed him towards fascinating generalizations of recognized outcomes that had someway eluded others.

A great instance is the Pythagorean theorem, which is taught in secondary colleges. The concept states that in a right-angled triangle the sq. of the hypotenuse, c, is the same as the sum of the squares of the opposite two sides, a and b.

a² + b² = c²

In 1940, Elisha Loomis collected at least 370 proofs in The Pythagorean Proposition, beginning with the proof that appeared in Euclid’s Components, written round 300 BCE. New proofs sometimes seem to at the present time.

In 1986, Dijkstra got here up with the next generalization to arbitrary triangles, which he included in EWD975:

Think about a triangle with the aspect lengths a, b and c and the angles α, β and γ, mendacity reverse a, b and c. Then the indicators of the expressions a² + b² – c² and α + β – γ are the identical (that’s, they’re both each optimistic or each zero or each detrimental).

signal(a² + b² – c²) = signal(α + β – γ)

A mathematician would possibly observe that this all appears fairly apparent. But, apparently, no one had considered this generalization earlier than Dijkstra. He concluded his report by observing that it was unclear the place he would possibly publish this end result. In his view, it must be taught at colleges as a substitute of the unique theorem. In 2009, EWD975 was republished posthumously by Nieuw Archief voor Wiskunde (New Archive for Arithmetic), the journal of the Royal Dutch Mathematical Affiliation. The five-page report was reproduced in its authentic handwritten kind.

In a 1985 lecture, “On Anthropomorphism in Science,” delivered on the College of Texas at Austin’s Philosophy Division, Dijkstra speculated that mathematicians caught to the usage of implication as a result of they related it with trigger and impact. “One way or the other,” he noticed, “within the implication ‘if A then B,’ the antecedent A is related to the trigger and the resultant B with the impact.” He claimed that equivalence must be most popular over implication. This straightforward precept had led to his generalization of the Pythagorean theorem.

Dijkstra additionally tried to use his methodology for growing right packages to systematically develop proofs of mathematical theorems. In EWD1016, “A Computing Scientist’s Strategy to a As soon as-Deep Theorem of Sylvester’s,” he derived a sublime proof of the next theorem, first conjectured in 1893 and proved 40 years later: “Think about a finite variety of distinct factors in the true Euclidean aircraft; these factors are collinear or there exists a straight line by way of precisely 2 of them.”

One other instance from this era is his method to the issue of a good coin. A coin toss is used to find out certainly one of two outcomes in a good manner. However how can a good final result be achieved when the coin is biased? In 1951, John von Neumann got here up with a easy answer. Quite a lot of researchers then tried to determine how one can make it extra environment friendly. Dijkstra first realized of the issue throughout a lecture in 1989. He solved it instantly and a short while later got here up with the answer to a associated downside that apparently no one had considered earlier than. His answer to the associated downside will be present in EWD1071, “Making a Truthful Roulette from a Presumably Biased Coin.” Dijkstra’s modification of von Neumann’s answer was not instantly apparent and depends on a basic end result from quantity idea, Fermat’s little theorem. For a change, Dijkstra submitted this text to a journal and it was printed the next yr as a one-page be aware.

The event of a pure and readable notation for representing proofs and calculations was nearly as vital for Dijkstra as the issues into consideration. The notation he got here up with forces the writer to not commit what he described as “any sins of omission”:

• A
• = { trace why A = B }
• B
• = { trace why B = C }
• C

In his remaining EWD, for instance, Dijkstra explains that for s = (a + b + c)/2 the equality s(s – b)(s – c) + s(s –c)(s – a) = s(s – c)c holds, by writing out his argument as:

• s(s – b)(s – c) + s(s – c)(s – a)
• = { algebra }
• s(s – c)(2s – a – b)
• = { definition of s }
• s(s – c)c

He used this notation in his personal publications, notably in a e book he wrote along with his longstanding pal and colleague Carel Scholten. The notation was adopted by a number of of his colleagues however didn’t unfold additional. EWD1300, “The Notational Conventions I Adopted, and Why,” was republished posthumously and gives a singular perception into Dijkstra’s in depth work on notation, a topic that saved him busy all through his profession.

Within the late Nineteen Eighties, Dijkstra’s analysis was described on his departmental homepage as follows: “My space of curiosity focuses on the streamlining of the mathematical argument in order to extend our powers of reasoning, specifically, by way of formal methods.” It was additionally the topic of his course for pc science college students.

In the course of the interval 1987–1990, I used to be a fellow school member in Austin and adopted his course for a semester. Dijkstra invariably arrived early for sophistication in order that he may write out an uncommon citation on the blackboard. The lectures themselves had been all the time meticulously ready and normally dedicated to presenting proofs of straightforward mathematical outcomes. He delivered the lectures with out notes, requiring solely a blackboard and a chunk of chalk. On the finish of every lecture he would assign an elementary however nontrivial mathematical downside as homework and accumulate all of the options on the following lecture. Per week later he would return all of the options with detailed feedback, typically longer than the precise submissions, after which current his personal answer intimately, stressing the presentation and use of notation. My very own options fared fairly properly by Dijkstra’s requirements and had been normally returned with solely brief feedback, reminiscent of “Many sins of omission.” It was, in truth, a course in orderly mathematical pondering, and no one appeared in any respect bothered that it had nothing to do with pc science.

Dijkstra was a extremely partaking lecturer. He knew how one can captivate an viewers with dramatic pauses, well-conceived remarks, and putting turns of phrase. The larger the viewers, the higher he carried out. Whereas I used to be working in Austin I helped manage a departmental occasion with him as the principle speaker. About 200 individuals got here alongside, some having flown in from Houston and neighboring states to attend the occasion. Dijkstra stole the present and delivered a mesmerizing presentation on Sylvester’s theorem.

Nineties

In 1990, Dijkstra’s sixtieth birthday was celebrated in Austin with a big banquet that includes a distinguished group of visitors, together with quite a few vital figures in pc science. A Festschrift was printed by Springer-Verlag to mark the event. The quantity started on web page 0, in deference to the way in which Dijkstra numbered the pages of his EWDs. He took the difficulty of thanking every of the 61 contributing authors by a handwritten letter.

The interval that adopted was marked by a visual change in Dijkstra’s angle and method to his work. Within the remaining twelve years of his life, regardless of producing about 250 new EWDs, he printed nearly nothing. These experiences merely might not have met his requirements for a journal publication. Lots of the EWDs had been dedicated to systematically deriving proofs of difficult outcomes, reminiscent of an issue from the Worldwide Mathematical Olympiad. He additionally used his methodology to acquire elegant options for classical puzzles, such because the knight’s tour or the wolf, goat, and cabbage puzzle. A few of the EWDs from this era contained accounts and assessments of his early contributions.

Following Dijkstra’s retirement from instructing within the fall of 1999, a symposium was organized in Might 2000 to honor his seventieth birthday. The occasion was known as “In Pursuit of Simplicity” and included visitor contributors from each Europe and the US. Right now, I used to be working on the Centre for Arithmetic and Informatics (CWI) in Amsterdam and in the course of the symposium I invited Dijkstra to provide a lecture. CWI was, in truth, the brand new identify for the Mathematisch Centrum the place he had labored originally of his profession. Six months later Dijkstra accepted the invitation. He had by no means seen the brand new and bigger constructing the place the CWI had relocated within the early Nineteen Eighties, and was visibly moved.

Previous to the lecture, the CWI’s communication division issued a press launch. Information of the occasion caught the eye of a serious Dutch newspaper. A journalist was dispatched and an intensive article with a outstanding photograph of Dijkstra was quickly printed. VPRO, an impartial Dutch public broadcasting firm, subsequently grew to become fascinated with Dijkstra and despatched a crew to Austin to make a half-hour-long program about him. “Denken als self-discipline” (Considering as a Self-discipline) was broadcast in April 2001 as an episode of the science present Noorderlicht (Northern Lights). The episode acquired a glowing evaluate in one other outstanding Dutch newspaper.

In early 2002, Dijkstra returned to Nuenen, incurably unwell with most cancers. The information unfold shortly within the pc science neighborhood and was invariably met with deep unhappiness. The final time I noticed Dijkstra was at his house in July 2002. As was normally the case with guests, he collected me by automotive from the closest practice station a few kilometers away from his home. In the course of the go to, we spoke collectively, shared lunch, and he instructed me that he didn’t have a lot time left. He additionally gave me a replica of EWD1318, “Coxeter’s Rabbit,” dated April 14, 2002, mentioning that it might be his remaining report.

Dijkstra handed away a month later. His funeral was attended by quite a few his colleagues, together with a number of from Austin. In his eulogy, Hoare mirrored on Dijkstra’s immense contributions to the event of his discipline:

He would lay the foundations that will set up computing as a rigorous scientific self-discipline; and in his analysis and in his instructing and in his writing, he would pursue perfection to the exclusion of all different issues. From these commitments he by no means deviated, and that’s how he has made to his chosen topic of research the best contribution that anyone particular person may make in anyone lifetime.

J Strother Moore, then chairman of the pc science division in Austin, additionally spoke warmly and evocatively of Dijkstra: “He was like a person with a lightweight within the darkness. He illuminated nearly each challenge he mentioned.”

Obituaries subsequently had been printed in a number of main newspapers, together with the New York Occasions, the Washington Publish, and The Guardian. Prolonged commemorative items and reminiscences appeared in the course of the months that adopted, wherein Dijkstra was variously acclaimed as a pioneer, prophet, sage, and genius.

Opinions and Attitudes

Dijkstra’s enduring affect in pc science shouldn’t be confined solely to his analysis. He held robust opinions about many features of the sphere, most notably about programming languages and the instructing of programming, but in addition the needs of training and analysis.

Dijkstra didn’t draw back from controversies. He was a devoted contrarian who reveled in expressing excessive and unconventional opinions. I noticed this firsthand in 1977 throughout a big pc science convention in Toronto. Audiences for plenary lectures on the occasion numbered someplace between a number of hundred and a thousand attendees. Every of the lectures concluded with a number of well mannered viewers questions for the speaker, typically a number one professional in his space. I’ve a vivid recollection of Dijkstra standing up on the finish of 1 lecture and delivering a stinging rebuke to the speaker. Opposite to appearances, he hoped to impress an informative dialogue. The chairman was visibly shocked by Dijkstra’s intervention and appeared at a loss as to how he ought to proceed.

Dijkstra was additionally unafraid to voice harsh critiques at smaller gatherings. Within the late Seventies, I attended a seminar in Utrecht with about twenty different individuals, together with Dijkstra. He repeatedly interrupted a extremely revered lecturer to question him about his use of terminology and abbreviations. Midway by way of the presentation Dijkstra abruptly received up and left. Different tales in the same vein had been removed from unusual and circulated all through the sphere.

Dijkstra took his work as a reviewer extraordinarily severely and his experiences had been detailed and thoroughly thought out. A few of these evaluations had been undertaken at his personal initiative and appeared as EWDs. These included a optimistic evaluate of a 400-page pc science e book that had no apparent connection to his analysis. He additionally produced in depth and considerate feedback on manuscripts despatched to him by his colleagues who had adopted his notation or methodology, or whose analysis he deemed vital.

In 1977, Dijkstra wrote a vitriolic evaluate of a report, “Social Processes and Proofs of Theorems and Applications,” by Richard De Millo, Richard Lipton, and Alan Perlis. The report later appeared as a journal paper. Dijkstra distributed his evaluate as EWD638, “A Political Pamphlet from the Center Ages,” wherein he referred to the report as “a really ugly paper.” The authors had argued that “program verification is certain to fail,” a view Dijkstra vehemently disagreed with.

A few of these evaluations led to additional correspondence with the unique authors. In 1978, Dijkstra distributed an in depth and scathing evaluate of the 1977 Turing Award Lecture delivered by John Backus. In EWD692 he argued that the lecture “suffers badly from aggressive overselling.” On the time, Backus was one of the outstanding working pc scientists. He was the co-inventor of a normal notation used to explain the syntax of programming languages, referred to as Backus–Naur kind, and had led the staff that designed and applied Fortran, the primary high-level programming language. In his lecture, Backus had advocated for an alternate type of programming, referred to as purposeful programming. 4 years in the past, Jiahao Chen found an intensive and extremely essential correspondence between Backus and Dijkstra that occurred following the evaluate. Dijkstra correctly saved these exchanges away from the general public eye.

In some quarters, Dijkstra was considered as smug and his opinions thought-about excessive. When cataloguing their correspondence in his papers, Backus added the remark: “This man’s vanity takes your breath away.” For a lot of, particularly those that adopted his notation, Dijkstra grew to become a determine akin to a guru. A small group of his followers even began their very own EWD-like experiences, all consecutively numbered and written by hand. Dijkstra appeared detached to such shows. “However he takes himself so severely,” a Turing Award winner as soon as confided to me. Certainly, one typically had the impression that he carried the load of pc science on his shoulders.

In 1984, I used to be invited to be a lecturer on the annual Marktoberdorf Faculty, co-organized by Dijkstra. Though I regarded this as an ideal honor, I couldn’t assist however really feel anxious about having him assessing my work. His evaluate appeared in EWD895, “Journey report E. W. Dijkstra, Marktoberdorf, 30 July–12 Aug. 1984.” I used to be vastly relieved to find his feedback weren’t solely pretty gentle, however even fairly optimistic compared to his different evaluations: “Apt’s lectures suffered considerably from this [i.e., talking ‘exclusively about CSP’] … The examples chosen as an example his factors had been a bit elaborate, however his aware efforts to be understood had been extremely appreciated.”

Inspired by this appraisal, I submitted one of many papers I had offered to a peer-reviewed journal. A few months later, the nameless referee experiences arrived. One of many evaluations was unmistakably the work of Dijkstra. An in depth criticism of what he thought to be an absence of sufficiently formal arguments, mixed with an extended checklist of calls for and questions, made trying passable revisions a hopeless job. Even in the present day, I might not know how one can meet these calls for as a result of the proper formalism continues to be missing. On the time, it was nonetheless thought-about a privilege to have a paper refereed by Dijkstra.

In 1989, Dijkstra offered his views on instructing pc programming in a lecture titled “On the Cruelty of Actually Instructing Laptop Science” throughout an ACM Laptop Science Convention. A transcript was later circulated as EWD1036. After presenting a sweeping historic survey aimed toward illustrating conventional resistance towards new concepts in science, Dijkstra argued that pc programming must be taught in a radically totally different manner. His proposal was to show a number of the parts of mathematical logic, choose a small however highly effective programming language, after which think about the duty of establishing provably right pc packages. In his view, packages must be thought-about the identical manner as formulation, whereas programming must be taught as a department of arithmetic. There was no place for operating packages or for testing, each of which had been thought-about customary follow in software program engineering.

The lecture and report led to an intensive debate that also makes for fascinating studying. Dijkstra’s report was printed in Communications of the ACM, alongside along with his well mannered however unapologetic responses to largely detrimental reactions from outstanding pc scientists. Whereas he was praised for initiating a much-needed debate, Dijkstra’s suggestions had been deemed unrealistic and too controversial.

Dijkstra usually expressed his opinions utilizing memorable turns of phrase or maxims that caught the ears of his colleagues and had been extensively commented upon. Listed below are some examples:

• Program testing can be utilized to point out the presence of bugs, however by no means to point out their absence.
• Laptop science isn’t any extra about computer systems than astronomy is about telescopes.
• The query of whether or not machines can assume is about as related because the query of whether or not submarines can swim.
• A components is price a thousand photos.

In certainly one of his EWDs, Dijkstra collected a number of jibes about programming languages, reminiscent of: “The usage of COBOL cripples the thoughts; its instructing ought to, due to this fact, be thought to be a prison offense.” On the time, COBOL was one of the extensively used programming languages and these feedback weren’t warmly acquired.

A few of Dijkstra’s opinions had been unavoidably controversial and highlighted his longstanding prejudices. Once I first met him in 1975 he really helpful the e book Structured Programming, however steered that I skip the ultimate chapter by Hoare and Ole-Johan Dahl, because it handled object-oriented programming. Nonetheless, object-oriented programming step by step grew to become a universally most popular strategy to construction a big program. However not for Dijkstra. He was nonetheless arguing in opposition to it in 1999, stating throughout a keynote deal with that, “For many who have questioned: I don’t assume object-oriented programming is a structuring paradigm that meets my requirements of magnificence.” By that point, the favored object-oriented programming language C++ was routinely taught to first-year pc science college students.

Character and Way of life

Throughout his skilled profession, Dijkstra remained remarkably modest. He by no means had a secretary; he typed or wrote all his publications himself. Most had been completely his personal work and even the few that listed coauthors had been clearly written by Dijkstra, or in his type. After 1979, he most popular to jot down by hand utilizing a Montblanc fountain pen. His writing type grew to become so recognizable amongst pc scientists within the Nineteen Eighties {that a} fellow tutorial, Luca Cardelli, designed a Dijkstra font for Macintosh computer systems. Not lengthy after it was launched, Dijkstra acquired a letter typeset in Cardelli’s font and mistakenly assumed it was handwritten. He felt tricked by the letter and was not amused. Some years later, he was in a position to admire the humor when a colleague in Austin, Bob Boyer, adopted the font for displays throughout departmental conferences.

It appears Dijkstra by no means utilized for any grants—although he did obtain at the very least one, to make use of a PhD pupil—nor did he carry any cash, within the type of analysis contracts, to the establishments he labored for. He additionally by no means bought a pc. Finally, within the late Nineteen Eighties, he was given one as a present by a pc firm, however by no means used it for phrase processing. Dijkstra didn’t personal a TV, a VCR, or perhaps a cell phone. He most popular to keep away from the cinema, citing an oversensitivity to visible enter. Against this, he loved attending classical music concert events.

When participating in conferences and summer time colleges Dijkstra usually felt uncomfortable in giant teams. Unaccustomed to small discuss, he normally remained awkwardly silent. Away from the work surroundings, nevertheless, he was utterly totally different. From his time in Austin, I and others recall him as pleasant, useful, and wanting to drop by along with his spouse for a brief social go to that always led to partaking conversations. He and his spouse favored to ask visitors over, for whom he sometimes performed brief items of classical music on his Bösendorfer piano. His favourite composer was Mozart. A putting function of Dijkstra’s front room was a lectern with a big copy of the Oxford English Dictionary, which he discovered indispensable in his work. He’s, by the way, talked about in the identical dictionary in reference to the usage of the phrases vector and stack in computing.

In Austin, Dijkstra stayed away from college politics. He was extremely revered by colleagues, not least due to his collegial angle throughout departmental conferences. He took his instructing duties very severely. Exams had been all the time oral and will final a few hours. Upon completion of the examination, an off-the-cuff chat adopted throughout which the scholar was offered with a signed photograph of Dijkstra, and a beer—age allowing. He held his weekly seminars in his workplace and served espresso to the scholars in attendance, usually stunning them along with his unassuming habits.

All through his life, Dijkstra was an uncompromising perfectionist, all the time targeted on tapping his creativity, unwilling to decrease his requirements, and detached towards different factors of view. He additionally discovered it tough to browse articles in his discipline to kind an thought of their contents and appeared tired of monitoring down and learning the related literature. For probably the most half, he adopted the suggestions of his shut colleagues and solely studied the papers they steered. Consequently, his personal papers usually had only a few, if any, bibliographic entries. The preface of A Self-discipline of Programming concludes with a frank admission: “For the absence of a bibliography I provide neither clarification nor apology.” This cavalier method led to occasional complaints from colleagues who discovered that their work was ignored.

As an alternative, Dijkstra most popular to check basic texts, reminiscent of Eric Temple Bell’s Males of Arithmetic, which he referred to sometimes throughout his programs in Austin, and Linus Pauling’s Normal Chemistry, a e book he praised in highest phrases. This angle served him properly in the course of the Nineteen Sixties and Seventies, nevertheless it grew to become more and more impractical as pc science matured.

Printed in 1990, Dijkstra’s Predicate Calculus and Program Semantics, cowritten with Scholten, was a working example. The e book not solely lacked references, but in addition exhibited an entire disregard for the work of logicians. Egon Börger penned an intensive and devastating evaluate, claiming that the method outlined by the authors was not in any manner novel, nor did it provide any benefits. He additionally vigorously criticized the e book’s rudimentary historical past of predicate logic, wherein the authors drew a line from the work of Gottfried Leibniz to that of George Boole after which to their very own contributions, neglecting to say anybody else.

In response to Börger’s evaluate, some colleagues tried to assist by publishing papers that offered a helpful logical evaluation and clarification of Dijkstra and Scholten’s method based mostly on their so-called calculational proofs. Dijkstra remained unrepentant. “I by no means felt obliged to placate the logicians,” he remarked some years later in EWD1227. “If nevertheless, [logicians] solely get infuriated as a result of I don’t play my sport in response to their guidelines,” he added, referring particularly to Börger’s evaluate, “I can’t resist the temptation to disregard their fury and to shrug my shoulders in probably the most well mannered method.”

Dijkstra’s humorousness was, at turns, wry and terse. I as soon as requested him what number of PhD college students he had. “Two,” he replied, earlier than including, “Einstein had none.” On one other event, he wrote to me that “[redacted] strengthened the Division by leaving it.” In Austin, collectively along with his spouse, he bought a Volkswagen bus, dubbed the Touring Machine, which they used to discover nationwide parks.

Dijkstra was additionally extraordinarily sincere. He was all the time insistent, for instance, that the primary answer to the mutual exclusion downside was discovered by his colleague Th. J. Dekker. In EWD1308, he admitted that F. E. J. Kruseman Aretz “nonetheless discovered and repaired quite a few errors [in the ALGOL 60 compiler] after I had left the Mathematical Centre in 1962,” and that the phrase “thought-about dangerous” was, in truth, invented by an editor of the Communications of the ACM, Niklaus Wirth. Dijkstra’s contribution was initially titled “A Case in opposition to the GO TO Assertion.” In the identical EWD, he additionally admitted utterly lacking the importance of Floyd and Hoare’s preliminary contributions to program verification. “I used to be actually gradual” he lamented.

Legacy

Dijkstra left behind a outstanding array of notions and ideas which have withstood the take a look at of time: the show, the mutual exclusion downside, the semaphore, lethal embrace, the banker’s algorithm, the sleeping barber and the eating philosophers issues, self-stabilization, weakest precondition, guard, and structured programming.

His shortest path algorithm is taught to all college students of pc science and operations analysis and is all the time known as Dijkstra’s algorithm. A number of years in the past I noticed it illustrated, below this identify, by way of an interactive gadget with lights and buttons on the Science Centre Singapore.

Dijkstra and Zonneveld’s ALGOL 60 compiler is rightly acknowledged as a milestone within the historical past of pc science—albeit extra so in Europe than elsewhere. A whole PhD thesis was not too long ago dedicated to its reconstruction and an in depth evaluation. The layered design of the THE multiprogramming system is mentioned in a number of textbooks on working techniques, and influenced the design of some later working techniques.

Among the many ideas invented by Dijkstra, some have been mirrored in e book titles. An early instance is Structured Programming, printed in 1972. There are actually a number of books known as Structured Programming Utilizing Language X. In 1986, a e book appeared with the title Algorithms for Mutual Exclusion—others with the same title finally adopted—and in 2000 a e book titled Self-Stabilization was printed.

Dijkstra’s approaches to nondeterminism and parallelism are a part of customary programs on these topics. His proposal for a primary synchronization mechanism triggered analysis that, in flip, resulted within the improvement of high-level synchronization mechanisms which are indispensable for parallel programming. His basic issues, such because the sleeping barber and eating philosophers, the latter named by Hoare, have turn out to be customary benchmarks. When strategies had been developed to formally confirm parallel packages, the primary examples tackled had been Dijkstra’s packages.

But Dijkstra’s most enduring contribution might be oblique—in software program engineering. The problem of manufacturing right software program was an ongoing concern all through his scientific profession. In 1962, he wrote a paper, “Some Meditations on Superior Programming,” wherein he raised the difficulty of program correctness and expressed the hope that this facet would possibly sometime be known as the science of programming. At a serious convention in 1968, it was acknowledged that the supply of more and more highly effective computer systems led to more and more complicated and unreliable software program techniques, an issue termed “the software program disaster.” Dijkstra, who was in attendance, couldn’t have agreed extra.

Within the years that adopted, he produced quite a few partaking and influential essays on software program improvement wherein he explicitly referred to the software program disaster as an pressing downside. He forcefully argued that software program techniques must be constructed on sound design rules, and that correctness must be a driving precept behind program development. Specifically, he launched the often-cited separation-of-concerns design precept, which, he remarked, “even when not completely attainable, is but the one out there approach for efficient ordering of 1’s ideas, that I do know of.” Following the instance of Hoare and Wirth, he additionally advocated for varied types of abstraction and the usage of assertions to annotate packages. At a later stage, he argued that the programming course of itself must be considered as a mathematical exercise.

Though Dijkstra’s idealized imaginative and prescient that packages must be constructed along with their correctness proofs has not been realized, it undoubtedly offered the impetus for brand spanking new strategies of structuring and growing packages—together with, considerably paradoxically, the emergence of the object-oriented programming paradigm that he so vigorously opposed. This imaginative and prescient additionally helped encourage the design of recent programming languages, together with platforms and techniques to facilitate the programming course of. Lastly, Dijkstra’s “Notes on Structured Programming” was extremely influential within the improvement of higher designed and extra systematic programs on programming, sometimes with an emphasis on systematic program development and correctness.

It’s tough to seek out one other scientist who left such a formidable mark within the historical past of pc science.