1951年にプログラミングする方法 – EDSACを例に

WARNING

この記事はChatGPTによって中国語から翻訳されたもので、いくつかの誤りが含まれているかもしれません。不正確な部分があればご了承ください。

❖EDSAC

EDSACは、ケンブリッジ大学の数学実験室で設計・製造されたコンピューターです。1949年、プロジェクトチームはEDSACを用いて平方数表を生成し、印刷することに成功し1、これはEDSACが正式に稼働を開始したことを象徴しています。

EDSACの基本的な計算モデルは現代のコンピューターと非常に似ており、以下のように要約できます：

  1. 32個のタンク（Tank）があり、各タンクには32個のワード（Word）が格納されています。ここでのワードは18ビットで、x86プラットフォームの16ビットとは異なります。これら32個のタンクは現代のコンピューターのメモリに相当します（以下では、これら32個のタンクを「メモリ」と呼びます）。
  2. 5つのレジスタがあり、そのうち2つのレジスタ（命令レジスタ、命令アドレスレジスタ）は制御用、残りの3つのレジスタは計算用です。
  3. 計算は順序的に命令（Order）を実行することで表現され、各命令は1ワードを占め、1ビットは未使用なので、各命令は17ビットを占めます。すべての命令とデータは前述のメモリに格納されます（実際には、EDSACの設計では、命令とデータに区別はありません）。各命令はレジスタやメモリを読み書きする可能性があります。
  4. EDSACの入力デバイスは5ポイントのパンチテープで、このテープはプログラムの入力（具体的な意味は以下で説明します）も担当します。EDSACの出力デバイスは電信式プリンターです。また、電話も装備されており、この電話を使って「人間とコンピュータのインタラクション」を行うことができます。EDSACで実装された世界初の電子ゲーム–三目並べ（議論の余地あり）は、この電話を通じてインタラクションを行っていました。

❖EDSACのプログラム

前述の通り、EDSACの設計では、「計算」は「命令を順序立てて実行する」ことを意味します。では、これらの命令はどこに格納されているのでしょうか？現代のコンピューターと同様に、これらの命令は「メモリ」に格納されています。しかし、「メモリ」に格納されているプログラムはどこから来るのでしょうか？

答えは、「メモリ」に格納されているプログラムはパンチテープから読み込まれるというものです。EDSACが使用しているテープは「5ポイントテープ」で、以下のようなものです：

テープの各セルには5つの穴があり、穴が開いている場合は1を、開いていない場合は0を表します。したがって、理論的には、テープをリストと見なし、リストの各要素は0から31の自然数と見なすことができます。

紙テープが表現しているのは機械語（18ビットの命令）ではなく、「テキストプログラム」の直接的なエンコードです。EDSACの時代、プログラマーはまずテキスト形式のプログラムを紙に書き、次にkeypunch（穴あけ機）を使ってテキスト形式のプログラムを紙テープに打ち込む必要がありました。

では、テキスト形式のプログラムとは何でしょうか？この種のプログラムは今日のアセンブリ言語プログラムに似ており、HIを出力するプログラムは以下のようになります：

1T64K
2GK
3ZF
4O5θ
5O6θ
6O7θ
7ZF
8*F
9HF
10IF
11EZ
12PF

これは何のことなのでしょうか？確かに、この形式のプログラムはまだ非常に読みにくいです。一つずつ見ていきましょう。

まず、このプログラムの各行は以下の3つの状況のいずれかを表しています：

  1. 命令
  2. 擬似命令
  3. データ

擬似命令は今日のアセンブリ言語の擬似命令に似ており、それは初期化命令に必要な情報を提供するためのものです。初期化命令（initial orders）は我々が以下で議論する重点であり、一時的にそれを一種のアセンブラと理解することができます。

上記のプログラムに少し注釈を付けてみましょう：

1T64K        擬似命令、現在のプログラムを64番目の単語（2番目の箱の0番目の単語）にロードする意味
2GK          擬似命令、再配置パラメータ（θパラメータ）を現在の位置（次の行、ここではZFの位置）に設定する
3--------------------------------------------------------------
4ZF          ハルト                                              }            
5O5θ         プリンタのオフセットモードを"Letter shift"に設定する     }     
6O6θ         プリンタに位置6の最上位5ビットが表す文字（H）を印刷させる             }
7O7θ         プリンタに位置6の最上位5ビットが表す文字（I）を印刷させる             }      これらの行は実際にメモリにロードされる
8ZF          ハルト                                              }
9*F          O5θ命令インデックスのデータ                                 }
10HF          O6θ命令インデックスのデータ                                 }
11IF          O7θ命令インデックスのデータ                                 }   
12--------------------------------------------------------------
13EZ          擬似命令、EZとPFを同時に使用すると、初期化命令にθパラメータの位置に実行する命令を設定するように指示する
14PF          上記と同じ

このプログラムを理解するためには、紙テープとEDSACの関係、そして初期化命令が何をするのかを理解する必要があります。

❖初期化命令

初期化命令はEDSACシステムの中で最も核心的な一部分のコード、一つのプログラムであり、今日の視点から見ると、それはEDSACのオペレーティングシステム、再配置可能なアセンブラとローダーと言えます。初期化命令には二つのバージョンがあり、それぞれ初期化命令1と初期化命令2と呼ばれています。上述のテキスト形式のプログラムは初期化命令によって読み取られるため、異なる初期化命令によって読み取られるテキスト形式のプログラムも異なります。

初期化命令を理解するためには、初期化命令の視点から紙テープ上のプログラムがどのようなものであるかを観察するのが最善です。まず、紙テープ上のプログラムはテキスト形式のプログラムの直接的な翻訳であり、紙テープ上の各ユニットは一つの文字または数字に対応しています。例えば、T64Kという行は紙テープ上で四つの対応するユニットを生成します。このように見ると、初期化命令が取得するプログラムは紙テープ上のテキスト形式のプログラムのエンコードです。初期化命令はそれを18ビットの命令に翻訳し、メモリにロードする必要があります。

初期化命令はIで始まる命令を使って紙テープ上の数を読み取ります。例えば：

1I2S

これは、テープヘッドのデータを位置2の最下位5ビットに読み込むことを意味します。（Sの意味は後で説明します）

これにより、私たちはすぐに一つの疑問を持つことになります。英字は26個、数字は10個、ギリシャ文字は4個（θ ϕ Δ π）があり、これらの各記号に一意のエンコードを提供するためには少なくとも40個の数が必要です。五点式の紙テープ（最大32個の数）では足りない場合はないのでしょうか？

実際には、パンチャーは穴を開ける際に、Pと0、Qと1、Wと2、Eと3、Oと9まで、同じ穴を開けます：

これは問題にならないのでしょうか？初期化命令の観点からすると、読み込んだ数がPなのか0なのかどう区別するのでしょうか？

答えは、初期化命令は区別する必要がないということです。テキスト形式のプログラムの各行は特定の形式を持っており、形式文法で表現すると次のようになります：

Order→Pre N∗ Post \mathsf{Order} \rightarrow \mathsf{Pre}\ \mathsf{N}^*\ \mathsf{Post}

ここで：

  • Pre\mathsf{Pre} は命令のタイプを表し、例えばIはテープからの読み込み、Oはプリンタからの出力を表します。
  • N∗\mathsf{N}^* は複数の（ない場合もあり、その場合はこの部分は0）0-9の整数を表し、アドレスを表します。
  • Post\mathsf{Post} は各命令のサフィックスで、初期化命令1の設計では、短命令と長命令を区別するために使用され、Sは短命令、Lは長命令を表します。初期化命令2の設計では、Fは短命令、Dは長命令を表し、θはこの命令のアドレスにθパラメータを加えることを表します。

これら3つの部分は、実際のマシンコードの18ビットの分割に対応しています：

少し考えてみると、Post\mathsf{Post}とN\mathsf{N}が同じエンコードを持たないようにすれば、曖昧性は生じないことがわかります。これは非常に簡単に満たすことができます。

❖関数呼び出し？

1951年のコンピュータがすでに関数呼び出しの能力を持っているとは、驚きです。少し安心するのは、この関数呼び出しはネストできないということです。

EDSAC上でこのように複雑な特性である関数呼び出しがどのように実装されているのでしょうか？実は、初期化命令1のプログラムでは関数呼び出しはできません。初期化命令2の登場は主にこの問題を解決するためのものです。

初期化命令2は一体どのような魔法を使ったのでしょうか？以前に言及したθパラメータを思い出してみてください。命令がθで終わる場合、そのアドレスは翻訳時にθパラメータの現在の値を加える必要があります。このメカニズムは、今日では「再配置」技術と呼ばれています。これにより、各プログラムは相対的な独立性を持つことができ、各プログラムは相対アドレスを参照することができ、これにより、単純なコピーだけで関数呼び出しを実現することができます。

具体的には、EDSACには標準ライブラリがあり、プログラマが特定のライブラリ関数を使用したいとき、彼はテキスト形式のプログラムに注記を付けます。そして、パンチャーを操作するオペレータがこの位置に到達すると、彼はテープコピーアでライブラリ関数をこのテープの対応する位置にコピーします2：

❖ブートストラップ？

世に信じられないことは三つある：一つは、知恵が全てを成し遂げられないこと、二つ目は、力が全てを持ち上げられないこと、三つ目は、強さが全てを勝つことができないこと。したがって、尧の知恵があっても人々の助けがなければ、大きな功績は達成できない。乌获の力があっても人々の助けがなければ、自分自身を持ち上げることはできない。贲、育の強さがあっても戦術がなければ、永遠に勝つことはできない。したがって、達成できない状況があり、成し遂げられない事がある。乌获は千鈞の重さを軽く感じるが、自身の重さを重く感じる。これは彼が千鈞より重いわけではなく、状況が適していないからだ。离硃は百歩を軽く感じるが、眉毛とまつ毛を難しく感じる。これは百歩が近く、眉毛とまつ毛が遠いわけではなく、道が適していないからだ。したがって、明智な君主は乌获を自己持ち上げ不能であるとして追い詰めず、离硃を自己視覚不能であるとして困らせない。可能な状況を利用し、容易な道を求めることで、力を少なく使い、功績と名声を立てる。時には満ち足りているか空虚か、事には利益と損害、物には生と死、人々の主がこれら三つに喜怒を表すならば、金石の士は心を離れる。聖賢の素朴さは深い。古代の明智な君主は人々を観察し、自分自身を観察させなかった。尧が一人では達成できないこと、乌获が自己持ち上げ不能であること、贲育が自己勝利不能であることを理解し、戦術を用いることで、行動の道を完全に理解した。

乌获は力持ちで、力持ちが多くのものを持ち上げることができますが、彼自身を持ち上げることができるでしょうか？

直感的には、もちろん無理です。形式的には、「持ち上げる」関係は反自反的であると言えます。

コンパイラの「自己ブートストラップ」はこの故事から来ています。L 言語のコンパイラ A が L 言語で書かれていると仮定すると、A を用いて A をコンパイルすることは「自己ブートストラップ」になります。

初期化命令も「ブートストラップ」の問題を持っています。初期化命令がなければ、テープ上のプログラムは全く実行できませんが、これまでに紹介したプログラムの入力方法はテープからの入力だけです。初期化命令がなければ、テープを読むことができず、テープを読むことができなければ、初期化命令を EDSAC に入力することはできません。

この問題をどのように解決しますか？論文3には次のように書かれています：

These orders are known as the initial orders and are permanently wired on a set of uniselectors. When the starting button is pressed, these orders are automatically transferred to the store and they then cause the input tape to be read.

初期化命令は、ユニセレクタと呼ばれる装置を通じて直接 EDSAC のメモリに書き込まれることがわかります。このユニセレクタはステッピングスイッチとも呼ばれ、電子に関する知識がないため、完全な説明はできません。

❖小さな問題

ここまで読んで、読者はこんなに偉大な初期化命令2が何行、あるいは何命令あるのか、自分で推測してみて、関連資料を調べてみてください。非常に驚くかもしれません。