A Trace Table from 1843: Ada Lovelace's Program

1 This section tells how a program was written for a machine that was never finished, and how its writer showed every step of it in a table so that anyone could check it by hand.

A Machine on Paper

2 In 1834, the English mathematician Charles Babbage began to design a machine he called the Analytical Engine. It was meant to do arithmetic by itself, following instructions punched into cards, an idea Babbage borrowed from the Jacquard loom, which used punched cards to weave patterns into cloth. The design had two main parts. The Store held numbers, and a separate part called the Mill did the arithmetic on them. Historians at the Computer History Museum note that the design could also repeat a set of steps and choose between paths, although Babbage himself never used those words.

3 The Analytical Engine was never completed. When Babbage died in 1871, only a small experimental piece of it was being built. For that reason, nobody in the 1800s could run a program on it, and nobody could find out whether a program worked by watching the machine.

Lovelace's Notes

4 In October 1842, a military engineer from Turin named Menabrea published an article describing Babbage's engine in a Geneva journal, the Bibliothèque Universelle de Genève. Ada Lovelace, who was born Augusta Ada Byron in 1815, translated the article into English and added extensive notes of her own, which she finished by the end of July 1843. She signed the notes with her initials instead of her full name. According to the Computer History Museum, the notes included the first published description of a stepwise sequence of operations, and Lovelace is often referred to as the first programmer.

5 In her last note, Note G, Lovelace set out, in her words, to follow "the steps through which the engine could compute the Numbers of Bernoulli," a series of numbers that, as Menabrea wrote, "frequently present themselves in calculations." Instead of describing the steps only in sentences, she laid them out in a large table. The Computer History Museum labels that table a Bernoulli number "algorithm." An algorithm is a set of steps, in order, that solves a problem.

A Trace Table from 1843

6 Lovelace's table works much like a trace table. Each line of the table is one operation, such as a multiplication or a division. The numbers in the Store were kept in columns that she called Variables, and an earlier note explains that the letter V was used "for the purpose of convenient reference to any column." She wrote that the table gives "a complete simultaneous view of all the successive changes" the columns go through. In other words, a reader can see what every column holds after every operation.

7 The writer Stephen Wolfram, who studied the table in 2015, called it "effectively the execution trace of a program that runs for 25 steps (plus a loop)." An execution trace is a record of each step a program takes and the values it leaves behind. Wolfram also pointed out a bug, or mistake, in the trace: on line 4, "the fraction is upside down," so one division was written in the wrong order. Because every step was written out, a reader can find the exact line where the mistake happens. Figure 1 shows Babbage's Store and Mill, Lovelace's table with its upside-down line, and a trace table today.

Checking a Program by Hand

8 A trace table is still the way to check a program without running it. Each line that stores a value is written as a new row, and the row shows every box after that line runs. The short program below divides two numbers, the kind of step Lovelace's line 4 took.

1a ← 13
2b ← 4
3c ← a ÷ b
4show c

3

9 Line 3 stores 13 ÷ 4, which is 3, because whole-number division keeps only the whole part. If the division were written upside down, as b ÷ a, a trace would show c holding 0, since 4 ÷ 13 has a whole part of 0. A loop also has to decide when to stop, and that decision is a question whose answer is true or false. Today's question asks how anyone could check a program that cannot be run, and a hand trace is one answer to it. On today's bench, each job uses the week's skills together: boxes, trace tables, ÷ and rem, and questions that are true or false.

Summary

10 Babbage designed the Analytical Engine starting in 1834 but never finished it, so no program for it could be run. In 1843, Lovelace published a program for the engine as a table that shows every column after every operation, much like a trace table. That table let a careful reader check each step of her algorithm by hand, and it still shows the line of the bug, where one division was written upside down. Tracing by hand is how a programmer checks a program without running it.

Sources: Computer History Museum, Ada Lovelace and The Engines (The Babbage Engine); Menabrea, Sketch of the Analytical Engine Invented by Charles Babbage, with notes by Lovelace (1842–1843; Fourmilab text); Wolfram, Untangling the Tale of Ada Lovelace (2015); course repository, Bench Basics B10 job data (2026).