Laufzeit-Stack

Aufbauen des Stacks

Aus dem gegebenen Programmcode sollen die verschachtelten Funktionsaufrufe zur Laufzeit in Form eines Stacks notiert werden. Pascal ist dabei wunderbar und erschreckend zugleich, da es die verschachtelte Definition von Funktionen erlaubt (die Punkte sind nur Platzhalter für beliebigen sonstigen Code):

        program P;
            function A .....;
            begin ..... C ..... { now } end;
            procedure B (function X .....);
                function D .....;
                begin ..... { here } end;
            begin ..... X ..... B(D) ..... end;
            function C .....;
                procedure E .....;
                begin ..... A ..... { then } end;
            begin ..... E ..... end;
        begin ..... B(A) ..... end;
    

Dafür hat Pascal eine etwas eigene Syntax, was hier mit Farben verdeutlicht wird. Zunächst wird der Kopf der Prozedur oder Funktion definiert, dann etwaige in dieser Funktion wiederum definierte Funktionen, und dann erst der Körper der Funktion. Z.B. wird hier in Prozedur B (Zeile 4) die Prozedur D definiert; beim Aufruf von Prozedur B wird erst die übergebene Funktion (auch das kann Pascal!) ausgeführt und anschließend B(D) ausgeführt.

Eine Prozedur ist eine Funktion ohne Rückgabewert.

Es werden also in folgender Reihenfolge Funktionen aufgerufen und daher auf den Stack gelegt:

• B(A) (Zeile 12): Begonnen wird mit dem Körper des Programms P
• A (Zeile 7): Die an B übergebene Funktion A wird aufgerufen (Parameter X)
• C (Zeile 3): In A wird C aufgerufen

Bevor es weitergeht, sehen wir, dass wir beim Markierungspunkt { now } angekommen sind. Allerdings erst nachdem C und alle enthaltenen Funktionen aufgerufen und wieder beendet wurden – aber dies ist uns hier egal. Dieser Zustand soll als Stack notiert werden, das sieht also für { now } so aus:

Es geht weiter von C bis zum nächsten Markierungspunkt (der also eigentlich vor { now } kommt – aber dies ist uns hier egal):

• E (Zeile 11): In C wird E aufgerufen
• A (Zeile 10): In E wird A aufgerufen

Der Stack sieht nach dem Abräumen von A, also bei { then } so aus:

Man kann sich nun verirren: Wie kommen wir zum { here }? Es hat keinen Sinn, dem A weiter zu folgen, dort würden wir höchstens auf ein weiteres { now } treffen. Wir wollen zu Funktion D und müssen uns dafür Funktion B ansehen, wo wir oben schon waren:

• A (Zeile 7): Die an B übergebene Funktion A wird ausgeführt (Parameter X) und ist irgendwann abgeschlossen
• B(D) (Zeile 7): Danach ruft die Funktion B sich selbst mit D als Parameter auf
• D (Zeile 7): Die an B übergebene Funktion D wird ausgeführt (Parameter X)
• { here } (Zeile 6): In Funktion D wird { here } erreicht

Der Stack für { here }:

Im Stack wird sichtbar, welche Funktionen aktiv (d.h. noch nicht wieder verlassen) sind, wenn ein bestimmter Markierungspunkt zur Laufzeit des Programms erreicht wird.

Zugriffskette (Zeiger rechts)

Dieser Teil ist einfach: Von jeder Funktion auf dem Stack zeigt ein Zeiger auf den Block, in der diese Funktion laut Programmcode definiert ist. Falls dieser Block mehrfach im Stack vorhanden ist, wird immer auf den von der Funktion (also von oben) nächsten Block gezeigt. Im Folgenden werden die notwendigen Zeiger bei { then } zur besseren Unterscheidung farblich hervorgehoben und bei { here } die übliche S/W-Darstellung verwendet. Bei letzterem wird deutlich, dass der Zeiger von D in diesem Fall auf das oberste B zeigen muss.

Jede Funktion zeigt auf ihre erste Deklaration auf dem Pfad zur Wurzel.

Display-Vektoren (Ebenenzeiger)

Für den Einsatz der sogenannten Display-Technik führen wir die Schachtelungstiefe ein. Im Beispielprogramm bestehen drei Schachtelungsebenen: Die erste, in der P definiert ist, die zweite, in der A, B und C definiert sind, und die dritte, in der D und E definiert sind. Stellt man dies schnell graphisch dar, braucht man sich den Programmcode anschließend nicht mehr anzuschauen:

Für jede dieser drei Ebenen soll vermerkt werden, welche Funktion der jeweiligen Ebene aktuell aktiv ist. Wir nennen die dafür eingesetzten Zeiger hier Ebenenzeiger. Der jeweilige Ebenenzeiger zeigt auf die Funktion ganz oben im Stack, wenn sie von dieser Ebene ist, oder auf die oberste Funktion der entsprechenden Ebene, in der die Funktion ganz oben im Stack definiert ist.

