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