Ich beschäftige mich mit Implementierungstechniken für Programmiersprachen und bin kürzlich auf Spaghetti-Stacks gestoßen, die angeblich gut für ein Continuation-Passing-Style-Modell geeignet sind (aufgrund ihrer Verwendung in z. B. Scheme und SML / NJ ). Betrachten wir der Einfachheit halber nur einen Single-Thread-Prozess für diese Frage.

Ich bin jedoch etwas verwirrt über das Diagramm auf Wikipedia (auch anderswo zu finden ). Insbesondere verstehe ich nicht, wie eine solche Situation entstehen kann. Ich kann mir nur vorstellen, dass die ausgegrauten Zweige nicht erreichbar sind und Müll gesammelt werden sollten. Andererseits kann ich mir mit meinem vagen Verständnis der Implementierung von CPS mithilfe von Spaghetti-Stacks nicht vorstellen, wie Sie jemals eine Schleife in dieser Struktur erhalten könnten. Ich muss zu dem Schluss kommen, dass es sich nicht um einen "Eltern-Zeiger-Baum" handelt, sondern um einen gerichteten azyklischen Graphen mit so vielen Nicht-Müll-Quellen wie Threads und so vielen Senken wie (potenziellen) "Austrittspunkten".

Aber mein Verständnis dieser Implementierung ist ziemlich vage, also vermisse ich wahrscheinlich etwas. Ich hoffe, jemand kann mich hier über "Spaghetti Call Stacks" aufklären, womit ich die Datenstruktur meine, wie sie in Schema und / oder SML / NJ zur Implementierung von CPS-basierten Prozessen verwendet wird.

1. Angesichts des folgenden Spaghetti-Call-Stacks:

   [exit point] <-- ... <-- [frame A] <-- [frame B (active)]
                                   ^
                                    `---- [frame C]
   

   Soweit ich weiß, wickelt jede Flusssteuerung von B entweder den Stapel ab, indem sie zu einem übergeordneten Element springt (A wird aktiv, B ist jetzt nicht mehr erreichbar), oder ersetzt den aktiven Frame durch einen Untergraphen, der nur mithilfe von Referenzen von B oder Referenzen verbunden ist zu den neuen Frames. Die Ausführung kann nicht zu Frame C fließen, was bedeuten muss, dass Frame C Müll ist.

2. Anstelle der vorherigen Situation würde ich denken, dass die folgende müllfreie Situation auftreten kann:

   [exit point] <-- ... <-- [frame W] <-- [frame X] <-- [frame Z (active)]
                                   ^                     |
                                    `---- [frame Y] <---´
   

   Zum Beispiel kann ich mir vorstellen, dass Frame Z zu einer Entscheidungsfunktion gehört, die entweder mit Frame X oder Frame Y fortgesetzt wird (von denen jeder zu W zurückkehren würde). Dies bedeutet , dass Spaghetti Call Stacks sind nicht „Abstammungszeiger Bäume “.

