スタックマシン
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/05/03 03:45 UTC 版)
計算のスタックモデル
計算機科学のオートマトン理論における「スタックマシン」は、メモリにランダムアクセスすることができず、LIFO型のスタックしか持たない計算モデルである。これは純粋に理論上のモデルであり、実在のコンピュータではメモリは任意のアドレスを指定してアクセスできる。
スタックマシンはいくつかのスタックを持つ。プログラムの初期入力はスタック1の初期状態として与えられ、他のスタックは初期状態では空である。スタックマシンの各時点の状態はリード状態かライト状態であり、各状態にはスタックからリード(ポップ)すべき値の個数かスタックにライト(プッシュ)すべき値の個数が付与される。さらにライト状態には書き込むべきシンボルが指定され、次に遷移すべき状態が指定される。リード状態ではアルファベットそれぞれについて、リード結果としてその文字を読んだときに遷移すべき次の状態が指定される。さらにリード状態ではスタックが空だったときの遷移先状態も指定される。スタックマシンは特別な停止状態に到達したとき停止する。
スタックを1つしか持たないスタックマシンは、計算モデルとしては非常に弱い。例えば、1-スタックマシンでは、0n1n(0の並びの後に同じ個数の1が並ぶ言語)のような単純な言語も認識できない。1-スタックマシンの計算能力は、有限オートマトンよりも高いが、決定性プッシュダウン・オートマトンよりも低い。
一方、複数のスタックを持つスタックマシンはチューリングマシンと等価である。例えば、2-スタックマシンでは、チューリングマシンをエミュレートできる(チューリングマシンのヘッド位置から左側のテープをひとつのスタックが代替し、右側のテープをもうひとつのスタックが代替する)。
- ^ a b c P.HAYES & 1978,1979, p. 39.
- ^ Koopman, Philip (1994). “A Preliminary Exploration of Optimized Stack Code Generation”. Journal of Forth applications and Research 6 (3) .
- ^ Bailey, Chris (2000). “Inter-Boundary Scheduling of Stack Operands: A preliminary Study”. Proceedings of Euroforth 2000 Conference .
- ^ Shannon, Mark; Bailey C (2006). “Global Stack Allocation : Register Allocation for Stack Machines”. Proceedings of Euroforth Conference 2006 .
- ^ a b "Computer Architecture: A Quantitative Approach", John L Hennessy, David A Patterson; See the discussion of stack machines.
- ^ a b c LaForest, Charles Eric (2007), Second-Generation Stack Computer Architecture
- ^ Stack Computers: the new wave book by Philip J. Koopman, Jr. 1989
- ^ 'Introduction to A Series Systems', Burroughs Corporation, page 41,
- ^ “BOOST: Berkeley's Out of Order Stack Thingy”. Research Gate. Kaushik Ravindran. 2016年2月16日閲覧。
- ^ HP3000 Emulation on HP Precision Architecture Computers, Arndt Bergh, Keith Keilman, Daniel Magenheimer, and James Miller, Hewlett-Packard Journal, Dec 1987, p87-89,
- ^ Migrating a CISC Computer Family onto RISC via Object Code Translation, K. Andrews and D. Sand, Proceedings of ASPLOS-V, October, 1992
- ^ "Virtual Machine Showdown: Stack vs. Registers", Yunhe Shi, David Gregg, Andrew Beatty, M. Anton Ertle
- ^ 'The Case for Virtual Register Machines', Brian Davis, Andrew Beatty, Kevin Casey, David Gregg and John Waldron
- ^ "Branch Prediction and the Performance of Interpreters - Don't Trust Folklore" Erven Rohou, Bharath Narasimha Swamy, Andr ́e Seznec
- ^ “The KDF9 Computer - 30 Years On”. 2022年12月11日閲覧。
- ^ "The World's First Java Processor", by David A. Greve and Matthew M. Wilding, Electronic Engineering Times, Jan. 12, 1998,
- ^ 'MARC4 4-bit Microcontrollers Programmers Guide', Atmel, http://www.atmel.com/dyn/resources/prod_documents/doc4747.pdf
- ^ Forth chips
- ^ F21 Microprocessor Overview
- ^ PSC1000 Microprocessor Reference Manual, Patriot Scientific Corporation
- ^ The 4stack processor by Bernd Paysan
- ^ 'Porting the GNU C Compiler to the Thor Microprocessor', Harry Gunnarsson and Thomas Lundqvist
- ^ “Instructions — WebAssembly 2.0 (Draft 2024-04-28)”. webassembly.github.io. 2024年5月3日閲覧。
- スタックマシンのページへのリンク