O-J Dahl, EW Dijkstra, and CAR Hoare
Academic Press, 1972
ISBN 0122005503 (boards)
Buy it from Amazon.com (commission paid)
Buy it from Amazon.co.uk (commission paid)
"A survey of more than 1,000 college professors identified the 38 most influential papers in computer science, and Dijkstra authored five of them."
(Peter Chen, IEEE Software)
This little book is remarkably still in print - remarkably, because in this age of so-called Internet Speed development, software people often don't even think of looking at any book over 2 years old. One is tempted to recall remarks such as George Santayana's (1863-1952) much-misquoted:
“Those who cannot remember the past are condemned to repeat it,”
(Life of Reason, “Reason in Common Sense,” ch. 12, 1905-6).
Of course the very title 'Structured Programming' sounds dated, like miniskirts or crinolines; other fashions have come and gone; but bear with it. This isn't a book whose ideas are restricted to block-structured code, or even to software.
Dahl, Dijkstra, and Hoare's writings in this book offer a snapshot of how the software world looked in 1972, a scant three decades ago, yet an age away in terms of technology. One snapshot can only portray a tiny bit of their thinking, yet they were clearly grappling with the great issues of the day, and - surprise, surprise - the issues remain. Listen to Dijkstra:
Let us restrict, for a moment, our attention to the hardware and let us wonder to what extent one can convince oneself of its being properlyl constructed. Some years ago a machine was installed on the premises of my University; in its documentation it was stated that it contained, among many other things, circuitry for the fixed-point multiplication of two 27-bit integers. A legitimate question seems to be: "Is this multiplier correct, is it performing according to the specifications?".
The naive answer to this is: "Well, the number of different multiplications this multiplier is claimed to perform correctly is finite, viz. 254, so let us try them all." But, reasonable as this answer may seem, it is not, for although a single multiplication took only some tens of microseconds, the total time needed for this finite set of multiplications would add up to more than 10,000 years! We must conclude that exhaustive testing, even of a single component such as a multiplier, is entirely out of the question.
Was that too bland for you? Now comes the famous Dijkstra sting in the tail:
(Testing a complete computer on the same basis would imply the established correct processing of all possible programs!)
I love those parentheses. Evidently he's thinking about rather deeper problems than just how to arrange your while loops. He goes on about correctness for a little while, and then:
Recalling that our true concern is with really large programs, we observe ... if the chance of correctness of an individual component equals p, the chance of correctness of a whole program, composed of N such components, is something likeP = pN.
As N will be very large, p should be very, very close to 1 if we desire P to differ significantly from zero!
This should sound like rather bad news even today, and it is a safe bet that people will still be struggling with its implications (whether they know it or not) for the next three decades too.
Dijkstra also discusses 'Program Families', that we more commonly call 'reuse' in software, and 'product-line engineering' otherwise; on understanding programs, that we perhaps tend to call 'maintainability', and other topics to do with program correctness, that we might group under 'formal methods'. The point of course is that these issues are timeless, and all too often the domain only of what Prof. PJ Brown calls 'academic pussyfoots'; whereas they concern us all.
With this much introduction, I can now be brief. Tony Hoare looks at the need for abstraction and high-level languages, data types and data structuring (which led to today's Objects that group together data and the allowed operations on those data), and the way that the choice of representations influences data manipulation. The list of references is delightfully short and comprehensible, including Dijkstra, Knuth, and Wirth - 'Giants ruled the Earth in Those Days'.
The third and final chapter has Dahl and Hoare talking about hierarchical program structures, which actually talks about classes and objects, making this certainly one of the earliest books to do so. Trees, lists, search algorithms, simulation, shortest-path, and scheduling are also illustrated with detailed examples.
So, no, this classic is not just something old and clunky, but a stimulating insight into some great minds, and into some of the deepest and probably most permanent challenges in systems engineering.
© Ian Alexander, September 2002