Ich verstehe, was ein Stapelzeiger ist - aber wofür wird er verwendet?

Der Stapelzeiger zeigt auf den oberen Rand des Stapels, in dem Daten auf einer sogenannten "LIFO" -Basis gespeichert werden. Um die Analogie eines anderen zu stehlen, ist es wie ein Stapel Geschirr, in das Sie Geschirr oben legen und nehmen. Der Stapelzeiger OTOH zeigt auf die oberste "Schüssel" des Stapels. Zumindest gilt das für x86.

Aber warum "kümmert" sich der Computer / das Programm darum, auf was der Stapelzeiger zeigt? Mit anderen Worten, welchen Zweck hat es, den Stapelzeiger zu haben und zu wissen, wohin er zeigt, um zu dienen?

Eine für C-Programmierer verständliche Erklärung wäre willkommen.

Welchen Zweck erfüllt dieser Stapel tatsächlich, anstatt seine Struktur zu erklären?

Sie haben viele Antworten, die die Struktur der auf dem Stapel gespeicherten Daten genau beschreiben. Ich stelle fest, dass dies das Gegenteil der von Ihnen gestellten Frage ist.

Der Zweck des Stapels ist: Der Stapel ist Teil der Verdinglichung der Fortsetzung in einer Sprache ohne Coroutinen .

Packen wir das aus.

Fortsetzung ist einfach ausgedrückt, die Antwort auf die Frage "Was wird als nächstes in meinem Programm passieren?" An jedem Punkt in jedem Programm wird als nächstes etwas passieren. Es werden zwei Operanden berechnet, dann fährt das Programm mit der Berechnung ihrer Summe fort, und dann fährt das Programm fort, indem die Summe einer Variablen zugewiesen wird, und dann ... und so weiter.

Reification ist nur ein hochkarätiges Wort für die konkrete Umsetzung eines abstrakten Konzepts. "Was passiert als nächstes?" ist ein abstraktes Konzept; Die Art und Weise, wie der Stapel angeordnet ist, ist ein Teil davon, wie dieses abstrakte Konzept in eine reale Maschine verwandelt wird, die wirklich Dinge berechnet.

Coroutinen sind Funktionen, die sich daran erinnern können, wo sie sich befanden, für eine Weile die Kontrolle an eine andere Coroutine abgeben und dann dort wieder aufgenommen werden, wo sie später aufgehört haben, jedoch nicht unbedingt unmittelbar nach den so genannten Coroutinenerträgen. Denken Sie an "Yield Return" oder "Warten" in C #, das sich daran erinnern muss, wo sie sich befanden, als das nächste Element angefordert oder der asynchrone Vorgang abgeschlossen wurde. Sprachen mit Coroutinen oder ähnlichen Sprachfunktionen erfordern erweiterte Datenstrukturen als ein Stapel, um die Fortsetzung zu implementieren.

Wie implementiert ein Stack die Fortsetzung? Andere Antworten sagen wie. Der Stapel speichert (1) Werte von Variablen und Provisorien, deren Lebensdauer bekanntermaßen nicht größer als die Aktivierung der aktuellen Methode ist, und (2) die Adresse des Fortsetzungscodes, der der letzten Methodenaktivierung zugeordnet ist. In Sprachen mit Ausnahmebehandlung kann der Stapel auch Informationen über die "Fehlerfortsetzung" speichern - das heißt, was das Programm als nächstes tun wird, wenn eine Ausnahmesituation auftritt.

Lassen Sie mich diese Gelegenheit nutzen, um festzustellen, dass der Stapel Ihnen nicht sagt, "woher komme ich?" - obwohl es oft so beim Debuggen verwendet wird. Der Stapel gibt an, wohin Sie als Nächstes gehen und welche Werte die Variablen der Aktivierung haben, wenn Sie dort ankommen . Die Tatsache, dass in einer Sprache ohne Coroutinen, wohin Sie als nächstes gehen, fast immer dort ist, wo Sie herkommen, erleichtert diese Art des Debuggens. Es ist jedoch nicht erforderlich, dass ein Compiler Informationen darüber speichert, woher die Steuerung stammt, wenn er ohne dies entkommen kann. Tail-Call-Optimierungen zerstören beispielsweise Informationen darüber, woher die Programmsteuerung stammt.

