It Began with Babbage (57 page)

35
. For collections of his papers and essays on his different interests in computer science, see, for example, D. E. Knuth. (1992).
Literate programming
. Stanford, CA: Center for the Study of Language and Information; D. E. Knuth. (1996).
Selected papers on computer science
. Stanford, CA: Center for the Study of Language and Information.

36
. Knuth, 1968, op cit., pp. 1–2.

37
.
Oxford English Dictionary
(2nd ed.). Available:
http://www.oed.com

38
. Minsky, op cit., p. 106.

39
. Knuth, 1968, op cit., pp. 8–9.

40
. Knuth, 1968, op cit., pp. 4–6.

41
. D. E. Knuth. (1966). Letter to the editor.
Communications of the ACM, 9
, 654.

42
. Knuth, 1968, op cit., p. 7.

43
. See, for example, A. V. Aho, J. E. Hopcroft & J. D. Ullman. (1974).
The design and analysis of algorithms
(pp. 2–5). Reading, MA: Addison-Wesley.

44
. J. Hartmanis & R. E. Stearns. (1965). On the computational complexity of algorithms.
Transactions of the American Mathematical Society, 117
, 285–306; P. M. Lewis, II, R. E. Sterns, & J. Hartmanis. (1965). Memory bounds for recognition of context-free and context-sensitive languages.
Conference Record, IEEE 6th Annual Symposia on Switching Circuit Theory and Logic Design
, 191–202.

45
.
Oxford English Dictionary
(2nd ed). Available:
http://www.oed.com

46
. Ibid.

47
. Ibid.

48
. Ibid.

49
. A. Padegs. (1964). The structure of System/360. Part IV: Channel design considerations.
IBM Systems Journal, 3
, 165–180.

50
. R. F. Rosin. (1969b). Supervisory and monitor systems.
Computing Surveys, 1
, 37–54.

51
. G. H. Mealy, B. I. Witt, & W. A. Clark. (1966). The functional structure of the OS/360.
IBM Systems Journal, 5
, 3–51.

52
. Rosin, 1969b, op cit.

53
. W. Y. Stevens. (1964). The structure of System/360. Part II: System implementation.
IBM Systems Journal, 3
, 136–143.

54
. T. Kilburn, D. B. G. Edwards, M. J. Lanigan, & F. H. Sumner. (1962). One-level storage system.
IRE Transactions on Electronic Computers, EC-11
, 223–235. An earlier but much briefer paper on this same proposal was written by J. Fotheringham. (1961). Dynamic storage allocation in the Atlas computer, including the automatic use of a backing store.
Communications of the ACM, 4
, 435–436.

55
. P. J. Denning. (1970). Virtual memory.
Computing Surveys, 2
, 153–190.

56
. Lavington, op cit.

57
. Ibid., p. 41.

58
. Ibid.

59
. J. K. Iliffe & J. G. Jodeit. (1962). A dynamic storage allocation scheme.
Computer Journal, 5
, 200–209; J. K. Iliffe. (1972).
Basic machine principles
(2nd ed., pp. 25–29). London: Macdonald.

60
. Ibid.

61
. J. B. Dennis. (1965). Segmentation and design of multiprogrammed computer systems.
Journal of the ACM, 12
, 589–602; J. B. Dennis & E. C. Van Horn. (1966). Programming semantics for multiprogrammed computations.
Communication of the ACM, 9
, 143–155; R. C. Daley & J. B. Dennis. (1968). Virtual memory, processes, and sharing in MULTICS.
Communications of the ACM, 11
, 306–312.

62
. E. I. Organick. (1972).
The Multics system: An examination of its structure
. Cambridge, MA: MIT Press.

63
. See, for example, Denning, op cit., for an excellent picture of this subparadigm as it was in 1970.

64
. P. J. Denning. (1968). The working set model of program behavior.
Communications of the ACM, 11
, 323–333; P. J. Denning. (1968). Thrashing: Its causes and prevention.
Proceedings of the AFIPS 1968 Fall Joint Computer Conference, 33
, 915–922.

