I'm pleased to present here a guest post, one that will be of special interest to anyone interested in the history of computer science and women programmers' role in that history.
The First Computer Program
By Greg Alt
With thanks to Kristin King, pair debugger for
this essay
I had been hearing for years about the first programmer, Augusta Ada King, Countess of Lovelace, now commonly referred to as Ada Lovelace. I learned that in 1843 she wrote and published the first computer program, for the never-completed, steam-powered mechanical computer known as the Analytical Engine. It’s an odd coincidence that this was just about a century before the first electronic computers were built and the first programs were actually run in the 1940s.
After I had learned of this, it was many years later that I first saw Lovelace’s program itself. I found it fascinating and I needed to keep digging in until I really understood it. With her program itself in an archaic table-based language and Lovelace’s commentary using unfamiliar technical jargon mixed with her nineteenth century prose, it’s not surprising that few articles touch on it. The vast majority of articles that do touch on her program typically start with Byron, Babbage, and Bernoulli and spend little time on the code itself.
As a software engineer, however, I found her program fascinating. My respect for her grew as I read the insights in her writing on software development in her “Notes.” I became interested in running and debugging her program, and documented my process on the blog “Pair Debugging With Ada Lovelace” [https://pairdebuggingwithlovelace.hashnode.dev/].
“Pair Debugging” in the software industry involves two programmers, sitting at the same keyboard and looking at the same screen while they talk through the fixing of a bug.
With going on two centuries between us, I couldn’t sit down with Lovelace, but I tried to get the next best thing—reading what she has written, both in her famous Notes and her available private letters. While getting her program running, I used her goals and intent as my guide.
Lovelace’s Program
At the age of 17, Lovelace met Charles Babbage and became fascinated with the possibilities of the Analytical Engine that he was in the process of designing. This would have been the first computer, fully mechanical and driven by steam, and with extraordinary capabilities. Its storage was planned to support 40-digit fixed point numbers or more, and as many as 1000 of them. Babbage predicted it could perform one multiply every minute.
A few years later, after a pause in her studies and after Ada and her husband had their third child, Ada was ready to get back to work on her scientific efforts. In 1842, at age 26, she started translating an article by L.F. Menabrea on the Analytical Engine. Charles Babbage had given a talk in Turin, and Menabrea was so impressed that he published a full account in French.
At the time, women were restricted from scientific publications, but it was considered acceptable for Lovelace to publish an English translation of a man’s work. She set to work translating Menabrea’s article for publishing in English.
As a bit of subterfuge, Lovelace added a series of “Notes” to the translation, signed with just her initials. These “Notes” dwarfed Menabrea’s translated text both in length and in scope.
Lovelace's program is encoded in the table accompanying her famous “Note G”, as published in 1843. The title summarizes the purpose of the program: “computation by the Engine of the Numbers of Bernoulli.” This, of course, refers to Charles Babbage’s planned Analytical Engine.
The “Numbers of Bernoulli” are a series of rational numbers that come up a lot in mathematical theory. They are useful and make some calculations easier, such as the sum of powers, and they are slow to calculate by hand and well-suited to a computer. Lovelace chose this “rather complicated example” of computing Bernoulli numbers because it was a fresh topic being discussed by mathematicians of the day. Showing that such a complicated calculation could be carried out automatically, and accurately, by a steam-powered machine would concretely show the value of the Analytical Engine.
The source code language was a table, first hand drawn and then typeset for publication. Bold horizontal lines between rows had semantic meaning, as did the English text for the loop. Variables had both subscripts and superscripts and two dimensional mathematical notation was used.
Her stated goal was “computing the Numbers to an indefinite extent, from the very beginning,” and “without having been worked out by human head & hands first.”
Running and Debugging the Program
It is a bit of a conundrum to talk about a program satisfying goals if the computer it was designed for was never built. All programs have bugs, and running your code for the first time always gives you new thoughts about how it could be improved. For this reason, I consider my investigation to be a bit speculative and subjective, even as I have tried to keep it concrete and objective. All programs require some modifications after they are first written. Sometimes those changes might be extensive rewrites, and sometimes they are more minor adjustments.
My intent has been to focus on the most minimal adjustments needed to satisfy Lovelace’s goals and intent as written in her own words.
As I’ve methodically walked through this process, I’ve shown that her program can be made to satisfy all of these goals with minimal adjustments:
"Compute the [Bernoulli] Numbers"
- "to an indefinite extent"
- "from the very beginning"
- "without having been worked out by human head & hands first"
Before starting the process, I simplified her program for the purpose of understanding it and found that it looked a lot like modern-day assembly code. It includes variables, conditional branching, and loops – all features of non-trivial programs.
Next, I transcribed her program as-published into a non-simplified spreadsheet and then performed an automated transliteration of the first six columns of the numbered rows in the table into legal C code. Then I used an online debugger to see how it worked. Aside from the lack of fire and steam, this is much like how an operator might run a program on an Analytical Engine.
Then I set to work fixing the bugs, and found that it could meet all four goals with minor adjustments, which I describe in my blog.
Along the way I’ve appreciated getting a better understanding of her program and her thoughts around it and around programming in general. Researching this one program has, in turn, brought to my attention its place and Ada Lovelace’s place amongst other notable programmers and hardware designers from her time through to the birth of the computer revolution in the 1940s.
Seemingly simple questions like “what is a computer?” and “what is a program?” took on complex significance as I dug into the details of the work of my other heroes including Charles Babbage, Grace Hopper, and Alan Turing, among others.
Is it the First Computer Program?
Before asking whether Lovelace’s Note G is the first computer program, we need to define a computer and a computer program.
What is a Computer?
My blog has a more thorough answer to this question, but here are a few key points that differentiate a computer from a simpler device.
Programmable means that you can give the computer one set of instructions and it will carry them out. If you want the computer to do something entirely different, you can give it a different set of instructions and it will carry those out as well. This allows an extreme amount of power and flexibility. There will always be a finite number of possibilities for a program of a given size, but even with just 100 instructions, that number might as well be infinite.
General-purpose means that it’s not limited to solving one kind of problem. It’s related to programmability in that a large enough set of operations are made available and the programmer can choose to arrange them as they see fit.
Turing-complete can be thought of as having a powerful enough instruction set to allow it to be equivalent to any other computer. This distinction largely ignores speed and resources. Early computers were very slow and had few resources in modern terms, but a program written for a modern computer could still be adapted to run on an early Turing-complete computer. In practice, what this means is that the computer supports a conditional branch. At runtime, if some condition is found to be true, the computer jumps to one sequence of instructions. If the condition is false, it runs another. It doesn’t sound like much, but this unlocks a universe of possible programs that are otherwise completely out of reach for a non-Turing-complete computer.
What is a Computer Program?
The intuitive and sloppy definition of a computer program is “a set of instructions for a computer.” But here are two important questions.
Does the Program Require a Turing-Complete Computer?
A set of instructions for a computer can be trivial or complex. As an example, many modern computers have a “NOP instruction, short for “no operation.” And it does exactly that – nothing. The most trivial program would be a sheet of paper with “NOP” written on it. This program might run on a Turing-complete Windows laptop, but the program itself doesn’t intrinsically use enough features to require a Turing-complete computer.
A Turing-complete computer doesn’t require a
lot of possible instructions, as complex behavior can be built up from a
surprisingly small set. For example, the 1948 Manchester Baby was
Turing-complete with only these seven instructions supported:
● JMP S - absolute unconditional indirect jump (to location specified in memory S)
● JRP S - relative unconditional jump
● LDN S - load memory into accumulator and negate
● STO S - store accumulator to memory
● SUB S - subtract memory from accumulator
● CMP - skip next instruction if accumulator is negative
● STP - stop
Like my NOP example, a program that consists entirely of STP is too trivial to be taken seriously. On the other hand, a program that consists only of JMP, LDN, STO, SUB, and CMP instructions requires a Turing-complete computer, even being only 5 instructions long.
This leads to a crisp, concrete dividing line between “trivial” and “complex” programs. Look at the set of operations used in a program.
Does it Have to Run?
Talk to any programmer, and they will tell you that their code rarely works perfectly on the first try. Unless it was trivial or they were exceedingly careful, something always goes wrong and something needs to be fixed.
At the same time, a program that is runnable with possibly some minor bugs is still a computer program even before it has been run. “Is it runnable?” is intrinsic to the program, while “has it been run?” is extrinsic.
My Definition of a Computer Program
Putting it all
together, my definition of a computer program is:
A series of instructions to be run on a computer that is programmable, general-purpose, digital, and also Turing-complete. Together the set of instructions is enough to require that the computer be Turing-complete.
Notably, my definition does not require that the computer yet exist and does not require that the program be run.
While this is my preferred definition, it doesn’t make sense to say that one is “correct” and others are simply “wrong.” It would be reasonable to use either a broader or more narrow definition. When thinking about what was the “first computer program,” the answer depends on your definitions. Most definitions are about the same as mine, above, differing only on the question of whether it must first be run to count and whether Turing-completeness is strictly necessary.
Three Other Candidates
If one’s
definition requires that the computer program must have been run, the first
program was written somewhere between 1938 and 1948. This was a period of rapid
innovation, marked by intense competition and collaboration.
Program for the 1938 Z1
One possibility is Z1, built in 1938 by a little-known German inventor named Konrad Zuse. The Z1 ran programs from a punched tape made from celluloid film. It was driven by an electric motor, but fully mechanical. Mechanical stresses and problems with synchronization meant that it couldn’t run reliably for more than a few minutes. That was probably long enough, though, to run a short test program, if not reliably. None of Zuse’s computers were Turing-complete until 1950.
Program for the 1945 ENIAC
If one’s definition requires that the program must run on a Turing-complete computer, that computer would have been ENIAC. ENIAC was Turing-complete and became operational in 1945, one year before the Harvard/IBM computer became Turing-complete. Thus, the first program would have been a test program run on ENIAC before the larger and more famous nuclear physics simulation.
Charles Babbage’s Series L Table #1
If one’s definition does not require that a program be run or use a Turing-complete instruction set, a few of Charles Babbage's “Series L” tables, created between 1836-1840, including #1, would fit. These tables had everything needed to run, but were not Turing-complete. The rest of the tables were missing essential details that would be needed to run at all. One table, though, was an exploration into conditional branches, a required feature for Turing completeness, but the table did not include variables and was therefore not runnable.
The First Computer Program is Ada Lovelace’s 1843 Table
By my definition, a computer program must be runnable but is not required to have been run. It must also require a Turing-complete computer.
Ada Lovelace’s program meets my definition. As my blog series shows, it is runnable with minor adjustments. I also explore in depth its use of conditional branching, a key requirement for Turing-completeness. This means, then, that Ada Lovelace’s 1843 table from Note G is the first computer program.
The First Programming Language
After seeing Lovelace’s Note G table, Babbage’s Series L tables can be seen in a new light. Together, they document the evolution of a programming language. He started by inventing the table language as means to document the hardware processes of the mechanisms of the Analytical Engine itself. When he started to document sequences of operations that might be fed to the engine as cards, he adapted the table language from a hardware process language to a software programming language.
Babbage’s tables from Series L that might be seen as incomplete programs were complete investigations of specific functionality with extraneous details omitted. When the different pieces of notation are used together in Lovelace’s 1843 table, the combination of notations becomes a complete programming language.
Ada Lovelace as the First Programmer
Ada Lovelace had befriended Babbage at a party in 1833, and over the course of many years she learned about his design for the Analytical Engine. The potential excited her. In 1841, she approached Babbage about dedicating herself to work related to the machine, writing:
I am very anxious to talk to you. I will give you a hint on what. It strikes me that at some future time […] my head may be made by you subservient to some of your purposes & plans. If so, if ever I could be worthy or capable of being used by you, my head will be yours. And it is on this that I wish to speak most seriously to you. (p. 140)
She saw her opportunity in 1842, when L.F. Menabrea wrote the article in French about the Analytical Engine. The notes she attached to her translation of the Menabrea article are a fascinating read into her visionary thoughts. As a programmer, though, what I found most interesting in her notes was her example program and all of her concrete discussions about the program and the process of creating it. In a letter from June 26, 1843, she wrote to Babbage:
I want to put in something about Bernoulli’s Numbers, in one of my Notes, as an example of how an implicit function, may be worked out by the engine, without having been worked out by human head & hands first. Give me the necessary data & formulae. (p. 198)
As she requested, Babbage gave her the algebraic formulae—included in Note G as equations numbered (1)-(9). The first three give alternative math for calculating Bernoulli numbers. The remaining six, (4)-(9) derive an equation that can be used as a starting point for her program. This would be the one “algebraic working out” that Babbage supplied and that Lovelace corrected.
From this math, Lovelace methodically developed her program, the table included with and described in great detail in Note G.
Crunch Time Communication
In the course of developing the program, Lovelace stayed in constant communication with Babbage. It’s a bit surprising to learn that mail was delivered multiple times a day, giving them something like a modern experience of rapid back and forth communication through email.
Amidst dozens of letters to Babbage, most of the talk is about various edits to the text, along with frequent confusion about who had the originals for one section or another. Unlike email, they were unfortunately unable to virtually copy attachments.
Lovelace frequently wrote about her hard work on the program and the problems she encountered. Modern programmers would be familiar with getting bogged down and having to explain missed deadlines.
On being delayed by finding new errors:
I have been hard at work all day, intending to send you the Diagram & all, quite complete. Think of my horror then at just discovering that the Table & Diagram, (over which I have been spending infinite patience & pains) are seriously wrong, in one or two points. […] I shall be up betimes tomorrow morning, & finish off the Table & Diagram; so as to send it [to] you by post; (p. 198)
After completing a new draft:
I have worked incessantly, & most successfully, all day. You will admire the Table & Diagram extremely. (p. 199)
After spending the day getting bogged down and
needing to step away from the writing desk to clear one’s mind:
I am in much dismay at having got into so amazing a quagmire and botheration with these Numbers, that I cannot possibly get the thing done today. I have no doubts it will all come out clean enough tomorrow; & I shall send you a parcel up, as early in the day as I can. So do not be uneasy. (Tho’ at this moment I am in a charming state of confusion; but it is that sort of confusion which is of a very bubble nature). I am now going out on horseback. Tant mieux. (p. 207)
As a programmer, I can empathize. Sometimes going off for a walk or a bike ride is exactly what is needed to come back and attack a bug with fresh clarity.
The First Bug
Despite the care she put into the table, it’s not surprising that some bugs persisted. One was especially interesting. The calculation of each Bernoulli number requires negating the result before storing it, but her program omits this operation. It’s more than just a typo. It’s clear that the bug was introduced in the handoff of the math from Babbage to Lovelace. The math that Babbage gave Lovelace was correct, but it left the negation implicit. Lovelace missed this, and in several places in the text of Note G, she talks about simply storing the result without mentioning negation. The bug persists in every step of her process, culminating in her program that preserved it.
To be clear, this is a minor bug, of the sort that programmers make all of the time. It is the kind you find quickly the first time you run. That’s how I found it.
I find it fascinating, though, to see this bug and her thought processes from over 180 years ago frozen in the text like an ancient bug caught in amber.
I set out to pair debug this program with Ada Lovelace so that I could learn how it worked. Finding her bug and helping her run her program as she intended collapsed the 180 years that separated us. We were two programmers, sitting at a writing desk, together. It works! Check it in.
Citations:
Toole, Betty A. Ada, The Enchantress of Numbers: A Selection of the Letters of Lord Byron’s Daughter and Her Description of the First Computer. Mill Valley, California, Strawberry Press. 1992.
Babbage’s Series L: https://collection.sciencemuseumgroup.org.uk/documents/aa110000065
Lovelace’s Notes: https://www.fourmilab.ch/babbage/sketch.html
No comments:
Post a Comment