It Began with Babbage

by Dasgupta, Subrata

  13. Wilkes, 1951, op cit., p. 59.

  14. Ibid.

  15. Ibid.

  16. For an example of random logic in the design of a computer’s control unit, see, for example, S. Dasgupta. (1989). Computer architecture: A modern synthesis. Volume I: Foundations (pp. 170–173). New York: Wiley.

  17. Wilkes, op cit., p. 59.

  18. For a discussion of empirical and conceptual problems in the natural sciences, see L. Laudan. (1977). Progress and its problems (pp. 11–69). Los Angeles, CA: University of California Press. For a discussion of empirical versus conceptual problems in the design of artificial sciences, see S. Dasgupta. (2009). Design theory and computer science (pp. 13–30). Cambridge, UK: Cambridge University Press (original work published 1991).

  19. M. V. Wilkes. (1984). The origins and development of microprogramming. Presented at a public lecture at the University of Louisiana, Lafayette, Louisiana, October 29.

  20. M.. V. Wilkes in an interview with S. Dasgupta, December 19, 1991, Olivetti Research Laboratory, Cambridge, UK.

  21. S. Dasgupta. (2011). “Contesting (Simonton’s) blind variation, selective retention theory of creativity. Creativity Research Journal, 23, 2, 166–182 (see especially pp. 170–172).

  22. A. Koestler. (1964). The act of creation. London: Hutchinson.

  23. Wilkes, 1986, op cit., p. 117.

  24. M. V. Wilkes. (1981). The design of a control unit: Reflections on reading Babbage’s notebooks. Annals of the History of Computing, 3, 116–120 (see especially p. 118).

  25. Wilkes, 1985, op cit., p. 178.

  26. Thus, a microinstruction actually encoded multiple operations called microoperations; the execution of each microoperation caused a specific control signal to be issued.

  27. S. Dasgupta. (1979). The organization of microprogram stores. ACM Computing Surveys, 11, 39–65.

  28. M. V. Wilkes & J. B. Stringer. (1953). Microprogramming and the design of the control circuits in an electronic digital computer. Proceedings of the Cambridge Philosophical Society, 49, 230–238.

  29. Wilkes, 1985, op cit., pp. 184–185.

  30. M. V. Wilkes, W. Renwick, & D. J. Wheeler. (1958). The design of a control unit of an electronic digital computer. Proceedings of the Institution of Electrical Engineers, 105, 121–128.

  31. M. V. Wilkes. (1992). EDSAC 2. IEEE Annals of the History of Computing, 14, 49–56 (see especially p. 52).

  32. Wilkes, 1985, op cit., p. 187.

  33. R. Moreau. (1984). The computer comes of age (pp. 56–58). Cambridge, MA: MIT Press.

  34. Wilkes, 1985, op cit., p. 185.

  35. Moreau, op cit., p. 68.

  36. Wilkes, 1985, op cit., p. 185.

  37. Ibid.

  38. Ibid., p. 188.

  39. M. V. Wilkes. (1969). The growth of interest in microprogramming: A literature survey. Computing Surveys, 1, 139–145.

  40. Ibid.

  41. Wilkes, 1992, op cit., p. 56.

  42. Wilkes, 1951, op cit., p. 60.

  43. Dasgupta, 1979, op cit.

  44. Dasgupta, 1989, op cit., pp. 214–227.

  45. R. F. Rosin, G. Frieder, & R. H. Eckhouse, Jr. (1972). An environment for research in microprogramming and emulation. Communication of the ACM, 15, 248–260; A. B. Salisbury. (1976). Microprogrammable computer architectures. New York: Elsevier; E. I. Organick & J. A. Hinds. (1978). Interpreting machines: Architecture and programming of the B1700/B1800 series. New York: North-Holland.

  13

  Language Games

  I

  IT MUST HAVE been entirely coincidental that two remarkable linguistic movements both occurred during the mid 1950s—one in the realm of natural language, the other in the domain of the artificial; the one brought about largely by a young linguist named Noam Chomsky (1928–), the other initiated by a new breed of scientists whom we may call language designers; the one affecting linguistics so strongly that it would be deemed a scientific revolution, the other creating a class of abstract artifacts called programming languages and also enlarging quite dramatically the emerging paradigm that would later be called computer science.

  As we will see, these two linguistic movements intersected in a curious sort of way. In particular, we will see how an aspect of Chomskyan linguistics influenced computer scientists far more profoundly than it influenced linguists. But first things first: concerning the nature of the class of abstract artifacts called programming languages.

  II

  There is no doubt that those who were embroiled in the design of the earliest programmable computers also meditated on a certain goal: to make the task of programming a computer as natural as possible from the human point of view. Stepping back a century, we recall that Ada, Countess of Lovelace specified the computation of Bernoulli numbers in an abstract notation far removed from the gears, levers, ratchets, and cams of the Analytical Engine (see Chapter 2, Section VIII). We have seen in the works of Herman Goldstine and John von Neumann in the United States, and David Wheeler in England that, even as the first stored-program computers were coming into being, efforts were being made to achieve the goal just mentioned. Indeed, a more precise statement of this goal was in evidence: to compose computer programs in a more abstract form than in the machine’s “native” language.

  The challenge here was twofold: to describe the program (or algorithm) in such a language that other humans could comprehend, without knowing much about the computer for which the program was written—in other words, a language that allowed communication between the writer of the program and other (human) readers—and also to communicate the program to the machine in such fashion that the latter could execute the program with minimal human intervention.

  The flow diagram invented by Goldstine and von Neumann was a pictorial kind of language that realized this twofold goal only in part, because a flow diagram, although appropriate for human–human communication, could not serve as a means of human–machine communication without further human intervention. The assembly language Wheeler created for the EDSAC facilitated the goal of automatic human–machine communication. A program written in this assembly language could be transformed automatically into EDSAC machine language using another program, the “assembler” (see Chapter 9, Section VI). However, Wheeler’s language was specific to the EDSAC, as were all subsequent assembly languages. To write programs in the EDSAC assembly language, one must be intimately familiar with the EDSAC.

  III

  Even before Goldstine and von Neumann began constructing the flow diagram notation, tucked away in a small village in the Alps, German computer designer Konrad Zuse was developing a programming language that, as would emerge much later, was well ahead of its time.

  The year was 1945. The war in Europe had finally ended, if not the one in the Pacific. Zuse was in his retreat along with the Z4 computer, the only one of his wartime inventions to survive (see Chapter 5, Section XI). Germany was in ruins. It was not the time to pursue practical work in computing. In any case, the Z4 was barely working.1 Instead, Zuse turned to the design of a language he called Plankalkül (or program calculus) that could serve to specify computational problems using some general symbolic notation.2

  Zuse’s 1945 manuscript on Plankalkül and its use in constructing programs was never published at the time. It lay ignored or unnoticed until 1972, when it appeared in a German journal. That same year, two German scientists, Friedrich Bauer and H. Wössner brought Plankalkül to the attention of the English reading world with an article in the silver jubilee issue of Communications of the ACM.3

  Thus, Zuse could claim priority once more. In building the Z3, which became operational in 1941, he was the first to have built a fully operational, general-purpose, programmable computer (see Chapter 5, Section XI); in developing Plankalkül in 1945, he invented what was arguably the first programming language that was not tied to a specific computer. Indeed, as Zuse would reflect years later, there was no computer in 1945 that conformed to the principles laid out in Plankalkü