Warum verwenden wir den Stack, um die Fortsetzung in Sprachen ohne Coroutinen zu implementieren? Da das Merkmal der synchronen Aktivierung von Methoden darin besteht, dass das Muster "Aktuelle Methode aussetzen, andere Methode aktivieren, aktuelle Methode fortsetzen und das Ergebnis der aktivierten Methode kennen", wenn es mit sich selbst zusammengesetzt ist, logisch einen Stapel von Aktivierungen bildet. Das Erstellen einer Datenstruktur, die dieses stapelartige Verhalten implementiert, ist sehr billig und einfach. Warum ist es so billig und einfach? Denn Chipsätze wurden seit vielen Jahrzehnten speziell entwickelt, um Compilern diese Art der Programmierung zu erleichtern.

Die grundlegendste Verwendung des Stapels ist das Speichern der Rücksprungadresse für Funktionen:

void a(){
    sub();
}
void b(){
    sub();
}
void sub() {
    //should i got back to a() or to b()?
}

und aus C-Sicht ist das alles. Aus Compilersicht:

• Alle Funktionsargumente werden von CPU-Registern übergeben. Wenn nicht genügend Register vorhanden sind, werden die Argumente gestapelt
• Nach Beendigung der Funktion sollten (die meisten) Register dieselben Werte wie vor der Eingabe haben. Daher werden die verwendeten Register auf dem Stapel gesichert

Und aus Sicht des Betriebssystems: Das Programm kann jederzeit unterbrochen werden. Nachdem wir mit der Systemaufgabe fertig sind, müssen wir den CPU-Status wiederherstellen, sodass wir alles auf dem Stapel speichern können

All dies funktioniert, da es uns egal ist, wie viele Elemente sich bereits auf dem Stapel befinden oder wie viele Elemente in Zukunft jemand anderes hinzufügen wird. Wir müssen nur wissen, um wie viel wir den Stapelzeiger verschoben und ihn wiederhergestellt haben, nachdem wir fertig sind.

LIFO gegen FIFO

LIFO steht für Last In, First Out. Wie in ist der letzte Gegenstand, der in den Stapel gelegt wird, der erste Gegenstand, der aus dem Stapel genommen wird.

Was Sie mit Ihrer Geschirranalogie (in der ersten Überarbeitung ) beschrieben haben, ist eine Warteschlange oder ein FIFO, First In, First Out.

Der Hauptunterschied zwischen den beiden besteht darin, dass der LIFO / Stapel am selben Ende drückt (Einfügungen) und platzt (entfernt) und ein FIFO / eine Warteschlange dies an entgegengesetzten Enden tut.

// Both:

Push(a)
-> [a]
Push(b)
-> [a, b]
Push(c)
-> [a, b, c]

// Stack            // Queue
Pop()               Pop()
-> [a, b]           -> [b, c]

Der Stapelzeiger

Werfen wir einen Blick darauf, was unter der Haube des Stapels passiert. Hier ist etwas Speicher, jede Box ist eine Adresse:

...[ ][ ][ ][ ]...                       char* sp;
    ^- Stack Pointer (SP)

Und es gibt einen Stapelzeiger, der auf den unteren Rand des aktuell leeren Stapels zeigt (ob der Stapel wächst oder wächst, ist hier nicht besonders relevant, daher werden wir das ignorieren, aber in der realen Welt bestimmt dies natürlich, welche Operation hinzugefügt wird und die vom SP subtrahiert).

Also lasst uns noch einmal pushen a, b, and c. Grafik links, "High Level" -Operation in der Mitte, C-ish Pseudocode rechts:

...[a][ ][ ][ ]...        Push('a')      *sp = 'a';
    ^- SP
...[a][ ][ ][ ]...                       ++sp;
       ^- SP

...[a][b][ ][ ]...        Push('b')      *sp = 'b';
       ^- SP
...[a][b][ ][ ]...                       ++sp;
          ^- SP

...[a][b][c][ ]...        Push('c')      *sp = 'c';
          ^- SP
...[a][b][c][ ]...                       ++sp;
             ^- SP

Wie Sie sehen können, wird jedes Mal pushdas Argument an der Stelle eingefügt, auf die der Stapelzeiger gerade zeigt, und der Stapelzeiger wird so angepasst, dass er auf die nächste Stelle zeigt.

Jetzt lass uns knallen:

...[a][b][c][ ]...        Pop()          --sp;
          ^- SP
...[a][b][c][ ]...                       return *sp; // returns 'c'
          ^- SP
...[a][b][c][ ]...        Pop()          --sp;
       ^- SP
...[a][b][c][ ]...                       return *sp; // returns 'b'
       ^- SP

