Categorie: Dijkstra

The roots of modern computing explained in EWD51 – Multiprogramming and the X8

Dijkstra’s EWD 51 is a structured educational coverage of the workings of semaphores in communicating processes and with IO devices. It is the first part in a series of three articles called MULTIPROGAMMERING EN DE X8″ (Multiprogramming and the X8), EWD54 and 57 describe part 2 and 3.

The X8 is the Dutch research computer for which Dijkstra and hos team developed the operating system, and he was able to test his now famous concepts for multiprogramming. 
In a way it is the formal part of the talk that Dijkstra held and was transcribed in EWD 35.

EWD 51 extensively discusses the mechanisms of semaphores, the conditions, and (hardware) implications. That is the summary. To give more would be pointless, and you’d rather read the entire article. (The article is in Dutch – I could provide a quick translation if you are interested. Please let me know through a comment on this post, or send me an email)

The Dutch language used in this article is highly interesting. Dijkstra invents concepts for which no words existed before (seinpaal/semaphore as computing concept to start with) the abbreviations P (prolaag/pass – probeer te verlagen) and V (verhoog/increase), critieke secties / critical sections, ingreep-flip-flop / interrupt-flip-flops, luisterbit / listener bit, doof-horend bit.

The article could still  function as a modern introduction into the topic and still be applicable to today’s computers.

So far ahead, so clear, so up to date still.

Singularity Is Near, so could humour be (Kurzweil meets Dijkstra)

I was reading Ray Kurzweil’s Singularity Is Near and couldn’t keep wondering what was missing. Then I hit this passage where Kurzweil quotes Edger W. Dijkstra.

“Computer Science is no more about computers than astronomy is about telescopes.”

Why this quote, in this context?

And Dijkstra’s statement: when and where did he say this?

So I did a bit of research on the internet, especially in the Dijkstra archive. I could not find the source of this phrase.
Other places on the internet https://en.wikiquote.org/wiki/Edsger_W._Dijkstra find the attribution disputed (and yes you can easily dispute this and other internet sources).

By the way Dijkstra could very well have said it. Even though he was a world famous computer scientist, he seems to only have owned a computer himself to read email and surf the web. So at least for him, this statement holds true.

Back to Singularity. I find the choice and place of this quote an example of the shortcomings of this book: the mixing of scientific facts with with personal and vaguely backed predictions. Some predictions are no more than Kurzweil’s personal believes. Also the context in which this quote is placed is odd: Kurzweil in this chapter talks about exponential growth, about Moore’s Law, curve of a paradigm and take over of new paradigm. It is unclear where this Dijkstra quote fits in this story.

This made me think about the differences between Dijkstra and Kurzweil. Dijkstra: unconventional theoretical scientist. Kurzweil: unconventional futuristic engineer. You would expect Dijkstra to be a dry personality and Kurzweil more flamboyant. But surprisingly the big difference and the major shortcoming in Kurzweil’s work is this one thing that Dijkstra sprinkles through all of his work: humour.

EDW 37 – a review of the new IBM 1620

In EWD 37 Dijkstra records a product review of the the new IBM 1620 computer, which came to the market in 1959.
As often, the article starts with a wonderful Dijkstra-esk introduction.

It is a good custom that scientific articles are reviewed and that no publisher ever thinks about starting a lawsuit or any other measures of vengeance against the author of a very unfavourable review of one of his publications.
I am not sure if it is the first review of a new computer ever, but it is an interesting one, and it goes quite deep into the technical aspects.
But not before making a justification for doing the review in general.
“It is a good custom that scientific articles are reviewed and that no publisher ever thinks about starting a lawsuit or any other measures of vengeance against the author of a very unfavourable review of one of his publications.

(BTW for the historians amongst us, the 1620 was considered the first “mini-computer”.)

With this in mind it is somewhat curious that it is not customary to review digital computers. Reviews of these scientific instruments are in some respects much more important: it is a pity if you have bought the wrong book, but it is much, much worse if you have bought the wrong computer.

eabcce7f-6977-4915-a117-14ede64e48f5

Foto from http://www-03.ibm.com/ibm/history/exhibits/mainframe/mainframe_PP1620.html

