Erste Programme liefen einfach von Anfang bis Ende und fertig, es wurde Anweisung nach Anweisung befolgt, bis das Programm abgelaufen war. „Moderne“ Programmiersprachen - und dazu gehört auch bereits Assembler auf so etwa allem, was wir als Prozessor kennen - verwenden zur Ablaufsteuerung eine Datenstruktur. C ist sehr maschinennah und verwendet daher die gleichen Datenstruktur wie Assembler und damit der Prozessor: einen Stack. Die meisten Prozessoren besitzen ein eigenes Register für den Stack. In diesem Artikel gehen wir also sehr nah an die Maschine heran und wollen vor allem verstehen, wie normale Programme seit den 50er Jahren eigentlich funktionieren.

Es gibt auch Programmiersprachen, die andere Datenstrukturen verwenden: Die Programmiersprache LISP verwendet zum Beispiel Listen. Dies ist jedoch so außergewöhnlich, dass es sich gleich entsprechend im Namen widerspiegelt: List Processing.

Stack wird im deutschen häufig als „Kellerspeicher“ übersetzt. Besser gefällt mir jedoch die ebenfalls übliche Übersetzung „Stapelspeicher“. Ein Stapelspeicher funktioniert genau wie ein Papierstapel: Man schreibt sich eine Notiz „A“ und legt sie oben auf den Stapel. Wenn man auf den Stapel schaut, sieht man seine Notiz „A“. Schreibt man eine neue Notiz „B“ und legt diese auf den Stapel, so ist die vorherige Notiz „A“ nicht verschwunden, aber nicht mehr so einfach zu erreichen. Man kann die Notiz „A“ auch nicht mehr vom Stapel nehmen, ohne Notiz „B“ ebenfalls vom Stapel zu nehmen.
Und das ist genau die Charakteristik eines Stacks, eines Stapels.

Wie schon beschrieben organisieren viele Programmiersprachen die Ablaufsteuerung über einen Stack. Zu organisieren sind Funktionsaufrufe, deren Parameter und Rückgaben, sowie lokale Variablen, innerhalb einer Funktion definiert werden. Beim Funktionsaufruf werden die Parameter und die Information, wo die Funktion überhaupt gerufen wird, auf eine Notiz geschrieben, damit man am Ende der Funktion an diese Stelle zurückspringen kann. Da am Ende jeder Funktion zur rufenden Funktion zurückgesprungen werden muss und man innerhalb von Funktionen auch andere Funktionen rufen kann, muss hier ein Stapel angelegt werden, wobei auf der obersten Notiz steht, wohin ich zurückspringen muss. Zusätzlich wird auf der Notiz soviel Platz gelassen, dass alle lokalen Variablen untergebracht werden können, so dass jede Funktion eigene, lokale Variablen definieren kann.
Nun wird die Notiz auf den Stapel gelegt und der Prozessor aufgefordert die Anweisungen der Funktion auszuführen. Am Ende der Funktion, bzw. bei einer return-Anweisung wird das Ergebnis auf die Notiz geschrieben. Danach wird von einer Notiz abgelesen woher die Funktion aufgerufen wurde, damit der Prozessor die nächsten Anweisungen findet und die Notiz mit dem Ergebnis hinterlegt. Die rufende Funktion kann sich nun das Ergebnis holen. Eine solche Notiz, mit der eine Funktion arbeitet und ihre lokalen Variablen ablegt, nennt man Frame (zu Deutsch Rahmen). Das ist der Rahmen in dem sich eine Funktion mit seinen lokalen Variablen bewegen darf und den sie nicht verlassen darf.
Was passiert, wenn man den Rahmen doch verlässt, beschreibe ich einem späteren Artikel „Buffer Overflow“, aber das ist zum Erlernen von C zunächst nicht wichtig.
Diese Vorgehensweise erlaubt es auch, dass Funktionen sich selbst wieder rufen können, da für jeden Funktionsaufruf eine eigene Notiz angelegt wird und damit jeder Funktionsaufruf eigene Parameter und lokalen Variablen besitzt. Dieses Verfahren, die eigene Funktion wieder aufzurufen, nennt sich Rekursion. Auch hierauf werden wir noch eingehen.

Der Stack funktioniert in der Regel sehr einfach. Schauen wir uns folgendes Programm an:

int add( int summand1, int summand2 )
{
  int temp;
 
  temp = summand1 + summand2;
 
  return temp;
}
 
int main( void )
{
  int temp;
 
  temp = add( 4, 5 );
 
  printf( "Ergebnis: %d\n", temp );
 
  return 0;
}

Wenn das Programm gestartet wird, bereitet das Betriebssystem einen großen Speicherbereich vor, der als Stack dient. Das Register im Prozessor erhält den Zeiger auf den Speicherbereich: Den sogenannten „Stackpointer“.

Der Compiler hat für die Funktion main zusammengerechnet, dass ihr Frame aus einer lokalen Variable (int temp, 4 Byte) und einem Rückgabewert (int, 4 Byte) besteht¹⁾. Dazu kommt die Rücksprungadresse (4 Byte für 32Bit-Systeme oder 8 Byte bei 64Bit-Systemen). Damit hat das Frame eine Größe von 12 (bzw. 16) Bytes. Die unterschiedliche Größe der Zeiger und sorgt dafür, dass die Frames für 32- und 64-Bit-Systeme unterschiedlich groß sein müssen, daher laufen 64-Bit-Programme auch nicht auf 32-Bit-Systemen. Dieser Platz wird auf dem Stack reserviert. Diese Reservierung wird „Push“ genannt. Das geht äußerst schnell, da man den Stackpointer, der auf den Speicherbereich des Frames der aktuellen Funktion zeigt, lediglich um 12 bzw. 16 Byte verschiebt. Diese Frames liegen im Speicher also direkt hintereinander.

Nun kann das Betriebssystem zur Funktion main() springen und diese ausführen. Hierbei wird die Rücksprungadresse ins Frame kopiert. Die erste Anweisung ist „int temp“, sie hat ihre Aufgabe bereits erledigt, sie hat für Platz auf dem Stack gesorgt. Diese Anweisung wird sich im kompilierten Programm also gar nicht wiederfinden. Die erste Anweisung, die etwas tut, ist „temp = add( 4, 5 )“.

Auch hier hat der Compiler die Framegröße berechnet: 2 Integer als Parameter, 1 Integer als Rückgabe und 1 Integer als lokale Variable: 16 Bytes + Rücksprungadresse ergibt eine Framegröße 20 Bytes (auf 64 Systemen 24 Bytes), die nun auf den Stack „gepusht“ werden (der Stackpointer wird also 20 bzw. 24 Bytes verschoben). Anschließend wird der Wert 4 an die Position kopiert, an der „summand1' auf dem Stack liegt und Wert 5 wird an die Stelle im Stack kopiert, an der „summand2“ liegt. Noch die Rücksprungadresse (nämlich da, wo die Zuweisung nach temp in main steht) auf den Stack und anschließend kann zu den Anweisungen der Funktion add() gesprungen werden.

Die erste Anweisung bei add() ist „temp = summand1 + summand2;“, es wird also der Wert, der im Frame bei „summand1“ steht mit dem Wert, der im Frame bei „summand2“ steht addiert und das Ergebnis anschließend an die Stelle im Frame kopiert, an der sich die lokale Variable „temp“ befindet. Die Stelle, die wir in C mit „temp“ bezeichnen, hat nun den Wert 9. Die letzte Anweisung ist „return temp;“, hier wird die Stelle „temp“ im Frame geladen und der Wert an die Stelle im Frame kopiert, die den Rückgabewert der Funktion enthalten soll. Damit enthält die Stelle für den Rückgabewert nun auch den Wert 9. Das war's, die Funktion add() ist durchgearbeitet, jetzt kann das Programm da fortgesetzt werden, wo die Rücksprungadresse hinzeigt. Mit dem Rücksprung wird das Frame vom Stack genommen. Dies nennt man „pop“ - der Stackpointer wird die 20 Byte (bzw. 24 Byte) zurückgeschoben.

Nachdem add() ausgeführt wurde, muss das Rückgabeergebnis noch ausgelesen werden. Das ist ja auch kein Problem, denn der Wert liegt ja noch auf dem Stack, nur dass der Wert außerhalb des dem eigenen Frames liegt. Wo genau hat der Compiler vorher berechnet. Die Zuweisung kopiert also nun von der Stelle des Rückgabewertes der zuletzt gerufenen Funktion den Wert auf die Stelle „temp“ im eigenen Frame. So kommt die „9“ endlich auf der eigenen lokalen Variablen an.

So kann das Programm weiterlaufen bis auch main durchlaufen ist und main zurück zum aufrufenden Programm springt (zum Beispiel die Konsole, die während das Programm lief warten musste).

: Skizzen folgen, bei Bedarf Xin im Forum anmeckern!

Der Stack ist natürlich nicht nur für die Programmiersprache selbst vorgesehen, moderne Computer verwenden diese Datenstruktur nur, um die Aufrufreihenfolge der Funktionen zu organisieren. Es steht jedem frei, Stacks auch für eigene Programme zu implementieren. Ein Stack hilft immer dann, wenn die Ausführung einer Anweisung warten muss. Bei einem Funktionsruf muss die Ausführung der rufenden Funktion warten. Bei einem Taschenrechner, der die Aufgabe „1+2*3“ lösen muss, muss die Operation „1+“ warten, bis die Operation „2*3“ ausgerechnet ist.

Diese Lektion war eher theoretischer Natur und hat Dir hoffentlich das Prinzip nähergebracht, wie Funktionen in C (und vielen anderen Programmiersprachen) gerufen werden und wieso man Ende einer gerufenen Funktion wieder an der rufenden Funktion zurückkommt.

Die Datenstruktur „Stack“ ist die erste Datenstruktur, die wir in diesem Tutorial betrachten. Wer programmieren lernt, muss lernen mit Datenstrukturen umzugehen und sie dann in der gewählten Programmiersprache zu beschreiben. Eine Implementation der Datenstruktur Stack für Integers in C findet sich hier. In diesem Artikel lässt sich ebenfalls schön das Zusammenspiel von Arrays, Strukturen und dynamischer Speicherverwaltung erkennen.

In der kommenden Lektion werden wir uns damit beschäftigen, wie man Strukturen organisiert und eine neue Datenstruktur kennen lernen: Listen.

Datenstrukturen: Stack