Popist das Gegenteil von push, es passt den Stapelzeiger so an, dass er auf die vorherige Position zeigt, und entfernt das Element, das dort war (normalerweise, um es an den Anrufer zurückzugeben pop).

Sie haben das wahrscheinlich bemerkt bund csind immer noch in Erinnerung. Ich möchte Ihnen nur versichern, dass dies keine Tippfehler sind. Wir werden in Kürze darauf zurückkommen.

Leben ohne Stapelzeiger

Mal sehen, was passiert, wenn wir keinen Stapelzeiger haben. Beginnen Sie erneut mit dem Schieben:

...[ ][ ][ ][ ]...
...[ ][ ][ ][ ]...        Push(a)        ? = 'a';

Ähm, hmm ... wenn wir keinen Stapelzeiger haben, können wir nichts an die Adresse verschieben, auf die es zeigt. Vielleicht können wir einen Zeiger verwenden, der auf die Basis anstatt auf die Oberseite zeigt.

...[ ][ ][ ][ ]...                       char* bp; // "base pointer"
    ^- bp                                bp = malloc(...);

...[a][ ][ ][ ]...        Push(a)        *bp = 'a';
    ^- bp
// No stack pointer, so no need to update it.
...[b][ ][ ][ ]...        Push(b)        *bp = 'b';
    ^- bp

Oh oh. Da wir den festen Wert der Stapelbasis nicht ändern können, haben wir den Wert einfach überschrieben, aindem wir ihn ban dieselbe Stelle verschoben haben .

Warum verfolgen wir nicht, wie oft wir gepusht haben? Und wir müssen auch die Zeiten verfolgen, in denen wir aufgetaucht sind.

...[ ][ ][ ][ ]...                       char* bp; // "base pointer"
    ^- bp                                bp = malloc(...);
                                         int count = 0;

...[a][ ][ ][ ]...        Push(a)        bp[count] = 'a';
    ^- bp
...[a][ ][ ][ ]...                       ++count;
    ^- bp
...[a][b][ ][ ]...        Push(a)        bp[count] = 'b';
    ^- bp
...[a][b][ ][ ]...                       ++count;
    ^- bp
...[a][b][ ][ ]...        Pop()          --count;
    ^- bp
...[a][b][ ][ ]...                       return bp[count]; //returns b
    ^- bp

Nun, es funktioniert, aber es ist eigentlich ziemlich ähnlich wie zuvor, außer dass *pointeres billiger ist als pointer[offset](keine zusätzliche Arithmetik), ganz zu schweigen davon, dass es weniger zu tippen ist. Das scheint mir ein Verlust zu sein.

Lass es uns erneut versuchen. Anstatt den Pascal-Zeichenfolgenstil zu verwenden, um das Ende einer Array-basierten Sammlung zu finden (Verfolgen der Anzahl der Elemente in der Sammlung), versuchen wir den C-Zeichenfolgenstil (Scannen vom Anfang bis zum Ende):

...[ ][ ][ ][ ]...                       char* bp; // "base pointer"
    ^- bp                                bp = malloc(...);

...[ ][ ][ ][ ]...        Push(a)        char* top = bp;
    ^- bp, top
                                         while(*top != 0) { ++top; }
...[ ][ ][ ][a]...                       *top = 'a';
    ^- bp    ^- top

...[ ][ ][ ][ ]...        Pop()          char* top = bp;
    ^- bp, top
                                         while(*top != 0) { ++top; }
...[ ][ ][ ][a]...                       --top;
    ^- bp       ^- top                   return *top; // returns '('

Möglicherweise haben Sie das Problem hier bereits erraten. Es ist nicht garantiert, dass der nicht initialisierte Speicher 0 ist. Wenn wir also nach der obersten Position suchen a, überspringen wir eine Reihe nicht verwendeter Speicherorte, in denen sich zufälliger Müll befindet. Wenn wir nach oben scannen, überspringen wir in ähnlicher Weise weit über das hinaus, was awir gerade gedrückt haben, bis wir endlich einen anderen Speicherort finden, der sich gerade befindet 0, und gehen zurück und geben den zufälligen Müll kurz davor zurück.

Das ist einfach zu beheben. Wir müssen nur Operationen hinzufügen Pushund Popsicherstellen, dass die Oberseite des Stapels immer aktualisiert wird, um mit einem gekennzeichnet zu werden 0, und wir müssen den Stapel mit einem solchen Abschlusszeichen initialisieren. Das bedeutet natürlich auch, dass wir keinen 0(oder einen beliebigen Wert, den wir als Terminator auswählen) als tatsächlichen Wert im Stapel haben können.

