［今日のPiet］スタック内のランダムアクセス（１）
今日のPietです。
拙作「GridPietGenerator」を使って、
テキストベースで書かれた「処理フローファイル」から、
所望の処理をするPietソースコード画像を生成します。
今回のテーマ
今回のテーマは壮大です。
「Pietのスタック内のメモリにランダムアクセスする」
のが、今回の目標です。
はじめに
今回のテーマですが、壮大すぎで1日では絶対に終わりません。
あらかじめ宣言しますが、複数回に分けて解説します。
また、最終成果物はまだできていません。
原理的にできるかどうかも今の時点ではわかりません。
途中で、「やっぱり原理的に無理でした。」となる可能性があるので
あらかじめご了承ください。
ちなみに「やっぱりやる気的に無理でした。」とはならないつもりです。
多分。
前置き〜解決すべき問題〜
Pietはスタック志向プログラミング言語です。
したがって、スタックトップの要素（＝最後にプッシュした要素）にしか操作ができません。
簡単な例でいくと例えば足し算。
スタックの状態が次のようになっているとします。
これに対してadd命令を実行すると、
スタックトップの2つの値をポップして、それらの和を再びプッシュします。
しかし、スタックの奥の方にあるaとbの足し算はできません。
Pietではスタックトップにしか演算ができないからです。
aとbの足し算をするには、roll命令を使って
それらをスタックトップに持ってくる必要があります。
これでめでたくaとbの足し算ができます。
しかし、そもそもaとbがスタックのどこにいるかがわからないと
roll命令を使うことはできません。
したがって、現在のスタックの状態（どの変数・数値がスタックのどこにいるか）を
常に正確に把握していないと、Pietのプログラミングはできません。
これは非常に厳しい制約ですので、何とか解消したい。
やりたいこと〜Idea〜
スタック上にメモリを展開して、アドレスを指定すれば読み書き参照ができるようにしたい。
つまり、「スタックの底から4番目にある値をコピーしてスタックトップに持ってきて」とか、
「スタックの底から15番目の値を削除して、7番目の位置にさっきプッシュした値を格納して」とか、
そういう、普通のコンピュータのメモリ管理のようなことを
Pietのスタック上で実現したいのです。
要求仕様
仕様ってほど、かっちりしたものではございませんが、
次の要件は満たしたいと考えています。
メモリは複数設置可能
何を言っているかというと、Pietスタック内を複数のエリアに分割して、
各エリアが独立したメモリとして機能するようにしたいということです。
例えば、
- スタックの底から10番目までは「メモリ1」
- 11番目から31番目までは「メモリ2」
- 31番目から41番目までは「メモリ3」
などとして、スタック内部をエリア分けします。
一般化
より一般的には、メモリ1、メモリ2、・・・、メモリMというように、
全部でM個のメモリ領域があるとします。
先ほどの例のように、各メモリは長さがバラバラでもいいとします。
そこで、メモリ1の長さを、メモリ2の長さを
、・・・、メモリMの長さを
とします。
先ほどの例だと、メモリは3つなので、M=3で、
メモリの長さはそれぞれ、、
、
となります。
メモリごとのアドレス管理
各エリアは独立したメモリとして機能します。
したがって、それぞれが独立したアドレスを持ちます。
例えば、メモリ2のアドレス1は、メモリ2のエリアの一番初めの要素のことをさすので、
スタック全体で見ればスタックの底から11番目の要素のことを指します。
同様に、メモリ3のアドレス2は、メモリ3のエリアの二番目の要素のことを指すので、
スタック全体で見ればスタックの底から32番目の要素のことを指します。
一般化
メモリ1は長さがでしたので、アドレスの値は
から
までです。
同様にメモリ2は長さがでしたので、
から
までとなります。
一般に、メモリmの長さはですので、
メモリmにはから
までのアドレスが存在します。
各メモリの番号はスタックボトム側から、1、2、・・・、Mと振って行きます。
また、各メモリのアドレスも、スタックボトム側から、1、2、・・・と振って行きます。
したがって、スタックの状態を図で示すと次のようになります。
※下付添字がかけないため、を「N_1」のように"_"を使って表現しています。
例えば、「MEM 1-1」は「メモリ1のアドレス1」を、
「MEM 1-2」は「メモリ1のアドレス2」を、
といったように表しています。
なお、メモリmのアドレスnの要素が、
スタックの底から数えて何番目になるかは、次式で計算できます。
アドレス指定の違反管理
また、メモリ同士は独立しているため、
各メモリからはみ出すようなアドレスの指定はできません。
例えば、メモリ1のアドレス11に対して操作をしようとします。
この時、メモリ1の長さは10なので、アドレス11はメモリ1の範囲外となり、
何らかのエラーとして処理されるようにします。
（実際にはメモリ2のアドレス1と同じ要素を指すことになりますが、
バグの温床になるので、このような指定は許容しないことにします。）
一般化
判定方法は簡単です。
一般に、メモリmにはから
までのアドレスが存在するはずなので、
それ以外のアドレスを指定されたらエラーとすればいいのです。
アドレスを管理するために
アドレスが正しいかどうかを判定し、スタックの位置に変換するには、
各メモリの長さをPiet側が把握しておく必要があります。
したがって、次の図のように、スタックにはメモリの情報だけでなく、
各メモリの長さも保持する必要があること、
その情報はメモリより上になければならないこと1、
が予想できます。
加えて、これだけではダメなこともわかります。
どこまでがメモリの長さ情報で、どこからが本当のメモリなのかが、
一見してわからないからです。
（今は色分けしてますが、所詮スタックなんぞ、ただの数字の羅列です。）
これを防ぐために、スタックトップにはメモリの個数Mを置いておきます。
こうすることで、まずスタックトップの値Mを見て、
「あぁ、スタックトップの次からM個は、メモリの長さの情報であって、
メモリそのものではないんだな。
それより奥が実際のメモリ部分なんだな」と、
Pietがわかるようにしておきます。
ここまでで、何となくスタックにどのように情報を配置すれば良いかまで見えてきました2。
メモリに対する操作
この項目は原理的に可能かはまだわかりませんし、まだ検証もできていませんが、
以下のような操作ができるといいなと考えています。
- 指定したメモリ・アドレスへの値の挿入 (insert)
- 指定したメモリ・アドレスの値の削除 (erase)
- 指定したメモリ・アドレスの値のコピー (copy)
- 指定したメモリ・アドレスの値の置き換え (replace)
最後に
以上が、スタック内のランダムアクセスをするために必要な仕様です。
この仕様を満たすメモリ管理システムをPietで実現できれば、
Pietで実装できるプログラムの幅も一気に広がるのでは？と妄想しています。
処理の概要
次のような方針で進めようと考えています。
まず、1つ目のタスクとして、メモリ番号とアドレスからスタック上の位置に変換する処理が必要です。
これと全てのメモリ長がわかれば、roll命令を実行して、
目的の要素をスタックトップに持ってくることができます。
このとき、スタック上の位置の複製をうまいこと保持しておきます。
このうえで、2つ目のタスクとして、上述した値の挿入・削除・コピー・置き換えの処理をします。
その後、先ほど保持しておいたスタック位置で再度roll命令を実行すれば、
スタックの状態を復帰させることができると考えられます。
次回以降で、具体的なタスクの実装に入ります。
最後に
今回は、コンセプトのみの説明でした。
実は１つ目のタスクである「メモリ番号とアドレスの変換」の部分はできているのですが、
・・・疲れてしまったので明日以降にします。
では。
