Dijkstra’ Notes On Structures Programming

There are a few big ideas (at the time and still most relevant today) in the text, which is actually a difficult read for being a “a jumping back and forth stream of consciousness” rather than a well-written scholarly article.

It is crucial to understand that he used an imperative low-level machine-oriented language with destructive assignments - just one level up from the assembly language, with arrays as a high-level abstraction.

But the essence of these notes is a programming methodology, and the generalizations he made, some of which turned out to be the fundamental principles, rediscovered by others again and again.

The universal principle (for programming) is that the hierarchical structure of a program should match the hierarchical structure of the problem domain, and should have, ideally, one-to-one correspondence between major concepts (of the domain) and corresponding modules (of the program).

And, yes, we – good programmers – just structure information, simiarly to how mother Nature structures “matter”. This is not just a metaphor, this is the right understanding – we create and manipulate abstract structures made out of binary numbers in a computer memory.

The art of programming is the art of managing complexity. See the Architecture Of Complexity by Simon, which identifies hierarchical structures everywhere.

Barbara Liskov systematized the use of procedural abstraction and data-abstraction, so almost all decisions about implementation details can be postponed (and abstract interfaces being used) and even whole implementations could be changed later, provided that the interface of an ADT is designed first (in a few iterative refinements) and then remain unchained.

The insight about using the smallest possible steps and on simplest decisions (plus the interfaces first manta) is also turned out to be a universal methodology.

It captures the fact that getting familiar with the problem domain, which is absolutely required in any programming task, is also a slow, gradual spiral-shaped process of continuous refinement and getting into all the details.

No wonder all the modern “Agile” nonsense is also spiral-shaped – this shape is universal, and in turn, captures the notion of a iterative convergence, which is a shape of a recursive process, reaching the base case.

The Systematic Program Design - the methodology of Gregor Kiczales, provide a set of explicit rules and repetitive practices for writing code in a disciplined, and, indeed, more systematic way.

Dijkstra got the right intuitions and generalization back then, so owe to him a lot, despite his writing style (mine is way superior LOL). Having the right hierarchical structure, postponement of implementation decisions, and continuous refinement by eventually filling up all the details (going deep “to the size”, all the way down to the language “primitives”) are the universal principles.

Liskov’s ADTs is the way to establish necessary abstraction barriers to make this actually possible, by literally partitioning the concepts and related abstractions into independent orthogonal, reusable “modules”, which contain data-abstractions (types) and the code.

The Functional Programming tradition only re-emphasized the central role of composition and functional pipelining in general, which implies to use just a few universal “patterns” (concatenation, conditionals and recursion for looping).

Modern Domain-Driven Design also added the fundamental principle of using the vocabulary of the problem domain and to rely on domain expert’s interpretation.

Recently at least some use of Monads and related comprehensions and notations, at least for error handling and failure propagation, have been well-established in a well-researched languages, which is just a composition (of “computations”) “behind” a type-system enforced abstraction barrier.

The ideas are: