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
