It's the implementation, dummy!


late 1971 -- early 1972

The transition from an informal problem to a formal specification is what Dijkstra in later years misgivingly called `the Pleasantness Problem' and which Naur discusses at length in Section 14 of Pluralism in Software Engineering: Turing Award Winner Peter Naur Explains. The subsequent transition, which Dijkstra took more seriously, goes from a specification to a program.

The relation between a specification and a program is similar to the relation between an abstraction and an implementation. I will now elaborate on the latter relation and I refer to Dijkstra's EWD 317: `On a methodology of design' for further details.

Consider a machine, Dijkstra says, that has a very funny adder: each integer addition takes one microsecond except when the sum formed happens to be a prime multiple of 7. In this latter case the addition takes sufficiently long that you, the programmer, cannot afford to ignore this awkward machine specific property. As a result, you try to avoid the exceptional additions as much as possible in your computations. To do so, you are forced to reason about the specific values of each integer variable in your program. This stands in sharp contrast to the ideal case where the value of an integer variable in a program need not be specified when reasoning about the program.

The fault, Dijkstra says, lies in the implementation, not in the abstraction. In his words:

[W]hen a vital abstraction is denied to a user, I call the implementation inadequate. [EWD317, p.5]

Likewise, consider a machine that does not provide dynamic stack management; that is, a machine that denies the user the vital abstraction of not having to distinguish between recursive procedures and non-recursive procedures. Then it is the machine that is inadequate and not the abstraction. In other words, keep the abstraction and wait for the better machine to be built in the near future. That's exactly how Dijkstra thought during the early 1960s, as elaborated on in my paper `Dijkstra's Rallying Cry for Generalization: the Advent of the Recursive Procedure, late 1950s -- early 1960s'.



It is very true and very sad.

Dear Edgar,

It is very true that, "...keep the abstraction and wait for the better machine..."
It is very sad that, our present day coward programmers (at least they are not courageous like Prof. Dr. Dijkstra), first try to see what a machine can do, and then try to do what they wish, being very much loyal to the metalic-machine. It is only because of the practice we have, "Read 'Users Manual' before using this machine." I have seen people who have become mentally handicapped after spending a lot of time in programming after reading a specified document. They, neither could think of any abstraction, not they could understand one.

Srinivas Nayak

A very controversial topic

Dear E.G.,
by choosing the hardware's ability to manage a stack -- and consequently the programmer's need to distinguish between recursive and non recursive code, you choose a very controversial example to make your point. In fact, GPGPU cores do not currently have a stack, nor they support recursive functions, but they are a prominent kind of architecture in the high-performance computing community.

Moreover, there is an entire current of hardware architects who argue that technological limits (the frequency wall and the power wall) are forcing programmers to give up more and more architectural comforts. Some of them seem to fall in the category of "vital abstractions".

Should I conclude that we shall ignore these machines and wait them to grow till they support these abstractions?