Code Read 4 - Dijkstra's Notes Part Two

Edsgar W. Dijkstra's "Notes on Structured Programming" is definitely a meal. Its quite a lot for one Code Read. So I broke it into two parts. First, we had the appetizers, now here's the main course.

Program families and evolving software

Dijkstra points out that programs exist in large families of similar programs. When we make changes, we are transforming it from one member of the family to another. By thinking of programs in this way, the importance of a programs structure becomes even more important - because we would like the families to share not just code, but also correctness. If the structure is confusing, the changing the program is difficult because lots of code changes and that code all needs to have its correctness reexamined. A simply structured program tends to require changes in areas that are already well-isolated, thus less code changes, and we need to think less about the correctness of the new code and the code that depends on it. (Similarly, although Dijkstra does not make this point explicitly, a layered structure can make it more clear which areas rely on the changed code, so they can also be verified easily.)

Moreover, Dijkstra points out, from the structure of a program we can understand not just how it works, but also what kind of changes will be easy to make - what other members of its family are close. This stuck me as another important point, since a great deal of time and effort is spent managing and responding to change.

Specifying clarity

Starting to get to the meat of his subject, Dijkstra spends a chapter discussing subroutines, or what has come to be called "structured programming". He sets out to avoid "motherhood" statements that are unobjectionable but hopelessly vague, and to be specific about what makes clear, easy to understand, and easy to modify programming.

Leaving aside his discussions of the fine points programming semantics, he makes several key arguments about subroutines:

• subroutines should not be used to simply shorten code, but rather to create a reliable abstraction
• properly used, they become helpful in limiting the scope of changes, by allowing us to replace the implementation of a subroutine with a different implementation
  
• they help clarify at a particular moment in time which associations are still valid between the state of the machine and the meaning we assign to that state
  
• they allow work to be divided into small units without having to re-invent the wheel for each unit
  

What is most relevant about this for us is not necessarily the application of these ideas to subroutines, but to any software design construct - objects, aspects, models, etc. Many novice programmers get so excited about a particular technique like Object Oriented programming, that the miss the fundamental reasons for using it in the first place - which Dijkstra has helfuly laid bare for us.

Also its important to note that Dijkstra is not describing the "lego-like" building block we'd all like to have, and which we may never get. He never describes having a large library of such objects and simply selecting and combining them to build programs. When he does refer to such "lego-like" tools, he only mentions the most basic of abstractions, things like "integer". And he seems to confine these largely to the realm of predefined hardware and language constructs:

"although these facilities have to be provided in some form or another - providing these facilities falls outside the scope of the programmer's responsibility and also that the programmer will accept any reasonable implementation of them."

In order words, we should not be too picky about our tools, since these tools will probably be equally suited to our task. Although certainly there are cases where this is untrue, the message seems to be that there are general libraries available for the basic things we do as programmers, and that baring specific needs, one will work as well as another. But Dijkstra says nothing about more complex libraries of building blocks - instead he introduces, in his next section, the image of a string of pearls.

The string of pearls

Having built his argument carefully, Dijkstra comes to his grandest image - the layers of abstraction in a program as a string of pearls.

In this metaphor, designing a program becomes a process of creating (at least intellectually) a somewhat larger set of pearls than we need, and then selecting the ones that we will finally use to build our program. Other programs in the same family would use a different subset of pearls, in a different order.

When we need to modify a program, we can replace a pearl, and some of those below it, with a new set of pearls. Again, Dijkstra is not simple enough to suggest that one could simply replace one pearl with another, and that everything would work out. Instead, he saw that along the string there are various concepts used by the pearls, and many of which will be shared among different pearls. Changing those concepts will require replacing all of the pearls that use that concept.

By looking at how many concepts span which pearls, one can get a sense of the complexity of a particular program (or design) - more complex program will have "thicker" and "longer" weaves of concepts. Such thick programs will be more difficult to create, understand, and debug, because they require more mental work for us to understand all of the pieces woven together. Thinner weaves are easier to understand, since there is less to hold in our heads at one time.

Dijkstra's image is not the image of massively reusable bits of code, but rather a way to think of the complexity of a program - almost to measure it - and a way to compare alternatives. And the central concept of this, as in almost all of Dijkstra's writings that we've read in Code Reads is this - simplicity is brought about by isolation of details through abstraction.

Its quite an important idea. Almost every development in software design techniques since then has been an attempt to provide this isolation and abstraction. And it has been very successful, in that we now regularly write working programs tens or hundred of times as long and complex as what Dijkstra was talking about. Of course, sometimes they do not work, so lets see what comes next in Code Reads.