It Began with Babbage (48 page)

58
. For example, as illustrated by the title of the article of R. L. Glass. (1969). An elementary discussion of compiler/interpreter writing.
Computing Surveys, 1
, 55–77; and by the title of the book by J. S. Rohl. (1975).
An introduction to compiler writing
. London: Macdonald and Jane's.

59
. Backus, op cit., p. 34.

60
.
Optimization
was, of course, an optimistic term because
optimal
—meaning, the very
best
—is usually an unattainable, if laudable, goal. In the language of compilers,
optimization
really meant a systematic process of
improving
the object program within the practical limits of time for compilation and the cognitive limits of the compiler writer.

61
. Backus, op cit., pp. 34–36.

62
. P. B. Sheridan. (1959). The arithmetic translator-compiler of the IBM FORTRAN automatic coding system.
Communication of the ACM, 2
, 9–21.

63
. J. Cocke & J. T. Schwartz. (1970).
Programming languages and their compilers
(pp. 510–515). New York: Courant Institute of Mathematical Sciences.

64
. Hopgood, op cit., pp. 2–3.

65
. G.. M. Hopper. (1981). Keynote address. In Wexelblat (pp. 7–24), op cit., p. 16.

66
. S. Rosen. (1969). Electronic computers: A historical survey.
Computing Surveys 1
, 7–36 (see especially pp. 10–11).

67
. Hopper, op cit., p. 15.

68
. Ibid.

69
. Ibid., p. 16.

70
. Ibid.

71
. Ibid., p. 17.

72
. J.. E. Sammet. (1981a). The early history of COBOL. In Wexelblat (pp. 199–276), op cit., p. 202.

73
. Ibid., pp. 200–201.

74
. Ibid., p. 203.

75
. Ibid., pp. 208–211.

76
. J. E. Sammet. (1981b). An overview of high level languages. In M. C. Yovits (Ed.),
Advances in computers
(Vol. 20, pp. 200–260). New York: Academic Press (see especially pp. 214–215).

77
. Ibid., p. 239.

78
. H.. Rutihauser. (1967).
Description of Algol 60
(pp. 4–6). Berlin: Springer-Verlag; A. J. Perlis. (1981). The American side of the development of Algol. In Wexelblat (pp. 75–91), op cit., p. 78; P. Naur. (1981). The European side of the last phase of the development of Algol 60. In Wexelblat (pp. 92–139), op cit., p. 94.

79
. Perlis, op cit., p. 76.

80
. Ibid., p. 77.

81
. Ibid.

82
. Rutihauser, op cit., pp. 4–5.

83
. Perlis, op cit., p. 77; Rutihauser, op cit., p. 5.

84
. The full group was, from ACM, John Backus, C. Katz, Alan J. Perlis, and Joseph H. Wegstein; and from GAMM, Friedrich L. Bauer, H. Bottenbruch, Heinz Rutihauser, and Klaus Samelson.

85
. Rutihauser, op cit., p. 6.

86
. Ibid.

87
. Ibid.

88
. Perlis, op cit., p. 79.

89
. Originally, in the manner of the naming of other prior languages, the name was written in upper case, ALGOL. Eventually, it became simply Algol.

90
. J. W. Backus, F. L. Bauer, H. Bottenbruch, C. Katz, and A. J. Perlis (Eds.), H. Rutihauser and K. Samelson (Ed.), J. H. Wegstein (1959). Report on the algorithmic language ALGOL.
Numerische Mathematik, 1
, 41–60.

91
. Perlis, op cit., p. 83.

92
. Rutihauser, op cit., p. 7.

93
. Perlis, op cit., p. 84.

94
. Later, the IFIP Congress was renamed the IFIP World Computer Congress.

95
. John W. Backus (USA), Friedrich L. Bauer (West Germany), J. Green (USA), C. Katz (USA), John McCarthy (USA), Peter Naur (Denmark), Alan J. Perlis (USA), Heinz Rutihauser
(Switzerland), Klaus Samelson (West Germany), Bernard Vauquois (France), Joseph.H. Wegstein (USA), Adriaan van Wijngaarden (Holland), and Michael Woodger (Britain).

96
. P. Naur. (Ed.). (1960). Report on the algorithmic language ALGOL 60.
Communications of the ACM, 3
, 299–314.

97
. P. Naur (Ed.) et al. (1962–1963). Revised report on the algorithmic language ALGOL 60.
Numerische Mathematik, 4
, 420–453; see also (1963).
Communications of the ACM, 6
, 1–17; (1962/63).
Computer Journal, 5
, 349–367. This report would be republished in many other places, including as a stand-alone publication. References to the report in our story cites, as source, its appearance as an appendix in Rutihauser, op cit.

98
. K. R. Popper. (1972).
Objective knowledge
. Oxford: Clarendon Press.

99
. J. W. Backus. (1959). The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM Conference. In
Proceedings of the 1st International Conference on Information Processing
(pp. 125–132). London: Butterworth.

100
. Another expansion of BNF is
Backus Naur Form
because Naur, editor of the Algol 60 reports, made slight changes to the original notation, but, more important, made the meta-language widely known by way of the two reports.

101
. Rutihauser, op cit., p. 268.

102
. J. W. Backus, responding to a question about the origins of BNF, Wexelblat, op cit., p. 162.

103
. E. Post. (1943). Formal reductions of the general combinatorial decision problem.
American Journal of Mathematics, 65
, 197–268.

104
. N. Chomsky. (1956). Three models for the description of language. In
Proceedings of the Symposium on Information Theory
(pp. 113–124). Cambridge, MA: MIT.

105
. N. Chomsky. (1957).
Syntactic structures
. The Hague: Mouton.

106
. J. Lyons. (1970).
Chomsky
(p. 9). London: Fontana/Collins.

107
. Chomsky, 1957, op cit., p. 13.

108
. Chomsky, 1956, op cit., p. 114.

109
. Ibid.

110
. Ibid.

111
. Chomsky, 1956, op cit., pp. 116–118; Chomsky, 1957, op cit., pp. 26–33.

112
. Chomsky, 1957, op cit., p. 29.

113
. N. Chomsky. (1959). On certain formal properties of grammar.
Information & Control, 2
, 136–167.

114
. Rutihauser, op cit., p. 274.

115
. See, for example, S. A. Greibach. (1966). The unsolvability of the recognition of linear context free languages.
Journal of the Association for Computing Machinery, 13
, 582–587; S. Ginsburgh. (1966).
The mathematical theory of context free languages
. New York: McGraw-Hill.

116
. R. W. Floyd. (1963). Syntax analysis and operator precedence.
Journal of the Association for Computing Machinery, 10
; T. Kasami. (1965).
An efficient recognition and syntax analysis algorithm for context free languages
. Scientific report no. AFCRL-65–758. Bedford, MA: Air Force Cambridge Research Laboratory; P. Z. Ingermann. (1966).
A syntax-oriented translator
. New York: Academic Press; D. H. Younger. (1967). Recognition and parsing of context-free languages in time
n
²
. Information & Control, 10
, 181–208; J. Earley. (1968).
An efficient context-free parsing algorithm
. PhD dissertation, Carnegie-Mellon University.

117
. Rutihauser, op cit., p. 275.

118
. O.- J. Dahl & K. Nygaard. (1966). SIMULA: An Algol-based simulation language.
Communications of the ACM, 9
, 671–682.

119
. A. van Wijngaarden (ed.), B. J. Mailloux, J. E. L. Peck, C. H. A. Koster. (1969). Report on the algorithmic language ALGOL 68.
Numerische Mathematik, 14
, 79–218.

120
. A. van Wijngaarden, B. J. Mailloux, J. E. L. Peck, C. H. A. Koster, M. Sintsoff, C. H. Lindsay, L. G. L. T. Meerttens, & R. G. Fisker. (1975). Revised report on the algorithmic language ALGOL 68.
Acta Informatica, 5
, 1–234.

121
. J. E. L. Peck. (Ed.). (1971).
ALGOL 68 implementation
. Amsterdam: North-Holland.

122
. J. T. Bonner. (1988).
The evolution of complexity by means of natural selection
. Princeton, NJ: Princeton University Press. See, however, D. W. McShea. (1997). Complexity in evolution: A skeptical assessment.
Philosophica, 59
, 79–112, for an alternative view of the relationship between biological evolution and the evolution of complexity.

123
. S. Dasgupta. (1997). Technology and complexity.
Philosophica, 59
, 113–140.

124
. N. Wirth. (1971). The programming language PASCAL.
Acta Informatica, 1
, 35–63.

