<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">% 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&gt; 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 &lt;# #s #&gt; ;
: 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 &gt; 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}
</pre></body></html>