\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}
