Core Wars システムとアセンブラ（月刊ASCII 1987年9月号7）

「MARSシステム,およびREDCODEアセンブラについて」をスクラップする。これをもとにプログラムを作れるはずだ。

MARSシステム,およびREDCODEアセンブラについて
1. 概要
　Core Warsを行う仮想のシステムをMARSシステムと呼ぶ.このシステムは,MARSシミュレータとREDCODEアセンブラからなり,ユーザーの書いたCore Warsプログラムを,REDCODEアセンブラで翻訳し,MARSシステム上で動作させる.
　MARSシミュレータは,対戦する2つのプログラム“A”と“B”をメモリにロードし,最初に“A”の命令を実行すると,次は“B”の命令というふうに,交互にそれぞれのプログラムを処理していく.また,無効な命令コードを実行したプログラムの動作は,停止してしまう(正確には,SPL命令によって,1つのプログラムが複数のプロセスを持っているような場合,該当する1つのプロセスが停止する.最後の1つのプロセスが無効な命令コードを実行した場合,そのプログラムは,停止する).
　十分なマシンサイクルを経過しても,決着がつかない場合は,引き分けとなる.また,両方のプログラムが,停止するまでに,同じ数の有効な命令を実行した場合も,引き分けとなる。
　MARSシステムのメモリ空間については,7月号で述べたとおりであるが,現在,次のサイズのメモリ空間が考えられている.
a)　8Kword
b)　16Kword
c)　32Kword
d)　64Kword
　本誌では,PC-9801シリーズ用に32Kwordのものを提供するが,8bitマシンについては,8Kwordバージョンとならざるを得ないだろう.このメモリ空間は、最高番地から,最低番地へサイクリックに連続している.MARSシステムのメモリ空間は,一般のコンピュータのように,1枚の板のようなものではなく,エンドレステープのような構造をしている.
　すべての命令,およびデータは,いずれも1wordを占有する.アドレッシングは,基本的に相対指定からなっており,メモリ上の特定の番地をアクセスすることはできない.たとえば,1,000番地にデータを転送するといったことはできない.
　メモリ上のどの番地も,つねにアクセスすることができるが,それは,相対番地指定によってである.プログラムは,具体的な番地を知らないことになる.
　対戦する2つのプログラムは,乱数によって十分離れた番地にロードされ,実行される.競技の際には,実行するマシンサイクル数などが,あらかじめ決められる.

2. REDCODEアセンブラ
〈表記法〉
　Core Warsプログラムは,MARSシステムの仮想的なマシンのための機械命令で書かれる必要がある.これは,REDCODEと呼ばれるアセンブラ言語によって記述し,REDCODEアセンブラによって実行形式ファイルを生成することができる.
　REDCODEアセンブラは、非常にシンプルなアセンブリ言語である.ソースコードの1行が,1ステートメントに相当する.1ステートメントは,4つのフィールド(ラベル,オペレーション,オペランド,コメント)から構成される.
a) ラベルフィールド
　ラベルは,そのステートメントのマシン語のある番地を,他のステートメントから参照するのに使用するために，使うことができる。
　ラベルフィールドは、1ステートメント中の最初のフィールドであり,最初のブランクまでがラベルフィールドとなる.もしステニートメントの最初の文字が,ブランクであった場合は,ラベル無しのステートメントとみなされる(区切り文字としてのブランクとタブは,同等に扱われる).
　ラベルは,英数字からなる1～8桁の文字列であるが,最初の文字は,英字でなければならない.また,大文字,小文字は区別されない。
b) オペレーションフィールド
　オペレーションフィールドは、マシン語の命令を意味するオペレーションニーモニック,データ定義命令,アセンブラ疑似命令を記入するものである.このフィールドは、ラベルフィールドの次に位置し,少なくとも1桁のブランクの次に書かれる.また,大文字,小文字の区別はされない.通常10桁目から記入される.
c) オペランドフィールド
　オペランドフィールドは、0～2個の,カンマ,またはブランクで区切られたオペランドからなる.このフィールドは、オペレーションフィールドに続く1桁以上のブランクに続いて記入され,ブランクで終る.
　あるオペレーションは,1つのオペランドを必要とし,あるオペレーションは,2つのオペランドを必要とする.オペランドが1つの場合は,マシン語上“Bフィールド”と呼ばれるエリアに格納される(JMP命令を除く.詳しくは,MARSシステムの命令セットを参照のこと).オペランドが2つの場合,1つ目のオペランドは,Aフィールドに,2つ目のオペランドは,Bフィールドに格納される.
　オペランドフィールドは、通常16桁目から記入される.各オペランドは,“+”と“-”で区切られた数値とラベルシンボルからなる式を記述することができる.式は,左から右へ評価される.特別なラベルとして“*”がある.これは,そのステートメントがラベルを持っているいないにかかわらず,現在実行中のステートメントの番地を意味する.また,オペランドは,4つのアドレッシングモードを持っているが,これについては,アドレッシングモードの項を参照のこと.
d) コメントフィールド
　コメントフィールドは、オペランドフィールドの次にくる“;"から始まるフィールドである.REDCODEプログラマ,あるいは,他のプログラマに対する注釈として使用される.このフィールドは、生成されるオブジェクトに対しては,なんら意味を持っていない.
　特別な使い方として,ステートメントが,";"で始まる場合は,ステートメント全体が注釈として扱われる.
〈アドレッシングモード〉
　オペランドの評価に際して,MARSシステムは、オペランドのアドレッシングモードを見る.アドレッシングモードは,“イミディエイト(即値)”,“ダイレクト(直接)”,“インダイレクト(間接)",“オートデクリメントインダイレクト(自動減算・間接)”の4つがある.
　各アドレッシングモードの使い方については,本文中で説明した.
a) イミディエイト
　イミディエイトアドレッシングは,“#”によって示される.たとえば,#3は,数値の3を意味する.
b) ダイレクト
　ダイレクトアドレッシングは,"$"によって示される.また,アドレッシングモードを示すシンボルがなかった場合も,ダイレクトアドレッシングとみなされる.ダイレクトアドレッシングの例は,-123やABCであり,これらは,現在実行中の命令からの相対番地指定として扱われる.
c) インダイレクト
　インダイレクトアドレッシングは,“@”によって示される.ダイレクトアドレッシングと同様に番地を表すのに使われるが,文字どおり間接的にアクセスするものである。
　相対番地によって示された番地に格納されている値を相対番地として評価する.このとき,値が格納されている番地からの相対番地指定となることに注意する必要がある.
d) オートデクリメントインダイレクト
　オートデクリメントインダイレクトアドレッシングは,"<"によって示される.これは,インダイレクトアドレッシングと同様にポインタを使用して番地を指示するものである.インダイレクトと異なる点は,使用する前に,ポインタの内容が1引かれることである.
　ここで注意が必要なのは,実行アドレスを計算するときには(ポインタの値-1)を使って計算し,実行アドレスを計算してからポインタの値を1減らす,という点である.この順番は,一見どちらでも同じことのように思えるが,2つのオペランドのアドレッシングモードの両方がオートデクリメントインダイレクトであるときにMARSシステムの動作が異なることがありえるので,システムを自作してみようというような場合は,考慮する必要があるだろう.

〈MARS命令セット〉
　MARSシステムが実行する命令,あるいは,データを定義する命令について,オブジェクトのフォーマットも含めて,簡単に説明する.このオブジェクトのフォーマットについては,Core Wars Standard'86と'87では,若干異なる.もっとも,これは,大きなメモリをサポートするためのものであり,8Kwordバージョンについては,影響がないと考えて差し支えないように思われる.ICWS版のMARSシステムのオブジェクトのフォーマットは,オブジェクトについてを参照のこと.
　すべての命令について,すべてのアドレッシングモードが使用可能である(ただし,分岐命令の飛び先でイミディエイト指定することはできない).

DAT　B

0

1

0

0

B値

　この命令は,メモリを確保して,データを定義する.データの値は,B値に初期化される.もし、この命令を実行しようとした場合,そのプログラム,あるいはプロセスは,停止する.すなわち,DAT命令は,自分のプログラムのデータとして以外に,敵のプログラムの障害としての使用方法がある.

MOV　A,B

1

Aモード

Bモード

A値

B値

　A番地の値が,B番地に転送される.一般にA番地の1 word(5つのフィールドの内容すべて)が,B番地に転送される.注意しなければならないのは,A番地の指定がイミディエイトであった場合である.このとき,即値のAが,B番地のBフィールドに書き込まれる.したがって,0爆弾の記述として,“MOV　#0,　1234"といった記述がされてきたものについて,最新のMARSシステムでは,0爆弾として機能しないものが出てくる可能性がある.

ADD　A,B

2

Aモード

Bモード

A値

B値

　A番地の値が,B番地に加えられ,B番地の内容が更新される.

SUB　A,B

3

Aモード

Bモード

A値

B値

　A番地の値が,B番地から引かれ,B番地の内容が更新される.

JMP　A

4

Aモード

0

A値

0

　A番地がプログラムカウンタに移される.A番地からの命令が次に実行される.Bオペランドには,何があっても無効となる.

JMZ　A,B

5

Aモード

Bモード

A値

B値

　もし,B番地のBフィールドの値が0ならば,上記のJMP命令と同様に,A番地に分岐する.それ以外の場合は,これに続く命令に移る.

JMN　A,B

6

Aモード

Bモード

A値

B値

　もし,B番地のBフィールドの値が0でないなら、上記のJMP命令と同様に,A番地に分岐する.それ以外は,これに続く命令に移る.

DJN　A,B

7

Aモード

Bモード

A値

B値

　B番地のBフィールドの値から1減算される.もし,その結果が0でない場合,A番地へ分岐する.0の場合には,これに続く命令に移る.分岐するしないにかかわらず,B番地のBフィールドの値は,1減算される.減算が行われてから評価されるため,この命令が実行される前に0だった場合は,-1(インプリメントされているメモリサイズ-1)になるため,分岐が実行されることになる.
　別冊サイエンスの命令表には誤りがあるので,それを参照されている方は、注意する必要がある.

CMP　A,B

8

Aモード

Bモード

A値

B値

　A番地の値が,B番地の値と比較される.比較した結果,等しい場合には,これに続く命令がスキップされ,等しくない場合には,これに続く命令に移る.
　A番地とB番地の1 word(5つのフィールドすべて)について比較する.ただし,一方が,イミディエイトアドレッシングしている場合には,相手のBフィールドの値と比較する.
　この命令については,Core Wars Standard'86,および'87と,古い命令セットの判断基準が異なっているので,十分注意する必要がある.7月号221ページのANTIIMPというプログラムは,古い命令セットに沿って作られているために,現在の命令仕様では、動作しないことになってしまう.

SPL　B

9

0

Bモード

0

B値

　この命令は,プログラムの実行を現在のプロセスと,B番地から開始するプロセスに分割する.つまり,プログラムの実行サイクルが兄弟プロセスに分配される.SPL命令で2回にわたって分割されたプログラムは,3つの兄弟プロセスを持つことになる.それぞれは,相手のプログラムと合わせて6サイクルに1回実行されることになる.
　SPL命令の後,このサイド(競技する2つのプログラムを,それぞれ“サイド”と呼ぶ)で次に実行される命令は,B番地の命令であり,実行したSPL命令に続くステートメントや,他の兄弟プロセスではない。
　各サイドは,64の兄弟プロセスを持つことができ,全体で128の兄弟プログラムがMARSシステムでは許される.すなわち,これを越えてSPL命令を実行しても、兄弟のプロセスは,新たに発生しない。このような場合でも,MARSシステムは,何らメッセージを表示しない。

〈疑似命令〉
　疑似命令は,アセンブラに対する命令であり,オブジェクトコードは生成しない.

SPACE　N,M
　N行スキップし,同じページ上にM行残っていなかった場合,改ページする.
　Mを省略した場合には,Nと同じ値が指定されたとみなす.SPACEは,リスティングを読みやすくするように,たとえば,次のように使用することができる.あるステートメントブロックが存在し,それが,3行のコメント行から始まる場合,そのステートメントブロックの前に“SPACE2,3”と記述しておけば,2行のブランク行を確保した後,3行のステートメントが必ず1つのページにリスティングされる(この命令は,アセンブラによっては、サポートされていないこの場合,この命令ステートメントは無視される).

END
　END命令は,アセンブルの終りを示す.

