What Did Ada Lovelace's Program Actually Do?
0b10
Two-Bit History
What Did Ada Lovelace's Program Actually Do?
Papers
18 Aug 2018
The story of Microsoft’s founding is one of the most famous episodes in<br>computing history. In 1975, Paul Allen flew out to Albuquerque to demonstrate<br>the BASIC interpreter that he and Bill Gates had written for the Altair<br>microcomputer. Because neither of them had a working Altair, Allen and Gates<br>tested their interpreter using an emulator that they wrote and ran on Harvard’s<br>computer system. The emulator was based on nothing more than the published<br>specifications for the Intel 8080 processor. When Allen finally ran their<br>interpreter on a real Altair—in front of the person he and Gates hoped would<br>buy their software—he had no idea if it would work. But it did. The next month,<br>Allen and Gates officially founded their new company.
Over a century before Allen and Gates wrote their BASIC interpreter, Ada<br>Lovelace wrote and published a computer program. She, too, wrote a program for<br>a computer that had only been described to her. But her program, unlike the<br>Microsoft BASIC interpreter, was never run, because the computer she was<br>targeting was never built.
Lovelace’s program is often called the world’s first computer program. Not<br>everyone agrees that it should be called that. Lovelace’s legacy, it turns out,<br>is one of computing history’s most hotly debated subjects. Walter Isaacson has<br>written that the dispute about the extent and merit of her contributions<br>constitutes a “minor academic specialty.”1 Inevitably, the fact that<br>Lovelace was a woman has made this dispute a charged one. Historians have cited<br>all kinds of primary evidence to argue that the credit given to Lovelace is<br>either appropriate or undeserved. But they seem to spend less time explaining<br>the technical details of her published writing, which is unfortunate, because<br>the technical details are the most fascinating part of the story. Who wouldn’t<br>want to know exactly how a program written in 1843 was supposed to work?
In fairness, Lovelace’s program is not easy to explain to the layperson without<br>some hand-waving. It’s the intricacies of her program, though, that make it so<br>remarkable. Whether or not she ought to be known as “the first programmer,” her<br>program was specified with a degree of rigor that far surpassed anything that<br>came before. She thought carefully about how operations could be organized into<br>groups that could be repeated, thereby inventing the loop. She realized how<br>important it was to track the state of variables as they changed, introducing a<br>notation to illustrate those changes. As a programmer myself, I’m startled to<br>see how much of what Lovelace was doing resembles the experience of writing<br>software today.
So let’s take a closer look at Lovelace’s program. She designed it to calculate<br>the Bernoulli numbers. To understand what those are, we have to go back a<br>couple millennia to the genesis of one of mathematics’ oldest problems.
Sums of Powers
The Pythagoreans lived on the shores of the Mediterranean and worshiped<br>numbers. One of their pastimes was making triangles out of pebbles.
One pebble followed by a row of two pebbles makes a triangle<br>containing three pebbles. Add another row of three pebbles and you get a<br>triangle containing six pebbles. You can continue like this, each time adding a<br>row with one more pebble in it than the previous row. A triangle with six rows<br>contains 21 pebbles. But how many pebbles does a triangle with 423 rows<br>contain?
What the Pythagoreans were looking for was a way to calculate the following<br>without doing all the addition:
\[1 + 2 + 3 + \cdots + n\]
They eventually realized that, if you place two triangles of the same size up<br>against each other so that they form a rectangle, you can find the area of the<br>rectangle and divide by two to get the number of pebbles in each of the<br>triangles:
\[1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}\]
Archimedes later explored a similar problem. He was interested in the following<br>series:
\[1^2 + 2^2 + 3^2 + \cdots + n^2\]
You might visualize this series by imagining a stack of progressively larger<br>squares (made out of tiny cubes), one on top of the other, forming a pyramid.<br>Archimedes wanted to know if there was an easy way to tell how many cubes would<br>be needed to construct a pyramid with, say, 423 levels. He recorded a solution<br>that also permits a geometrical interpretation.2
Three pyramids can be fit together to form a rectangular prism with a tiny,<br>one-cube-high extrusion at one end. That little extrusion happens to be a<br>triangle that obeys the same rules that the Pythagoreans used to make their<br>pebble triangles. (This video<br>might be a more helpful explanation of what I mean.) So the volume of the whole<br>shape is given by the following equation:
\[3(1^2 + 2^2 + 3^2 + \cdots + n^2) = (n+1)n^2 + (1 + 2 + 3 + \cdots + n)\]
By substituting the Pythagorean equation for the sum of the first n<br>integers and doing some...