Coding with Ada: Programming Babbage's Analytical Engine

What is The Analytical Engine

In 1837, Charles Babbage designed a machine. Like any machine of the Victorian era, it would probably consist of a great deal of brass and steam. But this machine wasn’t like any other: it was the first general purpose computer. Or it would have been, had it ever been completed.

If we look back to 1833, Babbage built a prototype of another machine, the Difference Engine, and liked to show it off to people of high society at his parties. However, this was a completely different beast, as it was only good for tabulating the soluion to equations in the form a + bx + cx^2 + ... + hx^7. As Ada Lovelace so eloquently states:

The Analytical Engine, on the contrary, is not merely adapted for tabulating the results of one particular function and of no other, but for developing and tabulating any function whatever. In fact the engine may be described as being the material expression of any indefinite function of any degree of generality and complexity…

The Difference Engine, itself a fairly impressive and complicated piece of gearwork, was nothing compared to the lofty dreams of the Analytical Engine, which had many of the concepts we now recognize as essential to computation, but made of brass. The construction of the Analytical Engine, besides a small proof of concept of a single part, was never even attempted. However, we have notes taken at his lectures and correspondence between him and Ada to tell us how the engine would have worked.

Description of the Engine

The engine would have been a behemoth that required its’ own building to house. In the 1800s it would have had more memory than an IBM 1401, completely represented by geared mechanisms. There are several sections important to this post, detailed below.

The Mill

The Mill is the CPU of the engine, performing the additions and subtractions necessary to carry out operations. Multiplication and Division was possible as a single instruction using hard-coded procedures which carried out the necessary additions and subtractions. It consisted of two ingress axis (where two different numbers were entered) and an egress axis (where the result would appear). There were some prime axis as well, which had different functions for different operations. Additionally, there was a lever which would get flipped during certain operations, such as a subtraction where the result was of a different sign than the first ingress number. This was the mechanism that would determine conditional looping and skipping.

The Store

The Store is the memory of the engine, and it consisted of 1000 columns of 50 gears with the numbers 0 through 9. The amount of data which can be stored in the store is astounding, and as Jon Walker states:

…one wonders what kind of problem Babbage had in mind which would have required 1000 intermediate values to solve.

One can calculate the total memory of the store using the following formula.

log(x^p) = p*log(x)

log((10^50)^1000) = 1000*50*log(10) = 166096.4047

This results in 166kb of memory.

The Card Readers

The Engine had multiple different types of cards: number cards, operation cards, and variable cards. These cards would be fed into the engine in three different stacks, it was unknown how they would end up keeping their order. Through these three types of cards we see all of the functions of a modern programming language: initializing a variable, performing an operation, and storing/reading the result.

Programming the Engine

The Analytical Engine is optimized for math operations, not for arbitrary computation, and thus lacks many built-in types common in modern day programming languages (strings, vectors, lists, etc.). However, since these types are represented by large binary numbers in modern computers anyway, they can be rebuilt in the Analytical Engine with some effort. This allows a machine envisioned to only calculate equations able to do things such as store strings, display graphics, etc.

John Walker has developed an incredibly realistic emulator of the Analytical Engine here. An incredible amount of information has been gathered by him here. I have ported his web emulator to NodeJS in the analytical-engine package, and have developed a language package for the Atom text editor

Patterns

Programming the engine is quite a challenge, and is more akin to programming with assembly language than with a modern programming language. Add to this that the branching of the system relies completely on the Mill’s run up lever, removing from existence the useful conditionals found in many assembly languages such as branch if zero, branch if positive, etc.

An entirely new set of patterns is needed to approximate common functions in modern programming languages. I have written some of these down in my analytical-engine-libraries repository, such as executing a block of code if two values are equal, going down a series of case statements with an incrementing counter, and performing an operation a specific number of times. While they may sound easy, these operations require much boilerplate code and their implementation is as complicated as any Java pattern you will find in an enterprise environment.

Considerations

Modern day computers store values in a binary format. Besides the boolean values true and false, objects usually need to be split up among multiple binary slots in memory to be stored. This is backwards from how data is stored in the Analytical Engine, as instead of slots of base 2, the store consists of slots of base 10^51, or sexdecillion. While you could theoretically store a string as a series of character code points in consecutive slots in memory, it is much better to compress the string as much as possible to make use of the incredibly large base of the storage slots. For example, in my analytical-engine-libraries repository, I have a library that will store a series of 23 code points in a single column by converting the ascii characters into a base 128 number.

Timing

John Walker included an incredibly useful utility with his implementation of the Analytical Engine (which has been reproduced in my port), the runtime estimation of a program on a real Analytical Engine. Using some estimates that Babbage made of the speed of addition, one can extrapolate the duration of all four operations. This utility makes it clear that the Analytical Engine would be nearly useless in it’s computation of anything attempted in the electronic computer era. Even though it has more RAM than the IBM 1401, it is severely slower. For example, a Mandelbrot program that would print the outline of the Mandelbrot bean at a certain escape (10) takes 391 days to print out the following picture.

..................................................#........................
...........................................................................
...........................................................................
...............................................##..........................
...........................................##.#####........................
.............................................#####.........................
............................................#######........................
............................................######.........................
.............................................#####.........................
....................................#.#.##.#########.##....#...............
....................................###.##############...#.#...............
....................................#######################.#..............
.....................................#######################...............
....................................######################.................
.................................##########################................
..................................#########################................
.................................#############################.............
...........................#.....############################..............
.....................##..#.#....############################...............
.....................########...#############################..............
.....................#########..#############################..............
...................############.############################...............
...............#...#########################################...............
.................#.########################################................
................###########################################................
#########################################################..................
................###########################################................
.................#.########################################................
...............#...#########################################...............
...................############.############################...............
.....................#########..#############################..............
.....................########...#############################..............
.....................##..#.#....############################...............
...........................#.....############################..............
.................................#############################.............
..................................#########################................
.................................##########################................
....................................######################.................
.....................................#######################...............
....................................#######################.#..............
....................................###.##############...#.#...............
....................................#.#.##.#########.##....#...............
.............................................#####.........................
............................................######.........................
............................................#######........................
.............................................#####.........................
...........................................##.#####........................
...............................................##..........................
...........................................................................
...........................................................................

What is possible?

Since the Analytical Engine is Turing complete, it can emulate any other Turing complete computer. This means that theoretically, you could run any program on the Analytical Engine that you could run on a modern day computer, and emulate that modern day computer as well. To demonstrate this, I wrote a Little Man Computer emulator, which transforms the Analytical Engine from a Harvard architecture computer into a von Neumann architecture computer, and takes 53 days to run a simple 31 instruction testing program with minimal looping. Eventually one could write a JavaScript emulator, or a C compiler, for the Analytical Engine, but I would posit that even a compiler would take several years to run for even the simplest program.