スパゲッティスタック

スパゲッティスタックとは

スパゲッティスタック（spaghetti stack）は、別名カクタススタック（cactus stack）、サグアロスタック（saguaro stack）、イントゥリー（in-tree）とも呼ばれる、特殊なN分木構造です。このデータ構造の特徴は、子ノードが親ノードへのポインタを持つ一方で、親ノードは子ノードへのポインタを持たない点にあります。この構造により、ノードのリストを葉から親へと辿る際に、連結リストのスタックのように動作します。

通常の連結リストとは異なり、スパゲッティスタックでは各ノードは唯一の親ノードへのポインタのみを持ちます。親ノードは他の子ノードに関する情報を保持しないため、子ノードから親ノードへの辿り方は一意に定まります。これにより、スパゲッティスタックは、実行中に動的にレコードがプッシュ・ポップされるものの、ポップされたレコードが後で利用される状況で特に有用です。

コンパイラにおける利用例

コンパイラは、ブロックスコープを表現するためにスパゲッティスタックを利用します。例えば、C言語のような言語では、新しいブロックスコープが開かれるたびに、そのスコープに対応するシンボルテーブルがスパゲッティスタックにプッシュされます。ブロックスコープが閉じられると、対応するシンボルテーブルはスタックからポップされますが、破棄されるのではなく保持されます。これにより、コンパイラは抽象構文木を翻訳する際、特定の式が含まれる環境におけるシンボルテーブルを簡単に参照し、識別子への参照を解決することができます。

例えば、変数Xへの参照があった場合、コンパイラはまず最も内側の静的スコープを表す葉のシンボルテーブルを検索し、見つからなければ親のシンボルテーブルを順に検索していきます。これにより、変数のスコープを正しく管理することができます。

プログラミング言語のランタイムにおける利用

スパゲッティスタックは、特に継続をサポートするプログラミング言語の実装において、重要な役割を果たします。継続とは、プログラムの実行状態を保存し、後でその状態から実行を再開する機能です。継続をサポートする場合、関数からリターンする際に、その関数のローカル変数を破棄することはできません。なぜなら、保存された継続が後でその関数に再び入る可能性があり、その際には完全な状態の変数と過去のスタックが必要になるからです。

この問題を解決するために、スタックフレームはスパゲッティスタック内で動的にメモリ確保されます。そして、その継続が不要になった場合、ガベージコレクションによってメモリが解放されるまで保持されます。この構造は、上向きおよび下向きのファンアグメント問題（関数が定義された環境とは異なる環境で呼び出されることによる問題）を解決し、一級レキシカルクロージャ（関数が定義された環境を保持するクロージャ）を容易に実装することができます。

スパゲッティスタックが利用されるプログラミング言語の例

SchemeやStandard ML of New Jerseyのような一級継続を持つ言語
Smalltalkのように実行時に実行スタックを検査・修正できる言語
Felix
Cilk

関連するデータ構造

スパゲッティスタックと類似のデータ構造は、素集合森に見られます。素集合データ構造では、要素をグループ化し、各グループを木構造で表現します。この木構造もまた、子ノードから親ノードへのポインタを持ち、スパゲッティスタックと同様の性質を持っています。

その他の関連事項

永続データ構造：スパゲッティスタックは、過去の状態を保持する必要があるため、永続データ構造との関連性があります。
バロースB5000：初期のコンピュータシステムであるバロースB5000も、スタックベースのアーキテクチャを採用しており、スパゲッティスタックの概念と関連付けられることがあります。

もう一度検索