l.4

  In present-centered language, Plankalkül was a machine-independent programming language or (also in present-centered language) a high-level programming language. His goal in designing Plankalkül, as stated by Zuse in his 1945 manuscript, was “to provide a purely formal description of any computational procedure.”5

  Of course, what Turing had offered in his 1936 Entscheidungproblem paper was a formal way of specifying computation. Zuse’s goal was far more practical: to describe formally algorithms that did not reference any specific physical computer and yet assumed an underlying, implicit, abstract “model” of a real computer that, in principle, could interpret and execute algorithms described in this language. Zuse had undoubtedly grasped, almost a decade before others, an essential characteristic of a programming language.

  Plankalkül was never carried to the stage at which it could be implemented—the second goal of a programming language, to enable human–machine communication. As such, it remained a “paper language,” one that met the desire for human–human communication of algorithms. It illustrated the kinds of features a generalized, machine-independent programming language should have.

  Perhaps most impressive was Zuse’s recognition of the concept that would later be called data structures or information structures—abstract representations of the various kinds of data objects with which algorithms have to deal. There were features in Plankalkül that could define a range of data structures, beginning with the most primitive, the “bit” or Boolean data (having values 1 or 0), spanning integers and real numbers, and extending to “composite” data objects such bit sequences, arrays of arbitrary dimensions, and “records,” comprised of two or more composite data objects that would allow, for example, paired items such as names and dates of birth to be specified as a single data object.6 These sorts of data structures anticipated by almost a decade features that would become established aspects in later and more mature programming languages.

  One of Zuse’s seemingly innocuous, but in fact quite profound, inventions was the concept of the “assignment” operation; he used the symbol => to denote this.7 An assignment, say, of the form

  Z + 1 => Z

  where Z is an integer variable, in Plankalkül notation signified that the “current” integer value of Z is “augmented” by one—that is, the current value of Z is incremented by one and this becomes Z’s “new” value. The assignment operator => thus indicates a process involving both a direction and a temporal flow of data. As Donald Knuth and Luis Trabb Pardo, in their extensive survey of early programming languages pointed out, an operator such as the assignment was quite unknown in mathematics—indeed, it signified “a distinct break between computer science thinking and mathematical thinking.”8

  Zuse recognized the necessity of “conditional commands”9—the ability to decide to go one way or another during the course of computation on the presence or absence of a condition. Thus, Plankalkül allowed for the specification (in present-centered language) of “If cond Then action” statements; if the state of computation at that point in the program is such that cond is true, then perform action; otherwise, proceed to the next statement in the program. The language also provided for “iteration”; until such-and-such condition is met, continue to execute such-and-such sequence of statements repetitively.10 And, quite remarkably, Zuse provided for one program to be specified and be invoked from another program—this, at least 2 years before John Mauchly conceived the idea of the subroutine in general terms, and 4 years before Wheeler invented a concrete mechanism for subroutine programming and activation for the EDSAC (see Chapter 10, Sections IV and V). Indeed, both the “calling” and the “called” programs were expressible in a uniform manner that, later, was termed procedure.11

  To a later eye, the notation Zuse created for Plankalkül would seem clumsy at best, dreadfully opaque at worst. The invention of notation, we will see, will become a contentious issue among later language designers, and Zuse certainly had no antecedents to guide him. But the features denoted by the notation in Plankalkül were unmistakably modern; and insofar as Zuse’s goal was concerned, the language was remarkably comprehensive in its power. The original (1945) manuscript included Plankalkül descriptions of a wide variety of algorithms that, in the words of Knuth and Pardo, were “far more complex than anything written before.”12 There were programs for sorting, performing integer and floating-point arithmetic in binary notation, determining whether a logical (Boolean) formula was syntactically correct, even algorithms for chess moves.13 Bauer and Wösner presented, in their article, Plankalkül programs for the syntax checking of Boolean expressions and one of the chess-playing programs.

  As the saying goes, sometimes an invention is too far ahead of its time and the world is not quite ready for it. Perhaps Plankalkül suffered from this fate.

  IV

  Such early investigators as Wheeler in Cambridge or Goldstine in Princeton did not use the word language. Zuse, hidden away in his village in the Alps, labored on what he called a kalkül—a calculus. Perhaps the earliest explicit use of “language” in the context of programming was in an unpublished report by Arthur Burks in 1951, then at the University of Michigan in An Intermediate Program Language as an Aid in Program Synthesis.14 Burks’s language incorporated features for assignment, conditional branching, and iteration.15

  In 1950, Zuse’s Z4 computer, rebuilt, finally found a home in the Swiss Federal Institute of Technology (ETH) in Zurich, Switzerland.16 Here, Heinz Rutihauser (1918–1970), a Swiss mathematician and numeric analyst, embarked, circa 1951, on what in German he called “automatische rechenplan fertigung” (“automatic machine code generation”). This coheres with the most common term used during the early 1950s: automatic programming—meaning, an environment that allowed the programmer to deploy symbolic notation to specify a program at a level of abstraction higher than that of the “real” machine itself.17

  We see here the emergence of what, in present-centered language, would be called an intermediate or virtual machine more abstract than the actual physical computer. This virtual computer would be programmed in symbolic notation (representing the order code for the virtual machine), and the task of an automatic programming system would be to translate mechanically this virtual machine program into the order code for the real machine. The virtual machine was easier to program than the real machine but the two were closely coupled. Most such systems, during the early 1950s, entailed, or were elaborations of, assembly languages and assemblers, which translated the assembly language programs into the real machine’s “native” language in the manner pioneered by Wheeler in Cambridge for the EDSAC (see Chapter 9, Section VI). The term automatic programming would prevail through the 1950s. In 1954, the Symposium on Automatic Programming for Digital Computers was held in Washington, DC, sponsored by the Office of Naval Research; and in 1960, an annual publication bearing the title Annual Review of Automatic Programming was launched. This publication, with that title, continued until 1994.

  V

  A certain thinking trend was, however, taking shape. This trend was toward abstraction—to move programming away, albeit cautiously, from the physical machine in a direction tending toward what humans found more natural for specifying computations. For those who were concerned with mathematical or scientific computations, this meant abstracting from the physical computer toward mathematical expressions and formulas. This was the reverse of what was previously the case. Beginning with Babbage and Lovelace, the strategy formerly had been to reduce mathematical thought to the level of the machine, to reduce algorithms to machine order code.

  But, by around 1954, this trend was being reversed. There were those who desired to express their programs in mathematical or algebraic notation itself.18 Automatic programming now came to mean the use of programs to translate efficiently algorithmic expressions and formulas stated in a mathematical language into economic machine code.19

  In fact, by 1952, the problem had been recognized as twofold: (a)
