Ich bin gestern über einen (für mich zumindest) schwerwiegenden Bug in einem Programm gestolpert, das ich benutze. Nichts sicherheitsre­levantes (von sowas habe ich zumindest keine Ahnung), aber es beeinträchtigt die Nutzbarkeit des Programms schon in einigen Fällen. Nachdem ich ein wenig umhergeschaut habe, wie man deinen einen Bugreport zukommen lassen kann, fand ich heraus, daß es keinen Bugtracker gibt – sie benutzen ein Forum dafür. Gut, es ist deren Entscheidung; ich muß damit ja nicht zurechtkommen. Aber dort anmelden reicht erst mal noch nicht, daß ich auch Beiträge erstellen kann. Ich muß zunächst freigeschaltet werden und darauf warte ich immer noch (seit 2010–11–10 12:10).

Ich schätze mal, es ist im Interesse der Entwickler, das Berichten von Fehlern einfach zu machen. Immerhin opfert nicht jeder Benutzer die Zeit, einen Bugreport zu schreiben, wenn er einen Fehler findet und von daher sollten sie dankbar sein, wenn es jemand tut, statt ihn in eine Warteschlange zu schieben, aus der er erst nach Tagen wieder heraus kommt. Zumindest für mich ist der Willen, einen guten Bugreport zu schreiben, nicht mehr so sehr vorhanden, je länger ich warten muß.

Kürzlich wurde mir jenes Bild zugespielt:

Im Grunde fasst es das Grundproblem gut zusammen. Benutzer und Entwickler denken auf sehr unterschiedlichen Abstraktionsebenen. Für einen Entwickler ist die Benutzeroberfläche lediglich „eine weitere Schale“ um den Kern herum und das meiste komische Verhalten in selbiger kann er problemlos anhand anderer Teile des Systems erklären. Für den Benutzer allerdings ist die Benutzeroberfläche das Programm. Und er wird sich nicht die Mühe machen, viel mehr als das zu durchschauen und zu begreifen. Für alle praktischen Belange ist der Rest, also, wie ein Programm eigentlich funktioniert, tatsächlich Magie.

Nun ist obiges Bild leider etwas klein und ich fand weder den Originalautor noch eine hoch aufgelöste Version. Also habe ich mich mal hingesetzt und eine Vektorgrafik auf der Basis erstellt, die hier angehängt ist. Tatsächlich sind es sogar zwei geworden: Einmal weiß auf schwarz und einmal schwarz auf weiß, was sich wohl etwas tonersparender drucken lassen sollte.

Die Schrift, die in den Grafiken verwendet wurde, ist die freie (und hübsche) Fontin.

Ich habe auch die Ausgangsdateien von Expression Design angehängt. Vielleicht mag jemand ja die „Quell“dateien haben. Sowohl die Design- als auch die PDF-Dateien veröffentliche ich hiermit gemeinfrei.

Angehängt sind hier sowohl die deutschen als auch die englischen Varianten.

Die Skript-Sommerspiele 2009 werden heute eröffnet. Ich werde teilnehmen und versuchen, die einzelnen Probleme auch zu golfen.

Die Ankündigung der einzelnen Ereignisse ist leider etwas schwer zu finden, deswegen habe ich auch erst heute gemerkt, daß sie schon bei Event 5 sind. Aber eigentlich und offiziell beginnt das ganze heute.

Meine Lösungen liegen in meinem SVN-Repository.

Update (2009–08–06): Ich habe eine signierte Ausgabe von Windows Powershell: Step by Step gewonnen.

Zelluläre Automaten

Eindimensionale zelluläre Automaten lassen sich relativ einfach beschreiben: Letztlich hat man nur eine Kette von Zellen, die jeweils einen von zwei Zuständen haben: An oder Aus (0 oder 1, lebendig oder tot, wie auch immer man es bezeichnen will). Das kann man natürlich dann auch einfach mit Bits repräsentieren.

Zustände in allen zellulären Automaten ändern sich aufgrund der Nachbarschaft einer Zelle im jeweils vorhergehenden Zustand. Nehmen wir an, man hat eine lebendige Zelle (An, 1) und ihre Nachbarn in beide Richtungen sind tot (Aus, 0). Nehmen wir uns weiterhin eine Tabelle, in der steht, daß für exakt diese Konfiguration der Zelle und ihrer Nachbarn ihr Zustand zu tot wechselt (kann gut passieren, vielleicht starb sie ja aus Vereinsamung). In einer anderen Konfiguration sind die Nachbarn vielleicht nicht tot, sondern lebendig und in diesem Falle lebt die Zelle weiter. In noch einer anderen Konfiguration hat man vielleicht eine tote Zelle und egal, wie ihre Nachbarn aussehen, ändert sie ihren Zustand zu lebendig.

