Analytical Programming » Hummus and Magnets
Analytical Programming
by Christian Plesner Hansen Posted on November 25, 2012
This is my third post about Babbage's calculating engines. The first two were about the difference
engine: why it was important at the time and how it worked. This post is about the analytical engine.
The analytical engine is famously the first programmable computing machine, and there was much
programming involved both in designing and operating it. In this post I'll take a look at the various
ways you could program the engine and the way programs were used to control the engine internally.
この記事はバベジの計算機械に関する三つ目の記事です。先の二つは階差機関についてのもので、階差機関が
当時どれほど重要なものであったかということとその動作原理について説明しました。今回は解析機関につい
ての話です。解析機関は最初のプログラム可能な計算機械として有名で、設計と運用の両面でプログラミング
に大きな進歩がありました。今回の post では解析機関をプログラムできる様々な方式と、解析機関を内部的
に制御するのに使われていたプログラムの手法についてとりあげます。
Programming the analytical engine
解析機関でプログラミング
When the analytical engine is mentioned as the first programmable computer the example you almost
always see is one particular program, the one for calculating Bernoulli numbers that was given in
note G of Ada Lovelace's notes on the engine. But that's only the tip of the iceberg. This post is
about the rest of the iceberg. (Don't worry, I'll give the Bernoulli program a whole post of its
own). The engine could be programmed on roughly three different levels and we'll take a look at
each of them in some detail, but first I'll give an brief overview of each of them.
解析機関が史上初のコンピューターとして言及されたときにはほぼいつもあるプログラムが例に出されます。
それは Ada Lovelace が書いた解析機関についての notes の note G に記載されているもので、Bernoulli
numbers を計算するプログラムです。しかしそれは氷山の一角 (the tip of the iceberg) に過ぎません。
今回はこの氷山の残りの部分について話します (ご心配なく。Bernoulli の program については丸々別の記事
で取り上げます)。解析機関は大まかに言って異なる三つのレベルでプログラムが可能です。それぞれについて
詳しく取り上げますが、まずはそれぞれの概観について触れておきましょう。
At the highest level programs were written as tables like the one here on the right. That one is
taken from Menabrea's 1842 article about the engine. Each row in the table is an instruction, a
mathematical operation to be performed. In modern terms we would call this a register language since
all the operation's inputs and outputs are given explicitly. This is the format that was used in all
contemporary articles about the engine and the format of the Bernoulli program. However, a program
in table form could obviously not be run by the analytical engine directly, it was more like what we
would call pseudocode today. It describes the program you want to execute but it's not executable
itself.
最高位レベルにあるプログラムは右図にあるような table として書かれたものです。この図は1842年の Menbrea
による解析機関に関する文献から引用しました。table の各行は instruction であり、実行される mathematical
operation です。すべての operation の入力と出力が explicitly に与えられているので、これは modern terms
で言えば register language と呼べるものでしょう。この format は解析機関に関するすべての contenporary
articles で使われているものであり、また Bernoulli program で使われている format でもあります。しかし
ながら table form になっているプログラムは解析機関が直接実行するものでないのは明らかで、それは今日わ
たしたちが擬似コード (pseudo code)と呼んでいるものに近いものでした。つまり、何を行いたいプログラムな
のかを記述するものであって、それ自体を実行するためのものではありませんでした。
The way you made executable programs was using punched cards. To run a program written in the table
format you would have to translate it into a stack of cards that could be interpreted by the machine.
You might think of the cards as a type of bytecode. Babbage seems to have considered this mostly an
implementation detail so it's not super well described, but we still know enough to get a pretty good
sense for how card-based programming would have worked.
実行可能プログラムを作る手段はパンチカード (punced cards) を使うものでした。table format で書かれた
プログラムを実行するにはそれを、機械が解釈可能な card の stack へと変換する必要がありました。この
cards をバイトコードのようなものと考える人もいるかもしれませんが、バベジはこれを mostly an
implementaion detail とみなしていたようで、not super well described でした。しかしそれでも、わたした
ちは card-based プログラミングがどのように行われるかについては十分理解できました。
At the bottom layer there was an internal “microcode” format that controlled how the engine executed
each of the punched-card encoded instructions. The microcode programs were encoded as rows of pegs on
the side of rotating barrels, like the pins on a music box. The pins controlled operations and data
flow within the engine and the control flow of the microprograms themselves. Some of the more complex
instructions such as multiplication and division had very elaborate implementations of more than a
hundred verticals, Babbage's name for a single micro-instruction.
解析機関の bottom layer には、instruction が encode された punched-card のそれぞれを解析機関がどの
ように実行するのか制御する内部的な「マイクロコード」format が存在していました。この microcode
program は music box の pin のように、rotating barrels の side にある pegs の raw として encode さ
れていました。このpin は解析機関内部で operations と data flow を制御していましたが micro program
そのものの flow も制御していました。乗除算のようなもっと複雑な instruction の一部は vertical 100個
を超える非常に elaborate (精密、精巧)な implementaions です。この verticalとはバベジがひとつの
micro-instruction につけた名前です。
In the rest of this post I'll describe two of these formats, tables and microcode. The punched card
format has a separate post which is linked at the end. First though, a quick note on sources. My
source for most of this post is some excellent articles by Allan Bromley: The Evolution of Babbage's
Calculating Engines from 1987 and Babbage's Analytical Engine Plans 28 and 28a – The Programmer's
Interface from 2000. If you want more information these are the articles to read. (Obscenely they
are both behind IEEE's paywall which I suspect is one reason they're not as widely read as they
deserve to be.)
この投稿の残りでは、これらの format の二つ tables と microcode の説明をします。punched card format
については分割した投稿にしてこの投稿の末尾にリンクをはっておきますが、情報源について簡単な覚書を書い
ておきましょう。この投稿でわたしが使った情報の大部分は Allan Bromley による excellent articles の幾
つかから得たものです。
With that let's get on to the first language level: tables.
Tables
The basic model of the analytical engine is similar to the difference engine but generalized along
several dimensions. The difference engine had 8 columns, what we would call registers, with 31
decimal digits of precision (roughly 103 bits). These could be added together in a fixed pattern,
right to left. The analytical engine had a much larger number of columns, Babbage considered 1000 to
be realistic, and it could add, subtract, multiply, and divide them in any pattern. The columns also
had more precision, 50 decimal digits (roughly 166 bits). Each column had an index, i; the i'th
column is written as Vi. The V stands for variable which I'll use interchangeably with the word column.
解析機関の基本的なmodelは階差機関と似ていますが、several dimensions において一般化されています。階
差機関は8つのカラムを持ち、カラムはそれぞれ十進31桁の精度があります (おおよそ103ビット分)。
これらのカラムは右から左に固定されたパターンで足し合わせることができました。解析機関はもっと大きな
数のカラムを持っていて、バベジは1000個を to be realistic な数と考えていました。また、階差機関のそれ
よりも大きな精度を持っていて十進50桁(おおよそ166ビット)ありました。各カラムにはそれぞれ i という
index があって、i番目のカラムは Vi のように記述します。この V は word column と交換して使う variable
を表しています。
The table format for programming the engine, the most high-level format, represents a sequence of
instructions as rows in a table. Each row specifies an operation along with the input and output
columns. For instance, to calculate (V1 + V2 + V3) and store the result in V4 you would do
something like:
解析機関のプログラミングをするための table format は最上位レベルの format であり、instrcutions の並
びを表現しています。table の各行は入出力のほかに operation を spefify します。たとえば (V1 + V2 + V3)
を計算してその結果を V4 へ格納するには次のようにします。
# op in out
1 + V1 + V2 V4
2 + V3 + V4 V4
The first instruction adds V1 and V2, storing the result in V4, and the second adds V3 to V4. It's
pretty straightforward really – but in this simple example I've cheated and omitted a few details.
We'll be adding those back now.
最初の instruction は V1 と V2 を加算してその結果を V4 に格納します。二番目の instruction は V3 を
V4 に加えます。これは実際、とても straightforward です。しかしこの simple example では cheat して
a few detail を省略します。
In modern programming languages we're used to being able to read a variable as many times as we want
with no side-effects. With the analytical engine on the other hand when you read a column what
you're actually doing is transferring the value mechanically from the column to the processing unit,
the mill, which causes the column to be cleared. It's obviously inconvenient if you can't read a
column more than once. To solve this the engine supported two kinds of reads: the simple read where
the column is cleared in the process and a the restoring read where the column retains its value. A
restoring read works by simultaneously transferring the value to the mill and a temporary storage
column and then immediately transferring the value back from temporary storage to the column.
modern なプログラミング言語では、変数の読み出しは副作用なしに好きな回数だけを行えます。一方解析機関
で column を読み出したときに実際に行われることは column から processing unit への値の transferring
であり読み出された column はクリアされてしまいます。これはその column を複数回読み出したい場合に明ら
かに不便です。これを解決するために解析機関は simple read と restoring read という二種類の読み出しを
サポートしています。restoring read は simultamepisly に値を mil と temporary stroage column に転送し
たあと即座にその temporary storage から column に値を書き戻すという動作をします。
To indicate which kind of read to do there's an extra field in the table indicating column value
changes. If we go back to the program from before, let's say that we don't mind that V2 and V3 are
cleared but we need to retain V1. We would express that as
table には読み出しの種類を indicate するための extra field があります。先ほどのプログラムに話を戻
すと、V2 と V3 がクリアされることを気にする必要はないけれども、V1 についてはその値を retain する必
要があります。We would express that as
# op in out vars
1 + V1 + V2 V4 V1 = V1
V2 = 0
2 + V3 + V4 V4 V3 = 0
In the first operation we want to restore V1 after it's been read but let V2 get cleared. In the
second instruction we let V3 get cleared and we don't need to specify what happens when we read V4
because that's where the result is stored.
最初の operation では V1 を読みだした後に restore を行いたいのですが、V2 はクリアしても問題ありませ
ん。二番目の instruction では V3 はクリアしますが V4 は結果が格納されるところなので V4 を読み出した
ときに起こることを指定する必要はありません。
This program contains the full information you would need to be able to run it on the engine. The
original tables annotate programs some more but anything beyond this is more like comments, it
doesn't change the behavior of the program.
このプログラムにはあなたが解析機関で実行できるようにするのに必要になるであろう full information が
あります。original tables はプログラムを some more annotate しますが、anything beyond this はよりコ
メントに近いもので、プログラムの振る舞いを変えません。
One additional piece of information you'll see in most of the original programs, the one on the
right here is another of Menabrea's, is that all the column names have a second index in
superscript. So where I've written V1 one of the original tables would have something like 1V1. The
second index indicates how many times the variable has changed. So 1V1 means “the first value
stored in V1“, 2V1 means “the second value stored in V1, after it had been overwritten once”.
This doesn't mean that you can recover old values of a variable, it's just for the programmer to
keep track of what the current value is of each variable. You can also write 0V1 which means the
original 0 stored in V1 in the case where we haven't written to that column at all yet. If we add
in these indices the program will look like this:
original programs の大部分で見ることになるであろう information の one additional piece が、すべての
カラム名は superscript に二番目の index を持っているということです。
ここで、わたしは original tables にある V1 を 1V1 のように書くことにします。
この second index はその変数が何回変更されたのかを indicate します。
ですから、1V1 の意味は V1 に格納された最初の値であり、2V1 の意味は V1 に格納された二番目の値です。
これはある変数の古い値を recover できるという意味ではありません。単に、プログラマーのために各変数の
current value を track させるためだけのものです。0V1という記述もできて、これはカラムにまだ書き込み
を行っていない状態のV1にあるオリジナルの0という意味です。これらの添え字群を使って加算を行うとプログ
ラムは以下のようになります。
# op in out vars
1 + 1V1 + 1V2 1V4 1V1 = 1V1
1V2 = 0V2
2 + 1V3 + 1V4 2V4 1V3 = 0V3
(The 0V2 assignment is just a convention, it means the same as resetting V2 to its initial state
where it contained 0).
(0V2 の代入は単なる convention であり、意味としては V2 をリセットして 0 を保持している初期状態に
するのと同じです).
This is the language used to write the first computer programs. Even though it's unusual it will
look familiar to any modern programmer familiar with assembly programming. There is no way to
specify control flow even though there is some indication in the Bernoulli program that it had been
considered. These are basically straight-line sequences of mathematical operations on a set of
variables. And being pseudocode the conventions weren't fixed, they were changed and adapted by
the authors to fit the programs they were writing.
これが最初のコンピュータープログラムを書くのに使われた言語です。それは unusual ではありましたがアセ
ンブリ言語でのプログラミングに慣れた modern プログラマーにとってはなじみのあるものです。Bernoulli
program にはいくつか indication するものはあるのですが、フローを制御する方法はありません。プログラム
は基本的に変数の集まりに対して行われる mathematical operation の stratight-line sequence です。また、
being pseudocode the convention は固定されていなかったので、彼らが書いたプログラムに fit させるため
に authors によって変更されたり adapt されたりしています。
The microprogram format is at the other end of the spectrum; where the tables were high-level and
meant for communicating programs clearly the microprograms where low-level and written and
understood only by Babbage, at least until recently.
このマイクロプログラムの format は spectrum の other end にあります。talbes が high-level に位置して
commuicating program を明確に意図していたものであったのに対して、マイクロプログラムは low-level にし
ており少なくとも最近まではバベジのみが理解し、書かれていたものでした。
Microprograms
The analytical engine could perform a number of complex operations including multiplication and
division. To give a sense for how complex I'll give an example of how the engine would multiply two
numbers.
解析機関は乗除算を含むたくさんの複雑な operations を行うことが可能でした。
sense for how complex を示すために、解析機関がどのように二つの数値の乗算を行うかの例を出します。
Say we instruct the engine to multiply 17932 with 2379. The multiplication logic would first
determine which of the operands had the fewest digits and put that in one register. (The computing
mill had a number of internal storage columns that were used to hold partial results during
individual operations. I'll call those registers to distinguish them from the user-accessible
columns). The other number, the one with most digits would be used to generate a table of all the
multiples of that number from 2 to 9, using addition. In this case that's 17932:
では解析機関に17932×2379を計算させてみましょう。解析機関が行う乗算のロジックでは最初にオペランドのい
ずれが fewest digits であるかを決定し、その短いほうをレジスターに格納します (computing mill は独立し
た演算の中間結果を保持するのに使われた internal storage colmuns をたくさん持っています)。もう一方の
桁の長いオペランドは2から9までを乗じた積の table を加算によって生成するのに使われます。今回の例で使
われるのは17932 です:
factor value
1 17932
2 35864
3 53796
4 71728
5 89660
6 107592
7 125524
8 143456
9 161388
Once this table had been built the engine would scan through the other number, in this case 2379.
For each digit it would look up the corresponding multiple in the table, shift it left by an amount
corresponding to the significance of the digit (that's base 10 shift), and add the resulting values
as it went:
この table を構築すると解析機関は別の数値、この例では 2379 を scan します。この数値の各桁の数字につ
いて table で対応する multiple を検索し、それを該当する(十進数における) significance of the digit の
量だけ左へシフトします。そして、as it went として resulting values を加算します。
digit product
9 161388
70 1255240
300 5379600
2000 35864000
Adding those four values together you get 42660228, the product of 17932 and 2379, calculated using
the primitive operations of addition and multiplication by 10. The whole operation took time
proportional to the number of digits of the shortest of the input numbers. Unlike the difference
engine which stored numbers as tens complement the analytical engine stored the sign of the number
as a separate bit. That way the multiplication could be unsigned and the sign could be computed
separately. This meant that the engine had two zeroes, plus and minus.
これら四つの値を加算すると 17932×2379の結果である 42660228 となります。加算と×10という primitive
operations を使って計算した operation 全体では、入力された数値のうち短いほうの桁数に比例した時間を要
します。数値が十の補数として格納される階差機関とは異なり、解析機関では数値の符号は独立したビットとし
て格納されます。この方式では乗算を無符号にでき、符号は別途計算できるようになります。これは解析機関が
プラスのゼロとマイナスのゼロという二種類のゼロを持っていたということを意味しています。
Back to multiplication. The engine needed an internal control mechanism to take it through this
complex process and what it used was a microprogram encoded by pegs on a rotating barrel. You can
see a simplified diagram of the barrel here on the right. Each “cycle” of the microprogram
proceeds in the same way.
乗算に戻りましょう。解析機関は take it through this complex process のために内部制御機構と
routating barrel 上の pegs によって encode された microprogramを必要とします。単純化された barrel
の diagram を右にある図で確認できます。microprogram の各“サイクル”は同じ方法で proceeds されます。
First the barrel is pushed left and the pegs along the vertical edge press against a row of levers
which causes them to engage or disengage other parts of the engine. Because of the way the pegs
are aligned with the vertical edge of the barrel Babbage called a single such instruction a vertical.
まず barrel が pushed left され、engine のほかの parts の engage か disengage を引き起こす levers
の row に対して pegs along the vertical edge が press します。その pegs が vertical edge of the
barrel と align されているやり方から、バベジはそのような single を instructcion a vertical と呼び
ました。
Second, the barrel is pushed to the right and connects to the big gear you see to the right of it in
the diagram. That gear, and the gears connected with it, Babbage called the reducing apparatus.
That's what controls the flow of the program. The reducing apparatus rotates the barrel some amount
in either direction to select the next vertical to apply. At the same time any other components that
were engaged by the current vertical perform their operation, for instance a single step of building
the multiplication table. The reducing apparatus takes input from those other components so for
instance it may move the barrel different amounts depending on whether the last addition overflowed.
That's the arm on the far right (Babbage called overflow “running up”). The reducing apparatus is
controlled by the barrel itself so each vertical explicitly specifies how the reducing apparatus
should rotate it to the next vertical. You'll notice that the three gears you see near the reducing
apparatus' main gear have 1, 2, and 4 teeth respectively. By engaging a combination of them one
vertical could have the reducing apparatus rotate the barrel any number of steps between 1 to 7. In
modern terms, each micro-instruction contains an explicit relative branch, conditional or
unconditional, to the next microinstruction. As you can see this is a highly sophisticated and
general mechanism. The only disadvantage is that it's slow – a single cycle takes a few seconds so
a multiplication can take several
minutes.
次に、barrel が diagram 中の右側に見られるように right に push され、そして big gear に connetct さ
れます。この gear とそれに connect している gears をバベジは reducing apparatus と呼びました。これは
プログラムの flow を制御するものです。この reducing apparatus は barrel を apply すべき next vertical
を選択するためにいずれかの方向に some amount だけ rotate します。同時に、current vertical によって
engage されている any other compnents はたとえば multiplication table の building の single step の
ような their operation を実行します。reducing appartus は最後の加算がオーバーフローしたかどうかによっ
て barrel を diffrent amount で move する可能性のある instance のために those other components から
input を take します。それが arm on the far right です (バベジはこれを overflow running upo と呼びま
した)。reducing appartus は barrel 自身によって control されるので、各 vertical は reducing apparatus
が next vertical へどのくらい rotate すべきなのかを explicitly に specify します。あなたは reducing
apparatus の main gear のそばにあってそれぞれ1、2、4個の teeth を持った三つのgear を notice できるで
しょう。これら三つの gear の combination を engaging することにより one vertical は1から7までの任意の
ステップ数だけ barrel を roate する reducing apparatus を持てるようになります。modern terms で言えば、
各 micro-instruction は next microinstruction への conditioal よび unconditioal な explicit relative
branch を保持します。見てわかる通りこれは高度に sophiscated され、かつ general な mechanism です。その
disadvantage は、一サイクルに数秒かかるので乗算一回に数分を要するほど遅いということだけです。
As you would expect the diagram above is simplified, in practice there were multiple barrels and
they were much larger both in the number of pegs for each vertical and number of verticals per drum.
I haven't been able to find any of Babbage's actual microprograms unfortunately so for now all I
know are the basic principles, and we know that designing them was one of Babbage's main interests
in designing the engine.
想像がつくでしょうが、上記の diagram は単純化したものであり、実際には複数の barrel があって、number
of pegs for each vertical と number of vertical of drum のどちらももっと大きなものです。残念ながらバ
ベジによる実際の microprogram は今もって発見されていません。したがって現状わたしが知っているのは
basic principles がすべてであり、またわたしたちはそれらの設計がバベジの階差機関の設計における main
interests のひとつであることを理解しています。
The third program format is the punched cards which is what would have been used by an operator of
the engine. I'll look at those in some detail because they give a good sense of what it would have
been like to work with the engine in practice. To keep this post to a reasonable length I've broken
that out into its own post called punched cards.
三番目の program formt は解析機関の operator によって使われていた punched cards (パンチカード)です。
engine がどのように動作しているのかを知るのに具合がよいので、この先は punched card という別の投稿に
分けることにします。