%&latex % Conversion to LaTeX2e by David.N.Williams@umich.edu. % Starting date: September 16, 2000 % Last revision: October 24, 2000 %\documentstyle[german,umlaut,a4wide,twocolumn]{article} % The "conversion" consists of these two lines, plus the replacement % of special characters by "a, etc., recognized by babel. \documentclass[german,a4wide,twocolumn]{article} \usepackage[german]{babel} \sloppy \def\pfe{{\bf pfe}} \pagestyle{myheadings} \markright{pfe---das Portable Forth Environment} \begin{document} \title{Das Portable Forth Environment \\ \large Eine einfache Realisierung von Forth in C} \author{Dirk Zoller} \date{Mannheim, 14.\ April 1994} \maketitle \abstract{Es wird eine Implementation des draft proposed American National Standard (dpANS) f"ur die Sprache Forth beschrieben. Das beschriebene System hat den Arbeitsnamen \pfe, setzt den dpANS vollst"andig um und ist selbst in ANSI-C geschrieben, so da"s es leicht portabel ist auf verschiedene Rechnerumgebungen. Obwohl das System den aktuellen Standard realisiert, ist der Ansatz in vieler Hinsicht traditionell und so einfach wie m"oglich. Dieses Papier erl"autert einige der De"-sign"-ent"-schei"-dun"-gen, die dabei zu treffen waren, und gibt Hinweise zum Einsatz und zur Portierung von \pfe.\footnote{\pfe\ kann per anonymous ftp bezogen werden: roxi.rz.fht-mannheim.de:/pub/languages/forth/pfe-x.x.x.tar.gz}} \section{Ziele} \label{sec:ziele} Der kommende ANSI-Standard \cite{dpans} f"ur die Sprache Forth ist wesentlich umfangreicher als alle bisherigen Standards f"ur diese Sprache. Gleichzeitig vermeidet er die Regelung von Implementationsdetails, eine Eigenschaft fr"uherer Standards, die zunehmend deren Akzeptanz beeintr"achtigte. Implementatoren, die bisher aus dem engen Korsett des fig-Modells oder dem 16-Bit-Diktat des FORTH-83-Standards ausbrachen, sahen sich auf sich selbst gestellt und waren gezwungen, nicht nur in Implementationsdetails abzuweichen, sondern wesentliche Spracheigenschaften frei zu gestalten. Die Folge war eine Phase des Wildwuchses, wo kein Forth wie das andere war. Sie geht nun hoffentlich zu Ende. \paragraph{Verf"ugbarkeit und Portabilit"at} Jetzt ist es wichtig, da"s treue und vollst"andige Implementationen des Standards bereitstehen, die es erm"oglichen, Quelltexte an den Standard anzupassen, und die auf die noch z"ogernden Anbieter den notwendigen Anpassungsdruck aus"uben. Der Umfang des Standards macht seine voll"-st"an"-di"-ge Umsetzung mit den bisherigen Methoden -- in Assembler oder mittels eines Meta"-com"-pi"-lers -- zu einer nicht"-tri"-via"-len Aufgabe, f"ur die die Anbieter offensichtlich noch Zeit brauchen. \pfe\ wurde dagegen aus zwei Gr"unden in ANSI-C geschrieben: Es sollte in vollem Umfang rasch zur Verf"ugung stehen und es sollte auf sovielen Plattformen wie m"oglich -- und das hei"st zuallererst auf UNIX -- zur Verf"ugung stehen. \pfe\ l"auft z.Z.\ auf verschiedenen UNIX-Derivaten\footnote{bisher sind erprobt: Linux, AIX 3.2x, HP-UX 8.x, Domain-OS, Sun-OS, Ultrix 4.3 RISC, Irix.} sowie auf DOS (ab 386) und OS/2 ab 2.0. Anpassungen an weitere 32-Bit-Systeme, deren C-Compiler gewisse UNIX-"ahliche Funktionen in der Library haben,\footnote{In erster N"aherung kann man vermuten, da"s \pfe\ mit geringem Aufwand portabel ist auf ein System, wenn dort auch GNU-C l"auft.} d"urften einfach sein. Seit fig-Forth ist kein freies Forth-System mehr so gleichartig auf so vielen verschiedenen Rechnern gelaufen. \paragraph{Vertrautheit} Damit ein zur Verf"ugung stehendes System aber auch benutzt wird, m"ussen sich potentielle Benutzer darin wohlf"uhlen. In \pfe\ wurde deshalb einiger Aufwand getrieben, den interaktiven ``Look and feel'' von Forth-Systemen auf typischen Einplatzsystemen (PC, Atari,\dots) trotz der Portabilit"at zu erhalten. So wird eine Tastatureingabe nicht einfach mit der C-Funktion {\sl gets()\/} abgeholt, sondern das Verhalten von {\tt EXPECT} nachgebildet. Die Kommandozeile erlaubt das Zur"uckholen und das Edieren alter Eingaben. Cursor-Positionierung und Text-Attribute sind m"oglich, Funktionstasten k"onnen mit Forth-Worten belegt werden und ein vollst"andiger Block-Editor ist integriert. Zum Wohlf"uhlen in einem System geh"ort auch, da"s es vertraut ist. Deshalb wurden bekannte Worte, die nicht den Weg in den Standard gefunden haben, trotzdem aufgenommen. Soweit es nicht im Widerspruch zum dpANS steht, gibt es alles aus fig-Forth und FORTH-83 sowie einiges aus Laxen\&Perry's F83. Die F"adelungstechnik "ahnelt dem traditionellen ``indirect threading'' und die Datenstrukturen im Dictionary sind "ahnlich den schon vor 15 Jahren von fig-Forth benutzten. \paragraph{Stabilit"at} ist eine Eigenschaft, ohne die kein System das Vertrauen der Benutzer erwirbt, das sie veranla"st darauf aufbauend Stunden und Tage in ihre Entwicklungen zu investieren. Stabil ist aber nur ein einfaches System. Ein weiterer Grund, bei den Designentscheidungen auf bew"ahrte und verstandene Konzepte zu bauen. \subsection{Was fehlt} Im Interesse der Einfachheit und Stabilit"at wurde auf verschiedene Dinge bewu"st verzichtet, weil sie eine Gr"o"senordnung mehr Komplexit"at in das System hineingetragen h"atten oder im Widerspruch zum Ziel der Portabilit"at stehen: \begin{itemize} \item die F"ahigkeit sich selbst zu "ubersetzen \item ein Assembler \item die F"ahigkeit, Maschinencode zu erzeugen \item die F"ahigkeit, Libraries aufzurufen.\footnote{Speziell f"ur Linux existiert eine L"osung von Kevin Haddock.} \item Multitasking \end{itemize} \section{Design} \label{sec:design} Schreibt man ein Forth-System in C, werden viele Dinge, die bei einer As"-sem"-bler-Im"-ple"-men"-ta"-tion Kopfzerbrechen bereiten k"onnen, sehr einfach. So ist ein in C programmierbares System von vornherein zur Flie"skommaarithmetik, Freispeicherverwaltung usw.\ f"ahig. Sehr viele Forth-Worte brauchen also nur den entsprechenden Funktionsaufruf zu tun. Es gibt aber auch Bereiche, in denen C gegen den Strich zu b"ursten ist, damit Forth herauskommt. Ich m"ochte mich hier auf die zu bew"altigenden Schwierigkeiten konzentrieren. Damit hoffe ich das Verst"andnis der entsprechenden Passagen im Quelltext zu erleichtern. Es wird sich allerdings zeigen, da"s bei Beachtung einiger einfacher Regeln "Anderungen und Erweiterungen am C-Quelltext leicht m"oglich sind, auch ohne sich in die Tiefen der Exception-Behandlung einzulesen. \subsection{Datentypen} \label{sec:datentypen} Im Gegensatz zu Forth ist modernes C eine streng typisierte Sprache\footnote{Wer's nicht glaubt, versuche einmal ein gr"o"seres Programm {\em ohne Warnungen\/} durch mehrere verschiedene ANSI-C-Compiler zu bringen.}. Forth macht zwar keinen Unterschied zwischen Adresse und ganzer Zahl, mu"s aber diese Laxheit ausgleichen durch pr"azisere Forderungen an das Verh"altnis der wenigen elementaren Typen zueinander. Implementiert man dpANS-Forth in ANSI-C, mu"s man es beiden recht machen. Im C-Quelltext folgen daraus viele explizite Typumwandlungen (``type casts''). Diese ansonsten bedenkliche Praxis f"uhrt hier nicht zu Problemen, weil die konsistenten Anforderungen von Forth an die beteiligten Datentypen eingehalten werden. Insbesondere fordert der dpANS, da"s eine Adresse und eine einfach genaue ganze Zahl dieselbe Gr"o"se im Speicher haben, und nennt solch eine Einheit {\sl ``cell''\/}. C erlaubt uns darauf einzugehen, indem wir unter mehreren ganzzahligen Datentypen denjenigen ausw"ahlen, der dieselbe Gr"o"se wie ein Zeiger hat. Dieser Datentyp wird zum ganzzahligen Grundtyp unter dem Namen {\tt Cell}. Der Standard fordert neben dem ganzzahligen Grundtyp noch einen doppelt so gro"sen ganzzahligen Datentyp.\footnote{Tats"achlich hat der Standard ein Herz und hat diese Forderung in einen optionalen ``double number extension word set'' ausgelagert.} Nachdem wir aber f"ur Forth' ganzzahligen Grundtyp schon {\em irgendeinen\/} ganzzahligen C-Typ nehmen mu"sten, k"onnen wir nicht davon ausgehen, da"s der C-Compiler unter dem Namen {\tt long} noch etwas gr"o"seres f"ur uns hat. Die Arithmetik mit Forth' doppelt genauen Zahlen mu"s also unter Verwendung von {\tt Cell} allein nachgebildet werden. Bei der Gelegenheit f"allt es dann auch nicht weiter schwer, die in Forth "ubliche Reihenfolge der beiden Zellen einer doppelt genauen Zahl auf dem Stack einzuhalten. Bei den laufenden Systemen sind durchweg die einfach genauen Zahlen 32 Bit gro"s und die doppelt genauen Zahlen 64 Bit. Es spricht aber nichts dagegen, auf einem entsprechenden System 64 Bit gro"se einfach genaue und 128 Bit gro"se doppelt genaue Zahlen zu haben. Eine Reduktion des Systems auf 16/32 Bit w"are -- aus anderen Gr"unden als der Arithmetik -- schwieriger. \subsection{Die Forth-Maschine in C} Es sollen m"ogliche Implementationsvarianten abgewogen werden, die gew"ahlte erkl"art und begr"undet werden. Dazu wird das Modell einer virtuellen Maschine herangezogen, das vom Forth-79 Standard definiert\footnote{vgl.\ \cite{dpans} S.\ 193} aber auch schon in fig-Forth verwendet wurde.\footnote{eine detaillierte Diskussion dieser virtuellen Maschine und ihrer Grund"-opera"-tio"-nen realisiert auf verschiedenen CPUs findet sich in \cite{zech} S.\ 27} Der dpANS erw"ahnt die virtuelle Maschine nicht mehr. Er stellt sich auf einen abstrakteren Standpunkt und redet "uber die verschiedenen "`Semantiken"' von Worten zur "Ubersetzungs- und Laufzeit. Das ist gut so, denn l"angst ist es g"angige Implementationspraxis, die genaue Arbeitsweise der virtuellen Maschine zugunsten von prozessorspezifischen Optimierungen und pers"onlichen Vorlieben zu ignorieren, dabei nur mehr oder weniger genau darauf achtend, da"s die oberste Ebene -- eben die Semantik -- noch genauso aussieht, wie man es von einem Forth erwartet. Andererseits steht die virtuelle Maschine nicht im Widerspruch zum Standard und ist nach wie vor geeignet, ein Standard-System zu treiben. \paragraph{Low-Level/High-Level} Ein Forth-System mu"s elementare Grundoperationen bereitstellen. Normalerweise sind dies in Assembler geschriebene Worte, auch genannt Low-Level- oder Code-Worte oder Primitives. Geeignete Primitives \begin{itemize} \item manipulieren Daten- und Returnstack \item machen die Arithmetik \item f"uhren bedingte und unbedingte Spr"unge aus \item verarbeiten zur Laufzeit literale Konstanten der verschiedenen Typen \item greifen auf lokale Variablen zu \end{itemize} High-Level-Worte sind dagegen die compilierten Worte, die in irgendeiner Form aus Adress- oder Token-Listen bestehen, die vom {\sl inneren Interpreter\/}, der Operation {\sl next\/} der virtuellen Maschine, abgearbeitet werden. Daneben gibt es noch die sogenannten ``runtimes''. In Assembler-Implementationen sind das Code-St"ucke, die in {\sl next\/} enden, aber nicht als Primitives auftreten. Vielmehr bestimmen sie das Laufzeitverhalten von Variablen, Konstanten und vor allem von High-Level-Worten. Nachdem der innere Interpreter ({\sl next\/}) jedes Wort bedingungslos anspringt, mu"s f"ur jedes Wort ausf"uhrbarer Code existieren. Die runtimes stellen diesen ausf"uhrbaren Code z.B.\ f"ur Variablen bereit. Das runtime {\sl nest\/} ist das ausf"uhrbare St"uckchen Code f"ur eine High-Level-Definition. \subsubsection{Die virtuelle Maschine} Ein klassisches ``indirect threaded'' Forth birgt in sich -- ohne da"s der Benutzer darauf direkten Zugriff h"atte -- eine virtuelle Maschine mit vier Registern, davon zwei Stackpointer in die beiden Stacks, und einigen Grundoperationen. Die Register der virtuellen Maschine sind: Daten-Stack-Pointer {\sl SP\/} und Return-Stack-Pointer {\sl RP\/}, der Instruction-Pointer {\sl IP\/} und ein weniger einleuchtendes aber wichtiges Register namens {\sl W\/}, das stets in das Datenfeld\footnote{fr"uher auch PFA genannt} der aktuell ausgef"uhrten Code-Definition zeigt. Um all das zu erreichen, was der dpANS vorschreibt, gen"ugt es nach wie vor, wenn ein Forth-System -- neben einer geeignet ausgew"ahlten Menge von Primitives -- die elementaren Grundoperationen der virtuellen Maschine realisiert: \begin{description} \item[next] eine gewisse Menge (je weniger, desto besser) von Maschinenbefehlen, die zum n"achsten auszuf"uhrenden Primitive springen. Wohlgemerkt ist das im klassischen Forth {\em kein\/} Unterprogrammsprung, sondern ein Weiterspringen, von dem es keine R"uckkehr gibt. Die Kontrolle "uber den Programmflu"s wird durch die anderen Grundoperationen ausge"ubt. Mit den Registern der virtuellen Maschine und einem Hilfsregister $X$ l"a"st sich die Aktion {\sl next\/} so beschreiben: \[ \begin{array}{rcl} W & \leftarrow & (IP) \\ IP & \leftarrow & IP + \mbox{1 Cells} \\ X & \leftarrow & (W) \\ W & \leftarrow & W + \mbox{1 Cells} \\ \multicolumn{3}{l}{\mbox{Sprung nach }X} \end{array} \] \item[nest] ist der zun"achst von einer :-Definition ausgef"uhrte Code. Legt den Instruction-Pointer {\sl IP} auf dem Return-Stack ab und setzt den {\sl IP} auf den Beginn des Datenfeldes der aktuell ausgef"uhrten Definition: \[ \begin{array}{rcl} RP & \leftarrow & RP - \mbox{1 Cells} \\ (RP) & \leftarrow & IP \\ IP & \leftarrow & W \\ \multicolumn{3}{l}{\mbox{Aktion von }next} \end{array} \] {\sl Next} f"uhrt nun das erste Wort aus der Liste von Worten aus, die das compilierte High-Level-Wort ausmachen. \item[unnest] Umkehrfunktion von {\sl nest}, kehrt zum rufenden Wort zur"uck indem der von {\sl nest} gesicherte Wert vom Return-Stack zur"uckgeholt wird: \[ \begin{array}{rcl} IP & \leftarrow & (RP) \\ RP & \leftarrow & RP + \mbox{1 Cells} \\ \multicolumn{3}{l}{\mbox{Aktion von }next} \end{array} \] \item[does] Mit {\sl nest} verwandt ist eine Funktion der virtuellen Maschine zur Unterst"utzung von {\tt CREATE...DOES>}-Definitionen. Ein mit einem Definitionswort {\sf DEF} definiertes Wort {\sf W} mu"s im Sinne einer high-level De"-fi"-ni"-tion compilierten Code ausf"uhren, der aber nicht im Datenfeld des Wortes {\sf W} steht, sondern irgendwo anders, vorzugsweise innerhalb des Wortes {\sf DEF}. \end{description} Nur auf die Operation {\sl unnest\/} hat der Programmierer direkten Zugriff, sie wird durch das Wort {\tt EXIT} repr"asentiert. Die "ubrigen Grundoperationen der virtuellen Maschine sind dem Forth-Programmierer nicht zug"anglich. {\sl nest\/} wird vom Compiler bei Bedarf eingeplant und {\sl next\/} bildet das Ende jeder Code-Definition, tritt f"ur den Programmierer nur dann in Erscheinung, wenn er selbst Code-Definitionen hinzuf"ugt, also den in viele Systeme integrierten Assembler benutzt. \subsubsection{Erste Ideen zur Umsetzung in C} Wir werden einen C-Compiler nicht dazu bewegen k"onnen, unsere in C geschriebenen Primitives mit Befehlen entsprechend der {\sl next\/}-Operation abzuschlie"sen, wie man das in einer Assembler-Implementation macht. Au"serdem k"onnen wir ihn nicht dazu "uberreden, irgendwo einfach hinzuspringen, ohne sich um die R"uckkehr zu k"ummern. Ruft er ein als C-Funktion definiertes Primitive auf, wird er sicherlich auf einem Unterprogramm-Sprung bestehen. Dem Primitive wird er entsprechend einen Unterprogramm-R"ucksprung anf"ugen. Der innere Interpreter wird in erster N"aherung\footnote{Die {\sl W\/}-Systemvariable wird hier ebenso ignoriert wie m"ogliche L"osungen f"ur die Operationen {\sl nest/unnest\/}} zu einer Schleife: \begin{verbatim} for (;;) (*ip++) (); \end{verbatim} {\sl IP} ist hier ein Zeiger auf Zeiger auf Funktionen, die Primitives realisieren. Compilierte High-Level-Definitionen sind also Listen von Zeigern auf die Funktionen, die die hineincompilierten Primitives realisieren. Die Operation {\tt (*ip++)()} kann man sich als {\sl next} vorstellen, die {\tt for}-Schleife drumherum hebt den Effekt des Unterprogramm-Sprungs wieder auf. \paragraph{Alternativen} Will man die Schleife vermeiden, darf man das einzelne Primitive nicht zu einer C-Funktion machen. Daraus folgt, da"s alle Primitives Teil einer einzigen C-Funktion sein m"ussen. Dies f"uhrt zur ``giant switch''-L"osung: Hierbei werden der innere Interpreter und die Realisierung aller Worte in eine einzige C-Funktion geschrieben. Diese C-Funktion besteht im wesentlichen aus einem {\sl switch\/}-Statement. Compilierte Forth-Worte sind Listen von Codes, deren jeder einen Zweig in dem {\sl switch\/}-statement ausw"ahlt. Der innere Interpreter sieht unvollst"andig ungef"ahr so aus: \begin{verbatim} for (;;) switch (*ip++) { case DROP: sp++; break; case DUP: --sp; sp [0] = sp [1]; break; ... \end{verbatim} Mit etwas Gl"uck ist diese Methode sehr schnell, n"amlich wenn der Compiler die wesentlichsten Systemvariablen {\tt sp}, {\tt rp} und {\tt ip}, die lokal zu der gro"sen Funktion deklariert sind, in Prozessorregister legt. Nachdem dpANS-Forth aber sehr umfangreich ist, wird diese Funktion entsprechend {\em sehr\/} gro"s. Es ist unwahrscheinlich, da"s eine so gro"se Funktion noch gut optimiert -- oder "uberhaupt von allen Compilern akzeptiert -- wird. Ausgliederung von aufwendigeren Worten in eigene Funktionen ist erschwert durch den Umstand, da"s wichtige Systemvariablen lokal zur Haupt-Funktion sind. Jegliche "Anderung erfordert das neue "Ubersetzen praktisch des gesamten Systems. Gr"unde genug, diese Variante nicht weiter in Betracht zu ziehen. \subsubsection{Probleme} Die erste Idee \verb$for(;;) (*ip++)()$ eignet sich bei n"aherer Betrachtung nur zur Ausf"uhrung von Worten, die ausschlie"slich aus Primitives zusammencompiliert sind. Denn es wird angenommen, da"s compilierter Forth-Code aus Listen von Zeigern auf ausf"uhrbare Funktionen besteht. Ein High-Level-Wort ist aber keine ausf"uhrbare C-Funktion. Die L"o"-sung besteht nat"urlich in der Ein"-f"uh"-rung einer wei"-teren In"-direk"-tion: Ein compiliertes Forth-Wort ist ein Zeiger auf einen Platz, in dem ein Zeiger steht, der "uber die Bedeutung des Wortes entscheidet. Der innere Interpreter wird zu: \begin{verbatim} for (;;) (**ip++) (); \end{verbatim} Daraus und aus der angestrebten Traditionalit"at ergibt sich eine vorl"aufige Struktur f"ur den Kopf einer Funktion im Dictionary: \begin{center} \begin{tabular}{|c|} \hline Countbyte \\ \hline Name \\ \hline Link \\ \hline CFA \\ \hline Body \\ $\cdots$ \\ \hline \end{tabular} \end{center} Wie "ublich werden also Name und Realisierung eines Wortes beieinander ins Dictionary geschrieben. CFA kann man jetzt als C-Funktions-Adresse lesen. Ihr Sinn ist derselbe wie in traditionellem indirect threaded Forth derjenige der Code Field Address: Dorthin wird verzweigt zur Ausf"uhrung des Wortes. Primitives haben hier die Adresse einer C-Funktion stehen, die die Semantik des Wortes bereitstellt und keinen Body. High-level-Definitionen haben hier einen Zeiger auf eine Runtime-Funktion (in C) stehen, die die im Body beginnende Liste von compilierten Adressen zu interpretieren beginnt: {\sl nest}. Wie kommt die Runtime-Funktion {\sl nest} zu dem Body der Funktion, von der aus sie aufgerufen wurde? Sie kann ihn etwas trickreich aus {\sl IP} schlie"sen: \verb$ip = &ip [-1][1]$ (mit einigen Type-Casts). Besser man erleichtert ihr diese Aufgabe indem man im inneren Interpreter die Variable {\sl W} der virtuellen Maschine einf"uhrt: \begin{quote} \begin{verbatim} for (;;) { w = *ip++; (*w) (); } \end{verbatim} \end{quote} Mit dieser endg"ultigen Form des inneren Interpreters lauten {\sl nest} und {\sl unnest}: \begin{quote} \begin{verbatim} nest () { *--rp = ip; ip = ++w; } unnest () { ip = *rp++; } \end{verbatim} \end{quote} Ein weiteres Problem ergibt sich mit Definitionsworten. Wie gesagt ist f"ur alle Definitionsworte der Code in der CFA eines von ihnen definierten Wortes derselbe. Das Datenfeld beginnt zwingend unmittelbar hinter der CFA. Wo also kann vermerkt werden, {\it von welchem} Definitionswort ein Wort definiert wurde?\footnote{Assembler-Implementationen generieren hier zur Laufzeit ein paar Maschinenbefehle, die in die CFA als ausf"uhrbarer Code eingetragen werden, und die in den high-level Code "uberleiten, der die Laufzeit-Semantik des Definitionswortes bereitstellt. Eine C-Implementation kann das nicht.} Die wenig befriedigende L"osung besteht in der Einf"uhrung eines weiteren Zeigers {\tt aux} in den Kopf jeder Definition, der im Fall einer von einem Definitionswort definierten Definition diese Information enthalten kann: \begin{center} \begin{tabular}{|c|} \hline Countbyte \\ \hline Name \\ \hline Link \\ \hline Aux \\ \hline CFA \\ \hline Body \\ $\cdots$ \\ \hline \end{tabular} \end{center} Dieser Zeiger hilft gl"ucklicherweise auch bei anderen Gelegenheiten: Er stellt z.B.\ den Zusammenhang her zwischen der compilierten Laufzeitsemantik von Kontrollstrukturen und der Definition, die diese Laufzeitsemantik compiliert hat. Dadurch kann der Decompiler {\tt SEE} zu einem compilierten {\tt ?BRANCH} entscheiden, ob er von einem {\tt IF} oder einem {\tt WHILE} her stammt und eine entsprechend strukturierte Ausgabe erzeugen. \subsection{Das Dictionary} Das Dictionary ist in klassischen Forth-Implementationen der eine lineare Speicherbereich, in dem sich alle Forth-Worte -- Namen und Realisierung -- sowie statisch allozierte Daten in bunter Mischung beieinander befinden. Moderne Implementationen zeigen eine starke Tendenz, diesen Bereich aufzuteilen in Symboltabelle, einen Bereich f"ur Maschinencode und einen f"ur High-level-Definitionen und statisch allozierten Speicher.\footnote{Die Motive daf"ur sind teilweise unseri"os: Wenn es n"amlich vor allem darum geht, einer ebenso misratenen wie verbreiteten Speicherarchitektur ein bi"schen mehr Raum abzuringen.} \pfe\ -- traditionell wie es ist -- bleibt bei der einen gro"sen Struktur f"ur Namen und Daten. Lediglich der vom C-Compiler erzeugte Maschinencode liegt au"serhalb. \subsubsection{Struktur} Die Namen werden sind wie "ublich in einer linearen Liste organisiert. Zuviel der Semantik von Forth h"angt von diesem Ansatz ab, als da"s man ihn ohne gr"o"seres Kopfzerbrechen "uber Bord werfen k"onnte. Die Liste ist allerdings -- weitgehend transparent -- aufgeteilt wird in mehrere ``Threads'', wovon einer durch eine Hash-Funktion auf dem Namen des Wortes ausgew"ahlt wird.\footnote{Diese L"osung habe ich in einem CSI-Forth gesehen.} Man k"onnte andersherum sagen: Das Dictionary ist eine kleine Hash-Tabelle mit gro"sem linear verkettetem "Uberlaufbereich. Es bedarf keiner komplizierteren Ans"atze: Die so erreichte Geschwindigkeit der Dictionary-Suche ist voll befriedigend. \subsubsection{Wortlisten} Die Dictionary-Struktur kann vom Compiler nicht ohne gro"sen manuellen Aufand etwa als initialisiertes Feld von {\tt char} angelegt werden. Deshalb werden die Forth-Worte im C-Quelltext in einfacheren Tabellen organisiert, die die Zuordnung von Namen und auszuf"uhrendem Code sowie Eigenschaften wie {\tt IMMEDIATE} enthalten. Beim Systemstart wird aus diesen Tabellen das Dictionary gebaut. Diese Tabellen, eine zun"achst technisch motivierte Vorstufe des Dictionary, k"onnen auch als ``Word Sets'' aufgefa"st werden, wie sie der Standard kennt. Sie erlauben, den Quelltext des Systems modular aufzubauen entlang der Vorgabe des Standards, jeden Word Set in einer eigenen Eingabedatei, die abgeschlossen wird von einer Tabelle, die die in dieser Eingabedatei definierten Worte geschlossen bereitstellt und die Implementationsdetails kapselt. \section{Erweiterung} Einen Assembler bietet \pfe\ nicht. Man kann es aber leicht durch C-Funktionen erweitern, was allerdings eine neue "Ubersetzung des Systems mit dem C-Compiler erfordert und insofern in der t"aglichen Arbeit ein schwacher Trost ist. Dem C-Programmierer bietet der Rest des Systems folgendes Programmiermodell: \begin{description} \item[Datentypen:] Mit den Objekten aus Sicht von Forth kompatible Objekte in C sind als die folgenden {\tt typedefs} bekannt: \begin{description} \item[\tt Cell] eine Einheit auf dem Stack, Integer-Typ mit Vorzeichen, zuweisungskompatibel mit Zeigertypen. \item[\tt uCell] eine Einheit auf dem Stack, Integer-Typ ohne Vorzeichen. \item[\tt dCell] eine doppelt genaue Zahl mit Vorzeichen, {\tt struct} bestehend aus {\tt Cell hi} und {\tt uCell lo}. \item[\tt udCell] wie {\tt dCell}, vorzeichenlos. \item[\tt void (*pcode) (void)] ist ein Zeiger auf eine ein Primitive realisierende C-Funktion, die also der Gestalt {\tt void primitive (void)} ist. Zur Vermeidung von Namenskollisionen enden die Namen all dieser C-Funktionen in einem Tiefstrich. Zur Erleichterung der Definition gibt es das Makro {\tt code(NAME)}, das den Funktionskopf \verb$void NAME_(void)$ erzeugt. Im Kopf jedes Wortes steht ein solcher Zeiger auf die auszuf"uhrende Funktion. \item[\tt pcode *CFA] ist der Typ des Execution Tokens, ein Zeiger auf die Position im Kopf eines Wortes, wo der Zeiger auf dieas Wort realisierende C-Funktion steht. \end{description} \item[Register der virtuellen Maschine] sind global deklarierte C-Variablen: \begin{description} \item[\tt Cell *sp] Daten-Stackpointer \item[\tt CFA *ip] Instruktionszeiger. Zeigt in die Liste compilierter Worte, deren jedes jeweils genau das Execution Token, also ein Zeiger des Typs {\tt CFA} ist. \item[\tt CFA **rp] Der Return-Stack dient zur Sicherung des {\tt ip}, der Stapelzeiger ist also ein Zeiger auf den Typ des {\tt ip}. \item[\tt CFA w] Das W-Register der virtuellen Maschine, hier kann ein Primitive seine eigene CFA ablesen. Zugriff auf den Body des Wortes "uber {\tt ({\it typ} *)\&w[1]}. \end{description} \item[Systemvariablen] Weil die Art der Speicherung der Systemvariablen sich "andern k"onnte, gibt es zum Zugriff auf die in Forth definierten Systemvariablen Makros mit nahenliegenden Namen. So kann in C-Funktionen z.B.\ auf den DP unter dem Namen \verb$DP$ zugegriffen werden usw. \item[Funktionen] Das System enth"alt hunderte von C-Funktionen, wovon nat"urlich nicht jede in ihrer jetzigen Form garantiert -- oder gar dokumentiert -- werden kann. Beispiele: \begin{description} \item[\tt void abortq (char *fmt, ...);] gibt -- mit den F"ahigkeiten von printf() ausgestattet -- eine Fehlermeldung aus und f"uhrt \verb$-2 THROW$ aus. \item[\tt void type (char *s, Cell n)] gibt eine Zeichenkette wie \verb$TYPE$ aus. \item[\tt char *word (char del)] wie das Forth-Wort \verb$WORD$, liest ein Wort aus dem Eingabestrom in den Speicher ab {\tt HERE} und "ubergibt diese Stelle als Funktionsergebnis. \item[\tt void run\_forth (CFA xt);] f"uhrt ein beliebiges (auch High-level) Forth Wort aus. Enth"alt den inneren Interpreter. \end{description} \item[Makros] erleichtern die Anpassung von C an Forth sehr, weil sich darin viele der notwendigen Type-Casts verbergen lassen. Einige Beispiele: \begin{description} \item[\tt POP(T,P,X)] liest ein Objekt des Typs {\tt T} "uber den Zeiger {\tt P} in die Variable {\tt X}, unabh"angig von den tats"achlichen Typen der Operanden. Erh"oht {\tt P} entsprechend. \item[\tt PUSH(T,X,P)] Umkehrung zu {\tt POP}, schreibt ein Objekt {\tt X} des Typs {\tt T} in einen zu kleineren Adressen hin wachsenden Stapel mit Stapelzeiger {\tt P}. \item[\tt RPUSH(X)] legt ein Objekt der Gr"o"se einer Cell auf den Return-Stack. \item[\tt RPOP(X)] holt eine Cell vom Return-Stack. \item[\tt FLAG(X)] macht aus {\tt X} ein Forth-Flag, also 0 bzw.\ -1. \item[\tt COMMA(X)] schreibt das Objekt {\tt X} der Gr"o"se 1 Cell ins Dictionary. \end{description} \end{description} Will man das System zum Beispiel um einen f"ur ein bestimmtes Betriebssystem wichtigen Satz von Worten erweitern, bietet sich die Anlage einer entsprechenden Quelltextdatei an. Sie enth"alt alle system- oder aufgabenspezifischen C-Funktionen, die in eine Reihe von C-Funktionen m"unden, die die Gestalt von Forth-Primitives haben, also mit dem Makro {\tt Code ({\it name})} deklariert sind. Diese Primitives werden in eine Wortliste zusammengefa"st, die beim System registriert wird\footnote{Zur Zeit durch Eintrag in die Tabellen innerhalb der Funktion {\tt preload\_dictionary()} in der Datei {\tt dictnry.c}} und so beim Start von \pfe\ mit ins Dictionary geladen wird. Vollst"andiges Beispiel: \begin{small} \begin{verbatim} #include "forth.h" #include "support.h" Code (user_added_primitive) { outs ("\nThis is a sample primitive." " See src/yours.c " "for it's definition.\n"); } LISTWORDS (your) = { CO ("USER-ADDED-PRIMITIVE", user_added_primitive), }; COUNTWORDS (your, "Your kernel extensions"); \end{verbatim} \end{small} Das Makro {\tt LISTWORDS} deklariert eine Wort"-lis"-ten-Struk"-tur, die zu Initialisieren ist mithilfe der Makros: \begin{center} \begin{tabular}{lp{4cm}} \tt CO(NM,PCODE) & gew"ohnliches Wort \\ \tt CI(NM,PCODE) & immediate Wort \\ \tt CS(NM,SEM) & Compiler Erweiterung \\ \tt SV(NM,VAR) & Systemvariable \\ \tt SC(NM,VAR) & Forth-Konstante, deren Wert aus einer Variablen stammt \\ \tt OC(NM,VAL) & normale Konstante \\ \tt VO(NM,RUNTM) & {\tt WORDLIST} \\ \end{tabular} \end{center} Das Makro {\tt COUNTWORDS} z"ahlt schlicht die Anzahl Worte in der Liste und stellt sie zur Einbindung bereit. \section{Ausblick} \pfe\ wird sich entsprechend seiner Bedeutung weiterentwickeln. Zur Zeit scheint Bedarf an einem solchen System zu bestehen. Allerdings setzen die eingangs begr"undeten Design-Prinzipien der Entwicklung Grenzen. Was sich nicht mit "uberschaubarem Aufwand und portabel machen l"a"st, wird nicht mit Priorit"at behandelt. Es bleiben als {\em denkbare} Entwicklungsrichtungen: \begin{itemize} \item Bereitstellung eines Metacompilers auf \pfe. Nicht mit dem Ziel \pfe\ selbst damit zu "ubersetzen, sondern um es als Entwicklungsplattform f"ur Mikro"-con"-trol"-ler-Pro"-gram"-mie"-rung einsetzen zu k"onnen. \item Einbindung in eine grafische Benutzeroberfl"ache, evtl.\ das X-Window-System. \item Bereitstellung einfacher Grafikbefehle \item Nuetzliche Eigenschaften, wie z.B.\ die Speicherung compilierter Module. \item Multitasking. \item Bessere Unterst"utzung von noch mehr Rechnern. \end{itemize} \begin{thebibliography}{99} \bibitem{dpans} American National Standards Institute: {\sl draft proposed\/} American National Standard for Information Systems -- Programming Languages -- Forth (X3J14 dpANS-6 -- June 30, 1993) \bibitem{fig} Forth Interest Group: {\sl fig-FORTH Installation Manual, Glossary, Model, Editor\/}, Version 1.3, San Carlos, CA, 1980 \bibitem{forth83} FORTH Standards Team: {\sl FORTH-83 Standard\/}, Mountain View, CA, 1983 \bibitem{zech} Zech, Ronald: {\sl Die Programmiersprache Forth\/}, M"unchen: Franzis, 1983 \end{thebibliography} \end{document}