3. オブジェクトについて
　オブジェクト形式については,基本的にREDCODEアセンブラと,それで生成されたオブジェクトを実行するMARSシミュレータとの間で整合性がとれていれば問題なく動作するわけであるが,ICWS版MARSシステムのオブジェクトは,次のような形式となっている。
　すなわち,テキストファイルの形として生成され,ASCII文字だけで表現されており,ヘッダレコード,コード,EOFレコードからなっている.なお,旧版のMARSシステムと異なり,命令wordを16進ダンプした文字イメージとなっている.これは,今回,MARSシステムのメモリ空間が広がったことに対応するためである.
〈ヘッダレコード〉
　最初に実行する命令のプログラムの先頭からの相対番地,およびコード部分のword数を持っている.
〈コード〉
　実際のプログラムのコード部分である.1命令は,次の構成からなる1 wordを16進ダンプイメージとした10桁のASCII文字列からなっている.
　各オペレーションコードについては,命令の説明の中で示した.アドレッシングモード(modeA,modeB)は,それぞれ次のような値となる.
・イミディエイト:　0
・ダイレクト:　1
・インダイレクト:　2
・オートデクリメントインダイレクト:　3
　また,古いシステムは,8,000番地のメモリ空間を持つものであったが,ICWS版では,2のn乗のメモリ空間を持つものとなっている.具体的には,各メモリ空間に相応して,オペランドの有効bit数が変化してくることになる.32Kwordバージョンでは,0～7FFFhまでが有効な値となる.
〈EOFレコード〉
　EOFレコードは、コードと同じ長さを持つ10桁のASCII文字の0からなるレコードである.
　具体的なオブジェクトの例を次に示す.これは,本文で紹介しているMICEのオブジェクトである.なお,ICWS版のMARSシステムでは、ソースコードについては“.RED",オブジェクトについては“.MOB”の拡張子を付ける.

4. MARSシステムの動作
　MARSシステムを作成するような場合や,本格的な戦いに入ってしまったプログラマにとっては,MARSシステムのより詳細な動作について知る必要が出てくるだろう.
　Core Wars Standardは,ICWSの入会者に配布される.ただし,現状では,Core Wars Standard'87の正式なドキュメントは届いていない.ここでは,問題となりそうな部分について述べることにする
〈オペレーションで使用されるフィールド〉
　各命令で使用されるフィールドの数を示す.1は,フィールドの値のみが使われることを意味し,5は,1word全体の5つのフィールドが使用されることを意味している.
〈プログラムキューのメンテナンス〉
　2つのプログラム(サイド)は,最初は,1つのプロセスしか持っていない.しかし,SPL命令によって,64個までのプロセスを持つことができることを先に述べた.このプロセスの管理は,プログラムキューによって行う.
　プロセスが1つしかない状態では,そのプログラムのプログラムカウンタは,プログラムキューの最初のセルに格納されている.その後ろには,63個のプログラムカウンタのためのセルが用意されているもちろん、相手のプログラムのために,このプログラムキュ-は,もう1セット用意されている.最初のSPL命令が実行されると,2番目のプログラムカウンタが2番目のセルに格納される.
　このキューをポインタが指しており,命令が実行されると次のプログラムカウンタが格納されているセルを指すようになっている.空のセルを指した場合には,1番目のセルを指すように制御される.
　複数のプロセスが存在する状態で,SPL命令を実行した場合,そのセル以降のセルを1つずつ下に移動し,プログラムキュー上に空きを作る.Bオペランドによって示される番地の絶対番地がその中に入れられる.SPL命令実行後には,ポインタが次のセルを示すので,次のサイクルでは、今生成されたばかりのプロセスが実行されることになる.
　プログラムが,実行不能な命令(データなど)を実行しようとした場合には,そのプロセスは停止する.プログラムキューのそのセルは削除され,それ以降のセルが1つずつ上に移動する.このとき,キューのポインタは更新されないため,次のサイクルでは、停止したプロセスの次に実行されるべきプロセスが,正しく実行される.
〈表示〉
　各プログラムの実行状況は,本文中に写真で示したようにグラフィックに表現される.各番地は、画面上で1ドット(あるいは,それに準ずるドットの集まり)で表現される.何も書かれていない状態では,その番地に相当する部分は,黒である.
　プログラムは,それぞれ色が決められており,プログラムのロードされた番地は,その色となる.また,プログラムによってデータ,または命令が書き込まれた番地も,同じ色となる.次に同じ番地を相手のプログラムが書き込みを行った場合には,上書きされる.また,実行中の番地は,点滅する.
　ただし,ICWS版のMARSシステムでは,便宜的に,MOV命令を行った命令の番地が黒になるようになっているようである.これは,いわゆるIMP(“MOV　0,　1”の1命令からなり,これ自身を1番地先に複写しながら,制御を移して行く)が実行された後は,連続してどちらかの色で塗りつぶされてしまい,全体の状況が見にくくなるのを防ぐ働きをするものだろう.もっとも,この工夫は,Core Warsの本質的な動作にかかわるものではない.

前回も書いたが3つ以上のプログラムによるバトルロイヤル、すなわち戦国時代をシミュレートするようなプログラムを誰か書かないかな。