Mathematics and reasoning by analogy

Dated: 

June 1972

Although he was a theoretical physicist by education, Dijkstra had been exposed to his mother's mathematical thinking during most of his teens. This observation helps explain why he continued to seek general mathematical arguments in his 1972 `Notes on Structured Programming' [2, Chapter 1].

We have already seen that in 1961 Dijkstra explained why it is important to have a small number of general language constructs. A decade later, in his `Notes on Structured Programming', Dijkstra put emphasis on “the effort to establish a few, well-chosen sequencing constructs in programming”. Examples of sequencing constructs are:

  • concatenation (;)
  • selection (if ... then ... else ...)
  • repetition (while ... do ...).

According to Dijkstra, a theorem for which several pages full of conditions have to be satisfied is not a convenient tool to use, “as all conditions have to be verified whenever the theorem is appealed to”. Generality reflected by a small number of conditions is a necessary requirement for practical applicability. Dijkstra used Pythagoras's Theorem in one of his many attempts to get this point across.

In Euclidean geometry, Pythagoras' Theorem holds for any three points A, B, and C such that through A and C a straight line can be drawn orthogonal to a straight line through B and C. How many mathematicians appreciate that the theorem remains applicable when some or all of the points A, B, and C coincide? Yet this seems largely responsible for the convenience with which Pythagoras' Theorem can be used. [2, p.3]

Avoiding case distinctions leads to an increase in clarity and “clarity has pronounced quantitative aspects, a fact many mathematicians, curiously enough, seem to be unaware of”. The many mathematicians were mostly close colleagues of Dijkstra in Eindhoven, colleagues with PhDs in mathematics. Dijkstra made clear, as he did in many of his writings, that he was not one of them.

In the 1976 book Structured Progamming: Analysis, Dijkstra was reported to have made an analogy between triangles & circles in classical geometry on the one hand and sequencing constructs in programming on the other hand [1, p.42]. Dijkstra openly wondered why mathematicians abundantly use triangles & circles in plane geometry, even though they do not satisfy all their needs. The answer, Dijkstra said, lies in that they provide a great number of general theorems like Pythagoras's Theorem. Therefore, the mathematician can use those results reliably. Likewise, in programming “we wish to stick to a limited set of sequencing primitives”. The few sequencing primitives “are to programming what the triangles and circles are to plane geometry.” [1, p.42]

Dijkstra furthermore relied on the same analogy with mathematics in order to advocate another important idea in his `Notes on Structured Programming': the clear-cut distinction between what an operation does and how it works.

There is a strong analogy between using a named operation in a program regardless of “how it works” and using a theorem regardless of how it has been proved. [2, p.11, my emphasis]

This separation of concerns between what and how was already several years old. Recall that already in 1953 Dijkstra had reasoned along these lines when writing the programming manual for the ARRA II machine. While Dijkstra elaborated on what the ARRA II would offer to the user, his colleagues in Amsterdam (Blaauw, Loopstra, Scholten) built the machine. They were concerned with how the machine would offer the functionality that Dijkstra was putting in writing. In his `Notes on Structured Programming', Dijkstra alluded to his prior work in Amsterdam:

There is also an abstraction involved in naming an operation and using it on account of “what it does” while completely disregarding “how it works”. (In the same way one should state that a programming manual describes an abstract machine: the specific piece of hardware delivered by the manufacturer is nothing but a — usually imperfect! — mechanical model of this abstract machine.) [2, p.11]

 

Finally, let me note that the above text is posted on August 6th, 2012. That's exactly 10 years after Dijkstra left our digital world for a more elegant one.

 

[1] Structured Programming: Analysis. Infotech International Limited, Maidenhead, 1976.

[2] O.-J. Dahl, E.W. Dijkstra, and C.A.R. Hoare. Structured Programming. Academic Press, London - New York - San Francisco, 1972.

Tags: