EDSACのプログラム技法

EDSACのプログラムの読み書きに重要なのが文字コードである. コードの知識なしでは仕事にならない. それ以前の計算機での入力法はよくわからないが, EDSACではプログラムを紙テープにパンチし, それをイニシアルオーダーで読み込むことが例の本で公開されたので, イニシアルオーダーを解読するためにも文字コードに関心をもつことになった.

EDSACは大学で作った計算機なので, 入出力は市販の機器を用いることになる. 当時はもちろんテレタイプは存在していたから, 当然それらを使うわけだ.

その頃 欧米で使われていたテレタイプは, 英大文字と数字と若干の記号のもので, 5単位テープが標準であった. このコードはInternational Telegraphic Alphabet No.2 (ITA2)という. (規格はここのFreely available itemsのEnglishから得られる) この種のテレタイプは昔は国際電電にいくと見られたがとおの昔に姿を消した.

テレタイプとしてはこのような形であった.



なかなか可愛らしくて1台ほしい. 数年前にアメリカのある空港で耳の不自由な人のための似たようなキーボードを見たことがあった.

コード表は次のとおり.



Figure shift(FIGS)を打つとその後は右の数字と記号を送受信することになる. Letter shift(LTRS)で英大文字になる.

このコードの特徴は, 使用頻度の高い文字は1が, つまりテープの孔が少ないことだ. Wikipediaでletter frequencyを見て, 頻度の順に孔の数をならべると

e t a i n o s r l d h c u m f p y g w v b k x j q z
1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 3 4 4 3 4 2

孔が少ないとテープが丈夫なのか, ごみを減らそうとしたのか知らないが, Morseコードと同様な精神で出来ている. ITA2の特殊記号も欧文Morseコードと同じである.

さてEDSACではこういう機器を使おうとしたが, 数字のコードが

P 0 01101
Q 1 11101
W 2 11001
E 3 10000
R 4 01010
T 5 00001
Y 6 10101
U 7 11100
I 8 01100
O 9 00011

と数値に関係がない. そこで最上段の文字のコードを00000から01001に変更した. ただそうするとP 0のコードはまったく孔が開かず, ブランクテープと同じになってしまうので, テープでは一番左の位置はコードが0の時に孔が開くようにした.

変更は最小にしたらしいが, T→F→Y→T, O→D→W→O, R→X→U→S→R, I→A→I, P→B→E→P, Z→Q→Zと交換した. ITA2と同じなのはH, N, M, L, G, C, V, J, Kである.

これがEDSACの文字コードだ.



左の方がPerforator, テープ鑽孔機で, そのすぐ右がTeleprinter, 出力用タイプライターである. 図形文字でない機能鍵のFigure shiftもプログラムでは文字として使いたいというので, 鑽孔機にはπの文字がついているという具合である.

EDSACの最初の本のコードでは, 鑽孔機の記号の位置はタイプライターのそれとずいぶん違っていた. その辺は上の表では省略した.

EDSACのプログラムでは命令を A 3 F のように書くが, 数字の前にFigure shiftを打つかというとそうではない. 命令の最初は文字と思い, そのあとPQWERTYUIOJが続くあいだは数字として扱う. Jは10として使え, そう使うプログラムを存在する.

一方数値だけの疑命令でも, 先頭にはPを書かなければならない. 命令はコード表のFからVまでの文字で終わる. π, S, Z, Kには別の機能があった.

EDSACはこのようにコードを変更したが, 我々のパラメトロン計算機では, コードは市販の機器のままで, あとはプログラムで挑戦するという方法をとった. 日本国内では6単位が標準だったので文字数も多く, プログラムが見やすいシステムが作れた. その話はまたいつか.

EDSACのプログラム技法

英国ケンブリッジ大学のEDSAC(Electronic Delay Storage Automatic Calculator)が稼働し始めたのは1949年5月6日であった.

EDSACのメンバーはプログラムの解説書(Maurice V. Wilkes, David J. Wheeler, Stanley Gill: The Preparation of Programs for an Electronic Digital Computer)を早々に出版した. 世界で最初のプログラムの本であり, 多くの人がそれでプログラミングの楽しさを知った. 私もその1人である.

遠い昔のテクニックはどんどん忘れ去られる. 最近EDSACのプログラムを眺める機会があったので, その頃のプログラムを解説したくなった.

当時のメモリーは水銀遅延線かブラウン管であった. EDSACはそのDelay Storageから分かるように, 水銀遅延線の記憶装置を持つ. つまり水銀タンクの一方からPiezo効果を使い音波を送り, 反対側で受けた音波を逆Piezo効果で電 気信号にもどす. その遅れを記憶装置として利用する. (水銀遅延線の写真はここに)

EDSACのアーキテクチャは簡単である. レジスタとしては71ビットのアキュムレータと35ビットの乗算レジスタ. 記憶装置は17ビットの短語が1024語. 2n番地と2n+1番地の短語を2語つなぐと35ビットの長語になる. 不思議な計算だがその秘密は, 水銀遅延線での短語は18ビット分あり, 語と語の切替えに1ビットの時間がかかるので, 長語は36-1ビット, 短語は18-1ビット, アキュムレータは72-1ビットということだ.



命令語は左端の5ビットが英文字1字で表すファンクション部, 次の11ビットがアドレス部, 最後の1ビットがL/S(long or short)部で, 0だとアドレス部の短語, 1だと長語を示す.

数値は2の補数表示で, -1≤x<1の範囲の値を持つ. 左端のビットが1なら負数である. 具体的には左端の方だけを示すと, 0.01₂は0.25, 0.1₂は0.5, 0.11₂は0.75, 1.00₂は-1, 1.1₂は-0.5, 1.01₂は-0.75である.

EDSACの命令は A n F のように書く. 先頭の英字がファンクションで, つづいて十進でアドレスを書き(0なら何も書かない), 最後のコードレターという英字を書く. コードレターはアドレスの終りを示す他, FはL/Sビットが0, Dは1を示す.

A n はn番地の内容をアキュムレータに足す; S n は引く. T n はアキュムレータをn番地に格納してアキュムレータをクリア. U n は格納するがクリアせず. E n Fはアキュムレータが正ならn 番地へジャンプ, G n F は負ならジャンプで, 無条件ジャンプはなかった.

乗算は乗数を H 命令で乗算レジスタに置き, V n はn番地と乗算レジスタを掛けて積をアキュムレータに足す; N n は積を引く.

EDSACに除算命令はない.

基本的な説明は以上で終る. サブルーチンジャンプの説明も要ろう. n番地からm番地にあるサブルーチンを呼ぶには, 引数を指定された場所に入れ(T 命令で入れるからアキュムレータはクリアされている)n番地に A n F の命令を置く. n+1番地に E m F を置く. 英文字Aは左端のビットが1なので, アキュムレータは負, 従って E 命令でm番地へジャンプする.

m番地のサブルーチンに来たときは, アキュムレータに A n F があるから, これに U 2 F を足す. EDSACの文字コードでは A+U=E だから和は E n+2 F の命令になり, これをサブルーチンの最後に格納する. サブルーチンからはこの命令を実行してn+2番地へ戻る. これをWheelerリンケージという.

次は二進法の小数を十進に変換して出力する方法.

0.0001₂は十進では0.0625である. これを10倍する. 二進の方は0.1010₂, 十進の方は0.625 この時の整数部が元の小数の1桁目だが, 今は0だから0を出力.

また10倍する. 二進は110.0100₂, 十進は6.25. 整数部は6だから6を出力. 整数部を捨ててまた10倍する. 二進は10.1₂, 十進は2.5. そこで2を出力. さらに10倍して5を出力. という次第で0625が出来る.

EDSACのプリントルーチンP6は次のように書いてある.



左の0から31は相対行番号である. 欄外の24→9のようなのは, 24番地から9番地へジャンプして來るの意味. 25行目の(E F)のかっこは, この命令は変更されること. その下の横線は, 無条件ジャンプを示す. 29番地から31番地の左の2本の縦線は, 偽命令, つまり命令の形はしているが実行されず, 定数であることを示す.

最初の G K はKで終っているから, 制御指令で, 次の命令が格納される番地を相対番地の原点に設定する. つまり命令がθ(短語)やπ(長語)で終っている時は, A 3 F 命令の場所を0 とする. 以下では相対番地を'で示す.