Der 1-Ebenenzeiger verbleibt immer auf P. Bei { now } zeigt der 2-Ebenenzeiger auf A, weil A die oberste Funktion auf dem Stack ist und eine Funktion der zweiten Ebene ist. Der 3-Ebenenzeiger zeigt nirgendwohin, da es auf dem Stack keine Funktion dritter Ebene gibt. Bei then zeigt der 3-Ebenenzeiger auf E, weil dies die oberste Funktion ist, der 2-Ebenenzeiger zeigt auf C, weil E, die oberste Funktion, in C definiert ist. Dies ist analog bei { here }: D ist in B definiert, daher zeigt der 2-Ebenenzeiger auf das oberste B.

Betrachten wir kurz ein anderes Beispiel, das nichts mit dem obigen Programmcode zu tun hat! Dafür ist der veränderte Programmbaum daneben aufgezeichnet:

E ist bei diesem abweichenden Beispiel nun in A definiert. Daher zeigt der 2-Ebenenzeiger auf A, nicht auf C. Der 2-Ebenenzeiger zeigt also nicht unbedingt auf die höchste Funktion zweiter Ebene im Stack!

Die Ebenenzeiger berücksichtigen nur die aktuelle Funktion ganz oben im Stack, und die Funktionen, in der diese Funktion definiert ist.

Retten der Display-Vektoren (Zeiger links)

Die Ebenenzeiger müssen gerettet werden, wenn eine neue Funktion auf den Stack gelegt wird, damit nach dem Verlassen dieser Funktion der vorherige Zustand wieder hergestellt werden kann. Die Zeiger links, die wir dafür später hinzufügen wollen, geben an, wo die Ebenenzeiger hin verschoben werden müssen, wenn diese Funktion vom Stack entfernt wird. Sie zeigen von der Funktion, die entfernt wird, auf die Funktion, auf die der Ebenenzeiger danach zeigen muss. Wir entfernen zur Veranschaulichung schrittweise Funktionen vom Stack:

Durch das Entfernen von E vom Stack in Schritt 2 ändert sich zunächst nichts Interessantes: Der 3-Ebenenzeiger wird ganz verworfen, der 2-Ebenenzeiger bleibt auf C. Beim Entfernen von C in Schritt 3 muss aber der 2-Ebenenzeiger zurück auf A gesetzt werden und analog in Schritt 4 von A auf B. Folgende Zeiger müssen daher links eingezeichnet werden:

Die Zeiger links zeigen genau an, welche Veränderungen oben dargestellt wurden: Der 2-Ebenenzeiger wird jeweils um eins nach unten verschoben. An dieser Stelle sollten die Zeiger der jeweiligen Ebenen farbig markiert werden, um sie später (wenn bei anderen Fällen auch Zeiger der dritten Ebene erscheinen) unterscheiden zu können. Wir markieren hier Ebene 2 rot und Ebene 3 blau.

Wird über einer Funktion dritter Ebene eine Funktion zweiter Ebene auf den Stack gelegt, verbleibt der 3-Ebenenzeiger, wo er ist.

Betrachten wir erneut ein vom Programmcode zu Beginn unabhängiges Beispiel:

Wenn D, eine Funktion dritter Ebene, oben vom Stack entfernt wird, muss der 3-Ebenenzeiger danach auf E und der 2-Ebenenzeiger auf B zeigen, weil E dann die oberste Funktion ist und E in B definiert ist. Daher geht ein blauer Zeiger von D nach E und ein roter Zeiger von D nach B. Sehen wir uns dieses separate Beispiel ebenfalls Schritt für Schritt an, wobei hier auch die Rettungszeiger des jeweiligen Schrittes eingezeichnet sind:

Ab dem zweiten Schritt wird nur noch der 2-Ebenenzeiger bewegt. Nach dem Entfernen von E muss der 2-Ebenenzeiger auf A und nicht mehr auf B zeigen. Daher geht ein roter Zeiger von E nach A (und wohlgemerkt nicht von B nach A!). Nach dem Entfernen von A zum vierten Schritt zeigt der 2-Ebenenzeiger dann wieder auf B, daher ein Zeiger von A nach B.

Die Schritt-für-Schritt-Aufzeichnung ist nicht erforderlich, sondern lediglich zur Veranschaulichung gedacht. Erwartet wird nur die Aufzeichnung mit allen Zeigern zu den jeweiligen Markierungspunkten.

Wenn eine Funktion vom Stack entfernt wird, muss bekannt sein, wo die Ebenenzeiger danach hinzeigen sollen. Dies wird durch Zeiger, die von der zu entfernenden Funktion ausgehen (und nicht von der aktuellen Position des Ebenenzeigers!), angegeben.