% Content-encoding: UTF-8
\documentclass[ngerman]{article}
\usepackage[utf8]{inputenc}
\usepackage{multicol,babel}
\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}
\begin{document}
% \renewcommand{\figurename}{Tabelle}
\title{Cedrics Codierwettstreit — eine Lösung in Forth}
\ifx\shorttitle\undefined\else
\shorttitle{Codierwettstreit}
\fi
\author{Samuel A.~Falvo II (Ãœbersetzt und aufbereitet von Michael Kalus)}
\maketitle
\begin{multicols}{2}
\section{Der Wettstreit}
Neulich fand ich einen Wettstreit im Netz:\\
\url{http://beust.com/weblog/archives/000491.html}\\
Posted by cedric at June 27, 2008 11:48 PM \medskip
Cedric schrieb:
\glqq Hier ist eine interessante Codieraufgabe: Schreibe einen Zähler, der von $1$ bis $\mathrm{MAX}$ zählt, aber nur die Zahlen wiedergibt, deren Ziffern sich nicht wiederholen. Als Beispiel diene dieser Teil der Ausgabe:
8, 9, 10, 12 ( 11 ist ungültig)\\
98, 102, 103 ( 99, 100 und 101 sind ungültig)\\
5432, 5436, 5437 ( 5433, 5434 und 5435 sind ungültig)
Außerdem:
\begin{itemize}
\item Gebe den größten Sprung an; im Beispiel ist es 4:\\
98 $\rightarrow$ 102.
\item Gebe an, wieviele Zahlen ausgegeben wurden.
\end{itemize}
Gib beides an für $\mathrm{MAX}=10000$.
Postet Eure Lösungen im Kommentar oder auf Eurem eigenen Blog. Es sind alle Sprachen und alle Herangehensweisen willkommen. Ich bin gespannt, ob jemand eine Lösung hat, ich habe keine...\grqq
Cedrics Herausforderung wurde angenommen, es trafen viele Lösungen in allen möglichen Sprachen bei ihm ein. Samuel A.~Falvo II postete seine Lösung in Forth am June 29, 2008 02:19 AM. Er war so freundlich, auf meine Mail zu antworten, und sehr entgegenkommend, hilfsbereit und gleich einverstanden, einen kleinen Beitrag für die VD daraus zu machen --- herzlichen Dank, Samuel.
Der im Blog etwas ramponierte Forth--Code --- der Blog entfernte alle \emph{überschüssigen} Blanks --- wurde von ihm in seinem Stil restauriert. Wer sein Video gesehen hat, wird schon eine Vorstellung von seinem Programmierstil haben.
\end{multicols}
\section{Listing}
\begin{quote}
\begin{listing}[1]{1}
vocabulary cedrics_challenge
cedrics_challenge definitions
10000 constant largest
: rdrop postpone r> postpone drop ; immediate
( a simple approximation of integer sets using bit-masks )
( good enough to satisfy the challenge )
: mask ( n -- n' ) 1 swap lshift ;
: union ( n a -- ) swap mask over @ or swap ! ;
: intersects ( n a -- f ) @ swap mask and ;
( the proper challenge solution )
variable seen-set
variable recurs-set
variable t
variable max-j
variable j
: digits ( n -- c-addr u ) 0 <# #s #> ;
: digit ( c-addr u -- c-addr u n ) over c@ [char] 0 - ;
: recurs ( n -- ) seen-set intersects recurs-set @ or recurs-set ! ;
: seen ( n -- ) seen-set union ;
: analyze ( c-addr u -- ) seen-set off recurs-set off begin dup while
digit dup recurs seen 1 /string repeat 2drop ;
: recur ( c-addr u -- f ) analyze recurs-set @ ;
: unique ( n -- n ) dup digits recur if 1 j +! rdrop exit then ;
( filters numbers for uniqueness )
: j0 ( -- ) 1 j ! ;
: initialize ( -- ) t off j0 max-j off ;
: jumps ( -- ) j @ max-j @ max max-j ! j0 ;
: total ( -- ) 1 t +! ;
: stats ( -- ) jumps total ;
: number ( n -- n ) unique dup u. cr stats ;
: report ( -- ) max-j @ . ." max jump" cr
t @ . ." total numbers displayed" cr ;
: numbers ( -- ) 1 begin number 1+ dup largest > until drop ;
: challenge ( -- ) initialize numbers report ;
\ challenge
words
0 [if]
Um das laufen zu lassen, fuege den obigen Code in eine Datei "challenge.fs" ein,
und fuehre "gforth challenge.fs" im Terminal nach dem shell prompt aus.
Posted by: Samuel A. Falvo II at June 29, 2008 02:19 AM
Uebersetzt und tested ok auf gforth; mka 28.12.2008.
[then]
\end{listing}
\end{quote}
\section{Links}
\begin{footnotesize}
\url{http://beust.com/weblog/archives/000491.html}\hfil
Lies auch die \emph{CODING CHALLENGE WRAP-UP}\hfill\\
\url{http://www.falvotech.com/blog/}\\
\url{http://www.falvotech.com/blog/index.php?/archives/372-Over-the-Shoulder-1-Text-Preprocessing-in-Forth.html}
\end{footnotesize}
\begin{multicols}{2}
\section{Das \emph{Making of ...}}
(Aus der email-Korrespondenz zu Falvos Lösung)
{\bf mk:} Wie kamst du zu deinem Programmierstil?
{\bf sf:} Der Stil, in dem ich codiere, entstand so. Mein Bildschirm ist recht groß und hat eine hohe Auflösung. Daher würde eine vertikale Anordnung des Codes sehr viel Platz verschwenden. Horizontal zu schreiben, gefällt mir mehr, denn ich neige dazu, \emph{fließend} Forth zu schreiben. Das liest sich dann wie ein Wörterbuch, und ich strebe an, dass jede Definition mehr oder weniger wie ein englischer Satz gelesen werden kann. Das hilft mir auch, auf Kommentare verzichten zu können. Die meisten meiner Kommentare sind nur noch Prüfvermerke. Meine Bildschirmauflösung, und die relativ kleine Schrift, ermöglichen es mir, die Regel einzuhalten, nur eine Zeile für eine Definition zu brauchen, selten mal eine zweite Zeile. Und aussagekräftige Namen voranzustellen und in der Definition dann leserliche Spalten einzuteilen. Die Namen kommen ganz nach links, Stackbilder mehr in die Mitte und die Definitionen nach rechts. Den Code beim Edieren \emph{hübsch} zu halten macht zwar etwas mehr Mühe, aber es bringt mir auch eine bessere Produktivität, und lohnt daher.
{\bf mk:} Möchtest du eine Erklärung geben, was \texttt{UNIQUE} macht, speziell was \texttt{RDROP} da tut? Ich vermute, du fällst damit aus \texttt{NUMBER} heraus, ohne dass die Zahl gedruckt wird --- so eine Art blitzartiger \texttt{EXIT}?
{\bf sf:} Das stimmt: \texttt{UNIQUE} prüft, ob eine Zahl (number) die Kriterien der Einzigartigkeit (uniqueness requirements) aus Cedrics Aufgabe erfüllt. Falls sie das nicht tut, nehme ich den \emph{vorzeitigen Ausgang} (early-exit) aus dem aktuellen Schritt, um in den nächsten Schleifendurchgang zu kommen. Das beseitigt eine Menge an visuellem und mentalem Wirrwar, man vermeidet so, tief verschachtelte Kontrollstrukturen entziffern zu müssen.
Die Art von Logik wird übrigens \emph{structured returns} genannt. Strukturierte Rücksprünge wurden in den 70igern unbeliebt wegen des starken Einflusses, den Dijkstra genommen hat, als er strukturierte Programmiersprachen implementierte. Überdies war es ohne die starre und sehr strikte Typprüfung --- die dem C und Pascal offenbar fehlten, was die strukturierte Programmierung für Jahrzehnte auf den Weg brachte --- einem Compiler gar nicht möglich, Korrektheit des erzeugten Codes zu verifizieren, wenn dieser keine eindeutigen Eintritts-- und Austrittspunkte für alle Programmstrukturen hatte.
Zum Glück kamen funktional höher entwickelte Sprachen auf, wie OCaml und Haskell, und strukturierte Rücksprünge erleben ihr comeback, insofern als die Compiler nun in der Lage sind, statistisch den resultierenden Code zu verifizieren, dank der Eigenschaft referentieller Transparenz und sehr starker Typprüfung.
Wenn man beim Softwareschreiben erst mal mit dem Stil vertraut ist, Fortsetzungen für einen Datenfluss zu übergeben (continuation-passing style of writing software), wird der Returnstack tatsächlich wie ein Pseudo-Parameterstack behandelt, auf dem mögliche Fortsetzungen liegen. Ich suche aus, welche Fortsetzung ausgeführt werden soll, indem der Returnstack entsprechend manipuliert wird.
Programmierer, die mit dem Z--80 Mikroprozessor vertraut sind, erinnern sich möglicherweise an die Instruktion für einen bedingten Rücksprung aus einem Unterprogramm (\texttt{RET Z}) und vermissen die in modernen Architekturen. Freigelegt wie der Returnstack im Forth nun mal ist, können wir diese Freiheit ja auch genausogut genießen und wieder strukturierte Rücksprünge machen.
{\bf mk:} Man sieht es dem \texttt{UNIQUE} auf den ersten Blick nicht an, dass es so einen Blitzabgang macht, und wundert sich zunächst einmal, wieso manche Zahlen nicht gedruckt werden.
{\bf sf:} Mit dem Namen, den ich da ausgesucht hatte, bin ich auch nicht mehr so glücklich inzwischen, aber es ist der beste aus einigen Alternativen, finde ich. Versucht hatte ich auch folgende, aber dann verworfen aus den genannten Gründen:
\begin{itemize}
\item \texttt{unique:} --- Der angehängte Doppelpunkt zeigt konventionell ein Wort an, das neue Worte erzeugt (defining word), passt also nicht.
\item \texttt{?unique} --- Das vorangestellte Fragezeichen suggeriert, dass das Wort optional ausgeführt wird, sagt aber nichts über den Rest der Definition dahinter aus. Dabei möchte ich das Gegenteilige sagen, nämlich dass \texttt{UNIQUE} immer ausgeführt wird, nur alles danach ist optional.
\item \texttt{unique?} --- Damit würde ein Prädikat angedeutet, das \texttt{TRUE} oder \texttt{FALSE} sein könnte. Auch das zeigt die bedingte Ausführung der verbleibenden Definition nicht an.
\item \texttt{only-if-unique} --- Zu viele Worte. Ich suche die Ein--Wort--ein--Konzept--Definition. (Ich schätze diese Wortfülle in anderen Sprachen, besonders in C oder Haskell, da es dort flüssiges Codieren verhindert :)
\item \texttt{if-unique} --- Besser, aber immer noch zwei Worte und Bindestrich.
\item \texttt{ifUnique} -- Hier nähme ich statt Bindestrich einen Großbuchstaben; aber immer noch zwei Worte.
\item \texttt{only} --- Das würde bestens ausdrücken, das der Rest der Definition von irgendeiner Bedingung abhängt. Aber es drückt nicht aus, welche Bedingung es sein könnte.
\end{itemize}
Auch könnte man sich irgendein anderes Wort ausdenken, das einen besseren Namen für die Funktion abgibt.
Auch wäre ein \texttt{CASE} für flüssige Codierung denkbar:
\begin{verbatim}
: blah unique? only
( Rest der Definition hier ) ;
\end{verbatim}
wobei \texttt{UNIQUE?} einen boolschen Wert abgeben müsste, und \texttt{ONLY} den bedingten Ausgang durchführte. Aber das wäre strukturell identisch zum \texttt{IF}/\texttt{THEN}:
\begin{verbatim}
: blah unique? IF ... THEN ;
\end{verbatim}
Das alles erschien mir damals viel zu viel Sehwirrwarr zu sein.
{\bf mk:} Und wozu setzt du die Masken (mask) in dem Programm ein?
{\bf sf:} Das Wort \texttt{DIGITS} wandelt eine Zahl in ihre Zeichenkette um. Die Zeichenkette erlaubt den Zugriff auf die einzelnen Ziffern der Zahl. \texttt{RECUR} wandert zu jeder Ziffer und protokolliert zum einen, welche Ziffer in der Zahl vorgefunden wurde, und zum anderen, welche mehrmals dabei gewesen ist.
Die \texttt{SEEN-MASK} erzeugt integer Werte. Da in der dezimalen Zahl nur die Ziffern 0..9 vorkommen, reicht für eine \texttt{SEEN-MASK} ein 16-Bit Wert hin. Damit wird angezeigt, welche Ziffern in der Zeichenkette tatsächlich vorhanden waren. \texttt{SEEN-MASK} ist vielleicht eine Fehlbenennung; indes, zumindest im Englischen, ist es bei Programmierern durchaus üblich, davon zu sprechen, dass ein Element in einer Sammlung \emph{gesehen} worden ist (item seen in a collection).
Die \texttt{RECUR-MASK} ist auch ein integer--Wert, ist aber immer nur eine ausgewählte Teilmenge der \texttt{SEEN-MASK}. Hierin wird festgehalten, welche Ziffern mehr als einmal in der Zahl waren. Nimm zum Beispiel die Zahl 343, die \texttt{SEEN-MASK} enthält dann \texttt{\{3,4\}} - also Bits 3 und 4 sind gesetzt. Die \texttt{RECUR-MASK} hingegen enthält nur \texttt{\{3\}}.
Der logische Operator \texttt{AND} berechnet den Durchschnitt zweier Datensätze (set), während \texttt{OR} die Vereinigung darstellt. Einen leeren Datensatz zu finden, ist dann so einfach wie die, den mask-Wert auf Null (zero) zu testen.
Ich habe eine bit-mask genommen, um die Datensätze zu erzeugen, weil das die trivialste Form in Forth ist, die es gibt: Integer. Auch in den meisten Pascal-- und Modula-2--Systemen implementiert man \texttt{SET}--Typen als Bitmasken, und Oberon und Oberon-2 geben ihre \texttt{SET}--Typen ebenfalls als Bitmasken ausdrücklich dem Programmierer an die Hand. Ich bin in guter Gesellschaft damit. :)
{\bf mk:} Vielen Dank für die freundliche Unterstützung.
{\bf sf:} Kein Problem. Vielleicht interessiert es dich auch, dass ich einen Vortrag auf dem SV--FIG Treffen im Februar (2009) halten werde; falls nicht noch ein besseres Thema auftaucht, wird es ein Durchgang durch meine
SEAforth-24--VGA--driver--software und video--clock--application werden.
\end{multicols}
\end{document}