Functions【Turing Complete編】

2023年9月12日

Functionsステージ

いよいよLevel mapにおけるFunctionsカテゴリーの最終ステージになります。

Functionsステージのゴールは、CALL命令とRET命令を扱えるように回路を組み、プログラム上でサブルーチンを実現することです。

サブルーチンを使えば、一部の処理を再活用できます。サブルーチンの先頭にジャンプする際にCALL命令を使い、サブルーチンの最後に到達して元のルートに戻る際にRET命令を使います。

元のルートに戻るためには、サブルーチンの先頭にジャンプする時点で、ジャンプする直前のアドレスを記憶しておかなければなりません。このアドレスを戻りアドレスと呼びます。

サブルーチンAがサブルーチンBを呼び出し、サブルーチンBがサブルーチンCを呼び出すという状況もありえます。サブルーチンCが終了する際にはサブルーチンBへの戻りアドレスのみが必要になります。そして、サブルーチンBが終了する際にはサブルーチンAへの戻りアドレスが必要になります。つまり、サブルーチンの呼び出しについて多重化（ネスト）していても、最後にスタックに追加した戻りアドレスが、RET命令の時に常に最新の戻りアドレスが必要になるわけです。

「後入れ先出し」になっており、これを実現するにはスタック構造がもってこいといえます。

CALL命令とRET命令

サブルーチンの呼び出しをCALL命令とRET命令で実現できます。

サブルーチンから戻ったら、CALL命令のアドレスの次のアドレスから処理を開始しなければなりません。もしCALL命令のアドレスから処理を開始したら、またCALL命令によってサブルーチンが呼び出されてしまいます。つまり、無限ループになってしまいます。

そこで、「戻りアドレス＝CALL命令の次のアドレス（＝CALL命令のアドレス＋命令幅）」とし、CALL命令では次の動作を行うものとします。この動作はハードウェアで実装することになります。

・戻りアドレスをスタックにPUSHする。その後、サブルーチンの先頭アドレスにジャンプする。

※CALL命令時は、CALL命令のあるアドレスをPUSHし、RET命令時にPOPしたアドレスに加算するという方法もあります。どちらを採用するかは自由ですが、本ページでは加算してからPUSHすることにしました。従来のアセンブリー言語でよくある設計であるためです。

そして、RET命令では次のことを行います。

・スタックから戻りアドレスをPOPして、そのアドレスにジャンプする。

サブルーチン間でデータをやりとりしたい

サブルーチン間でデータをやりとりするには、レジスター、RAMメモリー、スタック^[1]最初に追加したスタックのことです。本ステージで追加するスタックは、戻り先アドレス用なので、それ以外のデータの保存には使いません。を使えます。

どれを使ってもよいですが、アセンブリー言語のルールとして「引数にはスタックを使う」「戻り値にはレジスターを使う」のように決めておくべきです。

※例えば、x86アーキテクチャーではレジスターが少ないので、スタックで引数をやりとりします。

既存のオペコード一覧

CALL命令とRET命令のオペコードを新たに定義することになりますが、既存のオペコードと重複してはいけません。改めて既存のオペコードの一覧をここで示します。

オペコードと書式を決定する

CALL命令とRET命令はスタックに関係し、そのスタックはRAMで実現していることから、RAM系のオペコードとして扱います。

・CALL命令･･･戻り先アドレス（＝CALL命令のアドレス＋4バイト）を計算しスタックにPUSHする。その後、第1引数のアドレスにジャンプする。

・RET命令･･･スタックから戻り先アドレスをPOPし、そのアドレスにジャンプする

※ハードウェア的に指定のアドレスにジャンプするためには、プログラムカウンターの保持するカウンター値を上書きする回路が必要になります。

1命令は4バイトで構成されていました。今回追加するCALL命令とRET命令のフォーマットは次のように定義します。

Functionsステージを解く

1：サブルーチン用のスタックの周辺回路を実装する

サブルーチン用のスタックを用意します。このスタックには、戻り先アドレスだけを保存します。スタックに入るデータは4を加算するようにしています。

