Loading article…
コンピュータサイエンスでは、インツリーまたは親ポインタツリーは、各ノードが親ノードへのポインタを持ち、子ノードへのポインタを持たないN分木データ構造です。スタックのセットを実装するために使用される場合、この構造はスパゲッティスタック、サボテンスタック、またはサグアロスタック（サボテンの一種であるサグアロにちなんで）と呼ばれます。[ 1 ]親ポインタツリーは、互いに素な集合データ構造としても使用されます。
この構造は、構造の一部、特に末尾部分を共有する単方向連結リストの集合とみなすことができる。どのノードからでも、そのノードの祖先ノードへは辿ることができるが、他のノードへは辿ることができない。
Cなどの言語のコンパイラは、ブロックスコープを表すシンボル テーブルを開閉する際に、スパゲッティ スタックを作成します。新しいブロック スコープが開かれると、シンボル テーブルがスタックにプッシュされます。閉じ括弧に遭遇すると、スコープが閉じられ、シンボル テーブルがポップされます。しかし、そのシンボル テーブルは破棄されるのではなく記憶され、上位レベルの「親」シンボル テーブルなども記憶されます。そのため、コンパイラが後で抽象構文木に対して変換を実行する際に、任意の式に対して、その式の環境を表すシンボル テーブルを取得し、識別子への参照を解決できます。式が変数 X を参照する場合、まず最も内側の字句スコープを表すリーフ シンボル テーブルで検索され、次に親、といった具合に検索されます。
スパゲッティスタックという用語は、継続をサポートするプログラミング言語の実装と密接に関連しています。スパゲッティスタックは、変数の束縛やその他の環境機能を含む実際の実行時スタックを実装するために使用されます。継続をサポートする必要がある場合、関数が戻るときにその関数のローカル変数を破棄することはできません。保存された継続が後でその関数に再び入る可能性があり、その場合、変数がそのまま残っているだけでなく、関数が再び戻ることができるようにスタック全体が存在することも期待されます。この問題を解決するために、スタックフレームはスパゲッティスタック構造で動的に割り当てられ、継続が参照しなくなったときにガベージコレクションされるためにそのまま残されます。このタイプの構造は、上方および下方のfunarg問題も解決するため、結果として、この基盤では第一級の字句クロージャを容易に実装できます。
スパゲッティスタックを使用する言語の例は次のとおりです。
Burroughs B6500とその後継機種の命令セットアーキテクチャを採用し、 MCPオペレーティングシステムを実行するメインフレームコンピュータは、同一プログラム内で複数のタスクを生成することができる。これらのシステムは元々ALGOLをベースとしていたため、ネストされた関数をサポートする必要があり、その結果、タスク生成時にスタックに分岐が生じる。Burroughsはこの分岐を非公式に「サボテンスタック」と表現した。