As a starting point for discussion, here is a copy of the thoughts I sent to Doron, initiated by the observation relating to note G. Some of this probably need splitting off into sub-topics:

Doron,

Here are some thoughts relating to control mechanisms as they may pertain to the issue Rainer has raised. Bear in mind, that these thoughts are largely off the top of my head at this point, and while everything is based on things I have read in the primary sources over the last few years, I make no claims that anything here is definitive. Further, since I was not specifically looking into this particular issue at the time I came across some of these things, I did not keep specific references to the exact places which support these comments/assertions. This whole area is ripe for extensive further research. As Bromley stated, this area of the AE is perhaps the part least well developed by Babbage. So, I offer this just as a starting point to stimulate discussion.

As an aside, one thing we (ie Plan 28) are desperately in need of is a searchable database for the notebooks and drawings along the lines of what Bromley claimed to have developed with his graduate student before preparing the red book. I suppose there is no prospect that that actual database survives somewhere.

First some background points. As we know, the AE has no form of index registers [were they first invented by Wilkes, or did the Manchester B-lines get there first?]. In fact of course it is worse than that, because the AE does not even have an addressable store in the sense that there is no way at all to compute an address in the Mill. Instead it has named storage locations, and even though Babbage used numeric labels (V0, V1, V2, etc) for store locations, they are just that - labels. Absolutely no form of data structure is possible. The only way a particular variable can be used at all by a program is if at least one variable card is included up front, punched with a machine readable representation of the corresponding label. It is curious that while addressing everywhere else (ie in the microcode and for moving cards in loops and conditionals) was exclusively relative, Babbage had nothing similar for the main store.

Regarding Ada’s examples in the Notes. While some have chosen to see these as the first programs, that is no way really the case. They are really just detailed execution traces of some assumed, but unspecified actual program, on some assumed but unspecified version of the hardware, showing the state transitions in the store as each operation is performed. Since Babbage retained no state in the mill between operations (except for the card counting apparatus) this is a reasonably powerful way of visualizing the activity. They are similar in style to the microcode traces for selected sets of operands which Babbage worked through extensively in the Notations for the great operations. There is no indication at all as to which operations are conditional, such as operation 7 in note G, and no indication of what additional operations would have been performed if the alternate branch of the conditional had been taken. Likewise there is no formal indication of where the loops are. All that is left to the informal English language description which accompanies the examples. So without knowing just what hardware functionality Babbage was assuming at the time he and/or Ada worked these out, and in detail how that hardware would have been controlled, we cannot give a definitive answer concerning note G. As you will see though, there are at least two ways this could have worked.

Early in the Menabrea/Ada paper there is an example like Ax^6, where it is observed that to compute this formula six multiplications are needed, five to develop x^6 then one more to combine that with the coefficient. At least three variables are needed for A, X and the result. Each of the six operations needs three variable cards to specify the sources and the destination for each step. Then it is noted that while there are six operations, really only one operation card is needed, because all these operations are the same, multiplication, so the same card can be used repeatedly without having to turn a new one, although the variable cards would still need to be turned for each operation. There is then discussion that when any new formula is prepared for the Engine it may be advantageous to mathematically manipulate the expression, if possible, into such a form that similar operations can be performed together, thus again reducing the number of distinct operation cards needed. Nowhere here is there any discussion of just how this would work. Where is the information which tells the Engine that that multiply card should be used 6 times before turning the next one?

We might wonder why it is there was such a concern with economizing on operation cards. After all, we know that on average at least three variable cards are needed for each operation and that there is much less possibility for eliding these. So, even if it were possible to eliminate all the operation cards it would still only represent at most a 25% saving, and since operation cards are small, simple, and of very few distinct types, whereas variable cards are larger and would be needed in at least three times as many distinct types as there are locations in the store, this saving through repeated application of operation cards seems even less worthwhile. Perhaps Babbage was thinking that by reducing the number of cards needed he might reduce the number of errors occurring in the preparation. I doubt that is the case. He did offer some excellent suggestions for how errors could be reduced, such as colouring the cards for different operations distinctly, and colouring the variable cards for the source operands differently from those for the destinations, so that when the two strings had been prepared it would be easy to check the operations were in the expected sequence and that there were matching variable cards for each one. This would be largely blown out of the water if operation cards were randomly elided.