Darüber hinaus haben wir O (1) -Operationen in O (n) -Operationen geändert.

TL; DR

Der Stapelzeiger verfolgt den oberen Rand des Stapels, in dem die gesamte Aktion ausgeführt wird. Es gibt Möglichkeiten, es loszuwerden ( bp[count]und topsind im Wesentlichen immer noch der Stapelzeiger), aber beide sind komplizierter und langsamer als nur der Stapelzeiger. Und wenn Sie nicht wissen, wo sich die Oberseite des Stapels befindet, können Sie den Stapel nicht verwenden.

Hinweis: Der Stapelzeiger, der in x86 auf den "unteren Rand" des Laufzeitstapels zeigt, kann ein Missverständnis sein, das damit zusammenhängt, dass der gesamte Laufzeitstapel auf dem Kopf steht. Mit anderen Worten, die Basis des Stapels befindet sich an einer hohen Speicheradresse, und die Spitze des Stapels wächst zu niedrigeren Speicheradressen herab. Der Stapelzeiger zeigt auf die Spitze des Stapels, an der die gesamte Aktion ausgeführt wird. Nur diese Spitze befindet sich an einer niedrigeren Speicheradresse als die Basis des Stapels.

Der Stapelzeiger wird (mit dem Rahmenzeiger) für den Aufrufstapel verwendet (folgen Sie dem Link zu Wikipedia, wo es ein gutes Bild gibt).

Der Aufrufstapel enthält Aufrufrahmen, die die Rücksprungadresse, lokale Variablen und andere lokale Daten enthalten (insbesondere verschütteten Inhalt von Registern; Formale).

Lesen Sie auch Informationen zu Tail-Aufrufen (einige Tail-rekursive Aufrufe benötigen keinen Aufrufrahmen ), Ausnahmebehandlung (wie setjmp & longjmp , bei der möglicherweise viele Stapelrahmen gleichzeitig gepoppt werden), Signalen und Interrupts sowie Fortsetzungen . Siehe auch Aufrufkonventionen und Application Binary Interfaces (ABIs), insbesondere das x86-64 ABI (das definiert, dass einige formale Argumente von Registern übergeben werden).

Codieren Sie außerdem einige einfache Funktionen in C, gcc -Wall -O -S -fverbose-asm kompilieren Sie sie dann und sehen Sie sich die generierte .s Assembler-Datei an.

Appel schrieb ein altes Papier aus dem Jahr 1986, in dem behauptet wurde, dass die Speicherbereinigung schneller sein kann als die Stapelzuweisung (unter Verwendung des Continuation-Passing-Stils im Compiler). Dies ist jedoch auf den heutigen x86-Prozessoren wahrscheinlich falsch (insbesondere aufgrund von Cache-Effekten).

Beachten Sie, dass Aufrufkonventionen, ABIs und Stapellayout bei 32-Bit-i686 und bei 64-Bit-x86-64 unterschiedlich sind. Außerdem können Anrufkonventionen (und wer für das Zuweisen oder Löschen des Anrufrahmens verantwortlich ist) in verschiedenen Sprachen unterschiedlich sein (z. B. haben C, Pascal, Ocaml, SBCL Common Lisp unterschiedliche Anrufkonventionen ....).

Übrigens legen die jüngsten x86-Erweiterungen wie AVX dem Stapelzeiger zunehmend größere Ausrichtungsbeschränkungen auf (IIRC, ein Aufrufrahmen auf x86-64 möchte auf 16 Bytes ausgerichtet sein, dh zwei Wörter oder Zeiger).

In einfachen Worten, das Programm kümmert sich darum, weil es diese Daten verwendet und nachverfolgen muss, wo sie zu finden sind.

Wenn Sie lokale Variablen in einer Funktion deklarieren, werden sie im Stapel gespeichert. Wenn Sie eine andere Funktion aufrufen, speichert der Stapel die Rücksprungadresse, damit er zu der Funktion zurückkehren kann, in der Sie sich befanden, als die von Ihnen aufgerufene beendet wurde, und dort weitermachen kann, wo sie aufgehört hat.

Ohne den SP wäre eine strukturierte Programmierung, wie wir sie kennen, im Wesentlichen unmöglich. (Sie könnten umgehen, wenn Sie es nicht haben, aber es würde so ziemlich die Implementierung einer eigenen Version erfordern, also ist das kein großer Unterschied.)

