Stapel

Der Stapel (engl. stack) ist ganz allgemein ein Zwischenspeicher, auf den nach dem "Last In - First Out"-Prinzip zugegriffen wird: Daten, die als letztes abgelegt werden, werden als erstes wieder entnommen.

Beim C64 und der dort eingesetzten CPU wird der Prozessorstapel auch vom BASIC-Interpreter mitgenutzt.

BASIC-Stapel

Von BASIC aus wird der Prozessorstapel nur implizit bzw. intern durch den BASIC-Interpreter genutzt, allerdings in einem beschränkten und kontrolliertem Ausmaß, sodass auch bei maximaler Nutzung durch ein BASIC-Programm, noch ausreichend Platz für den Prozessorstapel-Bedarf der BASIC-Interpreter- und KERNAL-Routinen bleibt.
Der Stapel beginnt bei Speicherstelle $01FB und dehnt sich maximal bis zur Speicherstelle $013F aus (190 Bytes). Siehe auch die Belegung der Page 1.

Spezielle Befehle zum direkten Zugriff auf den Stapel gibt es nicht - sie wären auch nicht sinnvoll, da der BASIC-Interpreter durch die "Zweitnutzung" des Prozessorstapels durch ein anderes Programm neben ihm nur durcheinander gebracht würde.

1. Unterprogrammbefehle GOSUB und RETURN legen Rücksprungreferenzen auf den Stapel bzw. holen sie wieder ab.
   • Maximale Verschachtelungen: 25 (praktisch allerdings nur 24, wenn der innerste Aufruf zumindest alle BASIC-Befehle in einfacher Form ausführen können soll).
   • Verbrauch für eine Verschachtelungsebene: 7 Bytes
2. Die Befehle FOR und NEXT legen Verwaltungsinformationen auf dem Stapel ab.
   • Maximale Verschachtelungen: 10 (praktisch allerdings nur 9, wenn die innerste Schleife zumindest alle BASIC-Befehle in einfacher Form ausführen können soll).
   • Verbrauch für eine Verschachtelungsebene: 18 Bytes
3. Verschachtelungen gebildet mit Hilfe von Klammern zur Bildung arithmetischer Ausdrücke, um eine gewisse Auswertungsreihenfolge der Operatoren zu erzwingen, belegen den Stapel in kombinierter Weise.
   • Maximale Verschachtelungen: 10 (oder 35 Klammern oder eine 15-stufiger klammerlose Ausdruckskette, welche sich aber in der Praxis ohne Klammern nicht realisieren lässt, da es nur 8 verschiedene Operatorprioritäten gibt, um dergleichen zu erzwingen)
   • Verbrauch für eine Verschachtelungsebene: 17 Bytes (5 Bytes für eine Klammer und 12 Bytes für eine Ausdrucksauswertung)
4. FN-Aufrufe mittels DEF deklarierter Funktionen.
   • Maximale Verschachtelungen: 12 (praktisch allerdings nur 11, wenn im innersten Aufruf noch eine sinnvolle Ausdrucksauswertung stattfinden soll)
   • Verbrauch für eine Verschachtelungsebene: 16 Bytes
5. Die Befehle CLR, NEW, RUN leeren den BASIC-Stapel bzw. setzen ihn zurück.

Werden Schleifen, Unterprogramme oder arithmetische Ausdrücke zu tief ineinander verschachtelt, so erfolgt bei einem Überlauf des Stapels die Meldung des Fehlers ?OUT OF MEMORY ERROR. Andere, spezifische Fehlermeldungen sind den oben erwähnten BASIC-Befehlen zu entnehmen, welche dann eintreten, wenn die Verschachtelung beispielsweise falsch oder unvollständig geformt ist.

BASIC verwendet noch einen weiteren Stapel, der die Zeichenkettenverarbeitung unterstützt und welcher als Temporary String Descriptor Stack (kurz Descriptor Stack) bzw. Zeichenkettenstapel bekannt ist. Dieser ist vom Prozessorstapel unabhängig.

Prozessorstapel

Der Prozessorstapel (engl. processor stack) ist ein besonderer Speicherbereich im RAM eines Computers, in dem die CPU Daten mit typischerweise geringem Speicherverbrauch und schnellem Zugriff (insbesondere Rücksprungadressen, Zwischenspeicherung von CPU-Register und Zwischenergebnisse von Unterroutinen) ablegen kann.

Bei der MOS 6510-CPU des C64 liegt der Prozessorstapel in einem 256 Byte großer Speicherbereich, der sogenannten Page 1, von hexadezimal $0100 bis $01FF (Speicherbelegungsplan). Der Stapelzeiger (engl. stack pointer oder kurz SP) verweist auf die nächste freie Stapelspeicherstelle. Der Stapel wird von hohen Adressen in Richtung niedrigere Adressen gefüllt (engl. push) und in umgekehrter Richtung geleert (engl. pull). Ist der Stapelzeiger mit $FF initialisiert, so kommt das erste auf den Stapel gelegte Byte an die Speicherstelle $01FF und der Stapelzeiger zeigt danach auf die noch freie Speicherstelle $01FE.

Bei CPUs der 6502-Familie auf Maschinenebene bzw. bei der Assembler-Programmierung gibt es mit folgenden Befehlen oder Subsystemen Berührungspunkte zum Stapel:

• PHA, PHP, JSR, BRK legen Daten am Stapel ab.
• PLA, PLP, RTS, RTI holen Daten vom Stapel.
• TSX und TXS dienen zum Auslesen bzw. zum Setzen des Stapelzeigers.
• Durch Interrupts werden Daten (Rücksprungadresse, ggf. Statusregister) am Stapel abgelegt.
• Das Statusregister (als 8-Bit-Wert) kann nur über den "Umweg" des Prozessorstapels gelesen bzw. geschrieben werden.
• Mit der Adressierungsart Absolut X-indiziert kann nach vorhergehendem Laden des X-Registers mit dem Stapelzeigerwert wahlfrei auf Elemente des Stacks zugegriffen werden:

TSX

LDA $0101,X ; das 1. Byte am Stack

LDA $0102,X ; das 2. Byte am Stack

Bei der Initialisierung durch das KERNAL nach einem CPU-Reset wird der Stapelzeiger auf die Adresse $01FF (d.h. das Register SP enthält $FF) gesetzt.

Forth-Stapel

Jeder Forth-Kern verwendet als zentrale Datenstruktur zumindest zwei Stapel, nämlich den sogenannten "Parameter Stack" und "Return Stack".

Weblinks

Wikipedia: Last In – First Out

Wikipedia: Stapelspeicher