Rather I think we may trace this thinking back to the earliest versions of the AE. Remember that there, the store was of very modest proportions because it consisted of columns which all had to fit around the main central wheels along with the rest of the mill. Also the idea of the Jacquard cards had not yet been introduced, so the “user program” would have been coded as studs on one or more barrels. If we assume that these barrels would have been similar to those used for the lower level microcode control and of similar proportions, then the available program space would have been severely limited, as the barrels had only about 80 verticals. At the microcode level Babbage was an expert at arranging the microcode to use the minimum number of verticals with a very sophisticated set of conditional controls to interlink them. If he applied any of this thinking to the user level, then it would have been natural for him to look for ways to reduce the number of distinct verticals required. He probably would have used distinct barrels for the operations and the variables, just as he split the control of the mill across several separate barrels.

Let us go back to cards though, because this is what is relevant to Ada’s examples. Just how would those repeated operation cards be controlled? Babbage introduced combinatorial cards. These were to be interspersed in the operation cards and would have contained numbers used to set a counter. The counter could then be decremented each time the succeeding operation card is applied, and when zero is reached, issue the order to turn the operation cards to bring the next one into play. This introduces a new issue though, because while the basic operation cards are small, few in distinct types, and need only a few holes to control the small number of levers that communicate with the reducing apparatus of the barrels to dispatch the appropriate microcode sequences, the combinatorial cards would have needed to be much larger. They have to be able to encode a number, and they need to communicate with a completely different part of the machine, the counting apparatus. It gets worse when we want to allow for the possibility of cycles (loops) of multiple operation cards, because now, in addition to specifying the iteration count, the combinatorial card also has to say how many cards are in the loop so that we can know when it is time to back them up, and by how many, to start the next iteration. If we are able to find corresponding cycles in the variable cards it is even more complex, because the number of variable cards to be backed is necessarily different from the number of operation cards, so we need yet another counter and another field on the combinatorial card to initialize it. You might think perhaps we should separate out the combinatorial cards, and give them their own card reading apparatus to get round these problems, but that introduces a new one of its own, which is that then we have no way to know when to turn the combinatorial cards. Which operation cards form part of a group under the control of a combinatorial card and which are just to be played sequentially? Unless we introduce a combinatorial card for each operation card that is to be used only once, it’s a mess. Why is the word “epicycles” going through my mind right now?

Consider now the example Ax^n. To evaluate this formula we need a fixed set of operation, variable, (and possibly combinatorial) cards which can be prepared ahead of time before we know the actual data to be operated on. Yet in this case the number of operations is actually data dependent. Menabrea/Ada says this is handled by having the value of the store location representing the variable n transferred to the mill to initialize the counter which will determine the number of multiplications. This fortunately is a case where the same variable locations can be used repeatedly as x^n is developed, independent of the value of n.

Now there is a place in the notebooks where Babbage states that (at least some of the) combinatorial cards have been superseded by having index values held in store locations and manipulated by regular operations in the mill. This might correspond with the description here, and brings us somewhat closer to modern practice. There are also drawings showing the counting apparatus as consisting of multiple three digit counters all mounted on a single vertical axis, where it would presumably have been easy to initialize one or more of them simultaneously with a value read straight from the store.

Also in the notebooks, there are several places where Babbage is exploring some formula to see how it would be handled by the Engine. He finds cycles in the operations to be relatively common, but cycles in the variables to be rare. (A notable exception of course is the method of differences.) Note G is exactly an example of this (and may have been one of the ones in the notebooks - I don’t recall what they actually were). We have a clear cycle in the operations, but one of the cycles in the variables is only approximate, since some locations have to change with each iteration of the loop. It would be completely impractical to imagine needing intervention, stopping the Engine at each iteration to insert new cards. For a start the variable cards are all stitched together. [There is a cartoon in Padua’s book where Ada is running round with a conductor’s hole punch in her hand to make last minute adjustments to cards. . .] (Note however that there is a place where Babbage wrote about how number cards could be used to provide things like logarithms, where the machine would stop, ring a bell and request the attendant to fetch the required logarithm from a storage cabinet and apply it to the Engine. This would require a number card reading apparatus that could handle individual unstrung cards, so there is a precedent, but as usual Babbage did not give us the practical details.)

