»In which we study the design of trains

A Parable by Edsger W.Dijkstra, sometime in 1973.

Years ago a railway company was erected and one of its directors -- probably the commercial bloke -- discovered that the initial investments could be reduced significantly if only fifty percent of the cars would be equipped with a toilet, and, therefore, so was decided.

Shortly after the company had started its operations, however, complaints about the toilets came pouring in. An investigation was carried out and revealed that the obvious thing had happened: despite its youth the company was already suffering from internal communication problems, for the director's decision on the toilets had not been transmitted to the shunting yard, where all cars were treated as equivalent, and, as a result, sometimes trains were composed with hardly any toilets at all.

In order to solve the problem, a bit of information was associated with each car, telling whether it was a car with or without a toilet, and the shunting yard was instructed to compose trains with the numbers of cars of both types as equal as possible. It was a complication for the shunting yard, but, once it had been solved, the people responsible for the shunting procedures were quite proud that they could manage it.

When the new shunting procedures had been made effective, however, complaints about the toilets continued. A new investigation was carried out and then it transpired that, although in each train about half the cars had indeed toilets, sometimes trains were composed with nearly all toilets in one half of the train. In order to remedy the situation, new instructions were issued, prescribing that cars with and cars without toilets should alternate. This was a move severe complication for the shunting people, but after some initial grumbling, eventually they managed.

Complaints, however, continued and the reason turned out to be that, as the cars with toilets had their toilet at one of their ends, the distance between two successive toilets in the train could still be nearly three car lengths, and for mothers with children in urgent need -- and perhaps even luggage piled up in the corridors -- this still could lead to disasters. As a result, the cars with toilets got another bit of information attached to them, making them into directed objects, and the new instructions were, that in each train the cars with toilets should have the same orientation. This time, the new instructions for the shunting yard were received with less than enthusiasm, for the number of turntables was hardly sufficient; to be quite fair to the shunting people we must even admit that according to all reasonable standards, the number of turntables was insufficient, and it was only by virtue of the most cunning ingenuity, that they could just manage.

With all toilets equally spaced along the train the company felt confident that now everything was alright, but passengers continued to complain: although no passenger was more than a car length away from the nearest toilet, passengers (in urgent need) did not know in which direction to start their stumbling itinerary along the corridor! To solve this problem, arrows saying "TOILET" were fixed in all corridors, thereby also making the other half of the cars into directed objects that should be properly oriented by the shunting procedure.

When the new instruction reached the shunting yard, they created an atmosphere ranging from despair to revolt: it just couldn't be done! At that critical moment a man whose name has been forgotten and shall never be traced, made the following observation. When each car with a toilet was coupled, from now until eternity, at its toileted end with a car without a toilet, from then onwards the shunting yard, instead of dealing with N directed cars of two types, could deal with N/2 identical units that, to all intents and purposes, could be regarded as symmetrical. And this observation solved all shunting problems at the modest price of, firstly sticking to trains with an even number of cars only -- the few additional cars needed for that could be paid out of the initial savings effected by the commercial bloke! -- and, secondly, slightly cheating with regard to the equal spacing of the toilets. But, after all, who cares about the last three feet?

Although at the time that this story took place, mankind was not blessed yet with automatic computers, our anonymous man who found this solution deserves to be called the world's first competent programmer.

I have told the above story to different audiences. Programmers, as a rule, are delighted by it, and managers, invariably, get more and more annoyed as the story progresses; true mathematicians, however, fail to see the point.

Dijkstra developed the concept of semaphores for inter-process communication. He also described the problem of deadlocks, as eventually retold in the Dining Philosophers Problem.