It is my considered opinion, however, that this machine embodies some very fundamental mistakes and certainly after the publication of the two letters mentioned above I regard it as my duty not to remain silent any longer. Manufacturers should be warned for these mistakes in order not to be tempted to incorporate them in their future designs, also machine users should be warned for these mistakes in order to help them in not chosing the wrong machine and in order to create a climate where machines will be judged more by their fundamental properties.

Dijkstra surfaces two major flaws in the design of this computer.
An instruction for constructing subroutines (Branch And Transmit) that is basically unusable because it is impossible to use in nested subroutines.

Another problem Dijkstra identifies is with the design of the paper tape processing. And it wouldn’t be Dijkstra if he would not illustrate this shortcoming with a great metaphor.

But now a curious problem arises: the terminal Record XXX Mark which has been stored is indistinguishable from previous Record Marks which might have been read from the tape, and therefore the machine is faced with a problem that shows a striking resemblance to the prototype of an improper algorithm: a man asking the way and getting the answer “You go straight on and turn to the right just before the last steel bridge.”

Dijkstra goes on to criticise the implementation of the variable field addressing method. He proves the implementation in not only very uneconomic (wasting memory – “cores”), but also severely limiting memory management. So severe that he questions the intelligence of the designers of the computer.

I always wonder whether the designers of such machines have been aware of the restrictive consequences of the technique in question; if so, it is hard to respect their conscious decision to stick to it, if not, are they the people that should have been designing machines? I always wonder……

Looking at these shortcomings they seem quite hilarious, but these were the early days of computing.

Dijkstra concludes his review with a final scathing verdict. Not only the buyers must have been totally ignorant to have bought such a machine, also the manufacturer is to blame.

As the reader will understand, my recent study of the IBM 1620 has been a shocking experience: I knew that it was a rather small machine but I had never suspected that it would embody so many basic blunders. Personally, I cannot undergo such an experience without asking myself what its morals are.
One of the facts we have to face is that this machine, despite of its poor qualities, has been bought or rented. Either the customer is incompetent to judge what he is buying, or the contracts are signed by the wrong persons; in both cases the conclusion is that the fact, that other people have chosen a particular machine, is no guarantee whatsoever as far as its quality is concerned.

The next fact that we have to face is that this machine, despite of its poor qualities, has been produced, in this case even by a big firm with a long and considerable experience. The straightforward conclusion is, that nor the size nor the experience is a guarantee as far as the quality of the product is concerned. Well, we can think of various explanations for this apparent inconsistency, but the most obvious explanation predicts still more blunders in the more ambitious and more complicated products of the manufacturer in question.

Thank you very much. There you go, IBM.

Watching the birth of modern computing – EWD 35

EWD 35 starts out in typical Dijkstra way.

It is not unusual for a speaker to start a lecture with an introduction. As some in the audience might be totally not familiar with the issues that I wish to address and the terminology, which I will have to use, I will to give two examples as a means of introduction, the first one to describe the background of the problem and a second one, to give you an idea of the kind of logical problems, that we will encounter.

The story that EWD 35 tells is a brief history of the resolution to the scientific topic that brought Dijkstra his fame: the problem of synchronising parallel processes and the invention of the the concept of the semaphore for these types of problems in computing.

Today it is almost impossible to imagine a time in which this problem was still unsolved. Collaborating parallel processes, semaphores and indivisible operations have become a such a commodity in computing. But at that time computing meant sequential processes and parallelism of interacting processes was being looked at for the first time.

In 1959, the question was of whether the described capability for communication between two machines made it possible to couple two machines such, that the execution of the critical sections was mutually excluded in time. In 1962, a much wider group of issues was considered and the question was also changed to “What communication possibilities between machines are required, to play this kind of games as gracefully as possible?”

A side note. The word “required” and “possibilities” here do not cover the meaning of Dijkstra’s original in Dutch “welke communicatiemogeljkheden tussen machines zijn gewenst”. I would say “which communication facilities between machines are desired” – expressing better that Dijkstra is in the mode of designing the thing, thinking up these communication facilities.

