スパゲッティスタック（spaghetti stack; 他に cactus stack, saguaro stack, in-treeとも）とは、子ノードが親ノードへのポインタを持ち、親ノードは子ノードへのポインタを持たないようなN分木である。ノードのリストが親のポインタをたどって葉から親へ向かうとき、スパゲッティスタックは連結リストのスタックのように振る舞う。リンクがある連結リストと比較して、他のノード唯一の親ノードへのポインタのみをもち、それぞれの親ノードは他の子を無視する（親ノードから子ノードへのポインタが無いためどうやってもアクセスできない）。
スパゲッティスタックは実行過程のようにレコードが動的にプッシュ・ポップされるもののポップされたレコードが使用時に残るという状況で発生する。
例えばC言語のようなコンパイラはブロックスコープ表現がシンボルテーブルを開閉するようなスパゲッティスタックを作る。新たなブロックスコープが開かれた時、シンボルテーブルはスタックにプッシュされる。閉じ中括弧が検出されたとき、スコープは閉じられ、シンボルテーブルがポップされる。しかしシンボルテーブルは破壊されるのではなく記憶される。そしてもちろんスタックは親のシンボルテーブルなども記憶している。そのためコンパイラが抽象構文木についてあとで翻訳を行うとき、与えられた任意の表現に対してスパゲッティスタックはその表現の環境で表現するシンボルテーブルを呼び出すことができ、識別子への参照を解決することが出来る。もし表現が変数Xを参照するときは、それは最も内部の静的スコープを表現する葉のシンボルテーブルをまずシークし次にその親のシンボルテーブルをシークしていく。
類似のデータ構造は素集合森において見られる（素集合データ構造を参照）。
プログラミング言語のランタイムにおける使用
スパゲッティスタックという語は継続をサポートするプログラミング言語の実装と密接に関係する。スパゲッティスタックは変数のバインディングや他の環境の特徴を含む実際のランタイムスタックの実装に使用される。継続がサポートされなければならないとき、関数から復帰(return)したとき関数の局所変数は破壊できない。a saved continuationはその関数に後に再び入るかもしれず、それは完全な状態の変数と過去のすべてのスタックを期待するので、関数から再び復帰する(return)ことができる。
この問題を解決するため、スタックフレームはスパゲッティスタック内で動的メモリ確保をし、そしてこれ以上継続がないときはそのまま残され、ガベージコレクションによるメモリ開放を待つことになる。この形式の構造は上向き(upward)・下向き(downward)のfunarg問題も解決できる。一級レキシカルクロージャはその基板で容易に実装される。
プログラミング言語でのスパゲッティスタックの使用例:
- SchemeやStandard ML of New Jerseyのような一級継続をもった言語
- Smalltalkのような実行時に実行スタックを検査や修正を行う言語
- Felix
- Cilk
脚注
関連項目
- 永続データ構造
- バロース B5000
