Programming is old enough now to have a history. Several of them, in fact. There are legends and folktales of programming's past, squabbles over priority of invention, alternate versions of events now known only through written records.
And there is a history to programming paradigms. Now and then, it seems appropriate that this column devote its space to some of those paradigms past, or paradigms lost, that can only be found in the early days of programming.
Sometimes a revolutionary new paradigm will be opposed by the graybeards of the field because it represents a threat to their assumptions, or their values, or their jobs. But sometimes the graybeards enthusiastically embrace the new paradigm--and get it all wrong.
One of the most significant paradigm shifts in programming took place as the result of an invention that we take for granted today: the compiler. Strange, then, that the compiler's inventor remains virtually unknown.
But maybe not so strange, at that. The compiler, which today we would call an unqualified success, wasn't always seen as even a particularly good idea. In fact, at a certain point in the history of programming, it took real courage to advance the idea of compiling programs.
At just this point in programming history, one rash programmer had the temerity to write and promote the first real compiler, and to do so pretty much in the face of one of the legendary figures in computing. This is that story.
In his essay "Programming in America in the 1950s: Some Personal Impressions," John Backus paints a picture of the world BC--that is, before compilers. His perspective is probably uniquely relevant: Not only was Backus actively programming back then, but he led the team that defined the first high-level language, still in use today, Fortran. He understands clearly what the transition from BC to the post-compiler era has meant.
"Programming in the early 1950s was a black art," Backus says, "a private arcane matter involving only a programmer, a problem, a computer, and perhaps a small library of subroutines and a primitive assembly program."
Most of 1950s programmers' time was spent working around the absurd difficulties that the machines forced on them. They had to fit their programs into a tiny data store, overcome bizarre difficulties in getting information in and out, and work with a severely limited and often downright peculiar set of instructions. There were no general algorithms for anything, no system documentation, no system in fact; just the big iron.
That, Backus explains, is what made it so much fun.
Backus and Cuthbert Hurd, who managed computer operations at IBM in the early 1950s, give similar descriptions of the Selective Sequence Electronic Calculator, or SSEC, in service from 1948 to 1952. The SSEC typified the hassles that the 1950 programmer faced. It had a 150-word memory, and programs were read in on any of 66 tape readers, with the tape glued into a closed loop. Backus recalls a mysterious cyclic error that defied diagnosis until someone noticed that one of the intermediate tapes had been glued to form a Möbius strip, so that on every other reading of the tape the entire tape was read backward.
Programming under these rugged conditions made the early programmers feel like bold explorers of a new land. "Programming had a vital frontier enthusiasm," Backus reports, "virtually untainted by either the scholarship or the stuffiness of academia. Recognition in the small programming fraternity was more likely to be accorded for a colorful personality_or the ability to hold a lot of liquor well than it was for an intellectual insight."
It could hardly escape the notice of these programmers that what they were doing was beyond the abilities of the average person, and some programmers began to think of themselves as a breed apart. Programmers of the 1950s, Backus says, "began to regard themselves as members of a priesthood, guarding skills and mysteries far too complex for ordinary mortals." Many programmers, at least as late as 1954, were hostile and derisive toward any plan to make programming accessible to a larger population.
There were not only priests but also high priests in this new computer culture. One of those high priests was Howard Aiken, who designed the first large-scale computer, the Automatic Sequence Control Calculator, or MARK I, which was the predecessor to the SSEC and was actually built by Frank Hamilton at IBM and presented to Harvard University in 1944. By 1946, Aiken and Grace Hopper (known for, among many things, the invention of Cobol) were collaborating on programs in the MARK I's complicated machine language.
"The digital computer was identified in Cambridge [Massachusetts] with Aiken's MARK I computer," pioneering programmer Garrett Birkhoff recalls; and by 1950, Howard Aiken was looked upon with the awe appropriate to a founder. In addition to designing the MARK I, Aiken "had a very great gift for anticipating computer applications." Then too, just Aiken's "colorful personality" inspired a degree of awe; Birkhoff tells stories of table pounding and says that the Harvard faculty committee supposedly empowered to decide how the expensive MARK I should be used "never had any control whatever on anything that [Aiken] did."
There were things called compilers in the early 1950s, but they weren't what we today would call compilers: programs that accept programs written in a human-readable high-level language and generate machine code.
Backus points out that it is hard to read "old" papers on programming--papers written in the early 1950s--because familiar words sometimes had radically different meanings. Legendary programmer Donald Knuth and Luis Pardo make the same point, citing the example that what we now call "statements" were variously referred to in the early 1950s as "formulas," "equations," and "operations."
Backus makes the point specifically with respect to the word "compiler," citing three articles from the early 1950s that used the word compiler in their titles, each with a different meaning, none of which is the modern meaning. Those who did describe something like our modern concept of a compiler used terms like "automatic coding." Backus himself, in his 1954 report that defined the Fortran language, never once used the word compiler.
Maurice Wilkes, who published a paper on one approach to compilation (real-ly macro expansion) in 1952, recalls "I do not think that the term compiler was [by 1954] in general use, although it had in fact been introduced by Grace Hopper." (Actually, Hopper's "compilation" was also what we would today call "macro expansion.") It wasn't until 1956 that the terms "compiler" and "statement" became established.
Not only was the word compiler in common (albeit ill-defined) use, but the concept of a program that could translate human-readable programs into machine code was also completely familiar in the early 1950s. In fact, it dates back to the prehistory of computers, to Charles Babbage, designer of the (never built but valid) Analytical Engine, who wrote about the idea in 1836.
Knuth and Pardo point out that Konrad Zuse, the German computer pioneer whose work was obscured by World War II and then languished in the poverty of post-war Germany, designed a remarkably ambitious language, Plankalkül, in 1945, based on the propositional and predicate calculi. Zuse had every intention of writing what we would today call an interpreter or a compiler for Plankalkül; but, like Babbage, Zuse lacked the resources to make his plan a reality.
Between the invention of the digital computer in the 1940s and the early 1950s, there were a number of attempts at doing at least part of what a compiler does.
In the late 1940s at the Moore School of Electrical Engineering at Pennsylvania, where the ENIAC and EDVAC computers were invented, Herman Goldstine, drawing on suggestions of John von Neumann, Adele Goldstine, and Arthur Banks, mapped out a high-level approach to representing programs. It was highly visual and led not to a high-level language and a compiler, but to the concept of flowcharts.
Haskell Curry, at the Naval Ordnance Laboratory in Silver Spring, Maryland, did some theoretical work on algorithms for converting general algebraic expressions into machine code for a computer at about this same time.
Meanwhile, in Switzerland, Heinz Rutishauser described compilers for hypothetical computers, and Corrado Böhm even defined a compiler in its own language. But these were not compilers for implemented languages on real machines.
The first high-level language, using the term loosely, actually to be implemented was the Short Code, or short-order code, originally suggested in the late 1940s by John Mauchly, the co-inventor of the ENIAC computer, and implemented on various machines in the late '40s and early '50s. But the Short Code was an interpreted language, and very simple.
Of these attempts, none was both successful and ambitious, and none was particularly popular with the programming priesthood.
There was a great deal of resistance to the invention of the compiler, and it wasn't all a matter of the priesthood trying to keep programming obscure, although that was a factor.
Much of the resistance had to do with perfectly legitimate efficiency concerns: specifically, the fact that attempts to produce automatic machine-code generation from high-level languages were so pitifully inefficient. The generated code ran slower and took more memory, which was the greatest sin imaginable in those days, when you couldn't just plug in some cheap RAM. Needing more memory basically meant that you needed a different computer.
Approaches to the problem of automatic programming, as compiler writing was sometimes called, were two:
Most took the approach of starting from what was easy, or at least possible, to implement. The limitations of the hardware and the expense of computer time were so great that these efforts just didn't go very far.
Zuse, on the other hand, had designed an impressive, powerful, general-purpose modern language. In doing so he placed himself so far ahead of the hardware that his plans were impractical. (Some of Zuse's innovations were later implemented in the specification for the language Algol.)
It took years for the hardware to reach the point where the two approaches could converge; where a meaningfully powerful high-level language could be implemented via a true compiler that could generate machine code fast enough, and code that ran fast enough, to be useful.
The first real compiler, in Don Knuth's judgement, was invented at Fort Halstead, the Royal Armaments Research Establishment, in 1952. It was a real compiler in the sense that:
When Glennie wrote AUTOCODE, there was already a tool for generating machine code for machines like the MARK I, a tool created by none other than the designer of the MARK I, the legendary and, um, colorful Howard Aiken. Aiken's approach differed from Glennie's in at least one significant detail: Aiken's approach was a piece of hardware.
AUTOCODE was being used on the MARK I at Manchester, England in September, 1952. Five months later, Glennie gave a lecture on compilation at Cambridge University, in which he explained his reasons for writing the compiler.
"The difficulty of programming has become the main difficulty in the use of machines," Glennie said. "Aiken has expressed the opinion that the solution of this difficulty may be sought by building a coding machine, and indeed he has constructed one."
And then Glennie made his heresy apparent: "There is no need to build a special machine for coding, since the computer itself, being general purpose, should be used."
Not "could be used," but "should be used." Take that, Howard Aiken.
The story could end here, with the brave programmer challenging the establishment and bringing in the new age of compiled programs. But history isn't that simple.
AUTOCODE may have been the first true compiler, but it was still very close to machine language. This allowed it to generate code that was, by Glennie's estimate, 90 percent as efficient as human-written machine code; but even if that was accurate, it wasn't enough for the programmers of the time, who needed to squeeze every cycle out of the machines. AUTOCODE was used, but not for the most important work, and it had little direct influence on programming at Manchester or elsewhere. It would take another four years and the invention of a more ambitious and efficient compiler to convince the programming priesthood that compilers were the wave of the future.
Between January and November, 1954, John Backus and a small group of programmers worked on and produced a specification for a new language. That was Fortran. Their effort "was met with the usual indifference and skepticism of the priesthood," Backus says. This despite the fact that the first Fortran compiler embodied a level of optimization of object code not to be seen in compilers again until the late 1960s, including identifying unnecessary code, moving calculations outside loops, and register-usage optimization based on expected frequency of execution of various parts of the program.
By this time the legitimate efficiency concerns had become less relevant. It was clear to Backus that the old paradigm had to go and that compilers were necessary for the advancement of the state of the art in programming. But it wasn't yet clear to everyone. "There was little awareness even as late as 1955 and 1956," Backus says, "that programming methods of that era were the most time-consuming and costly roadblock to the growth of computing."
And at least as late as 1954 the priesthood was still trying to keep programming obscure, or at least was unwilling to admit that it could be made less obscure. But things were changing. Programmer John Carr delivered a lecture that year in which he categorized programmers into the primitives, who believed that all instructions should be written in octal, and the space cadets, "who saw themselves as pioneers of a new age," Wilkes recalls. Wilkes immediately enrolled himself as a space cadet.
Not everyone did. Wilkes tells a poignant story about computing legend Alan Turing. Watching Turing lecture at a blackboard one day, Wilkes became terribly confused. All Turing was doing was multiplying two numbers together to illustrate a point about checking a program, but Wilkes couldn't follow his math at all. The rest of the audience seemed equally puzzled.
Finally Wilkes realized that Turing had written the decimal numbers backward, with the least significant digit on the left, and hadn't bothered to mention the fact to his audience. He wasn't trying to be cute, Wilkes, insists, "It was simply that he could not appreciate that a trivial matter of that kind could affect anybody's understanding one way or the other." It was a perfect example of the primitive mindset.
Turing, Wilkes sadly concludes, would have been on the side of the primitives. Ironic, considering the paradigm shift that Turing himself was responsible for. In fact, we should consider that paradigm shift, because it is a fascinating story.
Sounds like a good topic for a future "Programming Paradigms" column.
A History of Computing in the Twentieth Century. N. Metropolis, J. Howlett, and Gian-Carlo Rota, eds. San Diego, CA: Academic Press, 1980.
The First Twenty Years: 1966--1985. Reading, MA: Addison-Wesley, 1987.
Cortada, James M. An Annotated Bibliography on the History of Data Processing. Westport, CT: Greenwood Press, 1983.
Heims, Steve J. Mathematics to the Technologies of Life and Death. Cambridge, MA: MIT Press, 1980.
Hodges, Andrew. Alan Turing: The Enigma. New York, NY:Simon and Schuster, 1983.
Toole, Betty. Ada, The Enchantress of Numbers. Mill Valley, CA: Strawberry Press, 1992.
Copyright © 1995, Dr. Dobb's JournalParadigm Shifts
Before Compilers
Compilers and "Compilers"
False Starts
The First Real Compiler
The compiler was called AUTOCODE, the first of many programs during the 1950s to bear that name, but who actually gets the credit for inventing AUTOCODE is a little murky. Knuth's detective work leads him to the conclusion that the inventor was one Alick E. Glennie, a programmer at Fort Halstead.Primitives versus Space Cadets
Sources