125
. B. Randell & L. J. Russell. (1964).
Algol 60 implementation
. New York: Academic Press; E. I. Organick. (1973).
Computer systems organization: The B5700/6700 series
. New York: Academic Press; R. W. Doran. (1979).
Computer architecture: A structured approach
. New York: Academic Press.

126
. K.. E. Iverson. (1981). Transcript of presentation. In Wexelblat (pp. 674–682), op cit., p. 682.

127
. A.. D. Falkoff & K. E. Iverson. (1981). The evolution of APL. In Wexelblat (pp. 661–674), op cit., p. 663.

128
. In January 1972, freshly arrived as a graduate student in computer science at the University of Alberta, Edmonton, Canada, I recall attending a talk by Iverson delivered at the College of Education.

129
. K. E. Iverson. (1980). Notation as a tool of thought (Turing Award lecture).
Communications of the ACM, 23
, 444–465.

130
. K. E. Iverson. (1962).
A programming language
. New York: Wiley.

131
. “Devotees” is the right word. APL commanded a fierce and loyal following the likes of which was rare during the first decade of programming languages.

132
. Iverson, 1981, op cit., p. 675.

133
. F. P. Brooks, Jr. & K. E. Iverson. (1969).
Automatic data processing: System/360 edition
. New York: Wiley.

134
. A. D. Falkoff, K. E. Iverson, & E. H. Sussenguth. (1964). A formal description of System/360.
IBM Systems Journal, 3
, 191–262.

135
. For a survey of this genus as it had developed from the mid 1960s through its first two decades, see S. Dasgupta. (1982). Computer design and description languages. In M. C. Yovits (Ed.),
Advances in computers
(Vol. 21, pp. 91–155). New York: Academic Press.

136
. Falkoff & Iverson, op cit., p. 664.

137
. Ibid., p. 665.

138
. Ibid., p. 666.

139
. A. D. Falkoff & K. E. Iverson. (1966).
APL\360
. White Plains, NY: IBM Corporation; A. D. Falkoff & K. E. Iverson. (1968).
APL\360 user's manual
. White Plains, NY: IBM Corporation.

LET US REWIND
the historical tape to 1945, the year in which John von Neumann wrote his celebrated report on the EDVAC (see
Chapter 9
). That same year, George Polya (1887–1985), a professor of mathematics at Stanford University and, like von Neumann, a Hungarian-American, published a slender book bearing the title
How to Solve It
.
¹

Polya's aim in writing this book was to demonstrate how mathematical problems are
really
solved. The book focused on the kinds of reasoning that go into making discoveries in mathematics—not just “great” discoveries by “great” mathematicians, but the kind a high school mathematics student might make in solving back-of-the-chapter problems.

Polya pointed out that, although a mathematical subject such as Euclidean geometry might seem a rigorous, systematic, deductive science, it is also experimental or inductive.
²
By this he meant that solving mathematical problems involves the same kinds of mental strategies—trial and error, informed guesswork, analogizing, divide and conquer—that attend the empirical or “inductive” sciences. Mathematical problem solving, Polya insisted, involves the use of
heuristics
—an Anglicization of the Greek
heurisko
—meaning, to find. Heuristics, as an adjective, means “serving to discover.”
³

We are often forced to deploy heuristic reasoning when we have no other options. Heuristic reasoning would not be necessary if we have algorithms to solve our problems; heuristics are summoned in the absence of algorithms. And so we seek analogies between the problem at hand and other, more familiar, situations and use the analogy as a guide to solve our problem, or we split a problem into simpler subproblems in the hope this makes the overall task easier, or we summon experience to bear on the problem and apply actions we had taken before with the reasonable expectation that it may help solve the problem, or we apply rules of thumb that have worked before.

The point of heuristics, however, is that they offer promises of solution to certain kinds of problems but
there are no guarantees of success
. As Polya said, heuristic thinking is never considered as final, but rather is provisional or plausible.
⁴

Problem solving, discovering, inventing—great and small, by scientists, inventors, artists, professional practitioners (such as doctors, engineers, designers, architects) or by students or, indeed, by people in the course of their everyday life—have always involved the use of heuristics, although perhaps most people are never conscious of it as a particular method of reasoning, or that it has a name. Like Monsieur Jourdain in the play
Le Bourgeois Gentilhomme
(1670) by the French playwright Molière (1622–1673) who suddenly learned that he had been speaking prose all his life without knowing it, Polya brought to the mathematical reader's attention that he had been using heuristic reasoning all his mathematical life without knowing it.