Für den Prozessorstapel in einem x86-Prozessor ist die Analogie eines Geschirrstapels wirklich ungenau.
Aus verschiedenen (meist historischen) Gründen wächst der Prozessorstapel von der Oberseite des Speichers zur Unterseite des Speichers, sodass eine bessere Analogie eine Kette von Kettengliedern wäre, die von der Decke hängen. Wenn Sie etwas auf den Stapel schieben, wird dem untersten Glied ein Kettenglied hinzugefügt.

Der Stapelzeiger bezieht sich auf das unterste Glied der Kette und wird vom Prozessor verwendet, um zu "sehen", wo sich dieses niedrigste Glied befindet, so dass Glieder hinzugefügt oder entfernt werden können, ohne die gesamte Kette von der Decke nach unten bewegen zu müssen.

In gewisser Weise steht der Stapel in einem x86-Prozessor auf dem Kopf, aber es wird eine normale Stapelterminologie verwendet, sodass die niedrigste Verbindung als die Oberseite des Stapels bezeichnet wird.

Die Kettenglieder, auf die ich oben Bezug genommen habe, sind tatsächlich Speicherzellen in einem Computer und werden verwendet, um lokale Variablen und einige Zwischenergebnisse von Berechnungen zu speichern. Computerprogramme kümmern sich darum, wo sich die Spitze des Stapels befindet (dh wo diese niedrigste Verbindung hängt), da die große Mehrheit der Variablen, auf die eine Funktion zugreifen muss, in der Nähe der Stelle existiert, auf die sich der Stapelzeiger bezieht, und ein schneller Zugriff auf sie wünschenswert ist.

Diese Antwort bezieht sich speziell auf den Stapelzeiger des aktuellen Threads (der Ausführung) .

In prozeduralen Programmiersprachen hat ein Thread normalerweise Zugriff auf einen Stapel ¹ für die folgenden Zwecke:

• Kontrollfluss, nämlich "Call Stack".
  • Wenn eine Funktion eine andere Funktion aufruft, merkt sich der Aufrufstapel, wohin er zurückkehren soll.
  • Ein Aufrufstapel ist notwendig, weil sich ein "Funktionsaufruf" so verhalten soll - "dort weitermachen, wo wir aufgehört haben" .
  • Es gibt andere Programmierstile, die während der Ausführung keine Funktionsaufrufe haben (z. B. darf die nächste Funktion nur angegeben werden, wenn das Ende der aktuellen Funktion erreicht ist) oder überhaupt keine Funktionsaufrufe haben (nur mit goto und bedingten Sprüngen ). Diese Programmierstile benötigen möglicherweise keinen Aufrufstapel.
• Funktionsaufrufparameter.
  • Wenn eine Funktion eine andere Funktion aufruft, können Parameter auf den Stapel verschoben werden.
  • Der Anrufer und der Angerufene müssen die gleiche Konvention befolgen, die besagt, wer für das Löschen der Parameter aus dem Stapel verantwortlich ist, wenn der Anruf beendet ist.
• Lokale Variablen, die innerhalb eines Funktionsaufrufs leben.
  • Beachten Sie, dass eine lokale Variable, die zu einem Aufrufer gehört, einem Angerufenen zugänglich gemacht werden kann, indem ein Zeiger auf diese lokale Variable an den Angerufenen übergeben wird.

Hinweis ¹ : Für die Verwendung des Threads vorgesehen, obwohl sein Inhalt von anderen Threads vollständig gelesen und zerschlagen werden kann.

In der Assembly-Programmierung C und C ++ können alle drei Zwecke von demselben Stapel erfüllt werden. In einigen anderen Sprachen können einige Zwecke durch separate Stapel oder dynamisch zugewiesenen Speicher erfüllt werden.

Hier ist eine absichtlich stark vereinfachte Version dessen, wofür der Stapel verwendet wird.

Stellen Sie sich den Stapel als Stapel Karteikarten vor. Der Stapelzeiger zeigt auf die oberste Karte.

Wenn Sie eine Funktion aufrufen:

