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

\begin{document}
\renewcommand{\figurename}{Tabelle}

\title{Minimaler$\!$ Basis--Befehlssatz für ein$\!$ Forth--System}
\ifx\shorttitle\undefined\else
\shorttitle{Minimaler Basis–Befehlssatz}
\fi
\author{Willi Stricker}
\maketitle

Es wird ein kleiner Basis--Befehlssatz vorgestellt, der es erlaubt, alle weiteren Forth--Befehle zu erzeugen. 

Er enthält möglichst wenige Befehle und keine, die durch andere Basisbefehle erzeugt werden können. Diese sollen so gestaltet sein, dass damit ein vollständiges Forth--System ohne weitere Primitives (in Assembler geschriebene Befehle) aufgebaut werden kann.
Ausgeschlossen ist jedoch der Zugriff auf die Stack--Pointer und die Stacks über Fetch und Store--Befehle.

Ursprüngliches Ziel war es, Forth--Systeme für unterschiedliche Micro--Controller mit möglichst wenig Aufwand zu schaffen. Das bietet folgende Vorteile: Der Aufwand für die (Assembler--) Programmierung der Controller ist verhältnismäßig gering, die Controller sind in ihrer (Forth--)Struktur nach außen identisch und sie können mit der gleichen Entwicklungs--Software bearbeitet werden. Jetzt soll der Befehlssatz auch als Basis für einen möglichst einfach aufgebauten Forth--Prozessor dienen, der wiederum die gleiche Entwicklungs--Software benutzen kann.

\begin{multicols}{2}
 
\section{Definition und Einteilung der Befehle}

\subsection{System--Befehle}

\begin{description}
\item[\tt ;S] \verb|( -> )|\\
  Return = pop address from return stack and store to IP
  
\item[\tt LIT] \verb|( -> data )|\\
 load immediate data on stack

\item[\tt BRANCH] \verb|( -> )|\\
  branch to the following address
  
\item[\tt ?BRANCH] \verb|( data -> )| \\
   branch to the following address if data equals zero else continue
\end{description}
Diese Befehle sind für den Benutzer normalerweise nicht sichtbar, sie werden vom Compiler zum Aufbau von Befehls--Strukturen und Immediate Daten benötigt.

\subsection{Indirekter Befehls-- und Unterprogramm--Aufruf}

\begin{description}
\item[\tt EXECUTE] \verb|( addr -> )|\\
 execute address (= instruction)
\end{description}

\subsection{Parameter-- und Return--Stackpointer – laden und speichern}

\begin{description}
\item[\tt RP@] \verb|( -> RP )|\\
 get Return--Pointer

\item[\tt RP!] \verb|( RP -> )|\\
 store Return--Pointer

\item[\tt SP@] \verb|( -> SP )|\\
 get Stack--Pointer

\item[\tt SP!] \verb|( SP -> )|\\
 store Stack--Pointer
\end{description}
Diese Befehle werden  bei Benutzung mehrerer Stacks etwa bei Interrupt--Programmen oder für Multitasking--Systeme benötigt.

\subsection{Return--Stack--Befehle}

\begin{description}
\item[\tt R>] \verb|( data -> )|\\
   pop data from return stack

\item[\tt >R] \verb|( -> data )|\\
 push data to return stack
\end{description}

\subsection{Parameter--Stack--Befehle}

\begin{description}
\item[\tt DROP] \verb|( data -> )|\\
 drop data from stack

\item[\tt PICK] \verb|( position -> data )|\\
 load data from relative stack position

\item[\tt -PICK] \verb|( data position -> )|\\
 store data on relative stack position
\end{description}
Die Befehle \texttt{PICK} und \texttt{-PICK} werden für den wahlfreien Zugriff zum Parameter--Stack gebraucht.

\subsection{Logik--Befehle}

\begin{description}
\item[\tt INVERT] \verb|( data -> [not data] )|\\
 bitwise NOT

\item[\tt AND] \verb|( data0 data1 -> [data0 and data1] )|\\
  bitwise AND

\item[\tt OR] \verb|( data0 data1 -> [data0 or data1] )|\\
  bitwise OR
\end{description}

\subsection{Arithmetische Befehle}

\begin{description}
\item[\tt +C] \verb|( data0 data1 -> [data0+data1] carry )|\\
 add data with sum and carry (lsb)