65
. J. N. Buxton, P. Naur, & B. Randell. (Eds.). (1975).
Software engineering
. New York: Petrocelli (report on two NATO conferences held in Garmisch, Germany [October 1968] and Rome, Italy [October 1969]).

66
. Mealy, Witt, & Clark, op cit.

67
. F. P. Brooks, Jr. (1975).
The mythical man-month: Essays in software engineering
(p. 31). Reading, MA: Addison-Wesley.

68
. F. J. Corbató, J. H. Saltzer, & C. T. Clingen. (1975). Multics: The first seven years. In P. Freeman (Ed.),
Software system principles
(pp. 556–577). Chicago: SRA (see especially p. 560).

69
. T. P. Hughes. (1987). The evolution of large technological systems. In W. E. Bijker, T. P. Hughes, & T. J. Pinch (Eds.),
The social construction of technological systems
(pp. 51–82). Cambridge, MA: MIT Press.

70
. F. J. Corbató. (1963).
The compatible time sharing system
. Cambridge, MA: MIT Press.

71
. For a discussion of memory protection schemes developed in the time frame of the Multics development, see M. V. Wilkes. (1975).
Time sharing computer systems
(3rd ed., pp. 52–83). London: Macdonald & Jane's (original work published 1968).

72
. F. J. Corbató. (1969). PL/I as a tool for system programming.
Datamation, May
, 68–76.

73
. Kuhn, op cit.

IN 1965, THE
Dutch computer scientist Edsger Dijkstra (1930–2002), then professor of mathematics at the Technische Universiteit Eindhoven (THE) in the Netherlands, wrote a paper titled “Programming Considered as a Human Activity” and thereby announced the birth of a movement to which he gave the name
structured programming
a few years later.
¹
Within the next 10 years, the movement would cause so much upheaval in the realm of programming, some came to call it a revolution—the structured programming revolution—and Dijkstra was viewed as its originator.
²

The movement did not precipitate an overthrow of the stored-program computing paradigm as a whole, but insofar as designing and building software systems was a major component of this paradigm, structured programming altered the very essence of the subparadigm in computer science that came to be called
programming methodology
. It brought about a new
mentality
concerning programming and its methodology.

A major part of this mini-revolution actually occurred during the 1970s, but its foundations were laid during the second half of the 1960s by just a handful of publications. And Edsger Dijkstra was the revolutionary-in-chief. He laid out the gospel.

Dijkstra's undergraduate training was in mathematics and physics at the University of Leyden; he went on to obtain a PhD in computing in 1959 from the Mathematics Centrum in the University of Amsterdam and worked there until 1962 before accepting a chair in mathematics at the Technische Universiteit Eindhoven.
³

As a computer scientist, mathematics was a source of inspiration for him, not only in terms of the method-of-proof construction, but also in the mathematician's search for
beauty
in mathematical reasoning. He quoted 19th-century English logician and mathematician George Boole, who spoke of perfectness in mathematical reasoning not just in terms of efficiency, but also in whether a method exhibited “a certain unity and harmony.”
⁴
And he tells us that contrary to the tacit assumption on the part of many that such aesthetic considerations as harmony and elegance were unaffordable luxuries in the hurly-burly world of programming, it actually paid to cultivate elegance. This became a mantra for him.
⁵

So the search for beauty in programming—a
programming aesthetic
—was a prime desideratum for Dijkstra. He did not mention English mathematician Godfrey Harold Hardy (1877–1947) and his haunting book
A Mathematician's Apology
(1940), but he would surely have approved Hardy's assertion that there is no room for ugliness in mathematics.
⁶
There was certainly no place for ugliness in Dijkstra's world of computing.

But Dijkstra's search for a programming aesthetic and the inspiration he took from mathematical reasoning was also prompted by a more practical consideration: mathematical reasoning also served as an exemplar of how the human mind, with its limited cognitive capacity, can deal with complexity.
⁷

Programming, for Dijkstra, was a
human
activity; and as a human, he had to live with his cognitive limits.
⁸
Like Herbert Simon, who recognized the cognitive limits to human rationality (see
Chapter 14
, Section III), Dijkstra understood the limits to the human ability to cope with complexity. Simon circumvented bounded rationality by way of heuristic problem solving. Dijkstra sought for ways out from the messiness of the programming habits of his time. One way was to discipline the use of certain types of statements in programming languages—in particular, the
goto
statement in Algol-like languages. In 1968, he wrote a letter to the editor of the
Communications of the ACM
that was published under the title “Goto Statements Considered Harmful” and in which he proposed that the
goto
statement in Algol-like languages should be simply abolished from all programming languages, for it was an open invitation to make one's program unnecessarily messy, thus unnecessarily complex. The
goto
statement, he pointed out, was entirely avoidable
⁹
This letter proved to be astonishingly controversial because many thought it posed a threat to their very freedom as programmers, a restriction, they believed, on their “first amendment” rights as programmers.

As for large programs such as OS/360 and Multics—he was writing in the first age of massive operating systems (see
Chapter 15
, Section XIII)—their complexity had to be controlled, or rather mastered, in some fashion. The solution lay in the Latin adage
divide et impera
, divide and rule.
¹⁰

But
how
should one divide to rule successfully? If a program is to be decomposed into many parts—or is to be composed
out of
many parts—then decomposition/composition of the parts must be done so that there is a harmonious fit between the parts to achieve a unity of the whole.

There was a corollary to this. Conventional wisdom on programming at the time had it that program
debugging—
weeding out errors (bugs) from a program already written—was a standard operating procedure. Dijkstra had a horror for debugging. Believing the precept “prevention is better than cure,” he also believed that program development should prevent nasty bugs from entering a program
at all
, from the moment its construction begins.
¹¹

So how does one divide and rule? Dijkstra laid out the fundamentals of the gospel that became structured programming in his 1965 paper.

The programmer first identifies and completely specifies the functional requirements of the individual program components—that is, what each component is required to do. He then demonstrates, rigorously, to his own satisfaction, that if components are put together properly, then the program will solve the intended problem. He then implements the individual components independently so that their respective functional requirements are met.
¹²
However, an individual component of the total program may itself be of such complexity that this, in turn, may need to be decomposed into subparts using the same procedure as just mentioned.
¹³

This, then, was the basic manifesto of structured programming, and Dijkstra used this term for the first time in 1969 at the NATO conference on software engineering.
¹⁴
Later, other terms would also be used to refer to this approach:
program development by stepwise refinement
and
top-down programming
.

The division into parts comes with responsibilities. One must ensure that the specifications of the components are such that, collectively, they do the job.
¹⁵
This is where aesthetics—elegance and clarity—enter the picture.
¹⁶
The insides of the components are (not yet) of concern. Indeed, they must
not
be of concern; they may not even have been constructed. The specifications describe the functional behavior of the parts, and the initial task of verification must be concerned only with these functional specifications and their “fitting together” into the desired whole so that, quite independent of the internal details of the components, when put together the components do not interfere with one another. Thus, one can guarantee the correctness of the whole program.
¹⁷

Only when this has been achieved does the programmer proceed to the implementation of the components. This implementation, in effect its internal design and construction, must satisfy the part's exterior, functional specification. If the component is still too complex (for the “small” human brain to cope with), then it must also be divided into subcomponents,
their
functional specifications be established, verification of their working together correctly be guaranteed before constructing the interior of the subcomponents, and so on.

In 1968, Dijkstra published a paper on a multiprogramming system he and a small team of colleagues were then designing and building at THE.
¹⁸
There was no reference to his “Programming Considered as a Human Activity” paper. In fact, there were no references at all, an idiosyncrasy of his style of writing scientific papers more reminiscent of a much earlier style of scientific writing than of his time. But, the paper gives us a sense of how the principle of
divide et impera
was applied in the design of a real operating system. This was not structured programming in the way described earlier; it was not “top down.” Rather, it was an exercise of what, in present-centered language, would be called
bottom-up, hierarchical structured design
. However, the imperative to produce a verifiably correct system as part of the design process was still in evidence. As significantly, Dijkstra claimed that the method presented in the paper could demonstrate the logical correctness (“soundness”) of the multiprogramming system in the design stage itself and thus make its empirical testing much easier after implementation.
¹⁹