So how to deal with this? The first and perhaps trivial solution is simply to “unroll” the loops, at least as far as the variable cards are concerned. You might object that this necessarily introduces an artificial limitation to the number of iterations we can perform for an otherwise unbounded formula, but that is not really the case, since each iteration requires one additional storage location and the store is of course finite (notwithstanding Babbage’s harebrained virtual memory system using number cards for backing store), so it’s bounded that way already. Regarding the absolute number of cards this would require, it is large but still plausible given that as we know Jacquard looms had run patterns needing tens of thousands of cards, though it would clearly be undesirable compared to the mere handful that would have been needed if there were a true cycle.

Now this raises a new question for me. We know Babbage was obsessed with the performance of his Engines and at least in the case of the Great Engine he was willing to throw large amounts of hardware at a problem for even relatively modest gains in performance. Given that, why would he not have been concerned about the performance implications of these cycles? Each time there is a cycle, at every iteration the cards have to be backed, and even though they probably could be backed at the rate of two per basic cycle period it would still add a non-trivial overhead during which time the mill is otherwise idle. In contrast, unrolling the loops (as with modern compilers) would eliminate the performance hit.

There is a second approach. In the notebooks where Babbage is working through examples, he lists out what is needed to run the example and in a couple of places he states “Variable Cards (two sets)”, and in at least one place “Number Cards (two sets)”. When I first saw this, I thought it was perhaps some way to deal with the fact that both number cards and variable cards have to have a great many holes. Babbage always wants everything to be positively driven with no ambiguity, so wherever a hole in a card or a stud on barrel is sensed, there are two opposing levers with two possible hole/stud locations so one can be pushed while the other is free to move. This means of course that the number of possible hole locations on the card has to be double the number bits actually encoded. I thought maybe he was splitting these complementary sets of holes on the two sets of cards so that one rod would be acted on by one card and the other by the second card of the pair, both working together on two separate prisms to get the desired effect with only half the number of potential hole locations needed in any one physical card.

I no longer believe this is actually the case. Instead, I think what Babbage was proposing here was that in a case where you have only an approximate cycle in the variable cards, they would be split into two separate strings. On the first string would be all those cards that really are constant on each iteration so they would form a true cycle. The ones that have to change on each iteration would be plucked out and strung together, as many as needed for the expected number of iterations, into the second set. This would be a relatively modest set (two per iteration) in the case of Note G.

Of course this comes with new problems and to back project a modern term, it does strike me as something of a kludge. First there would have to be a physical means to allow either prism of variable cards to be applied as required to the store. Babbage actually has a sketch in the notebooks showing how this would be done, and it’s simple. He has horizontal sets of sensing rods with one prism working against one end, and the second prism working against the other. This single set of rods then controls the store and so long as only one prism is ever brought forward at a given time there would be no conflict. What this does not detail though is how it would be decided which prism is to act. I.e. How do we know that a particular operation is the one that needs to get one or more of its operands, or place its result at a variable location specified by a card on the secondary prism? I have no answer for that particular detail at this point.

So where does all this leave us? Clearly with a lot of work to do. In the case of my model, I sized the store to allow me to be able to compute about the first 20 of the Bernoulli numbers. I will have no problem simply unrolling the variable loop to make this possible for that number of iterations and I will be astounded if the hardware is ever reliable enough to run that long without failing! If a real AE ever exists, a demo of a similar extent would likewise be more than enough to convince people how significant the Engine would have been had Babbage built it in the 1840’s. I also suspect that had he done so, it would not have take long for him to figure out he needed a better addressing scheme.

Tim Robinson
4/20/2015