What did the Ada Lovelace program actually do?

The founding episode of Microsoft is one of the most famous in computer history. In 1975, Paul Allen flew to Albuquerque to demonstrate the BASIC interpreter, which he and Bill Gates wrote for the Altair microcomputer. Since they did not have a working Altair computer, they checked their interpreter using an emulator written by them that was run on a Harvard computer system. The emulator was based only on the published specifications of the Intel 8080 processor. When Allen finally launched the interpreter on a real Altair computer — in front of the person who they hoped would buy their software — he didn't even know if the program would work. She earned. The following month, Allen and Gates officially founded the new company.

More than a hundred years before the BASIC interpreter Allen and Gates, Ada Lovelace wrote and published a computer program. She also wrote a program for the computer, which she knew only by description. But its program, unlike the BASIC interpreter, was never executed, because the computer for which it was written was never built.

The Lovelace program is often called the world's first computer program. But not everyone agrees that it should be so called. Heritage Lovelace is one of the most hotly debated topics of computer history. Walter Isaacson wrote that a dispute over the extent and merit of her contributions is of "minor academic importance." Inevitably, the debate is fueled by the fact that Lovelace was a woman. Historians cited all kinds of evidence to prove that the honors provided to her correspond to the case, or, conversely, are not deserved. But they spend much less time explaining the technical details of her published work, which is insulting, since it is the technical details that represent the most interesting part of this story. Who would not be interested to know how the program, written in 1843, should work?

Honestly, the Lovelace program is hard to explain to the townsfolk. But it is the complexity of her program that makes her so remarkable. She deserves to be called the first programmer, or not, her program was recorded with such accuracy that surpassed everything that happened before. She carefully thought out which operations can be combined into groups that can be repeated - thus inventing a cycle. She realized how important it is to monitor the state of changing variables, and came up with a record reflecting these changes. I, as a programmer, am amazed at how much Lovelace’s work resembles the experience of writing software today.

So let's take a closer look at the Lovelace program. She designed it to calculate Bernoulli numbers.. To understand what it is, you need to go back a couple of millennia to the past, to the beginning of one of the oldest problems of mathematics.

Degree sums

The Pythagoreans lived on the shores of the Mediterranean and worshiped numbers. One of their hobbies was making triangles from pebbles.



One stone, followed by a row of two stones, together form a triangle of three stones. Add another row of three stones and you get a triangle of six stones. This procedure can be continued, each time adding a row with the number of stones increasing by one. The six-row triangle contains 21 stones. And how many stones will be in the triangle of 423 rows?

The Pythagoreans were looking for a way to calculate the sum of the next row without summing up:

1 + 2 + 3 + ⋯ + n

As a result, they realized that if you place two triangles of the same size next to each other so that they form a rectangle, you can find the area of ​​the rectangle and divide it into two to get the number of stones in each of the triangles:

1 + 2 + 3 + + n = n (n + 1) / 2

Archimedes studied a similar problem. He was interested in the following sequence:

1 ² + ^{2 2} +3 ² + ⋯ + n ²

It can be imagined as a column of larger squares (consisting of tiny cubes), standing one on another in the form of a pyramid. Archimedes wanted to find out if there is an easy way to tell how many cubes it will take to create a pyramid with, say, 423 levels. He wrote down the solution of the problem, which also admits a geometric interpretation.



Three pyramids can be made together so that they form a rectangular prism, from one end of which there is a small ledge in one cube high. This protrusion is a triangle, subject to the same rules as the Pythagorean stone triangles. Therefore, the volume of the whole figure is given by the following equation:

3 (1 ² + ^{2 2} +3 ² + ⋯ + n ² ) = (n + 1) n ² + (1 + 2 + 3 + ⋯ + n)

Substituting the Pythagorean equation for the sum of the first n integers, and after performing some algebraic operations, we get:

1 ² + ^{2 2} +3 ² + ⋯ + n ² = n (n + 1) (2n + 1) / 6

In 499, the Indian mathematician and astronomerAryabhata published his work, known as Aryabhatiya, in which the formula for calculating the sum of cubes was given:

1 ³ +2 ³ +3 ³ + ⋯ + n ³ = (1 + 2 + 3 + + n) ²

Formula for the sum of the first n positive integers in the fourth degree were published only 500 years later.