\item[\tt U2/C] \verb|( data -> carry [data/2] )|\\
 shift right one bit with result and carry (msb)
\end{description}

Die Erweiterung der üblichen Befehle \texttt{+} und \texttt{U2/} durch das Carry--Bit (als Wort) ist notwendig für die Möglichkeit zur Erweiterung der Befehle auf doppelte Genauigkeit, da Forth kein Flag--Register kennt. 

\subsection{Speicher--Zugriff}

\begin{description}
\item[\tt @] \verb|( addr -> data )|\\
 fetch data from memory address

\item[\tt !] \verb|( data addr -> )|\\
 store data on memory address
\end{description}

\subsection{Byte--Befehle}

\begin{description}
\item[\tt CSWAP] \verb|( byte0:byte1 -> byte1:byte0 )|\\
 swap bytes in data

\item[\tt C@] \verb|( addr -> byte:0 )|\\
 fetch byte from address (upper byte = 0)

\item[\tt C!] \verb|( byte:0 addr -> )|
 store byte to address (upper byte is discarded)
\end{description}

Diese Befehle sind im Prinzip substituierbar, machen dabei aber besondere Probleme, deswegen werden sie hier aufgeführt.

\subsection{Interrupt--Steuerung}

\begin{description}
\item[\tt DISINT] \verb|( -> )|\\
 disable interrupts

\item[\tt ENINT] \verb|( -> )|\\
 enable interrupts
\end{description}

Forth kennt als Programmiersprache zwar keine Interrupts und damit keine Interrupt--Befehle, Micro--Controller aber haben immer welche. Deswegen sind diese Befehle notwendig.

Es zeigt sich, dass mit Hilfe dieser geringen Anzahl von 26 Befehlen ein vollständiges Forth--System aufgebaut werden kann. Dazu wird im Folgenden ein Forth--Kernel vorgeschlagen, der mit Hilfe des minimalen Befehlssatzes programmiert wird. 

Die Reihenfolge der Definitionen ist dabei wichtig, da später definierte Befehle vorangegangene benutzen. Der Befehlssatz ist auf minimalen Speicherbedarf optimiert. Er erhebt aber keinen Anspruch auf Vollständigkeit!

\end{multicols}

Definition eines Forth--Kernels bei Benutzung des Minimal--Befehlssatzes

\begin{quote}
\begin{footnotesize}
\begin{listing}{1}
: DUP ( data -> data data ) 0 PICK ;

: SWAP ( data0 data1 -> data1 data0 ) DUP 2 PICK 1 -PICK 1 -PICK ;                                                              

: R@ ( -> data ) R> R> DUP >R SWAP >R ; 

: OVER ( data0 data1 -> data0 data1 data0 ) 1 PICK ;                                                            

: ROT ( data0 data1 data2 -> data1 data2 data0 ) >R SWAP R> SWAP ;

: ?DUP ( data -> data data ) DUP IF DUP THEN ;

: + ( data0 data1 -> [data0+data1] ) +C DROP ;         

: U2/ ( data -> [data/2] ) U2/C SWAP DROP ;                      

: +! ( data addr -> ) DUP @ ROT + SWAP ! ;

: XOR ( data0 data1 -> [data0 xor data1] ) OVER OVER INVERT AND >R 	
     SWAP INVERT AND R> OR ;                                    

: D+ ( data0_l data0_h data1_l data1_h -> 
     [data0+data1]_l [data0+data1]_h ) >R SWAP >R +C R> + R> + ;                                     

: 1+ ( data -> [data+1] ) 1 + ;                                  

: NEGATE ( data -> [-data] ) INVERT 1+ ;                      

: DNEGATE ( data_l data_h -> [-data]_l [-data]_h )
     SWAP INVERT SWAP INVERT 1 0 D+ ;

: - ( data0 data1 -> [data0-data1] ) NEGATE + ;                 

: D- ( data0_l data0_h data1_l data1_h -> [data0-data1]_l [data0-data1]_h )
     DNEGATE D+ ;                                     

: 1- (data -> [data-1] ) 1 - ;                                   

: 0= ( data -> flag ) IF 0 ELSE -1 THEN ; 

: 0< ( data -> flag ) [ HEX ] 8000 AND 0= 0= [DECIMAL] ;