• Sie schreiben die Adresse des Codes unmittelbar nach der Zeile, in der die Funktion aufgerufen wurde, auf eine Karte und legen sie auf den Stapel. (Dh Sie erhöhen den Stapelzeiger um eins und schreiben die Adresse an die Stelle, auf die sie zeigt.)
• Dann schreiben Sie die in den Registern enthaltenen Werte auf einige Karten und legen sie auf den Stapel. (dh Sie erhöhen den Stapelzeiger um die Anzahl der Register und kopieren den Registerinhalt an die Stelle, auf die er zeigt.)
• Dann legst du eine Markierungskarte auf den Stapel. (dh Sie speichern den aktuellen Stapelzeiger.)
• Dann schreiben Sie den Wert jedes Parameters, mit dem die Funktion aufgerufen wird, eins auf eine Karte und legen ihn auf den Stapel. (dh Sie erhöhen den Stapelzeiger um die Anzahl der Parameter und schreiben die Parameter an die Stelle, auf die der Stapelzeiger zeigt.)
• Anschließend fügen Sie für jede lokale Variable eine Karte hinzu und schreiben möglicherweise den Anfangswert darauf. (dh Sie erhöhen den Stapelzeiger um die Anzahl der lokalen Variablen.)

Zu diesem Zeitpunkt wird der Code in der Funktion ausgeführt. Der Code wird zusammengestellt, um zu wissen, wo sich jede Karte relativ zur Oberseite befindet. Es ist also bekannt, dass die Variable xdie dritte Karte von oben ist (dh der Stapelzeiger - 3) und dass der Parameter ydie sechste Karte von oben ist (dh der Stapelzeiger - 6.)

Diese Methode bedeutet, dass die Adresse jeder lokalen Variablen oder jedes lokalen Parameters nicht in den Code eingebrannt werden muss. Stattdessen werden alle diese Datenelemente relativ zum Stapelzeiger adressiert.

Wenn die Funktion zurückkehrt, ist die umgekehrte Operation einfach:

• Suchen Sie nach der Markierungskarte und werfen Sie alle Karten darüber weg. (dh setzen Sie den Stapelzeiger auf die gespeicherte Adresse.)
• Stellen Sie die Register der zuvor gespeicherten Karten wieder her und werfen Sie sie weg. (dh einen festen Wert vom Stapelzeiger subtrahieren)
• Starten Sie den Code von der Adresse auf der Karte oben und werfen Sie ihn dann weg. (dh 1 vom Stapelzeiger subtrahieren.)

Der Stapel befindet sich jetzt wieder in dem Zustand, in dem er vor dem Aufruf der Funktion war.

Wenn Sie dies berücksichtigen, beachten Sie zwei Dinge: Die Zuweisung und Freigabe von Einheimischen ist eine extrem schnelle Operation, da nur eine Zahl zum Stapelzeiger hinzugefügt oder von diesem abgezogen wird. Beachten Sie auch, wie natürlich dies mit Rekursion funktioniert.

Dies ist zu Erklärungszwecken zu stark vereinfacht. In der Praxis können Parameter und Lokale als Optimierung in Register eingetragen werden, und der Stapelzeiger wird im Allgemeinen um die Wortgröße der Maschine inkrementiert und dekrementiert, nicht um eine. (Um ein paar Dinge zu nennen.)

Wie Sie wissen, unterstützen moderne Programmiersprachen das Konzept von Unterprogrammaufrufen (am häufigsten als "Funktionsaufrufe" bezeichnet). Dies bedeutet, dass:

1. In der Mitte eines Codes können Sie eine andere Funktion in Ihrem Programm aufrufen .
2. Diese Funktion weiß nicht explizit, woher sie aufgerufen wurde.
3. Wenn die Arbeit erledigt ist und sie abgeschlossen ist, returnkehrt die Steuerung jedoch zu dem genauen Punkt zurück, an dem der Anruf initiiert wurde, wobei alle lokalen Variablenwerte zum Zeitpunkt der Initiierung des Anrufs wirksam sind.

Wie verfolgt der Computer das? Es wird fortlaufend aufgezeichnet, welche Funktionen auf welche Rückrufe warten. Dieser Datensatz ist ein Stapel - und da er so wichtig ist, nennen wir ihn normalerweise den Stapel.

Und da dieses Call / Return-Muster so wichtig ist, wurden CPUs seit langem so konzipiert, dass sie spezielle Hardwareunterstützung bieten. Der Stapelzeiger ist eine Hardwarefunktion in CPUs - ein Register, das ausschließlich dazu dient, den oberen Rand des Stapels zu verfolgen, und das von den Anweisungen der CPU zum Verzweigen in eine Unterroutine und zum Zurückkehren von dieser verwendet wird.