［今日のPiet］スタック内のランダムアクセス（３）
前々回まで、Pietのスタックを、あたかも通常のメモリのように使う方法を考えていました。
ymos-hobby-programing.hatenablog.com
そこで、前回は、全てのメモリ操作の基本となる
「メモリアドレス変換関数」を設計したところで終わっていました。
ymos-hobby-programing.hatenablog.com
今日は、そのソースコードの解説をします。
途中スタックの状態を可視化するツールを作ってお遊びしていましたが、
ymos-hobby-programing.hatenablog.com
このツールの力を借りても、まあ労力がかかるかかる。
ということで解説が遅くなりすみませんでした。
・・・とか言いつつ、書き切れませんでしたが。
解説に入る前に
「メモリ・アドレス変換関数」（以下「ptr関数」）の設計で一点訂正です。
前回の解説では、メモリの「基本形」に、メモリ番号m、アドレスnをプッシュした状態
この状態に「ptr関数」を適用して、次の状態にすることが目標としていました。
Sはメモリ番号m・アドレスnのスタック上の位置、
Nはメモリの長さ、Fはエラーフラグでした。
ですが、その後色々試して「ptr関数」適用後の状態を次のように変更した方がいいことがわかりました。
出力される値（緑色）に、メモリ個数Mを追加しました。
今回はこの訂正後の「ptr関数」の解説をしていきます。
処理フローファイル
Pietソースコードは拙作の「GridPietGenerator」で生成しますが、
Pietに実行させたい処理をテキストファイル（以下、「処理フローファイル」）で
記述する必要があるのでした。
まずは、処理フローファイルの内容を載せたいと思います。
処理フローファイルを見る
:len_mem push4 push2 push6 push3 :num_mem push4 :sum_mem push15 :push_address inn inn ######################################## ## ptr ######################################## :ptr :ptr_check_m push4 push1 roll dup push5 push3 roll dup push6 push1 roll push1 add push3 push2 roll push1 dup sub push3 push1 goto:ptr_inorder :ptr_inorder_ret1 if::ptr_err :ptr_check_n push1 goto:ptr_sub_R :ptr_sub_R_ret1 dup push5 add push1 push2 sub roll dup push3 push2 roll push5 add push1 roll push1 add push2 push1 roll dup push3 push1 roll push1 push2 sub push3 push2 goto:ptr_inorder :ptr_inorder_ret2 if::ptr_err :ptr_calc push2 goto:ptr_sub_R :ptr_sub_R_ret2 dup dup push7 push6 roll dup dup dup push10 push1 roll push5 push1 roll push3 push1 roll push9 add push2 roll :ptr_emb_num_mems push5 push4 roll dup push6 push1 roll push1 sub push2 push1 roll push7 add push1 roll :ptr_move2top push7 add push2 push1 roll push4 add roll goto:ptr_sum :ptr_sum_ret push2 push1 roll dup push3 push1 roll push4 add push1 roll :ptr_prep_rewind push2 add push1 push3 sub roll :ptr_rewind push5 add push1 push2 sub mul push2 push1 roll push5 add push2 push1 roll roll :ptr_add_ofs push2 push1 roll dup push3 push1 roll add :ptr_dup_N push4 push3 roll dup push5 push1 roll :ptr_dup_M push6 push5 roll dup push7 push1 roll push1 goto:ptr_end :ptr_err push1 dup sub dup dup dup goto:ptr_end :ptr_sub_R push5 push1 roll push4 push3 roll dup push4 push3 roll dup push5 push1 roll sub push1 add push2 push1 roll push5 push1 roll push6 push5 roll push1 sub if:ptr_sub_R_ret2:ptr_sub_R_ret1 :ptr_sum ######################################## ## sum ######################################## :sum dup push1 dup sub push3 push1 roll :sum_loop dup if::sum_end push4 push2 roll push2 push1 roll dup push5 push1 roll add push3 push1 roll push1 sub push3 push1 roll dup push4 push3 roll push5 push4 roll push3 push2 roll push3 add push1 roll goto:sum_loop :sum_end pop push2 push1 roll ######################################## ## /sum ######################################## goto:ptr_sum_ret :ptr_inorder push2 push1 roll dup push3 push1 roll push2 add push1 roll ######################################## ## inorder ######################################## :inorder push1 push2 push1 roll dup if::inorder_err :inorder_loop dup push1 sub if::inorder_end push4 push3 roll dup push5 push4 roll gt push4 push3 roll mul push3 push2 roll push1 sub goto:inorder_loop :inorder_err pop pop push1 dup sub dup dup :inorder_end push3 push2 roll pop pop ######################################## ## inorder ######################################## push2 push1 roll push1 sub if:ptr_inorder_ret2:ptr_inorder_ret1 :ptr_end ######################################## ## /ptr ######################################## outn push4 dup push2 mul mul outc outn push4 dup push2 mul mul outc outn push4 dup push2 mul mul outc outn end
今回から処理フローファイルの行末コメントは削除しました。
これにより、文字数はなんと1/3まで削減されました。
コメントの字数の多かったことよ・・・。
行末コメントは、その時々のスタックの状態をメモ程度に書いていたものです。
書き方の一貫性がなかったことや、一貫性を持たせるのが少々難しかったので、
今後はスタック画像で説明したいと思います。
解説
解説は長いので、折りたたみました。 興味のある箇所を開いてみてください。
冒頭（1-12行目、
ここは、スタック内にメモリを展開し、:ptrまで）
メモリ番号ｍとアドレスｎをユーザーに入力させています。
具体的には前回例として取り上げた、以下のメモリを作っています。
- メモリ数Mが4
- メモリ全体の長さNは15（=4+2+6+3）
ただし、今回作る関数は、メモリ本体（図の青っぽい色の部分）に
アクセスしないため、メモリ本体部分は省きました。
（なくても動作しますし、わざわざ入れると訳がわからなくなるので。）
つまり、今回は、
- 各メモリの長さ（＝アドレスの最大値）
、・・・、
- メモリの個数M
- メモリ全体の長さN （＝
）
- 位置を求めるメモリ番号mとアドレスn（ユーザー入力）
のみを格納しています。
より一般的にこの時のスタックの状態を表現すると、以下のようになります。
「ptr関数」では、スタックを最終的に、次の状態にします。
ユーザー入力mのチェック（13-21行目、
:ptr_check_mから:ptr_check_nの前まで）
ここでは、
- ユーザーが入力したmに対応するメモリがあるか
- ユーザーが入力したnに対応するアドレスがメモリm内にあるか
を順番にチェックします。
チェックには以前説明した「順序判定関数」を利用します。
ymos-hobby-programing.hatenablog.com
メモリ番号ｍ
まず、メモリ番号ｍは以下の条件を満たす必要があります。
つまり
「順序判定関数」を利用する場合は、スタックトップを次の状態にする必要があります。
「順序判定関数」を適用すると、スタックの状態は次のようになります。
Rは判定結果で、を満たすなら1が、そうでなければ0が格納されます。
この結果によってmが条件を満たしているかを判定することができます。
判定までのスタック操作
「順序判定関数」では、mやMの値を使う必要があるので、まずmを複製します。
最初は次のような状態になっています。
mをスタックトップに移動するには、現在スタックトップにあるnを一旦どける必要があります。
例えば、スタックに４、１を順にプッシュしてroll命令を実行します。
roll命令は、スタックトップから２つだけ値を取り出して、その値に応じてスタックの値を回転させます。
この場合は、
スタックトップから4番目の位置に、スタックトップの値を埋め込む操作を1回行う、
ということなので、スタックトップのnが埋め込まれ、mがスタックトップにきます。
この状態でdup命令を実行すれば、スタックトップのmがコピーされます。
ちょっと脱線
もし、この次の命令が、push5 push4 rollなら、スタックは次のようになり、
さらにpush2 push1 rollを実行すると、スタックは次のようになります。
これは、操作を始める前の状態に対して、
あたかもスタック内にあった値mを複製して、プッシュしたかのように見えます。
このように、Pietではスタックトップにある値にしか操作できないため、
操作対象の値をスタックトップに移動→操作→操作対象の値を元の位置に戻す
という操作を地道に繰り返して、スタックの状態を変化させていきます。
閑話休題
話を戻します。今、スタックの状態は以下のようになっていました。
実際には、次にMを複製する必要があるため、push5 push3 rollの順に実行します。
これは、
スタックトップから5番目の位置に、スタックトップの値を埋め込む操作を3回繰り返す、
という意味なので、m、m、Nが順に埋め込まれ、最終的にスタックトップにはMが現れます。
この後dup命令でMを複製します。
その後push6 push1 rollでMの一つを元の位置に戻します。
最後に、push1 addで、スタックトップのMに1を足す操作をして、
push3 push2 rollで、mをスタックトップに持ってくれば
このように、初めのスタックの状態
に対して、M+1、mをこの順でプッシュしたかのような状態
になります。
あとは、0、3をこの順でプッシュすれば、
順序判定関数に入れる準備が完了します。
ここではさらに1をプッシュして、以下の状態にします。
最後にプッシュした1については、後で説明します。
「順序判定関数」適用後のスタックの状態は次のようになります。
mの値は、R＝1なら適切、R＝0なら不適切となるため、
この値を使ってif命令で分岐して、アドレスnの判定に移行するか、
エラー処理に移行するかを決めます。
ユーザー入力nのチェック（23-35行目、
:ptr_check_nから:ptr_calcの前まで）
アドレスnの判定
次にアドレスnの判定をしますが、メモリ番号mの判定と
同様の流れになりますので、詳細は割愛します。
nの満たすべき条件は次の通りです。
つまり
なお、諸事情により、ここではn=0でもOKとしています。
この条件が満たされているかどうかを調べるため、
23行目の:ptr_check_n以降では、はじめ、
上図の状態となっているスタックを、次の状態に変化させます。
判定までのスタック操作
まず、早速25行目で、サブルーチン:ptr_sub_Rに飛びます。
このサブルーチンは、Rという値をプッシュする（かのように見せかける）ルーチンです。
Rは、スタック中の値から、
までの要素数です。
この値とroll命令を使って、スタックの値をスタックトップに持ってきます。
roll命令を実行する直前のスタック状態を以下に示します。
この状態になるようにスタックを操作していきます。
roll命令を使うには、よりスタックトップ側にある要素の個数（
含む）を知る必要があります。
から
まではR個、
その後、N、M、n、m、R（Rは複製してあえて1つ残す）と5個あるので、
rollの対象になるのはスタックトップからR+5個の要素です。
また、roll命令の回数には-1を指定します。
負数を指定すると、roll命令の操作の向きが逆になります。
つまり、スタックトップの値を深さR+5に埋め込むのではなく、
深さR+5の値をスタックトップに掘り起こす、
という操作になります。したがって、この状態からroll命令を実行すれば、
このようにがスタックトップに来るので、
を複製することができます。
さて、このあとを戻します。
先ほどわざとRをひとつ残しておいたのは、ここで戻すのに使うためです。
Rをスタックトップに移動させたあと、
先ほどと同様にスタックの要素の個数を数えてroll命令の引数を決めます。
そしてrollすると、
このようにが元の位置に戻り、
あたかも最初のスタック状態に対して、がプッシュされたかのように
見せかけることができます。
あとは、roll命令を駆使してnの複製を作り、
スタックの状態を所望の状態にすればOKです。
このあと、「順序判定関数」にジャンプすれば、
スタックは次の状態になり、
mの時と同様に、Rの値から判定が可能となります。
fについて
さて、mの判定でも、nの判定でも、同じ「順序判定関数」を利用していました。
順序判定関数は 126−148行目の## inorderというコメントのある行に書かれています。
実は今回、mの判定でも、nの判定でも、この126-148行目に書かれた
処理を呼び出しています。
この時に気をつけなければいけないのが、
「順序判定関数の適用後は、どの処理を実行すればいいのか」
という問題です。
例えば、mの判定のために順序判定関数が呼び出された場合、
その後はnの判定処理に続くはずです。
一方で、nの判定のために順序判定関数が呼び出された場合、
その後は判定処理ではなく、別の処理に続くはずです。
単純に順序判定関数に進んでしまうと、次にどこに進むべきかがわからなくなり、
正しくプログラムが組めません。
そこで、順序判定関数に進む前に、
「その関数はどこで呼ばれたもので、その後どこに進むべきか」を教えてあげる必要があります。
この役割をしているのが、先ほど説明を割愛した「f」です。
mの判定をするときはf=1とし、
nの判定をするときはf=2として両者を区別し、
その後のプログラムの進行先を正しく選択させています。
プログラムの進行先の選択については、
順序判定関数inorderに前処理と後処理を追加することで
実現しているのですが、それはまた別の機会に説明します。
最後に
いや、プログラムの冒頭を説明しただけなのに、
ものすごい労力がかかっています。しかもまだ書き切れてません。
図が大量にあるため、一旦ここで切って、
次回解説の続きをしたいと思います。
今日は疲れたべよ。
では。