0',1'番地はWheelerリンケージである. 帰り命令は25'番地に格納される. 2'番地は29'番地の偽命令を乗算レジスタに置く. Jは01010, 995は二進では1111100011₂で, 最後がFつまり0だから, 命令の形としては
01010 01111100011 0
であり, 数値的には
(/ #b01010011111000110 65536.0) => .655364990234375
だから, 2¹⁶/10⁵を上に丸めたものである.

0番地には短語の範囲に5桁の整数があり, それを5桁で出力するのだが, 最大の99999と最小の1とを見ると,

1 ]=> (* (/ 99999 65536) .655364990234375)

;Value: .9999976144172251

1 ]=> (* (/ 1 65536) .655364990234375)

;Value: 1.00000761449337e-5

だから, 純小数にして5桁出力する方針である.

4'番地の T 4 D でこうして出来た長語を4,5番地に置く. 5',6'番地は3'番地の命令V F を0番地に入れる. Vは11111なので, コメントのように-1/16を置くことになる. 0番地の負は, 出力の先頭の0をスペースにする目印である. 7'番地は乗算レジスタに10/16を置き, 10倍の準備をする. 8'番地は6'番地の命令を0から引き, Tが00101, 5なので1番地のカウンタを-5/16にする. 10'番地は4,5の長語に10/16を掛ける, すなわち10倍して小数点を4ビット右へ. つまり整数部が先頭の5ビットに収まる.

11'番地ではアキュムレータを残したまま積を戻し, 12'番地の A F で6'番地で入れた0番地の-1/16を足す, つまり整数部が0だったら-1/16になり, 26'番地へ進む. 26'番地で先程引いた1/16を足し, O 31 θ で空白を出力, 20'へ戻る.

整数部が0でなければ, 13'番地のジャンプは起きず, 14'番地の T F でアキュムレータをクリアし, 15'番地の T F で0番地を0にする.

16'番地の O 5 F は, 4番地の長語の先頭の5ビットが数字のコードなので, それを出力する.

17'番地で4番地の長語を取り出し, F 4 F では O 5 F で出力レジスタにいれた数字のコードを4番地の先頭の5ビットに取り出す. 残りのビットは0. それを19'番地で引き, 整数部をなくしてから, L 4 F で左へ4ビットシフト, 4番地へ戻す.

EDSACのシフトは難しい. 命令の下位から見て最初の1のビットが現れるまでシフトする. だから L D は1ビット, L 1 F は2ビット, L 2 F は3ビット, L 4 F は4ビットシフトになる. それより上に1のビットがあっても影響しない.

22'番地からは5桁出力したかのチェック. 最初に入れた1番地の-5/16から3'番地の-1/16を引く. 初めの4回は負なので9'番地へ戻る. 5回済むと25'から主ルーチンに戻る.

思わず長い説明になったが, EDSACの頃のプログラムはこういう感じであった.

このプログラムの問題点は0を出力すると, 5個の空白になることだ. 当時はメモリーが少く, プログラムを短かくするのが重要であった.

EDSACについては, シミュレータのTutorial Guideを参照されたし. その23ページにP6の記述がある.

多面体描画道楽

このタイトルの前回のブログ(2012年7月21日), 大二十面体の絵はもっともらしいと思ったが, 実は違っていた. 最後の方の図の三角形ABCの面は, 芯だと考えた正十二面体の面であって, 星形の面が20あるのはいいのだが, 十二面体の12は余計であった. というより, その図でBはもっと深い位置にあるべきであった.

間違いに気づいたのは, 面を色分けにしようとして, 面の数が多すぎると分かったからだが, 正しいB点の位置の計算に手間取っていた. その計算もやっと計算が終わったら, 次は隠面消去のアルゴリズムに手間取った. 秋風も吹き始めた今頃になって, どうやら正しい図を描くことが出来た.

まず前回の失敗の図だ. 頂点0の正5/2角錐が立つ正5角形は存在しない.



それに対して, 正しい図は次のとおり.



20枚の面のうち, 頂点0に関わって, しかも見える6枚の面に色をつけたのが次の図だ.



先ほどの正5/2角錐は, 底面が平面ではなくなったが, 一応角錐ということにすると, その底は逆に窪んだ5角錐になり, 見ている範囲でも3色別々の3枚の平面で出来ていることが分かる.

結構面倒な図形であった.