By this time you might have a question - is there any universal method for calculating the sum of the first n integers raised to the power of k? Mathematicians were also interested in this. Johan Faulhaber, a German mathematician, slightly advanced on numerology, was able to derive formulas for sums of integers up to the 17th degree, publishing them in 1631. But it took him many years, and he did not give a general solution.Blaise Pascal finally came up with a generalized method in 1665, which, it is true, depended on counting the sum of integers raised to the previous degrees. For example, to calculate the sum of the first n positive integers raised to the 6th degree, you first had to learn how to calculate the sum of the first n positive integers raised to the 5th degree.

A more practical generalized solution was given in the posthumously published work Swiss mathematician Jacob Bernoulli , who died in 1705. Bernoulli began by deriving formulas for calculating the sums of the first n positive integers raised to the first, second, third, and fourth degrees. He wrote them down as polynomials:

1 + 2 + 3 + ⋯ + n = 1 / 2n ² + 1 / 2n

1 ² + 2² +3 ² + ⋯ + n ² = 1 / 3n ³ + 1 / 2n ² + 1 / 6n

1 ³ +2 ³ +3 ³ + ⋯ + n ³ = 1 / 4n ⁴ + 1 / 2n ³ + 1 / 4n ²

Using Pascal's triangle, Bernoulli realized that these polynomials follow predictable patterns. In fact, Bernoulli divided the coefficients of each term into two factors, one of which he could determine using the Pascal triangle, and the other to deduce from an interesting property, according to which all coefficients in the polynomial were equal to one in total. It was easy to understand which exhibitor to put in each member, since they also followed predictable patterns. The multipliers of each coefficient, which had to be calculated according to the “sum equals one” rule, formed a sequence, which became known as the Bernoulli numbers.

Bernoulli's discovery did not mean that the sum of the first n positive integers raised to any power could now be calculated trivially. To calculate the sum of the first n positive integers raised to the power of k, it was necessary to find out all the Bernoulli numbers up to the k-th. And each Bernoulli number could be counted, only knowing all the previous ones. But it was incomparably easier to calculate the long sequence of Bernoulli numbers than to calculate each sum of numbers raised to the power, therefore the Bernoulli discovery was a big breakthrough for mathematics.

Babbage

Charles Babbage was born in 1791, almost a hundred years after Bernoulli’s death. I always had such an idea about him that he developed, but did not build a mechanical computer. But I never really understood how this computer should work. As it turned out, the basic ideas are quite easy to understand. The Lovelace program was supposed to work on one of the Babbage machines, so we need to take another small digression and talk about how these machines worked.

Babbage invented two separate mechanical computing machines. The first was called the differential machine . Before the invention of pocket calculators, people relied on logarithmic tables.to count the product of large numbers. Large logarithmic tables are not so difficult to compile in principle, but the number of calculations required to compile them led to the fact that during the days of Babbage they often contained errors. Annoyed by this, Babbage decided to create a machine capable of mechanically creating tables of logarithms, avoiding errors.

The difference machine was not a computer, because it only knew how to add and subtract. She used the method invented by the French mathematician Gaspard de Prony , who broke the process of building the table into small steps. These steps required only addition and subtraction, which meant that a small army of people who did not have the ability to mathematics could be used to build the table. Method de Prony, known as the methoddivided differences could be used to compile a table for any polynomial. And polynomials could already be used for an approximate calculation of logarithmic and trigonometric functions.

To imagine how this process worked, consider the following simple polynomial function:

y = x ² +1

The method of divided differences finds the difference between successive values ​​of y for different values ​​of x. Then there are differences between these differences, and then, perhaps, still differences between the last differences, until a constant difference appears. This difference can then be used to obtain the next value of the polynomial through addition.

Since this polynomial has only the second degree, we can find a constant difference after just two columns of differences:

x	y	Diff 1	Diff 2
one	2
2	five	3
3	ten	five	2
four	17	7	2
five	?	?	2
...	...	...	...

Now, knowing that the constant difference is 2, we can find the value of y, when x is 5, with one addition. By adding 2 and 7, the last value in the Diff 1 column, we get 9. By adding 9 and 17, the last value in the y column, we get 26 — our answer.

The difference Babbage machine for each differential column of the table had its own physical column with gears. Each gear represented a decimal position, and the entire column represented a decimal number. The differential machine had eight columns with gears, so it could compile tables of polynomials up to the seventh power. The columns were initially set to values ​​that coincide with an early series of a table of differences, calculated in advance. The operator then had to rotate the crankshaft, which caused the constant difference to move around the car when the values ​​stored in each of the columns were added to the next.

Babbage managed to build a small part of the difference machine and use it to demonstrate his ideas at parties. But, even having spent so much money that they would have been enough to build two large warships, he could not complete his car. At the beginning of the XVIII century, Babbage did not find anyone who could make the necessary number of gears with the necessary accuracy. The working version of the differential machine was built only in the 1990s, after the appearance of high-precision machine tools.


