Functions【Turing Complete編】
目次
はじめに
いつもブログをご覧いただきありがとうございます。
コーストFIRE中のIPUSIRONです😀
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命令のオペコードを新たに定義することになりますが、既存のオペコードと重複してはいけません。改めて既存のオペコードの一覧をここで示します。
1バイト目 | オペコード | 処理内容 |
---|---|---|
xy00 0000b | ADD | 引数1と引数2を加算した結果を転送先にセットする。 |
xy00 0001b | SUB | 引数1から引数2を減算した結果を転送先にセットする。 |
xy00 0010b | AND | 引数1と引数2をAND演算した結果を転送先にセットする。 |
xy00 0011b | OR | 引数1と引数2をOR演算した結果を転送先にセットする。 |
xy00 0100b | NOT | 引数1をビット反転した結果を転送先にセットする。 |
xy00 0101b | XOR | 引数1と引数2をXOR演算した結果を転送先にセットする。 |
0001 0000b(=16d) | LOAD_RAM | REG 5内のデータを指定アドレスとして、RAMにロードする(読み込む)。 |
0001 0001b(=17d) | SAVE_RAM | REG 5内のデータを指定アドレスとして、RAMにセーブ(保存)する。 |
0001 0010b(=18d) | PUSH | スタックにPUSHする。 |
0001 0011b(=19d) | POP | スタックからPOPする。 |
0010 0000b(=32d) | IF_EQUAL | 引数1と引数2が一致したら、指定のアドレスにジャンプする。 |
0010 0001b(=33d) | IF_NOT_EUQAL | 引数1と引数2が不一致なら、指定のアドレスにジャンプする。 |
0010 0010b(=34d) | IF_LESS | 引数1が引数2より小さいなら、指定のアドレスにジャンプする。 |
0010 0011b(=35d) | IF_LESS_OR_EQUAL | 引数1が引数2以下なら、指定のアドレスにジャンプする。 |
0010 0100b(=36d) | IF_GREATER | 引数1が引数2より大きいなら、指定のアドレスにジャンプする。 |
0010 0101b(=37d) | IF_GREATER_OR_EQUAL | 引数1が引数2以上なら、指定のアドレスにジャンプする。 |
指定の際に使う値 | 取り出す場所 or 格納する場所 |
---|---|
0 | REG 0 |
1 | REG 1 |
2 | REG 2 |
3 | REG 3 |
4 | REG 4 |
5 | REG 5 |
6 | カウンター |
7 | 転送元の場合は入力端子 転送先の場合は出力端子 |
オペコードと書式を決定する
CALL命令とRET命令はスタックに関係し、そのスタックはRAMで実現していることから、RAM系のオペコードとして扱います。
1バイト目 | オペコード | 処理内容 |
---|---|---|
0001 0100b(=20d) | CALL | サブルーチンを開始する。 |
0001 0101b(=21d) | RET | サブルーチンの呼び出し元に戻る。 ※厳密には呼び出し元アドレスの次のアドレスにジャンプする。 |
・CALL命令・・・戻り先アドレス(=CALL命令のアドレス+4バイト)を計算しスタックにPUSHする。その後、第1引数のアドレスにジャンプする。
・RET命令・・・スタックから戻り先アドレスをPOPし、そのアドレスにジャンプする
※ハードウェア的に指定のアドレスにジャンプするためには、プログラムカウンターの保持するカウンター値を上書きする回路が必要になります。
1命令は4バイトで構成されていました。今回追加するCALL命令とRET命令のフォーマットは次のように定義します。
1バイト目 | 2バイト目 | 3バイト目 | 4バイト目 |
---|---|---|---|
オペコード CALL | 第1引数 | なし | なし |
0001 0100b(=20d) | サブルーチンの開始アドレス | 1111 1111b(未割り当て用) | 1111 1111b(未割り当て用) |
1バイト目 | 2バイト目 | 3バイト目 | 4バイト目 |
---|---|---|---|
オペコード RET | なし | なし | なし |
0001 0101b(=21d) | 1111 1111b(未割り当て用) | 1111 1111b(未割り当て用) | 1111 1111b(未割り当て用) |
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命令についてのテストができなくても、過去のステージに戻ってテストさせれば既存の回路に影響を与えていないかどうかをテストできます。
実施しておくとよいテストのあるステージは次の通りです。
以前のステージを開くと、最終的に作り上げた回路が引き継がれているはずです。[Run]ボタンからテストを実行してください。テストをパスすれば、デグレードしてないと判断できます。
2:CALL命令とRET命令を使ったプログラムを作ってテストする
クリア済みのステージにおいて、CALL命令やRET命令を使ったプログラムに書き換えれば、サブルーチン回路のテストができます。
PUSH and POPステージやDivideステージに戻ります。この中ではジャンプ命令があるので、テストに使えそうです。ここでは、PUSH and POPステージのテストを利用することにします。
PUSH and POPステージのProgramコンポーネントで使ったプログラムにちょっと手を加えて、CALL命令とRET命令を使うようにします。
No.1の処理をサブルーチン側で実行することにします。
修正後のプログラムは次の通りです。
No. | アドレス | 1バイト目 | 2バイト目 | 3バイト目 | 4バイト目 | 処理内容 |
---|---|---|---|---|---|---|
1 | 00h | 0001 0100b(=20d) ※CALL | SubRoutine1 | 1111 1111b(=255d) | 1111 1111b(=255d) | SubRoutine1を呼び出す。 |
2 | 04h | 0100 0000b(=64d) ※ADDかつImmediateモード | 0000 0111b(=7d) ※入力端子 | 0000 0000b(=0d) ※即値 | 0000 0001b(=1d) ※REG 1 | 入力端子からくるバイトデータをREG 1に保存する。 ※ADD命令で代用している。 |
3 | 08h | 0010 0000b(=32d) ※IF_EQUAL | 0000 0001b(=1d) ※REG 1 | 0000 0011b(=3d) ※REG 3 | 0001 0100b(=20d) ※アドレス14h | REG 1とREG 3(ゼロ固定)を比較して、一致したら指定アドレスにジャンプする。 |
4 | 0Ch | 0001 0010b(=18d) ※PUSH | 0000 0001b(=1d) ※REG 1 | 1111 1111b(=255d) ※未使用 | 1111 1111b(=255d) ※未使用 | REG 1をスタックにPUSHする。 |
5 | 10h | 0010 0000b(=32d) ※IF_EQUAL | 0000 0011b(=3d) ※REG 3 | 0000 0011b(=3d) ※REG 3 | 0000 0100b(=4d) ※アドレス04h | 指定アドレスに無条件ジャンプ。 ※IF_EQUALで代用している。 |
6 | 14h | 0001 0011b(=19d) ※POP | 1111 1111b(=255d) ※未使用 | 1111 1111b(=255d) ※未使用 | 0000 0111b(=7d) ※出力端子 | スタックからPOPして、出力端子に送る。 |
7 | 18h | 0010 0000b(=32d) ※IF_EQUAL | 0000 0011b(=3d) ※REG 3 | 0000 0011b(=3d) ※REG 3 | 0000 0100b(=4d) ※アドレス04h | 指定アドレスに無条件ジャンプ。 |
8 | 1Ch ※ラベル"SubRoutine1″ | 0000 0101b(=5d) ※XOR | 0000 0011b(=3d) ※REG 3 | 0000 0011b(=3d) ※REG 3 | 0000 0011b(=3d) ※REG 3 | 比較用の定数ゼロをREG 3に用意する。 ※Conditionモードの命令は即値が使えないので、定数をレジスターに保存しておく必要がある。 |
9 | 20h | 0001 0101b(=21d) ※RET | 1111 1111b(=255d) | 1111 1111b(=255d) | 1111 1111b(=255d) | SubRoutine1を抜ける。 |
実際にアセンブリーエディターに入力するプログラムは次の通りです。
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:サブルーチンのネストをテストする
サブルーチンをネストしても動作することを確認します。
No. | アドレス | 1バイト目 | 2バイト目 | 3バイト目 | 4バイト目 | 処理内容 |
---|---|---|---|---|---|---|
1 | 00h | 0001 0100b(=20d) ※CALL | 1Ch(=28d) ※SubRoutine1 | 1111 1111b(=255d) | 1111 1111b(=255d) | SubRoutine1を呼び出す。 |
2 | 04h | 0100 0000b(=64d) ※ADDかつImmediateモード | 0000 0111b(=7d) ※入力端子 | 0000 0000b(=0d) ※即値 | 0000 0001b(=1d) ※REG 1 | 入力端子からくるバイトデータをREG 1に保存する。 ※ADD命令で代用している。 |
3 | 08h | 0010 0000b(=32d) ※IF_EQUAL | 0000 0001b(=1d) ※REG 1 | 0000 0011b(=3d) ※REG 3 | 0001 0100b(=20d) ※アドレス14h | REG 1とREG 3(ゼロ固定)を比較して、一致したら指定アドレスにジャンプする。 |
4 | 0Ch | 0001 0010b(=18d) ※PUSH | 0000 0001b(=1d) ※REG 1 | 1111 1111b(=255d) ※未使用 | 1111 1111b(=255d) ※未使用 | REG 1をスタックにPUSHする。 |
5 | 10h | 0010 0000b(=32d) ※IF_EQUAL | 0000 0011b(=3d) ※REG 3 | 0000 0011b(=3d) ※REG 3 | 0000 0100b(=4d) ※アドレス04h | 指定アドレスに無条件ジャンプ。 ※IF_EQUALで代用している。 |
6 | 14h | 0001 0011b(=19d) ※POP | 1111 1111b(=255d) ※未使用 | 1111 1111b(=255d) ※未使用 | 0000 0111b(=7d) ※出力端子 | スタックからPOPして、出力端子に送る。 |
7 | 18h | 0010 0000b(=32d) ※IF_EQUAL | 0000 0011b(=3d) ※REG 3 | 0000 0011b(=3d) ※REG 3 | 0000 0100b(=4d) ※アドレス04h | 指定アドレスに無条件ジャンプ。 |
8 | 1Ch ※ラベル"SubRoutine1″ | 0001 0100b(=20d) ※CALL | 24h(=36d) ※SubRoutine2 | 1111 1111b(=255d) | 1111 1111b(=255d) | SubRoutine2を呼び出す。 |
9 | 20h | 0001 0101b(=21d) ※RET | 1111 1111b(=255d) | 1111 1111b(=255d) | 1111 1111b(=255d) | SubRoutine1を抜ける。 |
10 | 24h ※ラベル"SubRoutine2″ | 0000 0101b(=5d) ※XOR | 0000 0011b(=3d) ※REG 3 | 0000 0011b(=3d) ※REG 3 | 0000 0011b(=3d) ※REG 3 | 比較用の定数ゼロをREG 3に用意する。 ※Conditionモードの命令は即値が使えないので、定数をレジスターに保存しておく必要がある。 |
11 | 28h | 0001 0101b(=21d) ※RET | 1111 1111b(=255d) | 1111 1111b(=255d) | 1111 1111b(=255d) | SubRoutine2を抜ける。 |
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本つないだらまたテストします。これを繰り返すことでバグのある場所を絞り込めます。

実際にこの戦法でバグを発見でき、すぐに修正できました。
回路設計やプログラミングにはバグがつきものです。
バグがあったとしても、すぐに気づいて修正できれば問題を最小限にできます。
問題なのは、バグがあることに気づかずどんどん進めてしまい、後でバグの存在に気づくことです。その頃には回路やプログラムが複雑になっているので、バグの箇所の特定に時間がかかりますし、複雑さが増した分整合性を取りにくくなります。バグを修正したら別の不具合が発生したという、いわゆるデグレードの危険性が増してしまうのです。
おわりに
お疲れ様でした。
本ステージでFunctionsカテゴリーは終了になります。
ただし、本ステージではテストがありませんでした。以降のステージで異常が出たら、本ステージの実装が誤っている可能性について見直してください。
References
↑1 | 最初に追加したスタックのことです。本ステージで追加するスタックは、戻り先アドレス用なので、それ以外のデータの保存には使いません。 |
---|