2つの無限に積むことができるスタックを使う

Perlで自作したスタックマシンのようなもの。結構動くみたいです。
スタックマシンは、値を積んで、崩して計算するマシン。

1 2 + 3 4 + *

この逆ポーランド記述法で書かれた数式なんか解釈するのに使われるよと。
1を積み、2を積み、上2つ(1と2)を崩し足したの(3)を積み、3を積み、4を積み、
上2つ(3と4)を崩し足したの(7)を積み、上2つ(3と7)を崩し掛けたの(21)を積み、終了。
値を積むことをpush、値を崩すことをpopと言う。Perlではリスト操作の関数にpushとかpopとかあって身近だったり。
最終的に21だけ積まれてる状態になる。これで(1+2)*(3+4)の計算ができたと。コンピュータにとっては便利。
2つスタックを用意すれば、Brainfuck(下品なので以後BF)以上のことはできるよと。
BFの命令は><+-.,[]の8つだけ。
この8つがあれば仮想の機械チューリングマシンでできることはすべてできると。
そして、チューリングマシンでできることは現在のコンピュータでできることらしい。
ちなみに、チューリングマシンとはw:ja:チューリングマシンによれば、
無限に長いテープ・テープを読み書きするヘッド・機械の内部状態を記憶するメモリからなり、
ヘッド位置のデータを読み書きできる、内部状態を変更する、ヘッドを左右に移動する
ことのできる機械のこと。無限に長いテープの代わりに無限に積めるスタックを使いますよと。


画面に出力する.(ドット)、1文字受け取る,(カンマ)の2つはまぁ最低限の入出力でして、これはいいでしょう。
+-はインクリメントとデクリメント、これも問題じゃないでしょう。
[と]はなにげに複雑なんですが、まぁこれもなんとかなるでしょう。
しかしスタック1つだとどうがんばっても、ポインタを左右に移動させる>と<は再現できない。
スタックの一番上を捨てることは<で表せるかも知れない。
けど、スタックの一番上しか見えないのに>なんてできるか? やはりそれは違うだろうと。
そこで、スタックを2つ使う。テープの左側を1つのスタック、右側をもう1つのスタックで再現すると。
しかし2ついるんだ。さてどうしたものか。


ところで、一番始めにスタック1つで、逆ポーランド記述法で打ち込んだら計算できる計算機を作ってたの。
そのとき、スタックを1つ用意してみた。
まぁせっかくだからサブルーチンを定義できるようにしてみようと。
サブルーチンをcallします。そしてサブルーチン内でretされたらcallされた地点に戻ると。
そのためにはサブルーチンをcallしたときのプログラムカウンタを保存しておかないといけない。
そのときに、コールスタックというやつを使うと。そんなわけでスタックをもう1つ用意してみた。
callするときプログラムカウンタをコールスタックにpush、それでプログラムカウンタをサブルーチンのに変更。
retされたら、コールスタックをpopして、プログラムカウンタをpopした値に変更。すれば元のところに戻る。
せっかくスタックを2つ用意したんだから、コールスタックの上の方に積んだりしてやろうと。
サブルーチンが終わるときにサブルーチンが始まったときと同じ状態に戻せば何も問題なし。
いや、戻さないとまずいけどね。これがバッファオーバーランの原因の1つですよ。
まぁ実用の機械でこんなアホなやつを使っちゃいけませんけど、いかに小さな機械であるかをアピールするためにこれもいいでしょう。


その逆ポーランド記述法で打ち込んだら動く計算機を改造することにした。
最終的にはこんな感じになった。

00	データスタックに00をプッシュ
P データスタックからpopして、Bにセット
Ps コールスタックからpopして、Bにセット
L データスタックにBの値をpush
Ls コールスタックにBの値をpush
> データスタックからpopして、コールスタックにその値をpush
< コールスタックからpopして、コールスタックにその値をpush
j00 プログラムポインタに00を加算
z00,11 データスタックからpopして、その値が0なら00を、違えば11をプログラムポインタに加算
func プログラムポインタ・Bの値をコールスタックにpushし、プログラムポインタをfuncのアドレスにセット
R コールスタックから2つpopし、それぞれプログラムポインタ・Bの値にセットする

(注意 : 00,11は任意の整数,funcは任意のサブルーチン名)

popがPなのはいいのだが、pushがLなのは変だよね。
もともとpopしかいらなかったから、Pとしたけど、後にpushを追加することにしたと。
そのときPとすると重なる。それでは困るのでloadのLを使うことにした。スタックに値を読み込んで積むということね。
コールスタックの方はPs・Lsとsが付くだけ。subという意味でsと付けたはずだが、なんかおかしい。
実はレジスタのようなものがA・B・Cと3つあります。
もともと2つでいいかと思ってて、AとBがあって、それでBの方を借り置きに使おうと。
そうすれば、P L Lと命令をかければ、スタックの上のを一旦popして、Bにセットされる。
そして、L LでBの値を2回pushする。するとスタックの上の値を複製できる。
もっと複雑なこともこれを使えばできますよと。
ところが、いろいろやってるとBの値をやたらに変えないでやろうとすると、もう1ついるなぁと。それでA・B・Cになったと。
このBの値はサブルーチンを動かすときも一旦待避するようにしたので、
サブルーチンを動かす前後でBの値は変わらないと。もしかすると便利かも知れません。
Bの値を経由せずに>と<で、データスタックとコールスタックの値の入れ替えをできるようにした。
…,1,2とデータスタックに積まれている状態で、 >とするとコールスタックに2が移動する。
ここで、Pとすると1もpopされて、Bに1が読み込まれる。ここで<で2を戻し、Lで1を積む。
すると…,2,1となって上下が入れ替わる。> P < Lとすればいいわけです。
まぁこんな風に結構融通が利くので、命令を組み合わせれば、いくらでもなる。
j-6とすれば、6命令戻る、z6,1とすれば、popした値が0なら次は6命令先を、違えば1命令先を実行すると。
あとはサブルーチンの名前を書くだけでサブルーチンで、サブルーチンの最後にはRと書けばいいと。
これだけでまぁなんとかなるでしょうと。
あと、演算子だが、+ – * /とPerlの<=>に相当する<>、以上5つをとりあえず搭載してみた。
こいつらは2つpopして、2つを足したり比較した結果をpushすると。


まぁこれだけあればいいでしょうと。
popした値を画面に出力する、printというサブルーチンを定義してみたが、
これに対応するアドレスは-1。
プログラムポインタに負の値がセットされたら、絶対値の番号のPerlのサブルーチンのリファレンスを実行すると。
1番には1つ値をpopして、printするサブルーチンのリファレンスがセットしてあると。
同様にプログラムポインタが0番にセットされたら、計算機を止めるようにした。
まぁなんか投げやりな気もするが、これでPerlでできることならなんでも呼び出せるようにできると。


その計算機で動くプログラムを書けばいいと思うのだが、
それを書くにはあまりにスペースが少なすぎる。いや、単に難解なだけです。
解釈のしやすさばかり追求して、jとzを使うときはいちいち間の命令の数を数えないといけない。
実はBFの[ と ] というのは、実際にインタプリンタを作るとき気付くのだが結構解釈がめんどくさい。
[ はポインタの指す値が0ならば対応する ]にジャンプする。] はポインタの指す値が1ならば対応する [ にジャンプする。
そんなわけでBFのプログラムはそれなりにわかりやすい。
しかしながらそれよりもjとzは明らかに低級。
なのですごく書きにくいし、jとzのバグは実際結構起きやすい。
そんなわけで、もうちょっと高級感溢れる記述方法でも考えようかなと。