\documentclass[ngerman]{article} %\usepackage{german, a4} \newcommand*{\F}{{\bf\tt 5}} %\usepackage[utf8]{inputenc} %\usepackage{multicol,babel} %\usepackage{xspace} %\setcounter{secnumdepth}{0} %\setcounter{tocdepth}{0} \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{\figurename}{Listing} \begin{document} \title{Forth + APL? \F!} \author{Bernd Ulmann} %\footnote{\tt ulmann@vaxman.de}} \begin{document} \maketitle \label{fuenf} % \begin{center} % {\Large Forth + APL? \F!}\footnote{Dr. Bernd Ulmann, {\tt ulmann@vaxman.de}.} % \end{center} \section{Einleitung} Gefragt danach, welche Programmiersprachen die interessantesten Konzepte beinhalten und am ehesten dazu geeignet sind, nicht nur kurze Implementationszeiten, hohe Flexibilit"at und andere direkt messbare Eigenschaften zu gew"ahrleisten, sondern dar"uber hinaus auch das Denken und Probleml"osen an sich nachhaltig zu ver"andern, antworte ich stets (in alphabetischer Reihenfolge): APL, Forth und Perl. \begin{multicols}{2} Jede dieser Sprachen verf"ugt "uber Eigenschaften, die sie einzigartig machen und aus der Masse der herk"ommlichen Programmiersprachen herausheben. "Uber Forth kann ich an dieser Stelle sicherlich nichts sagen, was nicht allen Lesern der \glqq Vierten Dimension\grqq\ l"angst bekannt w"are -- an erster Stelle der bemerkenswerten Eigenschaften stehen hier f"ur mich die Klarheit und Pr"agnanz von Forth-Programmen, die M"oglichkeit, die Sprache mit den ihr eigenen Mitteln nahezu unbegrenzt erweitern zu k"onnen, und die wunderbare Interaktivit"at, die wie in kaum einem anderen Umfeld zum Experimentieren einl"adt. So sehr ich diese Eigenschaften sch"atze und liebe, so sehr vermisse ich jedoch oft die M"oglichkeit, auf abstrakterer Ebene mit Forth zu arbeiten -- HPs \glqq Reverse Polish LISP\grqq, kurz \glqq RPL\grqq, kommt mir in dieser Hinsicht schon weiter entgegen, indem nahezu beliebige Objekte (nicht im Sinne einer Objektorientierung) auf dem Stack abgelegt und verarbeitet werden k"onnen, hat aber den Nachteil, nur auf HP-Taschenrechnern verf"ugbar zu sein. An APL sch"atze ich vor allem die wunderbare Klarheit und Pr"agnanz seiner Konzepte sowie die Eleganz, mit der Konzepte aus der linearen Algebra und anderen Bereichen der Mathematik direkt auf die L"osung klassischer IT-Fragestellungen angewandt werden k"onnen. Als -- zumindest in meiner Erfahrung -- enormes Problem erweisen sich jedoch fast stets der f"ur APL notwendige arkane Zeichensatz sowie unterschiedliche, mehr oder weniger subtil voneinander abweichende Keymappings, die ein Arbeiten an anderen Rechnern als dem eigenen oft unm"oglich machen. \begin{figure*} \begin{quote} \begin{listing}[1]{1} # Simuliere n Wuerfe mit einem 6-seitigen Wuerfel und bestimme das # arithmetische Mittel hieraus. n wird auf dem TOS erwartet. : wuerfel_mittel dup # Erzeuge eine Kopie von n fuer die Division am Ende. iota # Erzeuge einen Vektor (0 .. n - 1). defined # Erzeuge einen Vektor, der eine 1 an jeder Stelle enthaelt, # an der obiger Vektor ein definiertes Element besitzt. Dies # gilt fuer alle Vektorelemente, so dass das Ergebnis ein # Vektor der Form (1, 1, 1, ... 1) ist. 6 * # Multipliziere den Vektor elementweise mit 6 -> (6, 6, ..., 6). ? # Erzeuge hieraus einen Vektor mit n Pseudozufallszahlen # zwischen 0 und 6 (ausschliesslich). int 1 + # Runde ab und addiere 1, so dass nun alle Elemente des # Vektors zwischen 1 und 6 liegen. '+ # Lege den Operator + auf den Stack und reduce # wende die reduce-Funktion an, um den Vektor elementweise # aufzusummieren. swap / # Dividiere das Resultat durch n. ; 100 wuerfel_mittel . \end{listing} \end{quote} \begin{center} \caption{\label{wuerfel}Ein Zufallszahlengenerator in \F} \end{center} \end{figure*} Das zu Beginn an dritter Stelle genannte Perl ist die Sprache, in der ich die Mehrzahl meiner Programme schreibe -- nicht zuletzt dank des Perl-typischen \glqq There Is More Than One Way To Do It\grqq-Ansatzes, der meiner Arbeitsweise stark entgegenkommt. Im Laufe der vergangenen Jahre habe ich Perl quasi als Allzweckvehikel sch"atzen und lieben gelernt, so dass die Idee nahelag, auf der Basis von Perl einen Interpreter f"ur eine kleine Programmiersprache zu entwickeln, welche die Grundkonzepte von Forth und APL in sich vereinigt. Diese Sprache, kurz \F\ genannt, soll im Folgenden kurz dargestellt werden. Wichtig ist an dieser Stelle die Anmerkung, dass der gegenw"artig existierende \F-Interpreter zwar voll funktionsf"ahig ist, aber noch an etlichen Stellen weiterentwickelt werden muss (unter anderem fehlt noch eine Vielzahl typischer APL-Operatoren und Funktionen). So gesehen versteht sich der vorliegende Artikel sowohl als ein \glqq Request for Comments\grqq\ seitens der Leserschaft als auch als Bitte um Mithilfe bei der weiteren Entwicklung von \F. % \section{\F\ im "Uberblick} Zentrales Element von \F\ ist, wie nicht anders zu erwarten, ein Stack, der in der Lage ist, beliebige Objekte aufzunehmen, solange diese als Skalare oder als beliebig tief verschachtelte Arrays darstellbar sind. Hierunter fallen auch Operatoren, d.h., es ist nicht nur m"oglich, sondern f"ur einige Funktionen auch notwendig, Operatoren wie {\tt +}, {\tt -}, {\tt *}\ oder {\tt /}\ auf dem Stack abzulegen\footnote{Einen Returnstack kennt \F\ nicht.}. Im Hinblick auf elementare Operatoren verh"alt sich \F\ (im Gro"sen und Ganzen) wie ein traditionelles Forth: \begin{verbatim} 5> : square dup * ; 5> 5 square . 25 5> \end{verbatim} Die eigentlich interessanten Eigenschaften von \F\ treten jedoch erst zu Tage, wenn mit verschachtelten Strukturen (\F\ wendet skalare Operatoren wie beispielsweise {\tt +}\ elementweise auf alle Elemente zweier strukturgleicher Vektoren an, so dass sich einfache Vektoroperationen syntaktisch nicht von herk"ommlichen skalaren Operationen unterscheiden) und APL-typischen Operatoren gearbeitet wird. Sollen zum Beispiel zwei dreielementige Vektoren addiert werden, kann dies wie folgt geschehen: \fbox{\tt [1 2 3]~[4 5 6]~+}\ liefert als Resultat den Vektor {\tt [5 7 9]}. Entsprechend liefert \fbox{\tt [1 2 3 4]~1 +}\ als Resultat den Vektor {\tt [2 3 4 5]}. % \section{Beispiele} Im Folgenden werden die wesentlichen Grundideen von \F\ anhand einiger kleiner Beispiele demonstriert. % \subsection{Arithmetisches Mittel von Pseudozufallszahlen} Es ist das arithmetische Mittel von 100 simulierten W"urfen mit einem sechsseitigen W"urfel zu bestimmen. Die Grundidee zur L"osung dieses Problemes in \F\ ist Folgende: \begin{enumerate} \item Erzeuge einen Vektor mit 100 Elementen, die jeweils den Wert {\tt 6}\ besitzen. \item Wende auf diesen Vektor den Operator {\tt ?} an. Dieser entspricht dem APL-Operator {\tt dice}, der eine Pseudozufallszahl zwischen {\tt 0}\ und einem (auf dem TOS) vorgegebenen Wert (ausschlie"slich) generiert. \item Da \F\ skalare Operatoren bei Vorliegen eines Arrays elementweise auf alle Elemente eines Arrays anwendet, erzeugt dies einen ebenfalls 100-elementigen Vektor, der nun allerdings 100 Pseudozufallszahlen im Bereich zwischen {\tt 0}\ und {\tt 6}\ (ausschlie"slich) enth"alt. \item Zur Bestimmung der Summe dieser 100 pseudozuf"alligen Werte kommt in der Folge die APL-typische Operation {\tt reduce}\ zum Einsatz, die auf dem Stack einen skalaren Operator, in diesem Falle {\tt +}, sowie einen Vektor erwartet. Der skalare Operator wird zwischen je zwei benachbarten Elementen eines Vektors zur Anwendung gebracht, was im vorliegenden Fall der Summe "uber alle Vektorelemente entspricht. \item Als abschlie"senden Schritt muss die solcherma"sen erzeugte Summe noch durch die urspr"ungliche Anzahl von Elementen des Ausgangsvektors dividiert werden, um das gew"unschte arithmetische Mittel zu bestimmen. \end{enumerate} In \F\ sieht dieses Beispielprogramm nun so aus, wie in Listing \vref{wuerfel} zu sehen ist. % \subsection{Stackdump} Mit Hilfe von Arrayoperationen kann in \F\ auch einfach ein Wort implementiert werden, das den gesamten Stackinhalt nicht-destruktiv ausgibt. Von zentraler Bedeutung sind hier die beiden Funktionen {\tt compress}\ und {\tt expand}, die im Folgenden kurz erl"autert werden: \begin{description} \item [{\tt compress}:] Fasse $n$ Elemente auf dem Stack in einen einzigen $n$-elementigen Vektor zusammen. Beispiel: \fbox{\tt 1 2 3 3 compress}\ liefert {\tt [1 2 3]}\ zur"uck. \item [{\tt expand}:] Zerlege einen Vektor in seine Elemente und pushe diese auf den Stack. Am Ende der Operation wird die Anzahl der Elemente auf dem Stack abgelegt. \fbox{\tt [1 2 3]~expand}\ liefert also {\tt 1 2 3 3}\ zur"uck, was wieder als Eingabe f"ur {\tt compress}\ genutzt werden k"onnte. \end{description} Die Grundideen zur zerst"orungsfreien Ausgabe des Stackinhaltes sind nun die folgenden: \begin{enumerate} \item Erzeuge einen Vektor aus allen Elementen, die sich auf dem Stack befinden und dupliziere diesen, um einen f"ur die Ausgabe der Elemente zu verwenden und mit Hilfe des anderen den Stack nach Abschluss der Operation zu rekonstruieren. \item Bilde eine Schleife "uber den entstandenen Vektor und entferne jeweils ein Element, das ausgegeben wird. Die Schleife wird abgebrochen, sobald der Vektor keine Elemente mehr enth"alt. \item Rekonstruiere den urspr"unglichen Stackinhalt, indem die Kopie des alle Stackelemente enthaltenden Vektors mit {\tt expand}\ ausgepackt wird. \end{enumerate} \begin{figure*} \begin{quote} \begin{listing}[1]{1} : .s depth # Bestimme die Tiefe des Stacks. compress # Packe alle Stackelemente in einen n-elementigen Vektor. dup # Dupliziere diesen Vektor. do # Schleifenbeginn dup length # Dupliziere den Vektor und bestimme die Anzahl # seiner Elemente. 0 == # Ist die Laenge gleich Null? if # Falls ja, break # verlasse die Schleife. then 0 extract . # Extrahiere das erste Element und gib es aus. loop drop # Enferne den nun leeren Vektor. expand # Packe den zu Beginn kopierten Vektor aus und drop # loesche die Anzahl ausgepackter Elemente. ; \end{listing} \end{quote} \begin{center} \caption{\label{dots}Das Wort \texttt{.S} in \F} \end{center} \end{figure*} % Die praktische Umsetzung hat dann die Gestalt in Listing \vref{dots}. % \subsection{Primzahlen} Das folgende Beispiel ist ein typisches Beispiel f"ur die M"achtigkeit von APL -- nun allerdings in \F\ umgesetzt. Die Aufgabe besteht darin, alle Primzahlen zwischen {\tt 2}\ und einer vorgegebenen oberen Grenze zu bestimmen (Effizienz steht hierbei, wie sich zeigen wird, nicht im Vordergrund). Die zugrunde liegenden Ideen zur Berechnung aller Primzahlen zwischen {\tt 2}\ und einem auf dem TOS gegebenen Wert {\tt n}\ sind die folgenden: \begin{enumerate} \item Erzeuge einen Vektor der Form {\tt [2 3 4 ... n]}\ (von diesem Vektor werden im Folgenden einige Kopien ben"otigt) mit Hilfe des {\tt iota}-Operators. \item Erzeuge auf Basis dieses Vektors eine Matrix als "au\-sseres Produkt zweier dieser Vektoren mit Hilfe der Funktion {\tt outer}. Diese Matrix enth"alt alle Produktkombinationen der in den beiden Vektoren enthaltenen Elemente. Da die Vektoren kein 1-Element enthielten, besteht diese Matrix ausschlie"slich aus zusammengesetzten Zahlen -- in ihr findet sich keine Primzahl\footnote{Die naheliegende Vermutung, dass es ausreicht, eine Matrix mit Kantenl"ange $\sqrt{n}$ zu betrachten, trifft hier nicht zu -- die Kantenl"ange muss $\frac{n}{2}$ betragen.}. \item Unter Verwendung des urspr"unglichen Vektors wird nun elementweise bestimmt, welche Elemente des Vektors in der Matrix auftreten und welche nicht. Die nicht auftretenden Elemente sind die gesuchten Primzahlen. Mit Hilfe der Funktion {\tt in}, welche die Mengenfunktion \glqq Element von\grqq\ abbildet, wird aus der Matrix und diesem Vektor ein Auswahlvektor erzeugt, der aus einer Folge von {\tt 1}- und {\tt 0}-Elementen besteht, die angeben, ob das korrespondierende Vektorelement in der Matrix auftrat oder nicht. \item Nach elementweisem Invertieren dieses Vektors liegt ein Auswahlvektor vor, der an jeder Stelle, deren Wert im urspr"unglichen Vektor einer Primzahl entspricht, eine {\tt 1}\ aufweist. Dieser Steuervektor wird dann verwendet, um aus dem urspr"unglichen Vektor nur die primen Elemente zu selektieren und hieraus einen neuen Vektor zu generieren. \end{enumerate} Die Implementation dieses Verfahrens hat in \F\ folgende Gestalt: \begin{verbatim} : prime_list 1 - iota 2 + dup dup dup '* outer swap in not select ; 100 prime_list . \end{verbatim} % \section{Sonstiges} Obwohl sich \F\ noch im Prototypenstadium befindet, hat es sich bereits bei der Auswertung von Messdaten und als Demonstrationssprache in einer Vorlesung bew"ahrt. Typische \F-Programme sind meist "ahnlich kurz wie klassische APL-Implementationen, ohne jedoch die Nachteile des speziellen Zeichensatzes sowie der doch recht ungewohnten Auswertung von Ausdr"ucken von rechts nach links zu "ubernehmen. Gerade die von Forth entlehnte gro"se Interaktivit"at vereint mit der M"oglichkeit, eigene W"orter zu definieren, macht \F\ zu einem m"achtigen und interessanten Instrument. Wie bereits erw"ahnt, ist der Interpreter in Perl implementiert und damit weitgehend maschinen- und betriebssystemunabh"angig (gegenw"artig wird \F\ bereits unter Mac OS X, LINUX, OpenVMS und Windows verwendet). Zu seinem Betrieb ist lediglich ein Perl-Interpreter notwendig (es werden keine besonderen Zusatzpakete ben"otigt). Das komplette \F-Paket, das neben dem eigentlichen Interpreter auch eine kleine Standard-Library ({\tt stdlib.5}), einige einfache Beispiele sowie eine recht ausf"uhrliche Dokumentation (in Englisch) enth"alt, kann unter {\tt http://lang5.sourceforge.net}\ in Form eines ZIP-Files (ca. 250 kB) heruntergeladen werden. % Der Autor Dr.\ Bernd Ulmann kann unter {\tt ulmann@vaxman.de}\ erreicht werden und freut sich "uber jede R"uckmeldung sowie (und vor allem) "uber m"ogliche Mitstreiter, deren Neugierde auf \F\ der vorliegende kurze Artikel geweckt haben mag. \end{multicols} \end{document}