3. Ich kann mir jedoch keine Situation vorstellen, in der eine Schleife aufgebaut werden kann. Nehmen Sie zum Beispiel die folgende Situation:

   [exit point] <-- ... <-- [frame P] --> [frame Q (active)]
                                   ^             |
                                   |             v
                                    `---- [frame R]
   

   Ich weiß, dass rekursive Bindungen eine Sache sind, aber ich bezweifle sehr, dass dies sinnvoll ist. Wenn Q zu R zurückkehren würde, wäre der Rahmen Q "verbraucht". Wenn R zu P zurückkehren würde und P nicht einfach zu Q zurückkehren könnte, müsste es zuerst neu initialisiert werden. Als solche würden Schleifen inkonsistente Zustände verursachen. (Es sei denn, ich verstehe den Zweck dieser Datenstruktur falsch und Sie würden nur die darin enthaltenen Knoten als Vorlage für Ihren aktuellen Frame verwenden.)

Aus diesen Beobachtungen muss ich schließen, dass ein Spaghetti-Call-Stack (ohne Müll) tatsächlich eine DAG ist. Ist das richtig? Oder verstehe ich den Zweck dieser Datenstruktur falsch?

Aktualisierung:

• Ich habe eine Kopie des folgenden Papiers durchgesehen :

  EA Hauck und BA Dent. 1968. Burroughs B6500 / B7500 Stapelmechanismus. In den Proceedings vom 30. April bis 2. Mai 1968, gemeinsame Frühjahrs-Computerkonferenz (AFIPS '68 (Frühjahr)). ACM, New York, NY, USA, 245-251. DOI = http://dx.doi.org/10.1145/1468075.1468111

  Dieses Papier scheint das Suguaro-Stapelsystem zu definieren. Wie sich herausstellt, handelt es sich bei diesem Suguaro-Stapelsystem um einen traditionellen Aufrufstapel, mit dem mehrere "Jobs" durch die Frames eines teilweise gemeinsam genutzten Stapels laufen können. es ist absolut nicht mit Fortsetzungen verbunden.

• Das folgende Papier (und sein Begleitpapier von 1996) erklärt anscheinend, was im SML / NJ-Compiler vor sich geht:

  Zhong Shao und Andrew W. Appel. 2000. Effiziente und platzsichere Umrüstung. ACM Trans. Programm. Lang. Syst. 22, 1 (Januar 2000), 129-161. DOI = http://dx.doi.org/10.1145/345099.345125

  Ich denke, ich sollte dieses Papier lesen ( Kopie auf der Website des Autors ), bevor ich etwas anderes mit dieser Frage mache. Das Konzept "Sicher verknüpfte Verschlüsse" ist dem Suguaro-Stapelsystem insofern sehr ähnlich, als es immer sehr flach ist und nur freie Variablen gemeinsam nutzen soll:

  Unser neuer Closure-Conversion-Algorithmus verwendet sicher verknüpfte Closures (die dritte Spalte in Abbildung 1), die nur tatsächlich in der Funktion benötigte Variablen enthalten, aber das Kopieren von Closures vermeiden, indem Variablen mit derselben Lebensdauer in einem gemeinsam nutzbaren Datensatz gruppiert werden. [...] Im Gegensatz zu verknüpften Verschlüssen überschreitet die Verschachtelungsebene von sicher verknüpften Verschlüssen nie mehr als zwei (eine Schicht für den Verschluss selbst; eine andere für Aufzeichnungen unterschiedlicher Lebensdauer), sodass sie immer noch eine sehr schnelle variable Zugriffszeit haben.

  Das Papier erwähnt auch ausdrücklich, dass es keinen "Laufzeitstapel" verwendet:

  Stattdessen behandeln wir alle Aktivierungsdatensätze als Abschlüsse für Fortsetzungsfunktionen und ordnen sie in Registern im Heap zu.

  Ich glaube, ich habe den Wikipedia-Artikel falsch verstanden und / oder falsch verstanden, da Spaghetti-Stapel nicht zur Flusskontrolle verwendet werden. Nach sorgfältiger Lektüre der Artikel von Appel und Shao könnte ich die Frage jedoch möglicherweise in Bezug auf das Abhängigkeitsdiagramm der Schließungen und nicht auf den "Spaghetti-Call-Stack" (der anscheinend keine Sache ist) wiederholen.

Sind Spaghetti-Stapel Eltern-Zeiger-Bäume?

Ja, Spaghetti-Stapel sind Eltern-Zeiger-Bäume. Sie können sich einen Spaghetti-Stapel mit derselben Struktur vorstellen wie eine Sammlung von einfach verknüpften Listen, die eine gemeinsame Struktur haben. Insgesamt betrachtet bildet die Listensammlung einen Baum. Bei individueller Betrachtung bildet jede Liste einen Stapel.

Jeder Prozess im System verfügt über eine dieser Listen, die den Kontrollstapel darstellt. Der Kopf der Liste befindet sich oben im Stapel (dh aktiver Frame). Sein nextZeiger verweist auf den übergeordneten Frame.

Was Sie im Diagramm sehen, ist die Struktur für mehrere Prozesse. Der Stapel für den "aktiven" Prozess wird hervorgehoben. Die Teile des Baums, die nicht Teil des aktiven Stapels sind, sind ausgegraut. Diese repräsentieren Stapel für andere Prozesse.

Bilden Spaghetti-Stapel eine DAG?

Da Spaghetti-Stapel Eltern-Zeiger-Bäume sind, handelt es sich tatsächlich um DAGs. Aber nur DAGs, die auch Bäume sind, können Spaghetti-Stapel sein. Also nein, Spaghetti-Stapel bilden keine DAGs, die keine Bäume sind.

Ihr Beispiel für eine Entscheidungsfunktion verbindet die Struktur eines Kontrollstapels mit den im Stapel gespeicherten Daten . Natürlich könnte jede Struktur gebildet werden, wenn wir anfangen, die Daten zu berücksichtigen. Als Datenstruktur hat jedoch jeder Knoten in einem Spaghetti-Stapel genau ein übergeordnetes Element.