スタックマシン
スタック領域をデータ保存領域として持っているコンピュータ
基本操作は、pushとpopの2つ
LIFO
アクセス可能な場所は一番上のみ
シンプル、プログラムサイズが小さい傾向がある
順序依存が大きいので、命令の並び替えによる最適化には向いていない
スタックマシンとそれに対応するコンパイラは実装が簡単
必要な部品が少ない
命令もスタックを利用する命令なので実装が簡単
しかし、命令の数は多くなる
pushしたりpopしたりして演算したりするから
このことはパフォーマンスにも影響がある
push
一番上にデータを積む
pop
一番上のデータを取り出す
スタック算術
加算の例
txt// 例 d = (2-x)*(y+5)
push 2
push x
sub
push y
push 5
add
mult
pop dadd
スタックマシンのスタックトップから2つpopし、加算し、結果をスタックへpushする
ブール式の評価の例
txt// if (x<7) or (y=8) then ...
// xとyのメモリに入っている値が、x=12, y=8の時を考える
push x
push 7
lt // ここで12<7を評価してスタックに`false`をpush
push y
push 8
eq // ここで8==8を評価してスタックに`true`をpush
or // false or trueを計算して`true`をpush最終的にスタックには
true がある状態になるPythonでdisライブラリを使ってプロセスVMが実行する命令列を確認できる
py>>> import dis
>>> dis.dis(lambda x,y,z: (x+y)*z)
1 0 LOAD_FAST 0 (x) # push x
2 LOAD_FAST 1 (y) # push y
4 BINARY_ADD # add
6 LOAD_FAST 2 (z) # push z
8 BINARY_MULTIPLY # mult
10 RETURN_VALUEサブルーチン呼び出しをスタックマシンを使って表現する
サブルーチンとは、関数のようなもので、呼び出されたときに、メインのルーチンから別れたサブルーチンへ行き、処理が終わるとそこへ戻ってくるようなもの
サブルーチン呼び出し時には、以下のような処理が起こる
メインのルーチン(サブルーチンの呼び出し側)の状態を保存し、
サブルーチンのローカル変数のためのメモリを確保し
サブルーチンへの実行を移す(junmp)
処理が終われば、メインのルーチンへ戻るために値を返し(return)
先程確保したメモリ空間を再利用できる状態にし、
メインの状態を復帰させる
引数をpushしたあとに、関数命令を実行、そしてその結果をスタックにpush
ir// x^3
push x
push 3
call powerサブルーチン呼び出し時に、呼び出し元の状態をスタックにpushしたあとで、サブルーチンに実行に切り替える
逆ポーランド記法とか
参考
『コーディングを支える技術』 p.18