% Content-encoding: UTF-8
\documentclass[ngerman]{article}
\usepackage[utf8]{inputenc}
\usepackage{multicol}
% \usepackage{babel}
\usepackage{xspace}
\setcounter{secnumdepth}{0}
\setcounter{tocdepth}{0}
\usepackage{german}

%\newcommand{\code}[1]{\texttt{#1}}
%\newcommand{\ret}{\textsf{$<$ret$>$}\xspace}
%\newcommand{\ret}{$\hookleftarrow$\xspace}

\renewcommand{\reftextbefore}{auf der vorherigen Seite}
\renewcommand{\reftextfacebefore}{auf der gegenüberliegenden Seite}
\renewcommand{\reftextafter}{auf der nächsten Seite}
\renewcommand{\reftextfaceafter}{auf der gegenüberliegenden Seite}
\renewcommand{\reftextfaraway}[1]{auf Seite \pageref{#1}}
\renewcommand{\figurename}{Listing}

\title{Kleine Stack--Philosophie}
\ifx\shorttitle\undefined\else
\shorttitle{Kleine Stack--Philosophie}
\fi
\author{Willi Stricker}

\begin{document}

\maketitle

In der Programmiersprache FORTH spielt der Stack eine dominierende Rolle, der Gebrauch des Stacks ist gewissermaßen das Markenzeichen von FORTH.
Es ist also sinnvoll, einige Anmerkungen zum Prinzip des Stacks zu machen.

\begin{multicols}{2}
 
Der Stack (deutsch: Stapel) ist ein LIFO--Speicher (last in, first out), d.$\,$h.\ das zuletzt auf den Stack gelegte Element ist das erste, das ausgelesen wird, wie bei Paketen, die aufgestapelt sind. Er hat normalerweise zwei unterschiedliche Funktionen:

\begin{enumerate}
\item Speicherung der Rücksprung--Adressen (Return Addresses) bei Unterprogramm--Aufrufen unter Benutzung von Call-- und Return--Befehlen,
\item Hilfs--Speicher zur Zwischen--Ablage von Daten unter Benutzung von PUSH-- und POP--Befehlen.
\end{enumerate}

Üblicherweise wird der Stack im RAM am obersten Ende an der höchsten Adresse gestartet und besetzt bei zunehmender Belegung den Speicher zu niedrigeren Adressen hin. Er \emph{läuft abwärts}\/! Die Speicherplätze für Variablen werden dagegen am unteren Ende aufsteigend platziert. Auf diese Weise wird erreicht, dass der gesamte RAM--Bereich oberhalb der Variablen für den Stack zur Verfügung steht. Das ist sinnvoll, da zwar die Variablen durch das Programm festgelegt sind, der Stack aber prinzipiell als \emph{unendlich groß} angenommen wird. Folglich kann der Stack je nach Programm--Ablauf \emph{überlaufen}, was in der Regel einen Programmabsturz zur Folge hat.  

Werden jedoch, wie bei FORTH, mehrere Stacks benötigt oder besitzt der Stack einen eigenen abgeschlossenen Speicher, so ist diese Überlegung nicht mehr zwingend, er kann also auch am unteren Ende starten und \emph{aufwärts laufen}. Anmerkung: Ich habe einmal eine FORTH--Implementierung gesehen, bei der die beiden Stacks gegeneinander liefen.

Der Stack benötigt einen Stackpointer (Stapelzeiger), der die jeweilige Adresse der aktuellen Stackposition enthält. Mit ihm wird die Startadresse als Beginn des Stacks und die \emph{Laufrichtung} definiert. Dabei gibt es verschiedene Möglichkeiten des Aufbaus je nach Richtung und Startadresse:

\section{Stackrichtung im RAM:}
\begin{itemize}
\item aufwärts (aufsteigende RAM--Adressen); die Stackelemente werden nacheinander in aufsteigende Adressen abgelegt, das zuletzt abgelegte Element liegt auf der höchsten Adresse,
\item abwärts (absteigende RAM--Adressen).
\end{itemize}

\section{Initialisierung:}
\begin{itemize}
\item Stackpointer \emph{zeigt} auf das oberste Stackelement,
\item Stackpointer \emph{zeigt} auf den nächsten freien Stackplatz.
\end{itemize}

Daraus ergeben sich \ref{maxcase} Fälle:
\begin{enumerate}
\item aufwärts, Stackpointer zeigt auf oberstes Stackelement,
\item aufwärts, Stackpointer zeigt auf freien Stackplatz,
\item abwärts, Stackpointer zeigt auf oberstes Stackelement,
\item \label{maxcase} abwärts, Stackpointer zeigt auf freien Stackplatz.
\end{enumerate}

Die Fälle 1.\ und 2.\ sind unüblich, benutzt nur bei Prozessoren, die einen festgelegten Stack besitzen, z.$\,$B.\ Intel 8051 und deren Derivate.
Der Fall 4.\ wird z.$\,$B.\ bei den 8--Bit--Prozessoren von Freescale (Motorola) eingesetzt,
der Fall 3.\ wird bei den heute üblichen Mikroprozessoren meist benutzt, er ist so etwas wie ein Standard. 

Auf die \emph{normale} Arbeit mit dem Stack unter Benutzung der oben genannten Befehle haben die unterschiedlichen Konfigurationen keinen Einfluss. Lediglich die Initialisierung des Stackpointers muss entsprechend angepasst werden. 

\section{Stackpointer, Bytezahl}
Das RAM, in dem sich der Stack befindet, ist üblicherweise in Bytes organisiert. Damit hat der Stackpointer abhängig von der internen Organisation ausschließlich gerade Adressen bei 16--Bit--Organisation (Adress--Bit 0 ist null) oder durch 4 dividierbare (ohne Rest) Adressen bei 32--Bit--Organisation (Adress--Bits 0 und 1 sind null).

\section{Praxis}
Wie erwähnt, ist die Stackorganistion bei Mikroprozessoren meist rückwärts laufend und der Stackpointer zeigt auf das oberste Stack--Element:

\textbf{Ablauf:}
\begin{itemize} 
\item Push:	Stackpointer mit predecrement,
\item Pop:	Stackpointer mit postincrement.
\end{itemize}

\textbf{Initialisierung:}
\begin{itemize}
\item Stackpointer zeigt auf das „nicht vorhandene“ Element unterhalb des Stackbereichs.
\end{itemize}

\section{Stacks beim STRIP--FORTH--Prozessor}

Der STRIP hat, wie bei FORTH üblich, zwei Stacks: 
\begin{enumerate}
\item \textbf{Return--Stack (RP)} zur Speicherung der Rücksprung--Adressen,
\item \textbf{Parameter--Stack (SP)} zur Speicherung von allgemeinen Daten und Adressen (Parametern).
\end{enumerate}

Die Stacks sind jeweils in einem separaten RAM hardwaremäßig vom allgemeinen RAM  getrennt untergebracht und nicht durch Datentransfer--Befehle zugreifbar. Sie werden folgendermaßen organisiert (abweichend vom üblichen Standard): 
\begin{itemize}
\item Vorwärts laufend,
\item der Stackpointer zeigt  auf den nächsten freien Stackplatz.
\end{itemize}

Die Stackpointer werden mit Null initialisiert (kein Stackelement vorhanden). Daraus folgt der Ablauf: 
\begin{itemize}
\item Push:	Stackpointer mit postincrement,
\item Pop:	Stackpointer mit predecrement.
\end{itemize}

Der Inhalt des jeweiligen Stackpointers ist immer identisch mit der Anzahl der abgelegten Elemente, es gilt (unabhängig von der Bytezahl pro Stackelement):

\begin{description}
\item[RP@] (  $\rightarrow$ Anzahl der Stackelemente auf dem Returnstack)
\item[SP@] (  $\rightarrow$ Anzahl der Stackelemente auf dem Parameterstack)
\item[RP!]   (vorgegebene Returnstack--Position  $\rightarrow$  )
\item[SP!]   (vorgegebene Parameterstack--Position  $\rightarrow$  )
\end{description}
Anmerkung: Der Befehl SP@ ist dann identisch mit dem Befehl DEPTH.

\section{Anmerkungen zur Programmierung}
Die Definition der STRIP--Befehle RP@, SP@, RP! und SP! sind letztlich unabhängig von der Stack--Konfiguration und der Hardware. Sie könnten damit als allgemein gültige Prozessor-- und Bitbreite--unabhängige Definition der Stack--Zugriffe auch für Mikroprozessor--Forth--Befehle folgendermaßen definiert werden:\medskip

\begin{tt}
: RP@$_{\texttt{allg}}$ ( - RP ) R0 @ RP@ - U2/ ;\\
: RP!$_{\texttt{allg}}$ ( RP - ) U2* R0 @ SWAP – RP! ;\\
: SP@$_{\texttt{allg}}$ ( - SP ) S0 @ SP@ - U2/ ;		 $\backslash$ = DEPTH\\
: SP!$_{\texttt{allg}}$ ( SP - ) U2* S0 @ SWAP – SP! ;\\
\end{tt}

Als Programmbeispiel soll ein Befehl definiert werden, der n Elemente vom Stack löscht:

STRIP--FORTH--Prozessor:
\begin{verbatim}
: NDROP ( n - )
    1+ SP@ + - SP! ;
\end{verbatim}

Mikroprozessor--FORTH (16--Bit--System):
\begin{verbatim}
: NDROP ( n - )
    1+ 2* SP@ + + SP! ;
\end{verbatim}

\end{multicols}


% \end{document}