[今日のPiet]スタック内のランダムアクセス(2)
今日は昨日に引き続き、スタック内のランダムアクセスをするための
Pietコードを書いていきます。
おさらい
ざっと昨日のおさらいです。
Pietでは、メモリはスタックで管理され、基本的にはスタックトップの値しか操作できません。
そこで、Pietのスタックを、あたかも通常のメモリのように使う方法を考えます。
誤解しないで欲しいのですが、どこまで行ってもPietにできることは、
「スタックトップの要素に対する操作」だけです。
しかし、Piet内のスタック内に、
決まった配置でメモリを展開し、
決まった手続きでメモリ内の要素の追加・削除・更新・参照ができれば、
その処理を外部からは隠蔽することで、
あたかも通常のメモリを操作しているかのように見せることは可能です。
メモリの構成
メモリは次のような構成にするのでした。
メモリには以下の特徴を持たせます。
メモリは複数用意できるようにします。
ここではM個のメモリMEM 1, MEM 2, ... , MEM Mがあります。
各メモリごとに独立にアドレスをもち、要素を指定できます。
MEM 2のアドレス2の要素が MEM2~2である、と言った具合です。
メモリ内の範囲を超えたアドレス指定はエラーとします。
MEM 1のアドレスの要素の位置は、
MEM 2のアドレス1と同じ位置ですが、
MEM 1の範囲外のためエラーになります。
各メモリの要素数とメモリの個数の情報もスタック内に保持
メモリの末尾に続いて格納されるのでした。
追加:メモリ全体の長さもプッシュしておきます。
メモリの個数Mに続けて、メモリ全体の長さNも格納することにします。
つまり、
をMの上にプッシュしておきます。
この状態をメモリの「基本形」とします。
メモリを操作するときは、この状態に続いて引数をプッシュし、
所望の操作をする関数を呼ぶことにします。
今日の目標:「メモリアドレス変換関数」を作る
メモリに対する操作の種類はいくつか考えられます。
例えば、メモリmのアドレスnの値を、
「取り出したい」、「削除したい」、「コピーしたい」、「違う値に置き換えたい」
・・・などです。
しかし、いずれにせよ、
「メモリm、アドレスnの値が、スタック上でどこにあるか」
を知る必要があります。
先ほども述べたように、あくまでもPietが操作できるのはスタックトップにある値だけです。
したがって、どんな操作をするときも、
メモリm、アドレスnの値を一旦スタックトップに持ってくる必要があります。
そのためには、
「メモリm、アドレスnの値が、スタック上でどこにあるか」
を知ったうえで、roll命令で掘り起こす必要があるのです。
そこで、今回はこの
「メモリm、アドレスnの値が、スタック上でどこにあるか」
を求める関数を作ります。
(みんな大好きC言語のpointerからもじって"ptr関数"と名づけます。)
仕様
今回作る処理では、メモリの基本形の上に、位置を知りたいメモリ・アドレスをプッシュします。
例えば、メモリmのアドレスnの要素の位置が知りたければ、
次のようにメモリの末尾にmとnをプッシュします。
実際のメモリ部分(青色部分)は「...」で省略しました。
ptr関数はこの状態からスタートし、スタックを次の状態にしてから処理を停止します。
まず、メモリ内部(省略した青色「...」部分)と、
メモリ情報(〜、、)の部分は(最終的には)変化しません。
また、初めにプッシュしたmとnもそのままです。
その上に新しい値が3つプッシュされています。
F : エラーフラグ
まず、スタックトップのFは処理中のエラー有無のフラグであり、
0ならエラー、1なら成功を示します。
0(エラー)になるのは、アドレスnがメモリmの範囲外だったときです。
N : メモリ全体の長さ
これはメモリ全体(省略した青色「...」部分)の長さです。
スタックを表した上図のオレンジ色部分の最上端にあるNと同じ値です。
なお、エラー時(F=0の時)には、N=0となります。
S : メモリm、アドレスnの要素のスタック上の位置
メモリmのアドレスnの要素のスタック上の位置です。
具体的には、スタックボトムから数えた位置であり、以下の式で計算されます。
具体的には、下図でピンク色で示した要素の個数となります。
なお、Nと同様に、エラー時(F=0の時)には、S=0となります。
具体例
例えば、
- メモリ数Mが4
- メモリ全体の長さNは15(=4+2+6+3)
と言ったメモリを考えます。
このメモリの基本形は次のようになります。
このメモリにptr関数を適用したときの挙動を示します。
例1(エラーなし)
例えば、メモリ3のアドレス2の要素の位置が知りたい場合は、
基本形に対して3、2の順にプッシュします。
流石に長いのでメモリ部分は省略します。
この状態からptr関数を適用すると、次の状態になります。
このケースでは、メモリ3の長さは6であるため、
メモリ3の内部にアドレス2が存在します。
したがってF=1となります。また、Nとしてメモリ全体の長さ15が入ります。
そして、この要素MEM 3-2は、下から8番目の要素になりますので、
S=8がプッシュされます。
実際に数えてみると、
確かにピンク色の要素は8個であることがわかります。
例2(エラーあり)
次に、メモリ2のアドレス3の要素の位置を知りたいとします。
この場合は、スタックに2、3の順にプッシュします。
この状態からptr関数を適用すると、次のようになります。
お察しの通り、メモリ2の長さは2しかないため、アドレス3は存在しません。範囲外です。
したがって、エラーとなってF=0がプッシュされ、それに伴い、NもSも0となります。
以上が、今回作りたいptr関数の概要です。
生成されたPietコード
いつもなら、まず「処理フローファイル」の中身を示して、
それを拙作の「GridPietGenerator」 で変換した結果を示すのですが、
今回の処理フローファイル、なんと文字数が10000文字程度あります。
これだけでブログ1日分ですね(棒)
さらにそこに解説を加えると、もう記事とやる気が爆発するので、
処理フローファイルとその解説は次回に回します。
今回は、先出力されたPietソースコードを先に示します。
元のサイズは321x306、みやすくするため3倍ズームでお送りしております。
このPietソースコードは、まず最初に
先ほど例で上げたメモリと同じものをスタック内に展開します。
そのうえで、ユーザーにメモリ番号mとアドレスnの入力を促し、
それらをスタックにプッシュしてからptr関数を実行します。
最後にスタックの最上部にプッシュされた3つの値を順次出力して終了します。
では実際に実行してみます。
例1(エラーなし)
メモリ3のアドレス2の要素の位置を知りたい場合を試します。
./npiet -tpic -tpf 3 -tps ptr.ppm ? 3 ? 2 1 15 8
スタックトップから出力するので、出力結果はF、N、Sの順に表示されます。
結果が正しく出力されていることがわかります。
次にトレース画像を見てみます。
なかなかクレージーですね。嫌いじゃないです。
例2(エラーあり)
メモリ2のアドレス3の要素の位置を知りたい場合を試します。
こちらはエラーが出るケースです。
./npiet -tpic -tpf 3 -tps ptr.ppm ? 2 ? 3 0 0 0
正しくエラーを吐くことがわかります。
次にトレース画像を見てみます。
やはり例1に比べれば線がまばらですが、それでもそこそこ動き回っています。
最後に
明日のエネルギーを前借りしてお届けしているため、
本日はここでお開きとさせてください。
次回はptr関数のソースコードのお披露目と、
内容の解説を行う予定です。
では。