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.

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.

He continues,

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.

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

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.
(BTW for the historians amongst us, the 1620 was considered the first “mini-computer”.)

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 criticize 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.