Zustandsübergänge

So eine Tabelle braucht im Grunde nicht viele Dinge: Der Zustand einer Zelle, die Zustände aller Nachbarzellen (nur zwei in diesem Fall) und der Zustand, den die Zelle in der nächsten Generation haben soll. Wir können das auch folgendermaßen darstellen:

In der oberen Zeile haben wir jeweils eine Zelle mit ihren zwei Nachbarn, links und rechts, also immer drei Zellen. Die untere Zeile liefert den jeweiligen Folgezustand für jede Konfiguration. Wie man vielleicht bemerkt hat, gibt es nur acht mögliche verschiedene Konfigurationen. Auf diesen können wir eine einfache Ordnung definieren, indem wir sie jeweils als drei Bits und damit als Zahl auffassen. Diese absteigende Ordnung habe ich hier auch verwendet. Haben wir diese Ordnung erst einmal, besteht diese komplette Regel nur noch aus acht Folgezuständen, die sich ebenfalls als Nullen und Einsen und damit als einzelne acht-bittige Binärzahl auffassen lassen. Diese Numerierung wurde vom britischen Mathematiker Stephen Wolfram erfunden und wird demzufolge auch als „Wolfram-Regel“ bezeichnet.

Die Regel in obigem Bild ist Regel 30.

Darstellung

Nun wissen wir, daß so ein zellulärer Automat als einzelne Zahl beschrieben werden kann und daß er im Laufe der Generationen seinen Zustand ändert. Nur was bringt uns das?

Wir könnten zum Beispiel einen einzelnen Zustand dieses Automaten als eine Reihe von schwarzen und weißen Kästchen darstellen:

und dann könnten wir jede Generation under der jeweils vorhergehenden darstellen:

und siehe da, wir kriegen ein hübsches Bild. Ein wenig chaotisch, aber das ist nun mal bei der Regel so. Es gibt auch welche, die regelmäßigere Muster liefern.

Also war der Sinn und Zweck des Ganzen lediglich, ein merkwürdiges Bild zu erzeugen. Nun also zum spaßigen Teil: So etwas zu programmieren.

Der Quelltext

Es ist nicht gerade sonderlich schwer, das zu programmieren, also fangen wir einfach oben an:

Wir brauchen natürlich ein wenig Kontrolle darüber, wo das Programm aufhört zu berechnen. Ich setze eine einzelne Zelle mit Zustand 1 in die Mitte der ersten Generation (Anfangszustand), daher ist eine ungerade Breite nicht unsinnig, da sich viele Muster gleichmäßig nach links und rechts ausbreiten. Die Höhe hängt in ähnlicher Weise damit zusammen, da die Ergebnisse meist aufhören, sinnvoll zu werden, sobald ein sich ausbreitendes Muster den rechten und linken Rand erreicht.

Wenn die Regel als Parameter für das Programm gegeben wird, brauchen wir nicht danach fragen, lediglich, wenn sie außerhalb des zulässigen Bereiches (0–255) liegt. Gefragt wird so lange bis eine korrekte Regel eingegeben wurde (ja, hier kann man noch hilfreiche Hinweise geben, aber da hatte ich keine Lust zu).

Ich habe hier ein kleines Unterprogramm geschrieben, welches die Regel in ihre acht Einzelkonfigu­rationen zerlegt:

Hiernach haben wir acht Variablen, wolfram_x mit x zwischen 0 und 7, die jeweils die Folgezustände für jede Konfiguration beinhalten.

Danach initialisieren wir den Bereich, wo die Zustände jeder Zelle für jede Generation gespeichert werden:

Im Prinzip wird nur jede Zelle mit 0 initialisiert und eine einzelne 1 in der Mitte der ersten Generation hinzugefügt.

Wir haben allerdings noch ein kleines Problem mit diesem Ansatz: Wenn folgende Generationen berechnet werden, braucht jede Zelle eine Nachbarschaft. Nur wie sieht diese Nachbarschaft für die jeweils ersten und letzten Zellen einer Generation aus? Anfangs habe ich einfach nur eine weitere Null links und rechts an jede Zeile gehängt. Das funktioniert gut für die meisten Regeln und wir belassen es erstmal dabei. Wie man das nun in obigem Quelltext umsetzt, lasse ich als Übung für den Leser.

Was auch praktisch wäre, ist ein Unterprogramm, welches das komplette Bild ausgibt:

Es sind tatsächlich sogar zwei Unterprogramme, diese werden später noch praktisch.

Was natürlich immer noch fehlt, ist die Berechnung der Folgezustände. Also tun wir dies mal:

Nichts außeregwöhnliches hier, wir delegieren lediglich die Berechnung einer einzelnen Zelle an ein weiteres Unterprogramm. Wie vielleicht auffällt, zeige ich die Zeile sofort nachdem sie berechnet worden ist, was das Zuschauen während das Programm läuft, etwas weniger langweilig macht, da wir dann alle paar Sekunden eine neue Zeile sehen (ja, das Ganze ist so langsam).

Hier wird der neue Zustand einer einzelnen Zelle berechnet unter Zuhilfenahme eines weiteren Unterprogramms, welches den spezifischen Fall aus der Tabelle sucht. Wir machen uns hier die Tatsache zunutze, daß die Zelle und ihre Nachbarn im Grunde eine drei-Bit-Zahl ist und die Tabelle auch zugreifbar ist, indem wir diese drei Bit in eine Dezimalzahl zwischen 0 und 7 überführen. Der Code dafür ist leider ein wenig unschön, da viel Escaping nötig ist (die Klammern habe ich jedoch lediglich aus Vorsicht so behandelt, da Klammern gern etwas kaputt machen, besonders, wenn man anfängt, Strukturen zu schachteln).

Aber das war eigentlich schon alles. Führt man diese Batchdatei nun ohne Argumente aus, kommt die folgende Abfrage:

geben wir hier nun sagen wir 54 ein, kommt das folgende Bild zustande:

Der eigentliche Quelltext der Batchdatei ist ein wenig länger, da ich inzwischen auch eine Option anbiete, was mit dem linken und rechten Rand geschehen soll (alles null, alles eins, zylinderförmig und kopieren, letzteres ist nun die Standardeinste­llung, da zum Beispiel Regeln wie 169 sehr merkwürdig aussehen, wenn sie mit Null-Kanten berechnet werden).

Momentan arbeite ich noch an SVG-Export aus dieser Batch-Datei (der Grund, warum ich die eigentlich geschrieben habe) und hoffe, inzwischen alle größeren Bugs gefunden zu haben. Die erste funktionierende Version hatte übrigens nur 54 Zeilen. Ich denke, hätte ich Java benutzt (was hier gerade die einzige andere Alternative war), hätte ich deutlich mehr gebraucht.

UPDATE (2008–12–26 16:21): SVG-Export ist fertig und werkelt nun auch wie er soll. Momentan lasse ich den Terminal Server in der Uni an allen 256 Automaten gleichzeitig rechnen:

Kürzlich stellte ich fest, daß die Suchvorschläge von Google, die in der Suchleiste von Internet Explorer oder Firefox erscheinen, den Google calculator mit benutzen:

Also habe ich Fiddler angeworfen, um zu schauen, wo die Anfragen für solche Vorschläge hingehen und fand folgende URL (für die Anfrage 1+1):

http://sugges­tqueries.google­.com/complete/se­arch?output=fi­refox&client=I­E8&hl=en&qu=1%2B1

Die Antwort auf diese Anfrage war ein wenig JSON:

Ich habe das hier mal ein wenig aufgehübscht, eigentlich kommt es in einer langen Zeile. Wie man sehen kann, sind das im Wesentlichen zwei geschachtelte Arrays. Das erste Element des äußeren ist die Suchanfrage und das innere enthält die Vorschläge. Wenn die Vorschläge ein Ergebnis einer Berechnung durch Google Calculator enthalten, dann ist dies der erste Vorschlag, der zurückkommt.

Das wissend habe ich ein kleines Programm zusammengehackt, was seine Argumente an Google schickt und den ersten Vorschlag ausgibt (was hoffentlich ein Rechenergebnis is­t):

Am liebsten mag ich die Möglichkeit zur Einheitenkonver­tierung. Leider funktioniert nicht alles. An Naturkonstanten (Lichtgeschwin­digkeit, Elementarladung, …) und sonstige hübsche Zahlen (e, π, …) kommt man leider nicht direkt heran. Bei Naturkonstanten schafft man es manchmal mit einer expliziten Konvertierung in deren Einheit (c in kilometers per second), aber das wäre noch ein Punkt, wo man verbessern könnte.

Das Programm wurde in C# 2.0 geschrieben und benutzt LitJSON zum Parsen von JSON. Es läuft auch auf Mono, ich habe dort allerdings noch nicht versucht, es zu kompilieren. Aber da alles .NET 2.0 ist, sollte das eigentlich problemlos funktionieren.

Das Programm sowie der Quelltext hängen an.

UPDATE (2008–10–26 00:34): Ich habe Quelltext und ausführbare Datei wie folgt aktualisiert:

1. Die Ausgabe erfolgt nun in Unicode (endlich weiß ich, wie das geht)
2. Falls kein Rechenergebnis vorliegt (also das erste Ergebnis kein = am Anfang hat), werden alle Resultate zurückgeliefert. Das dient hauptsächlich der Nutzung der Suchvorschläge, wie sie vorgesehen waren, aber es hat einige spaßige Seiten:

Hach ja, Rekursion, das Lieblingstierchen jedes Programmierers. Sicher ist sowas auch in Batchdateien möglich (Ich versuche übrigens immer noch Turingvollständig­keit nachzuweisen :-)).

Der erste zaghafte Test wäre erstmal eine unendliche Rekursion:

Und siehe da, sie funktioniert:

Genau das, was wir haben wollten. Etwas sinnvolleres als einen Stacküberlauf hatten wir uns ohnehin nicht erhofft. Also offensichtlich kann cmd Rekursion.

Dann sollten wir das auch mal mit einem zumindest ansatzweise praxisbezogenem Problem testen: Fakultäten. Ungeachtet dessen, daß man die besser iterativ berechnet. Wir wollen aber nur sicherstellen, daß die Rekursion vernünftig funktioniert:

Wir brauchen hier leider eine temporäre Variable, da cmd keine Berechnungen ohne SET /A erlaubt, aber ansonsten sieht es in etwa so aus, wie es sollte. Der Rekursionsabbruch wurde am Anfang des Unterprogramms durch ein IF abgefangen, leider gibt es keine funktionalen Nettigkeiten wie verschiedene Funktionsdefi­nitionen hier.

Und funktioniert das nun auch? Aber sicher:

Mein Taschenrechner sagt mir sogar, daß die Werte richtig sind. 12! ist leider die höchste Fakultät, die man damit berechnen kann, da wir auf 32-bittige vorzeichenbehaftete Ganzzahlen beschränkt sind. Ein kleiner Fehler ist noch vorhanden, wenn man negative Zahlen als Argument angibt (wieder eine unendliche Rekursion). Das ist allerdings in der angehängten Version behoben, ebenso bekommt man in selbiger eine hilfreiche Nachricht, wenn man die Batch ohne Parameter aufruft.

Und nur so nebenbei, eine nette Variante, Fakultäten zu berechnen, indem wir einfach den eingebauten „Taschenrechner“ von cmd benutzen:

Wir basteln uns hier einfach die komplette Berechnung in einer Zeile zusammen und lassen die dann von SET /A auswerten. Nichts großartig aufregendes aber wahrscheinlich schneller als Rekursion.

@echo off
set X=0
echo set /a X+=1 >>%0
echo echo %%X%%>>%0

... es funktioniert ... jedes Mal, wenn man diese Batch-Datei ausführt, wächst die Liste der ausgegebenen Zahlen um eins :-)

Der interessante Teil hieran ist, daß die Zeilen, die erst zur Laufzeit des Skriptes hinzugefügt werden, noch im gleichen Durchlauf der Batch ausgeführt werden.

Ich mochte es noch nie, wie mein Code hier bislang aussah: Einrückungen waren unmöglich, alles unbunt, … also suchte ich mal nach einem Drupal-Plugin, was Syntax-Highlighting übernehmen kann. Gefunden habe ich genau eins: GeSHi filter.

Ich bin ein großer Fan von RSS, da es mir erlaubt, einfach auf die Schnelle nachzuschauen, ob diverse Seiten, die ich sonst alle einzeln abklappern müßte, neue Beiträge haben. Gerade mit einigen unregelmäßig aktualisierten Webcomics ist das recht praktisch. Hier sei noch angemerkt, daß ich es im Grunde gern hab, wenn die Comicstrips selbst auch im RSS von Webcomics auftauchen, statt nur ein Link zu der entsprechenden Seite; würde das Lesen wesentlich angenehmer machen (und dürfte den Traffic auch reduzieren).

Vor ein paar Stunden habe ich zwei reichlich widerliche Skripen zusammgengehackt, die einen Webcomic für einen Mitstudenten und einen für mich abholen und als RSS aufbereiten. Momentan scheint es zu funktionieren, mal abwarten, ob Updates irgendwelche unerwarteten Probleme zutage fördern.

Wer mag, kann die Skripten ja für sich selbst anpassen.

UPDATE (2008–01–31 10:20): Code für bash.org fehlte. Ist nun behoben.

UPDATE (2008–11–06 07:42): Code für ruthe.de angepaßt, da die Seite sich geändert hatte.

UPDATE (2008–02–27 14:16): Beim bash.org-Feed kam ungültiges RSS zustande, wenn Nicht-ASCII-Zeichen im Text standen. Das sollte nun behoben seni.

UPDATE (2010–04–14 12:40): Code für ruthe.de angepaßt, da die Seite sich schon wieder geändert hatte.