Calibrating Laser Cannons【Turing Complete編】

2023年9月12日

Calibrating Laser Cannonsステージ

「レーザー砲の校正のために、高度な式（2πr）を使って隕石の円周を計算して欲しい。ただし、πは3としてよい。計算を終えたら、その答えを出力に送って欲しい」という要請です。

つまり、Calibrating Laser Cannons（レーザー砲の校正）ステージのゴールは、上記の指示にしたがって、入力を6倍（＝2×3）して出力するプログラムを作ることです。

アセンブリーエディター

プログラムメモリーの右上の鉛筆アイコンを押すと、シミュレーター上にアセンブリーエディターが起動します。

※前ステージではバイナリーエディターが起動しましたが、これからはアセンブリーエディターが起動します。

・左上：プログラムの操作インターフェース。ステップ実行（1行ずつ実行）もできる。

・左下：命令の定義

・中央：アセンブリコードの記述部。タブで新規プログラムを追加できます。実行対象のプログラムをアクティブにする。

・右上：Level Screen

・右下：Link components

※使う場面になったら解説します。

独自の命令名を定義できる

アセンブリーエディターの左側に列挙されている文字列は、定義された命令名になります。

※アセンブリー言語の世界でいうニーモニック^[1]コンピューターが解釈するマシン語を、人間に分かりやすい形式で表現した記号のことです。に相当します。

[Add]ボタンを押して、特定のInstructionビット列に対して、好きな命令名を定義できるようになります。

既存の命令について確認してみます。

例えば、"add"という命令名をクリックすると、対応するアセンブリコード、すなわちInstructionビット列が表示されます。0100 0100bはCalculationモードのADD演算を意味します。

ここで1つ命令を定義してみます^[2]ここで定義した命令はステージの攻略で使います。。

“input_to_reg1″という命令名にしたいのですが、命令名は最大10文字までなので、"in_to_reg1″とします。

指定のInstructionビット列が正しいかどうかを確認するために、隣にInstructionsのマニュアルを表示させています。

アセンブリー言語でプログラミングできる

アセンブリーエディターの中央部分では、アセンブリー言語のプログラムを記述できます。

7行表示されていますが、最初の2行はコメントなので無視できます。以降の5行は、1+1を実現するプログラムになります。

※各行それぞれ、1バイトデータのInstructionビット列（一般のコンピュータ用語でいうとマシン語）に対応しています。

キャンバス上のプログラムメモリーを見ると、「1 129 130 68 158 0 ･･･」と並んでいて、上記のアセンブリコードに対応する10進数値の数列と一致します。

※マイナス表記になっていたら、ナンバーフォーマットを切り替えてください。

Calibrating Laser Cannonsステージを解く

入力の6倍して出力するプログラムを作成します。

1：プログラムの設計方針を決める

レジスターを介して入出力はCopyモードで実現できますので、問題は乗算の処理になります。

CPUには乗算の仕組みは備わっていません。そこで、加算を繰り返して乗算を実現するという素朴な方法を採用します。

入力値を5回足せば、6倍した結果と同じです。

$R+R+R+R+R+R$

$((((R+R)+R)+R)+R)+R$

以上でプログラムの設計方針は決定しました。

2：具体的な処理内容に落とし込む

※未定義の命令については、定義してください。in_to_reg1は定義済みなので、reg1_to_reg2、reg3_to_reg2を追加で定義します。

※addが5回登場することになります。

3：コーディングする

「+」を押してコード入力タブを新規に作ります。タブ名は"new_program"となっています。

私はブログの記事のためにexampleコードを取っておきます。読者の方はexampleコードを編集しても構いません。

ここにアセンブリーコードを記述していきます。

# 2×π×Rを計算して出力する.
# ただし、Rは入力バイトデータ.
in_to_reg1
reg1_to_reg2
add
reg3_to_reg2
add
reg3_to_reg2
add
reg3_to_reg2
add
reg3_to_reg2
add
reg3_to_reg2
reg3_to_out

コードの左側にある数値は、コメントを含めた行番号です。コードの右側にある数値は、コメントを除いた行番号です。

右側の数値が12になっていれば、命令が12個並んでいることを意味します。ステップ2で考えた処理は12命令あり、数が一致しているので問題なさそうです。

また、入力した命令の文字色がすべて緑色になっていることを確認してください。定義済みの命令は緑色、未定義の命令は白色になります。白色の命令が1つでもあれば、記述ミスか、定義忘れのどちらかになります。

4：テストする

アセンブリーエディターの左上にある「Run」ボタンを押します。

右上のLevel Screenに様々な隕石が表示されます。それに伴い、隕石の半径（Level Screenの右下のR）が入力され、計算が始まります。

すべての隕石の計算が正常に終われば、クリアになります。

2倍した結果を利用してコードを短くする【別解】

ステージはクリアできましたが、もう少し回答を整理してみます。

同じ処理が5個もあり、本当は共通化したいところですが、現状のCPUではできません。

それでも5回の加算を減らす方法はあります。

2倍した結果（R+R）を保存しておき、それを使い回すのです。

$tmp \leftarrow R + R, result \leftarrow tmp + tmp, result \leftarrow result + tmp$

※コードが12行から10行に減りました。同時にaddが5回から3回に減りました。

この一連の処理をコーディングすると次のようになります。

定義済み、未定義にかかわらず、命令を1行ずつ入力していきます。すべてを入力すると次のようになります。

# 2×π×Rを計算して出力する.
# ただし、Rは入力バイトデータ.
in_to_reg0
reg0_to_reg1
reg0_to_reg2
reg0_to_reg2
add
reg3_to_reg1
reg3_to_reg2
add
reg3_to_reg1
add
reg3_to_out

白色の命令があれば、それは未定義のものであり、これが緑色になるように定義すればよいのです。

※先に命令をすべて入力してから、未定義がなくなるまで定義していくという手順だと、スムーズに作業ができます。

※未定義の命令は正しく認識されておらず、右側の行番号も飛ばされています。

ro_to_reg0、reg3_to_reg1を定義します。

完成したコードは次の通りです。テストにパスしました。

従来のアセンブリー言語風の書式に改良する【別解2】

1：入力値をREG 0に記憶するin命令（これまでのin_to_reg0）を定義します。

2：REG 0の内容を出力値とするout命令（これまでのreg0_to_out）を定義します。

転送元はREG 0固定です。

※後述するmov命令で直前に任意のレジスターからREG 0にセットし、その後でout命令を実行すれば、実質的に任意のレジスターの内容を出力できます。ただし、REG 0の内容は上書きされます。その内容を後で使うのであれば、使っていないレジスターに一時退避しなければなりません。この処理が面倒な場合は、「out+<転送元レジスター>」のように記述すれば、そのレジスターの内容を出力値にできます。バイナリ列の加算だからです。

3：レジスター間でデータを転送するmov命令を定義します。

転送元と転送先は「＋」で指定することにします。

今回のプログラムで使う転送元はREG 0とREG 3、転送先はREG 1とREG 2です。REG 0は0bなので定義する必要はありません。mov命令で転送元と転送先を省略した場合は実質的にREG 0を使っていることになります。

この3つの転送元・転送先を意味する文字列を定義します。定数として定義するのも冗長ですので、本当は命令ではありませんが、ここでは命令のところで定義します。

※従来のアセンブリー言語でいうと、これらの転送元や転送先はニーモニックの引数であり、オペランドといいます。

※これらの定義では、上位2桁は00bとします。これはモードを意味する他の命令と組み合わせて使うためです。

4：別解のコードをコピー＆ペースとして、これまでに定義した命令に置き換えていきましょう。

最終的に次のコードになります。

# 2×π×Rを計算して出力する.
# ただし、Rは入力バイトデータ.
in
mov+reg1_dest
mov+reg2_dest
mov+reg2_dest
add
mov+reg3_src+reg1_dest
mov+reg3_src+reg2_dest
add
mov+reg3_src+reg1_dest
add
mov+reg3_src
out