to design a mathematical language in which to express computations and (b) to develop a programming system that could translate programs cheaply in such languages into efficient machine code. This was what Corrado Böhm (1923–), an Italian and later a distinguished theoretical computer scientist, set about doing as a graduate student at ETH Zurich in 1950 to 1952. In his doctoral dissertation, Böhm described both a language and a complete translator for that language.20 This was what Halcombe Laning (1920-2012) and N. Zierler set about doing at MIT, where they created a “program for translation of mathematical equations for Whirlwind I.”21 This was what, in England, Alick Glennie (1925–2003) of the Royal Armament Research Establishment desired to do when he designed a system he called AUTOCODE for the Ferranti/Manchester Mark I computer (see Chapter 8, section XIII, for more on the Manchester Mark I; the Ferranti Mark I was the industrial version of the Manchester University Mark I). Glennie—“the unsung hero” in the story of programming languages and automatic programming, according to Knuth and Pardo22—delivered a lecture on AUTOCODE at Cambridge University in February 1953 based on notes he had prepared in December 1952,23 in which he asserted that programming notation must make it easier to make the programming task “comprehensible.”24

  By 1953/1954, the word compiler was being used to mean the kind of process required to translate programs written in algebraic form into machine code.25 Indeed, Glennie’s AUTOCODE system, according to Knuth and Pardo, was the first implemented compiler that was actually used.26

  It was this trend in thinking toward abstraction that led John Backus (1924–2007) and his team at IBM in New York to conceive and develop an automatic programming system around a language he called FORTRAN.