スタックマシン（計算モデル）

特徴

スタックマシンでは一般に、push、pop、スタック最上位の要素に作用する算術演算子・論理演算子、制御フロー命令などの単純な操作を用いる。代表的な特徴として、暗黙的なオペランド指定（明示的なレジスタ欄を持たないこと）、後入れ先出し（LIFO）の値の扱い、レジスタファイルが限定的であるか存在しないことが挙げられる。命令ではオペランド指定子を省略するため、プログラムはバイト数で短くなることが多い。

歴史と発展

スタックを用いて式を評価する考え方は現代のコンピュータより古く、数学における後置記法（RPN）にも見られる。スタック操作を重視するハードウェアおよびソフトウェアの機械は、設計者がコンパクトな命令符号化と容易な式評価を求めるなかで登場した。のちに、スタック指向の仮想マシンと言語は、可搬性とインタプリタの単純さを目的としてこのモデルを広めた。

用途と例

• 仮想マシン：多くのインタプリタやバイトコードシステムは、コンパクトさと実装の容易さから、スタックベースの命令セットを使用する。
• プログラミング言語：スタック指向言語や一部のランタイムは、push/popの意味論で式評価を実装する。
• 電卓と小規模組込みシステム：スタックコードは高密度にできるため、メモリが限られた環境で魅力的である。

具体例には、よく知られたバイトコードシステムや複数のスタック指向言語がある。実装では、メモリを基盤とするスタック、または性能向上のためスタック最上位の値を保持する小型で高速なキャッシュを利用する場合がある。3 + 4の単純なスタック上の処理は、push 3、push 4、addとなり、スタック最上部は7になる。

トレードオフと注目すべき事項

スタックマシンはコードのコンパクトさと式木のコンパイルの容易さに優れる一方、レジスタマシンと比べて、より多くの命令や追加のメモリアクセスを必要とすることがある。コンパイラのバックエンドは、高水準コードをスタックコードへ変換したり、スタックコードをレジスタ操作へ変換したりすることが多い。アンダーフローやオーバーフローを防ぐには、スタック深さの計算などの解析が重要である。技術的な背景については、関連資料を参照。