前のページ 1/1 次のページ

スタックマシン(stack machine)とは、メモリがスタックの形式になっている計算モデルを意味する。

スタックマシンを実装あるいはシミュレートしている実在のコンピュータもスタックマシンと呼ぶ。

加えて、スタックマシンは「0オペランド」命令セットのマシンも意味する。0オペランドマシンでは、命令は暗黙のうちにスタックのトップにある値を使って演算を行い、結果をスタックのトップに置く。そのようなマシンでも、メモリの任意の位置の読み書きをする "load" 命令や "store" 命令がある(ただし、アドレスは明示的に指定せず、スタックのトップにある値をアドレスとして使用する)。

スタックマシン(0オペランド命令セット)がアキュムレータマシン(1オペランド命令セット)やレジスタマシン(2オペランド命令セット、3オペランド命令セット)に比較して優れているのは、0オペランド命令セットで書かれたプログラムのコード密度が他の命令セットで書かれた同じプログラムに比較して一般に高い点である。

◆ 計算のスタックモデル

スタックマシンはいくつかのスタックを持つ。プログラムの初期入力はスタック1の初期状態として与えられ、他のスタックは初期状態では空である。スタックマシンの各時点の状態はリード状態かライト状態であり、各状態にはスタックからリード(ポップ)すべき値の個数かスタックにライト(プッシュ)すべき値の個数が付与される。さらにライト状態には書き込むべきシンボルが指定され、次に遷移すべき状態が指定される。リード状態ではアルファベットそれぞれについて、リード結果としてその文字を読んだときに遷移すべき次の状態が指定される。さらにリード状態ではスタックが空だったときの遷移先状態も指定される。スタックマシンは特別な停止状態に到達したとき停止する。

スタックを1つしか持たないスタックマシンは、計算モデルとしては非常に弱い。例えば、1-スタックマシンでは、0ⁿ1ⁿ(0の並びの後に同じ個数の1が並ぶ言語)のような単純な言語も認識できない。1-スタックマシンの計算能力は、有限オートマトンよりも高いが、決定性プッシュダウン・オートマトンよりも低い。

一方、複数のスタックを持つスタックマシンはチューリング機械と等価である。例えば、2-スタックマシンでは、チューリング機械をエミュレートできる(チューリング機械のヘッド位置から左側のテープをひとつのスタックが代替し、右側のテープをもうひとつのスタックが代替する)。

◆ スタックマシン型命令セット

スタックベースの命令セットを持つマシンは、1つ以上のスタックを持つ。2つのスタックを持つ場合、一方を「データスタック」、もう一方を「リターンスタック」と呼び、データスタックはデータの処理に使われ、リターンスタックはサブルーチンコールの戻りアドレスを保持するのに使われる(コールスタックとも)。

オペランドとしてレジスタを使うマシンは、容易にスタックマシンをシミュレートできる。このようなシミュレーションを「仮想スタックマシン」とも呼ぶ。スタックベースの命令セットがレジスタベースのアーキテクチャより優れているのは、オペランドのアドレスを指定する必要がないので、命令長を小さくできる点である。これにより、コンパイルされた実行コードが劇的に小さくなる。命令セットやプログラム対象領域に依存するものの、RISCの1/6、CISCの1/4程度と言われる。

スタックマシンを商用に実装したものでは、コンテキストを保持するための特殊レジスタを持っている(例えばバロース B5000など)。これは厳密にはスタックマシンとは呼べないかもしれないが、それによってスタックマシンを汎用の情報処理に適したものにしているのも事実である。

スタックマシンを商用化した例を以下に挙げる。

・ ハードウェアで直接実行される命令セットアーキテクチャ

  ・ バロース B5000 アーキテクチャ(1961年から)

  ・ ユニシス Clearpath/MCP(上記バロースのアーキテクチャの2006年現在の実装)

  ・ タンデム・コンピュータ T/16

  ・ HP 3000 (PA-RISC ではなく、それ以前の CISC)

  ・ [外部リンク] Atmel MARC4 マイクロコントローラ

  ・ Forth言語を実装したチップ[外部リンク]http://www.colorforth.com/chips.html。RTX2000、Sh-Boom、[外部リンク] F21、[外部リンク] PSC1000 など。

  ・ [外部リンク] The 4stack processor by Bernd Paysan 4つのスタックを持つマシンの提案

  ・ [外部リンク] "Ignite" スタックマシン。チャールズ・ムーアがアーキテクチャを設計。

・ 仮想機械

  ・ UCSD Pascal p-machine

  ・ Java仮想マシン命令セット

  ・ .NET Framework環境における共通中間言語命令セットおよびその仮想機械である VES(仮想実行システム)

  ・ Forth言語処理系。特に threaded code で実装されているもの。

  ・ アドビのPostScript

  ・ サン・マイクロシステムズの Sun Ray スマートカードの定義作成のための SwapDrop 言語

バロースのアーキテクチャは、スタックマシンにタグ付きメモリを組み合わせたものである(各メモリワードの一部ビットでデータ型などを表す)。タグ付きメモリはオペコード(命令コード)の縮小に貢献している。つまり、整数や浮動小数点数といった区別はメモリワード自身が持っているので、命令コードで示す必要がない。スタックマシンであるためオペランドも少なく、結果として命令長が小さくて済むようになっている。

◆ 外部リンク

・[外部リンク] Stack Computers: the new wave book by Philip J. Koopman, Jr. 1989

・[外部リンク] Homebrew CPU in an FPGA - FPGA で自家製スタックマシンを作る

・[外部リンク] Mark 1 FORTH Computer - TTLチップで構成した自家製スタックマシン

・[外部リンク] Mark 2 FORTH Computer - ビットスライス/PLDを使った自家製スタックマシン

前のページ 1/1 次のページ

・スタックマシン page1