スタックマシン
スタックマシン向けのコンパイラは、相対的に単純であり、作成が容易である。特にコード生成は単純であり、前後関係を考慮する必要がなく、構文解析に容易に組み込める。レジスタ割り付けを考慮する必要がなく、定数参照や簡単なメモリ参照を最適化する必要がない。加算命令、インデックス付きロード命令、コール命令などは、複雑な式や入れ子のプロシージャ呼び出しであっても全く同じ命令コードを使うことができ、コンパイラが特殊ケースを考慮する必要がない。
コンパイラが単純ということは、メモリ容量の小さなマシンでもコンパイラを利用可能ということでもある。また、オペレーティングシステムを高水準言語で素早く開発することが可能で、バロース B5000 や HP 3000 で実際にそのように開発された。UCSD p-System が初期の8ビットマイクロプロセッサを使ったメモリ容量の小さなシステムで動作できたのも、仮想スタックマシンをターゲットとしてコンパイルしたためである。
コンパイラが単純ということは、コンパイラ最適化の最新技術の恩恵にあずかれないという欠点もある。スタックマシンでのコンパイラ最適化は不可能ではない。バックエンド部の最適化で劇的にコードの効率を向上させた例があり、大域的な最適化でさらに性能向上させた例もある。
オペランドを指定する必要がないため、個々の命令が一般に小さく、6ビット程度で済む。分岐命令、即値のロード命令、ロード/ストア命令はオペランドを必要とするが、多くの場合それらの命令もスタック上の値をオペランドとすることで命令を小さくできる。前の命令の結果をスタックに自動的にプッシュすることで、次の命令でそれを暗黙のうちに利用できる。対照的にレジスタマシンでは、ALU命令で2つまたは3つのレジスタを指定するオペランドを必要とし、1命令あたり少なくとも16ビット以上を必要とする。アキュムレータマシンはオペランドが1つだが、複雑な式を計算する際に一時変数へ値を退避しなければならないので、余計なロード/ストア命令を必要とする。スタックマシンでは、逆ポーランド記法が括弧を使わないことからもわかるように、一時変数への退避が発生しない。
プロシージャや関数の局所変数や引数にアクセスするため、スタックマシンにも一種のロード/ストア命令がある。スタックのトップのアドレスからのオフセットでアドレスを指定する場合やフレームベースを指すレジスタにオフセットを指定する場合などがある。
計算機科学のオートマトン理論における「スタックマシン」は、メモリにランダムアクセスすることができず、LIFO型のスタックしか持たない計算モデルである。これは純粋に理論上のモデルであり、実在のコンピュータではメモリは任意のアドレスを指定してアクセスできる。
スタックマシンはいくつかのスタックを持つ。プログラムの初期入力はスタック1の初期状態として与えられ、他のスタックは初期状態では空である。スタックマシンの各時点の状態はリード状態かライト状態であり、各状態にはスタックからリード(ポップ)すべき値の個数かスタックにライト(プッシュ)すべき値の個数が付与される。さらにライト状態には書き込むべきシンボルが指定され、次に遷移すべき状態が指定される。リード状態ではアルファベットそれぞれについて、リード結果としてその文字を読んだときに遷移すべき次の状態が指定される。さらにリード状態ではスタックが空だったときの遷移先状態も指定される。スタックマシンは特別な停止状態に到達したとき停止する。
スタックを1つしか持たないスタックマシンは、計算モデルとしては非常に弱い。例えば、1-スタックマシンでは、01(0の並びの後に同じ個数の1が並ぶ言語)のような単純な言語も認識できない。1-スタックマシンの計算能力は、有限オートマトンよりも高いが、決定性プッシュダウン・オートマトンよりも低い。
一方、複数のスタックを持つスタックマシンはチューリングマシンと等価である。例えば、2-スタックマシンでは、チューリングマシンをエミュレートできる(チューリングマシンのヘッド位置から左側のテープをひとつのスタックが代替し、右側のテープをもうひとつのスタックが代替する)。