スタック周辺は比較的簡単ですが、問題はプログラムカウンターの上書き処理です。これについては後で解説します。

周辺回路をワイヤリングすると次のようになります。

※今回のワイヤリングは黄色にしました。

※簡単なワイヤーコメントを追加してあります（方法は後述）。また、スペースの関係上、Level Screenを移動させました

2：ワイヤーにコメントを入れる

[Alt]キーを押しながらワイヤーの先端を選ぶと、先端を引っ張り、引き直せます。

ワイヤーの色を変更するボタンの左に「Wire comment」ボタンがあります。ボタンを押した状態で、ワイヤーを左クリックすることでコメントをつけられます。ワイヤーにどういったデータが流れるのかわかりやすいコメントを必要に応じてつけるとよいでしょう。

3：プログラムカウンター周辺を修正して整合性を保つ

CALL命令とRET命令のいずれもジャンプします。つまり、プログラムカウンターにアドレスを渡して上書きする処理が走らなければなりません。渡すべきアドレスは、CALL命令の場合は第1引数のジャンプ先アドレス、RET命令の場合はスタックから出力される戻り先アドレスになります。

これを回路に実装するのはそれほど難しくありませんが、既存のLEGアーキテクチャーの回路を維持したまま組み込むのが難しいのです。OR回路やSwitch回路を駆使して、実装した結果が次の通りです。

4：ステージを終える

本ステージにはテストがありません。"We thought better of you."に対して、[Level is complete]ボタンを押すと、"Can you trust you?"と尋ねられます。

[Yes]ボタンを押すと、ステージクリアになります。[No]ボタンを押すと、"We thought better of you."のメッセージに戻ります。

CALL命令とRET命令をテストする

1：クリア済みのステージで再テストする

CALL命令とRET命令についてのテストができなくても、過去のステージに戻ってテストさせれば既存の回路に影響を与えていないかどうかをテストできます。

実施しておくとよいテストのあるステージは次の通りです。

• Divideステージ
• PUSH and POPステージ
• RAMステージ

以前のステージを開くと、最終的に作り上げた回路が引き継がれているはずです。[Run]ボタンからテストを実行してください。テストをパスすれば、デグレードしてないと判断できます。

2：CALL命令とRET命令を使ったプログラムを作ってテストする

クリア済みのステージにおいて、CALL命令やRET命令を使ったプログラムに書き換えれば、サブルーチン回路のテストができます。

PUSH and POPステージやDivideステージに戻ります。この中ではジャンプ命令があるので、テストに使えそうです。ここでは、PUSH and POPステージのテストを利用することにします。

PUSH and POPステージのProgramコンポーネントで使ったプログラムにちょっと手を加えて、CALL命令とRET命令を使うようにします。

No.1の処理をサブルーチン側で実行することにします。

修正後のプログラムは次の通りです。

実際にアセンブリーエディターに入力するプログラムは次の通りです。

20 SubRoutine1 255 255
64 7 0 1
32 1 3 20
18 1 255 255
32 3 3 4
19 255 255 7
32 3 3 4
label SubRoutine1
5 3 3 3
21 255 255 255

3：サブルーチンのネストをテストする

サブルーチンをネストしても動作することを確認します。

20 SubRoutine1 255 255
64 7 0 1
32 1 3 20
18 1 255 255
32 3 3 4
19 255 255 7
32 3 3 4
label SubRoutine1
20 SubRoutine2 255 255
21 255 255 255
label SubRoutine2
5 3 3 3
21 255 255 255

テストが失敗したら

もし「テストがNGになる」「無限ループでテストが終わらない」といった場合はどこかにバグがあります。

追加した回路に問題があるのか、もともとバグがあったのかを確認したい場合は、追加した回路とつながったワイヤーの一部を切断しておきます。長いワイヤーを消すと元のつながりがわからなくなるので、ハサミでカットするようなイメージで短く切ります。

テストがパスしたら、大丈夫と思われるワイヤーから元のつなげた状態に戻します。1本つないだらまたテストします。これを繰り返すことでバグのある場所を絞り込めます。

おわりに