As a result, Babbage lost interest in the differential machine, realizing that you can create a much more powerful and flexible machine. His " analytical machine " today is known as the Babbage mechanical computer. The analytical machine was based on the same gear columns as the differential, but if the latter had only eight columns, then the analytical one should have several hundreds. An analytical machine could be programmed using punched cards like a jacquard loom.and she could divide and multiply, and not just add and subtract. To perform one of these operations, a part of the machine called “the mill” would rebuild itself into the desired configuration, read the operands from other columns used for data storage, and then write the result to other columns.

Babbage called it an analytical machine, because it was powerful enough to do something resembling mathematical analysis. A difference machine could produce polynomial tables, but an analytic machine could calculate, for example, the polynomial multiplication coefficients of another expression. It was an amazing machine, but the British government made the wise decision to reject a request for its funding. Therefore, Babbage went abroad to Italy to try to find support there.

Translator's Notes

In Turin, Babbage met an Italian engineer and future Prime Minister Luigi Federico Menabrea. He convinced Menabrea to write an overview of the capabilities of the analytic machine. In 1842, Menabrea published a paper on this topic in French. The following year, Lovelace published a translation of the work of Menabrea into English.

Lovelace, then known as Ada Byron, met Babbage at a party in 1833, when she was 17 and he was 41. Lovelace was struck by the difference Babbage machine. But she was able to figure out how she works, because in her childhood she was actively trained in mathematics. Her mother, Anabella Milbank, decided that the solid mathematical basis of her daughter’s education would ward off her wild and romantic nature, which her father, Lord Byron, had, the famous poet. After meeting in 1833, Lovelace and Babbage remained in the general social circle and often corresponded.

Ada Byron married William King in 1835. King later became the Earl of Lovelace, as a result of which Ada became the Countess of Lovelace. And even having given birth to three children, she continued to study mathematics, taking as a teacher Augustus de Morgan, who discovered the laws of Morgan . Lovelace immediately recognized the potential of the analytical machine, and readily agreed to work with him to advance this idea. Her friend suggested that she translate the work of Menabrea to an English audience.

The paper contained a brief description of the operation of the difference machine, and then it was shown how much the analytical machine would have surpassed it. The analytical machine had to be so powerful that it could "form the result of multiplying two numbers, each of which consists of twenty characters, in just three minutes." Menabreyd gave other examples of the machine's capabilities, showing how it would solve a simple system of linear equations and decompose the result of multiplying two binomials. In both cases, Menabrea presented what Lovelace called “development diagrams,” describing the sequence of operations necessary to calculate the correct answer. These were programs, in the same sense in which the Lovelace program was a program, and they were published a year before its work. But as we will see Menabrea programs were just examples of the possible. They were all trivial in the sense that they did not require any branching or cycles.

Lovelace added a few notes to her translation of the work of Menabrea, and in sum they were longer than the original work. It was there that she made her main contribution to the calculations. In note A, which Lovelace did to the original description of the analytic machine, she explained in detail, and sometimes lyrically, that this machine could perform arbitrary mathematical operations. She foresaw that a machine like this would not be limited to working with numbers, and would be able to handle any objects “whose mutual fundamental interaction can be expressed by the abstract science of operations, and which can be adapted to operational records and the mechanism of the machine.” She added that someday such a machine would be able, for example, to compose music. Such foresight was all the more remarkable that Menabrea himself considered this machine only a tool for automating “lengthy and boring computations” that would free up the intellectual possibilities of brilliant scientists for more advanced research. Lovelace's wonderful foresight, shown in note A, is one of the main reasons why we honor her today.

Another famous note, note G. Lovelace, starts it, arguing that, despite the impressive possibilities, it cannot be said that the analytical machine “thinks”. It is this note that Alan Turing will later call the Ada Lovelace Objection. Still, Lovelace continues, the machine is capable of amazing things. To demonstrate the ability to handle more complex tasks, Lovelace offered her program for calculating Bernoulli numbers.

Its full text, in the form of an extended “development chart”, the format of which Lovelace describes in Note D, can be found here . This is essentially a list of operations indicated by mathematical symbols. Babbage or Lovelace does not seem to go so far as to develop a set of operating codes for the analytic machine.

Although Lovelace described the method of calculating the complete sequence of Bernoulli numbers to a certain limit, the program she cited showed only one step of this process. She counted the number she called B7, known to modern mathematicians, as the eighth number of Bernoulli. Therefore, its program solved the following equation:

B7 = −1 (A ₀ + B ₁ A ₁ + B ₃ A ₃ + B ₅ A ₅ )

Here each member represents a coefficient in a polynomial formula for the sum of integers raised to a certain power. Here we are talking about the eighth degree, since the eighth number of Bernoulli first appears in the formula for the sum of positive integers raised to the eighth degree. The numbers B and A represent two kinds of multipliers discovered by Bernoulli. Numbers from B1 to B7 are different Bernoulli numbers, numbered according to Lovelace. The numbers from A0 to A5 are multipliers of coefficients that Bernoulli could calculate using the Pascal triangle. The values ​​of A0, A1 and A3 are given below. Here n denotes the index of the Bernoulli number in a sequence of odd Bernoulli numbers starting from the first. In the Lovelace program, n = 4.

A ₀ = −1 / 2⋅ (2n − 1) / (2n + 1)

A ₁ = 2n / 2

A ₃ = 2n (2n − 1) (2n − 2) / (2⋅3⋅4)

A ₅ = 2n (2n − 1) (2n − 2) (2n − 3) (2n − 4) / (2⋅ 3⋅4⋅5⋅6)

I translated the Lovelace program into C , and so it will probably be easier to read. First, her program calculates A ₀ and the result of the multiplication B ₁ A ₁ . Then a cycle begins, repeated twice, to calculate B ₃ A ₃ and B ₅ A ₅ , since they are counted according to the same scheme. After counting each multiplication, the result is added to the previous ones, so by the end of the program we get the full amount.

Obviously, translation to C cannot be an exact reproduction of the Lovelace program. It declares variables on the stack, and Lovelace variables were more like registers. But it makes more obvious the most prophetic part of the Lovelace program. The C program has two while loops, one inside the other. The Lovelace program had no while loops, but it grouped the operations, and described in a note why they should be repeated. The variable v10 from the original program and translated into C, works as a counter, decreasing with each pass of the cycle - this design is familiar to every programmer. In general, apart from the abundance of variables with obscure names, the C program does not look like something unfamiliar.

It is also worth noting that translating the Lovelace program to C was not very difficult, thanks to one detail in its diagram. Unlike the Menabrea tables, there is a column in its table “a sign of a change in the value of a variable”, thanks to which it is much easier to track the state change. It adds a superscript to each variable to indicate the sequential values ​​stored in them. Index 2, for example, means that the value used is the second value assigned to a variable from the beginning of the program.

First programmer?

After I translated the Lovelace program into C, I was able to run it on my computer. To my disappointment, the result was wrong. After searching for errors, I finally realized that the problem was not with my code - the bug was contained in the original program!

In the “development diagram”, Lovelace writes in the fourth operation v5 / v4. But it will be correct v4 / v5. This error could appear when printing, and not in Lovelace. Anyway, this is the oldest computer bug. I was surprised that I spent about ten minutes searching for the very first bug in history.

Jim Randal, another blogger who translated Lovelace to Python, also noted this division bug and two other problems. What do small mistakes in Ada Lovelace's published program tell us? Perhaps that she tried to write not just a demonstration, but a real program. After all, you can not write something other than toy programs, avoiding errors?

In one of the articles of Wikipedia, it is written that Lovelace was the first to publish a “complex program”. Perhaps this is the way to perceive its achievement. Menabrea in his work published the “development charts” a year before the publication of the Lovelace translation. Babbage has also written more than twenty programs that have never been published. Therefore, it is not quite correct to write that Lovelace wrote or published the first program, although you can always argue about what to consider as a program. And still, the Lovelace program is far ahead of everything that was published before it. In the longest program, Menabrea had 11 operations and there were no cycles and branches. The Lovelace program had 25 operations and a nested loop (and, therefore, a branch). Menabrea at the end of his work wrote the following:

After the machine is built, the difficulties will be reduced to making cards; but since this is just a translation of algebraic formulas, it will be quite simple to reassign them to some worker through some simple notation.

Neither Babbage nor Menabrea was particularly interested in using an analytical machine for tasks that go beyond the limits of mathematical problems, which prompted Babbage to create computers. Lovelace realized that the analytical machine was capable of much more than Babbage and Menabrea could imagine. Lovelace also caught on the fact that “making cards” will not become a mechanical work, and that this can be done badly or well. It is difficult to evaluate this without understanding its program from note G, and not seeing how much concern it showed during its development. But, having done this, you can agree that Lovelace, even without being the very first programmer, was the first programmer to deserve this name.