: 0> ( data -> flag ) DUP 0< SWAP 0= OR 0= ;                                                                                                                                                                                              

: = ( data0 data1 -> flag ) - 0= ;

: < ( data0 data1 -> flag ) - 0< ;

: > ( data0 data1 -> flag ) - 0> ;                                                                                                                                                                                                                                                               

: U< ( data0 data1 -> flag ) 0 SWAP 0 D- 0< SWAP DROP ;                 

: U> ( data0 data1 -> flag ) SWAP U< ;

: MIN ( data0 data1 -> [min(data0|data1)] ) OVER OVER > IF SWAP THEN 	
     DROP ;                                                      

: MAX ( data0 data1 -> [max(data0|data1)] ) OVER OVER < IF SWAP THEN 	
     DROP ;                                                     

: ABS ( data -> [abs data] ) DUP 0< IF NEGATE THEN ;              

: DABS ( data_l data_h -> [abs data]_l [abs data]_h )
     DUP 0< IF DNEGATE THEN  ;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              

: ROLL ( data position -> ) DUP 1+ PICK >R BEGIN DUP WHILE DUP PICK
     >R DUP 1+ R> SWAP 	-PICK 1- REPEAT DROP DROP R> ;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               

: 2* ( data -> [data*2] ) DUP + ;                             

: 2/ ( data -> [data/2] ) [ HEX ] DUP 8000 AND SWAP U2/ OR 	
     [ DECIMAL ] ;                                         

: LSHIFT BEGIN DUP WHILE SWAP 2* SWAP 1- REPEAT DROP ;          

: RSHIFT BEGIN DUP WHILE SWAP U2/ SWAP 1- REPEAT DROP ;

: S>D ( data -> data_l data_h ) [ HEX ] DUP 8000 AND IF -1 ELSE 0 	
     THEN ;                 

: D>S ( data_l data_h -> data ) DUP >R DABS OVER 0< OR IF DROP R@ 0< 
     IF [ HEX ] 8000 ELSE 7FFF	[ DECIMAL ] THEN THEN R> 0< IF NEGATE 	
     THEN ;            

: UM* ( data0 data1 -> uprod_l uprod_h ) 0 ROT ROT 16 BEGIN >R >R DUP 	
     0< >R OVER OVER D+ R> IF R@ 0 D+ 	THEN R> R> 1- DUP 0= UNTIL 	
     DROP DROP ;                                                                                                                                                                                                                                                                                                                               

: M* ( data0 data1 -> prod_l prod_h ) OVER OVER XOR >R ABS SWAP ABS 	
     UM* R> 0< IF DNEGATE THEN ;

: * ( data0 data1 -> prod ) M* D->S ;

: UM/MOD ( data1_l data1_h data2 -> umod uquot_l uquot_h ) 0 SWAP 32 	
   BEGIN >R >R OVER >R	>R OVER OVER D+ R> 2* R> 0< IF 1 OR THEN DUP 	
   R@ U< NOT IF R@ - ROT 1+ ROT ROT THEN R> R> 1- DUP 0= UNTIL 	
   DROP DROP ROT ROT ;                                                                                                                                                                                               

: M/MOD ( data1_l data1_h data2 -> mod quot ) OVER >R OVER OVER XOR 	
   >R ABS >R DABS R> UM/MOD R> 0< IF DNEGATE THEN D>S SWAP R> 0< IF 	
   NEGATE THEN SWAP ;                                                        

: M/ ( data1_l data1_h data2 -> quot ) M/MOD SWAP DROP ;

: /MOD ( data1 data2 -> mod quot ) >R S->D R> M/MOD ;

: / ( data1 data2 -> quot ) /MOD SWAP DROP ;

: MOD ( data1 data2 -> mod ) /MOD DROP ;

: */MOD ( data1 data2 data3 -> mod [data1*data2/data3] ) >R M* R> M/MOD ;

: */ ( data1 data2 data3 -> [data1*data2/data3] ) */MOD SWAP DROP ;
\end{listing}
\end{footnotesize}
\end{quote}

Hinweis: Der Befehl \texttt{UM/MOD} ist anders als in Forth üblich definiert: Der Quotient ist vom Typ double. Das Ergebnis ist damit immer eindeutig. 

\end{document}
