\documentclass[a4paper]{article}
\usepackage[utf-8]{inputenc}
\usepackage[german]{babel}
\usepackage{url}
\usepackage{alltt}
\usepackage{multicol}
%llncs float params
%\setcounter{topnumber}{3}
%\def\topfraction{.9}
%\setcounter{bottomnumber}{1}
%\def\bottomfraction{.3}
%\setcounter{totalnumber}{3}
%\def\textfraction{.15}
%\def\floatpagefraction{.85}
%\setcounter{dbltopnumber}{3}
%\def\dbltopfraction{.85}
%\def\dblfloatpagefraction{.85}
\newcommand{\code}[1]{\texttt{#1}}
%\wfig{content}{label}{caption}
\newcommand{\wfig}[3]{
\begin{figure*}\hrule\vspace{1ex}
\centerline{#1}\vspace{1ex}
\hrule
\caption{#3}
\figlabel{#2}
\end{figure*}
}
%\nfig{content}{label}{caption}
\newcommand{\nfig}[3]{
\begin{figure}\hrule\vspace{1ex}
\centerline{#1}\vspace{1ex}
\hrule
\caption{#3}
\figlabel{#2}
\end{figure}
}
\newcommand{\figlabel}[1]{\label{fig-#1}}
\newcommand{\figref}[1]{\ref{fig-#1}}
\newcommand{\fig}[1]{Abb.~\figref{#1}}
\newcommand{\Fig}[1]{\figurename~\figref{#1}}
\newcommand{\sectref}[1]{\ref{sect-#1}}
\newcommand{\sect}[1]{Section~\sectref{#1}}
\newcommand{\Sect}[1]{Section~\sectref{#1}}
\title{Factor, Postscript, und Forth: Ein kleiner Vergleich}
\ifx\shorttitle\undefined\else
\shorttitle{Factor, Postscript, und Forth}
\fi
\author{M.~Anton Ertl}
\begin{document}
\maketitle
\begin{figure*}[b]\hrule\vspace{1ex}
\begin{verbatim}
: map-array ( ... addr u xt -- ... )
\ executes xt ( ... x -- ... ) for every element of the array starting
\ at addr and containing u elements
{ xt }
cells over + swap ?do
i @ xt execute
1 cells +loop ;
create array 1000 cells allot
: init 1000 0 do i array i cells + ! loop ;
init
: step 0 array 1000 ['] + map-array drop ;
: bench 100000 0 do step loop ;
bench
\end{verbatim}
\vspace{1ex}
\hrule
\caption{Forth-Programm (Anton Ertl)}
\figlabel{map-array.fs}
\end{figure*}
\begin{multicols}{2}
Auf der Forth-Tagung präsentierte Ulrich Hoffmann die
Programmiersprache Factor von Slava Pestov
u.a. (\url{http://factorcode.org}). Diese Programmiersprache ist in
der Syntax recht ähnlich zu Forth, unterscheidet sich aber ansonsten
in vielerlei Hinsicht: vor allem hat Factor eine dynamische
Typüberprüfung, während Forth keine Typüberprüfung verwendet. Damit
einher geht die automatische Speicherverwaltung (garbage collection)
in Factor; weiters zeichnet sich Factor noch durch das Vorhandensein
von Wörtern aus, die von funktionalen Programmiersprachen inspiriert
sind. Es gibt noch weitere interessante Features von Factor, auf die
ich in diesem Artikel aber nicht eingehe.
Ich fühlte mich natürlich gleich inspiriert, Factor mit einer
älteren stack-basierten Programmiersprache mit dynamischer
Typüberprüfung und Speicherverwaltung zu vergleichen: Postscript
\cite{adobe99}. Hier gibt es deutlichere Abweichungen in der Syntax,
aber von der Semantik sind sich Factor und Postscript näher als
Factor und Forth. Als weitere Sprache zum Vergleich wählten wir
natürlich Forth.
Wir beschlossen, ein kleines Programm in allen drei Sprachen zu
schreiben, um die Unterschiede und Gemeinsamkeiten der drei Sprachen
klarer zu sehen; außerdem wollten wir dann noch die Laufzeit der
Programme messen. Ich postete die Programme dann in
\url{comp.lang.forth} und \url{comp.lang.postscript}, und erhielt
dabei noch verbesserte Programme (siehe News-Artikel
\url{<2007May3.220119@mips.complang.tuwien.ac.at>} ff.).
Das Programm soll ein Array mit den 1000 Elementen 0...999 (oder
1...1000) erzeugen, und dann die Elemente des Arrays 100.000--mal
aufaddieren. Diese Aufgabe ist besonders dazu gedacht, um die
funktionalen Elemente von Factor zu zeigen, daher sollte es dabei
nicht wundern, wenn Factor besser ausschaut. Die Programme und
englischer Text dazu sind auf
\texttt{complang.tuwien}\footnote{\url{http://www.complang.tuwien.ac.at/forth/programs/map-array/}} zu
finden.
\section{Forth}
Fangen wir zunächst mit einem Forth-Programm (\fig{map-array.fs})
an, dann versteht man die anderen auch leichter.
Die Definition von \code{map-array} (aus dem Gforth-Tutorial \cite{gforth03}\footnote{\url{http://www.complang.tuwien.ac.at/forth/gforth/Docs-html/Execution-Tokens-Tutorial.html}})
erlaubt einen ähnlich funktionalen Programmierstil wie Factor.
Bevor \code{map-array} aber verwendet wird, wird zuerst das Array
allokiert und initialisiert, mit einem Forth-üblichen
Programmierstil.
In \code{step} werden die Elemente des Arrays mithilfe von
\code{map-array} aufaddiert: Und zwar wird das Array \code{array 1000}
und das Execution Token (XT) von \code{+} an \code{map-array} übergeben; weiters
steht noch 0 auf dem Stack. \code{Map-array} legt jetzt das erste
Element des Arrays auf den Stack und führt das XT aus, addiert das
Element also zum schon vorhandenen 0 dazu; in der nächsten
Iteration legt es das nächste Element auf den Stack, führt
nocheinmal \code{+} aus, und addiert so das zweite Element zur
Zwischensumme. Am Ende steht die Summe aller Elemente auf dem Stack
(und wird dann mit \code{drop} weggeworfen).
\begin{figure*}[t]\hrule\vspace{1ex}
\begin{verbatim}
USING: syntax vectors namespaces math kernel sequences tools ;
: step 0 [ + ] reduce drop ; inline
: numbers 1000 [ 1+ ] map ; inline
: bench numbers 100000 [ dup step ] times drop ;
bench
\end{verbatim}
\vspace{1ex}
\hrule
\caption{Factor-Programm (Slava Pestov)}
\figlabel{slava.factor}
\end{figure*}
\begin{figure*}[b]\hrule\vspace{1ex}
\begin{verbatim}
/v [ 0 1 999 {} for ] def
/step {0 v { add } forall} bind def
100000 {step pop} bind repeat
\end{verbatim}
\vspace{1ex}
\hrule
\caption{Postscript-Programm (Anton Ertl)}
\figlabel{bind.ps}
\end{figure*}
In \code{bench} wird \code{step} dann 100.000--mal ausgeführt.
Bemerkenswert bei \code{map-array} ist noch, dass es mit XTs mit
verschiedenen Stack-Effekten umgehen kann, solange dabei immer ein
Datenstack-Element verbraucht wird und ansonsten die Anzahl der
Elemente gleich bleibt, z.B. kann man es mit \code{.} zum Drucken und
mit \code{max} zum Finden des Maximums einsetzen.
\section{Factor}
Was beim Factor-Programm (\fig{slava.factor}) zunächst einmal
auffällt, sind die eckigen Klammern. Sie schließen quotations
ein, das sind Codestücke, die nicht sofort ausgeführt werden,
sondern den nachfolgenden Wörtern übergeben werden, die sie dann
mehrmals ausführen. Das ist ähnlich den XTs in Forth, aber
etwas bequemer. Auf diese Weise wird Kontrollfluss in Factor
implementiert.
In \code{numbers} wird unser Array erzeugt: \code{map} führt die
quotation \code{[ 1+ ]} auf den Werten von 0 bis 999 aus, und sammelt
das Ergebnis (die Werte 1...1000) in einem Array.
In \code{step} werden die Werte im Array aufaddiert, genauso wie im
Forth-\code{step}, nur dass statt dem selbstdefinierten
\code{map-array} das vordefinierte \code{reduce} verwendet wird, das
sich von \code{map-array} durch den Stack-Effect \code{( array x1 quot
-- x2 )} unterscheidet; es ist eigentlich nur zur Verwendung auf
quotations mit dem Stack-Effekt \code{( x1 y -- x2 )} gedacht (kann
aber auch flexibler eingesetzt werden).
Schließlich führt \code{bench} 100.000--mal \code{step} aus, wieder
über eine Quotation und das Kontrollflusswort \code{times} gesteuert.
Die \code{inline}s helfen dem Compiler, schnellen Code zu produzieren,
u.a.\ indem der Compiler Typüberprüfungen wegoptimieren kann.
\section{Postscript}
Auch bei der Postscript-Version (\fig{bind.ps}) gibt es Codestücke,
die nicht sofort ausgeführt werden, diesmal in geschwungenen
Klammern und Procedures genannt, aber eigentlich das gleiche wie
Quotations. Dafür sind Arrays in eckigen Klammern, die geschwungenen
und eckigen Klammern vertauschen also im Vergleich zu Factor die
Rolle.
In Postscript gibt es im Prinzip nur ein Definitionswort: \code{def}
nimmt einen Namen (z.B. \code{step}, als Literal so geschrieben
\code{/step}) und ein Objekt (z.B. eine Prozedur) vom Stack, und
bindet das Objekt an den Namen.
Die erste Definition definiert das Array \code{v}. Bemerkenswert ist
hier, wie das Array aufgebaut wird: da wird nämlich zunächst die Marke
\code{[} auf den Stack geschrieben, dann alle Werte des Arrays, und
schließlich baut \code{]} das Array aus allen Elementen auf, die auf
dem Stack über der obersten Marke liegen (und nimmt dabei diese Werte
alle vom Stack).
Die 1000 Werte in dem Array werden von dem \code{for} produziert, das
alle Werte von 0 bis 999 in 1er-Schritten erzeugt und dann der leeren
Prozedur \verb/{}/ übergibt, die damit aber nichts macht, sodass die
Werte alle auf dem Stack liegen bleiben.
Auf diese Weise lassen sich sehr flexibel Arrays erzeugen und
transformieren, mit deutlich weniger verschiedenen Wörtern als in
Factor.
Die Verwendung einer Schleife, bei der die Stack-Tiefe mit jeder
Iteration zunimmt, ist in Forth unüblich und schlechter Stil, aber
in Postscript ist das durchaus üblich, um Arrays aufzubauen. Das
hängt auch damit zusammen, dass die dynamische Typinformation in Postscript es
erlaubt, die Marke \code{[} von Werten zu unterscheiden, die als Elemente des
Arrays gedacht sind, was in Forth im Allgemeinen nicht möglich ist.
Die Definition von \code{step} erfolgt wieder nach dem altbekannten
Muster, nur dass hier \code{forall} statt \code{map-array} bzw.\
\code{reduce} verwendet wird.
Zwischen der Prozedur und \code{def} steht noch \code{bind}, was die
Ausführung noch etwas beschleunigt, indem es dafür sorgt, dass
bei eingebauten Operatoren wie \code{add} der Name gleich aufgelöst
wird und nicht erst bei der Ausführung.
Schließlich erfolgt die 100.000--fache Ausführung mittels
\code{repeat}, das Postscript-Äquivalent zum Factor-Wort \code{times}.
\begin{figure*}\hrule\vspace{1ex}
\begin{verbatim}
: (map) ( a n - a a') cells over + swap ;
: map[ postpone (map) postpone ?do postpone i postpone @ ; immediate
: ]map 1 cells postpone literal postpone +loop ; immediate
create array 1000 cells allot
: init 1000 0 do i array i cells + ! loop ;
init
: step 0 array 1000 map[ + ]map drop ;
: bench 100000 0 do step loop ;
bench
\end{verbatim}
\vspace{1ex}
\hrule
\caption{Forth-Programm (Andrew Haley)}
\figlabel{haley.fs}
\end{figure*}
\section{Forth, die zweite}
Andrew Haley wies darauf hin, dass die in \fig{map-array.fs}
gezeigte Forth-Version nicht idiomatisches Forth ist, und
präsentierte eine andere Lösung (\fig{haley.fs}).
Statt \code{map-array}, das ein XT nimmt und ausführt,
gibt es hier zwei Wörter \code{map[} und \code{]map}, die als
Macros eine Schleife um das \code{+} herum bauen, die pro Element
einmal ausgeführt wird, wobei das Element zuerst noch auf den Stack
gelegt wird.
\section{Messungen}
Die Programme wurden auf einem Dual-Xeon 5160 (3GHz) System unter
Linux (Debian Etch) durchgeführt (alle Systeme für 64-bit,
ausgenommen die Forth-Systeme (32-bit)), und dabei die Laufzeit
(User Time) gemessen:
\begin{tabular}{cll}
Zeit&Programm&System\\\hline
%0.94s&map-array.fs&Gforth 0.6.2 (Debian)\\
0.64s&map-array.fs&Gforth 0.6.2 (gcc-2.95)\\
0.48s&map-array.fs&iForth 2.1.2541\\
0.96s&slava.factor&Factor 0.88\\
1.99s&bind.ps&ESP Ghostscript 815.03\\
%0.73s&haley2.fs&Gforth 0.6.2 (Debian)\\
0.51s&haley2.fs&Gforth 0.6.2 (gcc-2.95)\\
0.23s&haley2.fs&iForth 2.1.2541\\
\end{tabular}
Wie man sieht, kostet die dynamische Typüberprüfung und die anderen
mehr oder weniger netten Features von Postscript und Factor schon
einiges, aber der Abstand (vor allem bei Ghostscript) ist kleiner, als
ich erwartet hätte.
\end{multicols}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\bibliographystyle{alpha}
%\bibliography{d,pub}
\newcommand{\etalchar}[1]{$^{#1}$}
\begin{thebibliography}{CEK{\etalchar{+}}03}
\bibitem[CEK{\etalchar{+}}03]{gforth03}
Neal Crook, Anton Ertl, David Kuehling, Bernd Paysan, and Jens Wilke.
\newblock {\em Gforth (Manual)}.
\newblock Free Software Foundation, 0.6.2 edition, 2003.
\bibitem[Inc99]{adobe99}
Adobe~Systems Incorporated.
\newblock {\em PostScript Language --- Reference Manual}.
\newblock Addison-Wesley, third edition, 1999.
\end{thebibliography}
\end{document}