Another side note, much of Dijkstra’s beautiful loose writing in Dutch is lost in this straightforward translation to English here. For example, we can translate “Jantje” to “Johnny” but in Dutch we have a completely different image in our head when we see Jantje than we someone, Dutch or non-Dutch, would have with Johnny.

Dijkstra uses the word machines in the paragraph quoted above. The terminology developed further and today we would call these, a bit more abstract, processes.

Further in his article he gives an insight into the potential for his “machines” and sees them simulated on a central computer. We really have to imagine this is a remarkable insight in the future. At that time computer ran single tasks. Running multiple processes at the same time on the same hardware was at best experimental. He makes this remark in the context of alternative ways of having machines collaborate and let them wait on each other by building in wait times in case they need access to the same resource.

However, if we consider now, that will be the majority of these machines will be simulated by a central computer so that any action in one machine can only be performed at the expense of the effective speed of the other machines, then it is very costly using a wait cycle to demand attention of the central computer for something completely useless.

The basic problem Dijkstra extensively examines is best described by Dijkstra in the following sentences. One machine wants to assign a value to a shared variable, after testing its value. For example something like:

if x=3 then x :=4 else x:=5

Another machine is trying to do the same thing, at the same time. What happens if machine 1 tests for the value of x, while at the same time machine 2 changes this value. Or, what happens if they both change the value of x at the same.

Dijkstra indicates a mechanism is necessary which he call indivisible actions. Today these things are indivisible, uninterruptible or atomic operations or instructions.

These two actions, assigning a new value and inquiring about the current value are considered indivisible actions, i.e. if both machines wish to “simultaneously” assign a value to a common variable then the value assigned at the end is one or the other value, but not some mixture. Similarly, if one machine asks for the value of a shared variable at the time that the other machine is assigning a new value to it, then the requesting machine will receive or the old or the new value, not a random value.

Having these instructions is key to the solution of the problem of interaction sequential processes.

In EWD35 Dijkstra then goes on to describe, in a rather lengthy paragraph – but remember this was front end research at that time – the invention of the semaphore in computing.

The programmed wait cycle that exists herein, is of course very nice, but it did little to what our goal. A tiny wait cycle is indeed the way to keep a machine busy “without effect” . However, if we consider now, that will be the majority of these machines will be simulated by a central computer so that any action in one machine can only be performed at the expense of the effective speed of the other machines, then it is very costly using a wait cycle to demand attention of the central computer for something completely useless. As long as the wait cycle cannot be exited, in our opinion the speed of this machine may be reduced to zero, To express this we introduce a statement instead of wait cycle, a basic instruction in the repertoire of the machines, that may take a very long time. We indicate this with a P (to Pass); in anticipation of future needs, we represent the statement “SX: = true” by “V(SX) – with V of “vrijgave” (in English: release) (This terminology is taken from the railway environment. In an earlier stage the common logical variables were called “Semaphores” and if their name starts with an S, it is a reminiscence of it). The text of the programs in this new notation is as follows:

“LXi: P(SX); TXi; V(SX); proces Xi; goto LXi” .

And you hold your breath, watching the birth of modern computing here in EWD 35.

The rest of the article provides the proof that this mechanism holds for any number of machines.

Edsger Dijkstra – blogger avant la lettre combines deep science with deadpan humor

Dijkstra, Holland’s most influential and remarkable computer scientist, was a blogger avant la lettre.
Her blogged in his EWDs (his initials – Edsger Willem Dijkstra) whatever he wanted to say – could be drafts of scientific papers or trip reports or angry letters.

His EWDs are fun to read. The language is precise but light, and pervaded with beautiful language, metaphors, humorous by-sentences and jokes.

If you can start a very theoretical discussion in this way, you are a genius of language, besides science. Here in EWD 28.

A machine defines (by its very structure) a language, viz. its input language: conversely, the semantic definition of a language specifies a machine that understands it. In other words: machine and language are two faces of one and the same coin. I am going to describe such a coin. I leave it entirely to you to decide which of these two aspects of the subject matter of my talk you think the most important as it is rather ridiculous in both aspects.

Who is going to write the biography of this broadly respected Dutch computer scientist?
Will probably end up kickstarting it myself.