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