スタックマシン（"stack machine"）とは、メモリがスタックの形式になっている計算モデルを意味する。スタックマシンを実装あるいはシミュレートしている実在のコンピュータもスタックマシンと呼ぶ。加えて、スタックマシンは「0オペランド」命令セットのマシンも意味する。0オペランドマシンでは、命令は暗黙のうちにスタックのトップおよびトップ近傍にある値を使って演算を行い、結果はやはりスタックに積む。スタックマシン（0オペランド命令セット）がアキュムレータマシン（1オペランド命令セット）やレジスタマシン（2オペランド命令セット、3オペランド命令セット）に比較して優れているのは、0オペランド命令セットで書かれたプログラムのコード密度が他の命令セットで書かれた同じプログラムに比較して一般に高い点である。コールスタックを使って入れ子になったサブルーチン呼び出しの局所変数群を管理する方式のコンピュータをスタックマシンとは呼ばない（普通は）。計算機科学のオートマトン理論における「スタックマシン」は、メモリにランダムアクセスすることができず、LIFO型のスタックしか持たない計算モデルである。これは純粋に理論上のモデルであり、実在のコンピュータではメモリは任意のアドレスを指定してアクセスできる。スタックマシンはいくつかのスタックを持つ。プログラムの初期入力はスタック1の初期状態として与えられ、他のスタックは初期状態では空である。スタックマシンの各時点の状態はリード状態かライト状態であり、各状態にはスタックからリード（ポップ）すべき値の個数かスタックにライト（プッシュ）すべき値の個数が付与される。さらにライト状態には書き込むべきシンボルが指定され、次に遷移すべき状態が指定される。リード状態ではアルファベットそれぞれについて、リード結果としてその文字を読んだときに遷移すべき次の状態が指定される。さらにリード状態ではスタックが空だったときの遷移先状態も指定される。スタックマシンは特別な停止状態に到達したとき停止する。スタックを1つしか持たないスタックマシンは、計算モデルとしては非常に弱い。例えば、1-スタックマシンでは、01（0の並びの後に同じ個数の1が並ぶ言語）のような単純な言語も認識できない。1-スタックマシンの計算能力は、有限オートマトンよりも高いが、決定性プッシュダウン・オートマトンよりも低い。一方、複数のスタックを持つスタックマシンはチューリングマシンと等価である。例えば、2-スタックマシンでは、チューリングマシンをエミュレートできる（チューリングマシンのヘッド位置から左側のテープをひとつのスタックが代替し、右側のテープをもうひとつのスタックが代替する）。スタックマシン型の命令セットでは、例えば加算 (ADD) 命令はスタック上のトップにある2つの値を暗黙のうちにオペランドとして使用し、それらの和をスタックのトップに格納する。オペランドとして使用した値はスタックから取り除かれ（ポップ）、和をスタックのトップに置く（プッシュ）。ほとんどの命令は命令コードだけで構成され、レジスタ番号やメモリアドレスや即値を指定する必要がない。演算を行う場合、先にスタック上に演算対象の値をプッシュし、その後に演算命令を実行することになる。これは逆ポーランド記法と呼ばれる数式の表現方法と同じである。この場合、演算命令は容易に3つ以上の値を対象とするよう拡張可能である。メモリ上の任意のアドレスにあるデータをスタックにプッシュする命令や即値をスタックにプッシュする命令が必要となる。スタックマシンと対比されるレジスタマシンは、高速で小さいレジスタファイルを持ち、一時的な値をレジスタに保持する。その中でもアキュムレータマシンはレジスタを1つだけ持ち、そのレジスタとオペランドで指定したメモリ位置との間で演算を行う。初期のコンピュータには一時レジスタを持たず、常にメモリ間で演算を行うものもあった。スタックマシンの実装方式は2つあり、レジスタファイルのみを小さなスタックとして利用する実装と、スタック自体はメモリ上にあって、スタックのトップを指すレジスタを持つ実装である。後者の例としては、バロース B5000 や HP 3000 がある。稀に、メモリ上のスタックとレジスタファイルによる小さいスタックを別々のスタックとして持つ実装もある。回路素子の高速化によりメモリアクセスなどの配線遅延が問題となるに連れて、スタックを階層構造のキャッシュに収める実装が現れた。明示的なロード命令を用いない限り、スタック内のオペランドが使われる順序は、スタックトップから下方へ積まれている順序と一致する。このため、スタックトップから優先してより高速の記憶素子に収められた状態を保つだけで、オペランドの強力なプリフェッチが実現され、配線遅延が隠蔽される。仮想スタックマシンの多くでは、スタックトップはメモリ領域ではなくホストマシンのレジスタファイルで実装されるレジスタで実現されている。FPGA上のJAVAプロセッサであるJOPでは、レジスタファイルよりさらに高速で小さい記憶素子である、命令パイプライン上のラッチ回路をスタックトップ2個に充てている。スタックベースの命令セットを持つマシンは、複数のスタックを持つことがある。2つのスタックを持つ場合、一方を「データスタック」、もう一方を「リターンスタック」と呼び、データスタックはデータの処理に使われ、リターンスタックはサブルーチンコールの戻りアドレスを保持するのに使われる（コールスタックとも）。データスタックとリターンスタックを分離すると、スタック管理処理の大部分を排除して、全体の動作を大幅に高速化できる。このスタックを2つ持つという方式は独自に3回発明されている(バロース B5000、Forth、PostScript)。また、Java仮想マシンでも使われている。ヒューレット・パッカードの関数電卓が有名だが、一種のスタックマシンを操作モデルとしている電卓がある。プッシュに相当する「Enter」キーが特徴である。具体例で説明すると、加算を行う際は、「数値1」「Enter」「数値2」「+」の順に操作する。この操作で、まず2つの数値がスタックにプッシュされた後、加算のためにポップされ加算され結果がプッシュされる。逆ポーランド記法(順)の電卓、と呼ばれている。オペランドとしてレジスタを使うマシンは、容易にスタックマシンをシミュレートできる。このようなシミュレーションを「仮想スタックマシン」とも呼ぶ。純粋なスタックマシンは、構造を持つデータオブジェクトの複数のフィールドにアクセスするのが不得意である。スタックマシンでは、オブジェクトのベースアドレスとフィールドのオフセットからアドレスを計算しなおして、ポインタをスタック上に置きなおす必要がある。一般的な対処方法としては、レジスタマシンの一部機能をスタックマシンに取り入れ、アドレス格納用にソフトウェアから見えるレジスタファイルを用意し、レジスタマシン風の命令でロードや単純なアドレス計算を行う。なお、レジスタファイルを汎用なものにするとスタックマシンである積極的な理由がなくなってしまう。もう1つの一般的なハイブリッド方式として、レジスタマシンのアーキテクチャを出発点とし、スタックマシンでのプッシュおよびポップをエミュレートする操作を追加する方式がある。この方式をポピュラーなものにしたのは、DECのPDP-11ミニコンピュータである。これがVAXに受け継がれ、MC6800やMC68000といったマイクロプロセッサにも採用された。これにより初期のコンパイラでスタックを簡単に扱えるようになった。また、スタックインタプリタまたはスレッデッドコードを使って仮想機械を効率的にサポートする。ただし、これによってレジスタマシンのコードが純粋なスタックマシンほどコンパクトになるわけではない。このようなハイブリッド方式のマシンで、スタックマシンのように頻繁にプッシュやポップを行うと性能は悪くなる。スタック操作はプロシージャコールの際にのみ行う方がよく、当然ながらメモリ参照せずにレジスタのみで処理するのが最善である。第2世代スタックマシンと呼ばれるものは、データスタックからメモリアドレッシングの処理を肩代わりするアドレスレジスタ群を備えている。例えば、MuP21は "A" というレジスタを持っており、もっと最近の GreenArrays のプロセッサは A と B という2つのレジスタを持っている。x86ファミリは基本的にレジスタ指向の命令セットだが、初期は外付けされ、後には内蔵・一体化された、浮動小数点関係のx87命令と浮動小数点レジスタは、スタック(マシン)指向である。これも一種のハイブリッドと言えよう。これは初期（1980年代）に、命令空間やチップ面積を節約する必要があったためである。現代の64ビット化されたx86であるx64では、（互換のために従来のFPUも残されているが）通常使用されるSSEの浮動小数点関係の命令も全てレジスタ指向の命令（レジスタ指向のSIMD命令）となっている。ハードウェアで直接実行されるスタックマシン型命令セットの例を挙げる。ソフトウェアで解釈される仮想スタックマシンの例を挙げる。現代のほとんどのコンピュータ（命令セットを問わない）とほとんどのコンパイラは、メモリ上のコールスタックを局所変数の格納場所およびサブルーチンからの復帰のための情報格納に使っている。サブルーチンコールのたびに「スタックフレーム」をコールスタック上に作り、そのサブルーチンから呼び出し側に復帰するまで対応するスタックフレームが維持される。コールスタックを特別なアドレスレジスタなどを使ってハードウェアで管理する場合もある。あるいは、コンパイラの呼出規約によって特定の汎用レジスタをコールスタック処理に使う場合もある。一般にコンピュータは、大域変数とその時点で実行中のプロシージャまたは関数の局所変数への効率的アクセス手段を提供する。一般に呼び出し側のプロシージャまたは関数のスタックフレームを遡ってアクセスする必要性はほとんどなく、ハードウェアが直接そのような手段を提供することもない。必要ならば、スタックフレーム内にあるフレームポインタで遡ることもできる。バロース B5000 ではハードウェアでスタックフレームを遡る手段を提供しているが、これは動的な入れ子構造ではなく、プログラムの静的な入れ子構造（変数のスコープ）を辿るものである。その後このような機能をハードウェアで実装した例はない。ニクラウス・ヴィルトは CDC 6000 シリーズ向けにPascalコンパイラを開発した際、フレームポインタを配列に格納して常に更新するよりも、コールスタック上のフレームポインタを遡ってたどった方が全体として高速だということを発見した。この方式だと、遡って参照することのないC言語などのプログラミング言語でも、余計なオーバーヘッドが発生しない。バロース B5000 では、タスクまたはスレッドの入れ子もサポートしている。あるタスクとそのタスクを作ったタスクは、タスク作成時点のスタックフレームを共有するが、作成した側の次のフレームや作成されたタスク自身のフレームは共有されない。そのため西部劇でよく見るようなサボテンのようなスタック構造になる。各タスクは自身のスタックとフレームを保持するメモリセグメントを持つ。そのスタックのベースは作成した側のスタックの途中とリンクされている。一般的なフラットなアドレス空間を持つマシンでは、あるタスクのスタックとそれを作成した側のスタックは1つのヒープ内の別々のヒープオブジェクトになる。プログラミング言語によっては、外側のスコープのデータ環境が常に入れ子になっているわけではない。そのような言語では、1つのスタックにスタックフレームを積んでいくのではなく、別個のヒープオブジェクトとしてプロシージャの「アクティベーション・レコード」を編成する。Forthのような単純な言語では、局所変数やパラメータの名前がなく、スタックフレームにはリターンアドレス以外に何も必要としない。そのため、リターンスタックにはフレームが存在せず、単にリターンアドレスが格納される。リターンスタックとデータスタックは分離しており、プロシージャの呼び出しと復帰は高速に行われる。

出典:wikipedia