Inhaltsverzeichnis

1. Einleitung
   1. Vorwort
   2. Syntax und Terminologie
2. Zellulare Automaten
   1. Was ist ein zellularer Automat?
      1. Elementarzustände der Zellen
      2. Nachbarschaft
      3. Zustandsübergangsfunktion
   2. Beispiele für zellulare Automaten
      1. Game Of Life
      2. Langton's Ant
      3. Stephen Wolframs Universum
      4. Greenberg-Hastings Automat
3. Softwareimplementation celmac 2.0
   1. Begrifflichkeiten in celmac
      1. Das CAP-Protokoll
      2. ABC ( a bit C )
         1. Besonderheiten
         2. Variablen
         3. Zuweisungen
         4. Kontrollstrukturen
         5. Schleifen
         6. Komplexe Anweisungen
      3. CAL ( CA Language )
         1. Variablen
         2. Kommentare
         3. Der CAL-Befehl
      4. PBML ( Portable Bitmap Like )
         1. Das PBML-Format
      5. SPG ( Statistics Per Generation )
         1. Das SPG-Format
   2. Bedienung von celmac
      1. Der Generator und der Player
      2. Der Generator
         1. Die Menüführung
         2. Programmierung mit ABC
      3. Der Player
         1. CAs öffnen
         2. Die Unterfenster
         3. Das Hauptmenü
            1. Der Menüpunkt CA
            2. Assistenten
               1. Der Simulationsassistent
               2. Der Iterationsassitent
               3. Der Parameterassistent
               4. Der Statistikassistent
               5. Der Optimierungsassistent
      4. Statistische Auswertung
         1. Kombinationen
         2. Das Auswertungsfenster
   3. Umsetzungen auf Quelltextebene
      1. Die Klasse TGlobal
         1. Wichtige Elemente
            1. Das Element MyDir
            2. Andere Elemente
         2. Wichtige Elementfunktionen
         3. Die Unterklasse TSettings
            1. Die Datei settings.dat
      2. Aufgabenfeld Generator
         1. Übersetzung von ABC in CAL
            1. Die Klasse TBlock
            2. Die Funktion Abc2Cal(..)
      3. Aufgabenfeld Player
         1. Handling von CAL
            1. Lösungsidee
            2. Die Klasse TArith
            3. Die Klasse TArithList
            4. Ablegung von Variablen
               1. Die Klasse TByteList
                  1. Schnittstellen
                  2. Interne Funktionsweise
               2. Die Klasse TVarList
               3. Die Klasse TCellDB
               4. Die Funktion TArithList::InitOp(..)
            5. Die Klasse TPtrList
            6. Das Laden einer CA-Datei
               1. Die Konstruktoren der Klasse TMDIChild
               2. Die Klasse TWorld
               3. Die Klasse TCA
               4. Die Klasse TInterpreter
                  1. Die Funktion TInterpreter::Prepare()
                  2. Zwei Optimierungsmethoden
                     1. Echtzeitinterpretierung von CAL
                     2. Zustandsübergangstabelle
                     3. Die Funktion SetCalcMode(..)
                     4. Die Funktion InitCombi(..)
         2. Iteration eines CAs
            1. Die Funktion TChildWin::Iteration(..)
      4. Aufgabenfeld Statistik
         1. Die Klasse TStatistics
         2. Die Klasse TStatEntry
         3. Der Statistikassistent
            1. Die Funktion TStatForm::InitValues()
         4. Statistische Auswertung
            1. Die Klasse TGraphBar
               1. Die Funktion TGraphBar::ActDisp(..)
   4. Anwendung der statistischen Möglichkeiten von celmac 2.0
      1. Grundlegendes
      2. Greenberg-Hastings Automat
      3. Stephen Wolframs Universum
      4. Game Of Life
         1. Regelwelt 23/3
            1. Ergebnisse
         2. Regelwelt 125/125
            1. Ergebnisse
      5. Fazit
4. Anhang
   1. Changelog
   2. Interne Darstellung der ABC-Operatoren
   3. Zeiger in C++
      1. Adressen
      2. Operatoren
      3. Zeigerarithmetik
5. Glossar
6. Quellen

1. Einleitung

1.1 Vorwort

Diese Arbeit beschäftigt sich mit dem Programm celmac 2.0, ein Simulationsprogramm für zellularen Automaten (engl. Cellular Automaton, abgekürzt CA). Meine Ambitionen, dieses Programm zu schreiben, hatten verschiedene Ursachen. Zum Einem beschäftige ich mich seit längerer Zeit mit CAs, celmac 1.0 entstand bereits Ende 2004. Dieses Programm konnte jedoch nur die CAs Game Of Life und Langton's Ant simulieren, so entstand bei mir der Wunsch nach einem Programm, das alle möglichen zellularen Automaten simulieren kann. Zum Anderen wollte ich der Frage nachgehen, ob sich die von zellularen Automaten erzeugten Räume als Zufallszahlengeneratoren eignen.

Der Quelltext von celmac 2.0 (erhältlich unter www.xilef-software.de) ist vor allem in der Speicherverwaltung durchzogen mit C-Syntax, so werden in allen Klassen (außer in TPtrList, dort gab es einen unauffindbaren Bug, der mich dazu zwang, C++ Syntax (new und delete) zu benutzen ) zur Speicherreservierung die C-Funktionen malloc() und realloc() und zur Speicherfreigabe die Funktion free() benutzt. Dies liegt daran, dass das Thema der vorliegende Arbeit auch den Umgang mit Pointern in C/C++ mit einschließt und die praktische Anwendung der Zeigerarithmetik besser mit C-Syntax zur Geltung kommt. Dazu kommt meine persönliche, aber nur irrational zu begründende Affinität zur C-Syntax.

Aus gleichem Grund bediente ich mich auch relativ wenig der Standardbibliothek von C++, auch hier wird die eigentliche Zeigerarithmetik hinter den Schnittstellen der Klassen versteckt.

Über Resonanz in jeglicher Richtung würde ich mich sehr freuen. Zu kontaktieren bin ich unter folgender E-Mail Adresse.

Please note a short english version is available as well at following URI.

1.2 Syntax und Terminologie

Wenden wir uns den in dieser Arbeit verwendeten typographischen Besonderheiten zu. Sie sollen Ihr Verständnis erleichtern, indem wir ihnen nun in der folgenden Tabelle eine scharf umgrenzte Bedeutung zuweisen.

2. Zellulare Automaten

Dieses Kapitel gibt einen kurzen Einstieg in das Thema zellulare Automaten. Dies ist jedoch nicht Thema dieser Arbeit und wurde so auch nur kurz und mit wenig bearbeitet. Dieses Kapitel stützt sich auf folgende Quellen.

• Technische Universität Darmstadt: Studienarbeit zum dem Thema Effiziente Implementierung zellularer Automaten in Software vorgelegt von Patrick Röder
• http://www.fim.uni-linz.ac.at/lva/rus/CellulareAutomaten/

2.1 Was ist ein zellularer Automat?

Ein CA wird durch folgende Punkte erschöpfend definiert.

• der zellulare Raum
• eine endliche Menge von Elementarzuständen der Zellen
• die Nachbarschaft der Zellen
• die Zustandsübergangsfunktion

2.1.1 Zellularer Raum

Das Verständnis für CAs wird erleichtert, wenn man mit der Erklärung des für den CA notwendigen zellularen Raums (ZR) anfängt. Der ZR ist ein n-dimensionaler Raum, der in einzelne diskrete Zellen aufgeteilt ist. Diese Zellen haben meist die Form eines Hyperwürfels. celmac 2.0 unterstützt jedoch nur zweidimensionale ZRs, so haben die Zellen immer die Form eines Quadrates. Auch andere geometrische Formen sind denkbar, in dem Vorgängerprogramm celmac 1.0 konnte man zum Beispiel zwischen Quadraten, Achtecken, Bienenwaben und Dreiecken wählen. Dies ist iin celmac 2.0 aufgrund der flexibleren Möglichkeiten zur Definition der Nachbarschaft nicht mehr nötig. In der Theorie können ZRs unendliche Ausmaße haben, aufgrund der Beschränktheit des Arbeitsspeichers des Computers sind in celmac 2.0 jedoch nur torusförmige ZRs möglich, das heißt der linke und rechte Feldrand und der obere und untere Feldrand sind jeweils miteinander verbunden.

2.1.2 Elementarzustände der Zellen

Die einzelnen Zellen des ZRs können endlich viele Zustände annehmen. Die einzelnen Zustände werden üblicherweise mit ganzen Zahlen numeriert, sodass sich für einen ZA, dessen Zellen z Zustände annehmen kann, die Zustandsmenge {0;1;...; z-1} ergibt. In celmac 2.0 können Zellen auch "negative" Zustände annehmen. Der im Generator festgelegte Wert bezeichnet den höchstmöglichen Betrag des Zustandswertes. Sollte also dieser Wert 1 betragen lautet die Zustandsmenge {-1;0;1}. Mehr über das Handling der Zustandsmengen finden Sie im Kapitel Programmierung mit ABC.

2.1.3 Nachbarschaft

In einem CA kann man jede einzelne Zelle als einen Automat ansehen. Ein Automat hat per Definition Eingabevariablen, die verarbeitet werden und auf Grundlage derer die Ausgabevariablen bestimmt werden. In einem CA stellen die Zustände der Nachbarn einer Zelle die Eingabevariablen und der Zustand der Zelle selbst die Ausgabevariable dar. Es ist also ein zentraler Bestandteil des CAs, wie man die Nachbarschaft einer Zelle definiert.

Generell gilt, dass man die Nachbarn einer Zelle ausschließlich über relative Bezüge bzw. Vektoren ausdrücken kann. Die relative Lage der Nachbarn ist bei jeder Zelle gleich. So wird deutlich, dass die Menge der benachbarten Zellen eine endliche Teilmenge des ZRs darstellt. Auch wenn der Nachbarschaftsbegriff komplexere Nachbarschaftsbeziehungen zulässt, unterscheidet man im zweidimensionale ZR meist zwischen der Von-Neumann-Nachbarschaft und der Moore-Nachbarschaft.

Von-Neumann-Nachbarschaft: Es werden nur genau angrenzende Zellen als Nachbarn angesehen.

Moore-Nachbarschaft: Auch die Zellen, die diagonal an der Zelle liegen, werden in der Nachbarschaft mit einbezogen.

Beide Nachbarschaftsmodelle lassen in ihrer allgemeinen Form auch die Zelle selbst als Nachbar zu.

2.1.4 Zustandsübergangsfunktion

Wir haben nun den ZR, die Zustandsmenge und die Nachbarschaft definiert, jedoch handelt sich es bei einem CA um ein sich mit der Zeit entwickelndes Konstrukt.Ein CA kann iteriert werden, indem man auf jede einzelne Zelle des ZRs eine bestimmte Funktion, die sogenannte Zustandsübergangsfunktion, anwendet.

Diese Funktion macht aus jeder einzelnen Zelle des CAs einen Automaten, indem sie die Eingabevariablen (die benachbarten Zellen) zum Zeitpunkt t benutzt und so den Zustand der Zelle zum Zeitpunkt t+1 berechnet. Diese Funktion kann in celmac 2.0 in ABC oder CAL geschrieben werden. Mehr Informationen zum Programmieren finden Sie im Kapitel Programmierung mit ABC.

2.2 Beispiele für zellulare Automaten

Alle für die hier vorgestellten CAs (in der Beta-Version von celmac 2.0 ausgenommen Langton's Ant) bietet celmac 2.0 einen Assistenten an, die Ihnen helfen sollen, Zustandsübergangsfunktionen für diese CAs zu schreiben. Sie gelangen zu diesen Assistenten, wenn Sie die entsprechende Option auswählen, nachdem Sie im Generator auf Neu... geklickt haben.

2.2.1 Game Of Life

Game Of Life ist wohl der beliebteste der hier vorgestellten CAs, so wird in vielen Programmierbüchern das Programmieren eines einfachen Simulators dieses CAs als Übung für Einsteiger angeboten.Es existiert ein ausführlicher Wikipediaartikel zu diesem CA, hier ist also nur eine grobe Übersicht zu finden.

Dieser binäre CA benutzt die Moore-Nachbarschaft zuzüglich der Zelle selbst. Eine Zelle mit Zustand 0 wird als tot, eine Zelle mit Zustand 1 als lebendig angesehen. Die Zustandsübergangsfunktion zählt nun die Anzahl der benachbarten lebenden Zellen (ausgenommen der Zelle selbst) und entscheidet nun über den Zustand der Zelle. Diese Reaktion können Sie in celmac im Assistenten für Game Of Life mithilfe eines Schalterfeldes definieren.

Die bekannteste Spielweise (23/3) geht davon aus, dass bei drei lebenden Nachbarn eine Zelle geboren wird (Mutter, Vater und Hebamme), bei zwei lebenden Nachbarn sich der Zustand der Zelle nicht verändert und bei einer anderen Anzahl lebender Nachbarn die Zelle entweder an Vereinsamung oder Überbevölkerung stirbt. Ein zu dieser Spielweise passendes Schalterfeld erzeugen Sie im Assistenten für Game Of Life durch einen Klick auf den Button Conway - Welt erzeugen (John Horton Conway, brit. Mathematiker, entwarf Game Of Life in dieser Spielweise).

2.2.2 Langton's Ant

Langton's Ant ist ein einfacher, aber schwer in celmac 2.0 umzusetzender zweidimensionaler zellularer Automat. Auf einer Zelle sitzt eine Ameise und schaut in eine bestimmte Richtung (oben, links, rechts, unten). Bei einer Iteration entscheidet der Zustand der Zelle unter der Ameise ihr Verhalten. Sollte der Zustand 0 sein wird er auf 1 gesetzt und die Ameise dreht sich um 90° nach links, andernfalls wird der Zustand der Zelle unter der Ameise von 1 auf 0 herabgesetzt und die Ameise dreht sich um 90° nach rechts. Anschließend krabbelt die Ameise ein Feld in ihre neue Richtung.

2.2.3 Stephen Wolframs Universum

Stephen Wolfram veröffentlichte 1983 eine Reihe von grundlegenden Arbeiten zu Zellularautomaten, in der er auch ein eindimensionales Universum mit einer Raum- und einer Zeit-Dimension vorstellt, das durch einen binären zellularen Automaten simuliert werden kann. Die Raumdimension ist in celmac waagerecht, während sich die Zeitdimension nach unten ausstreckt. Beim Urknall (in der obersten Zeile) wird der Zustand der Zellen mit fünfzigprozentiger Wahrscheinlichkeit auf 1 gesetzt. Nachbarschaft umfasst in der ursprünglichen Form die linken zwei Nachbarn, die Zelle selbst und die rechten zwei Nachbarn. Wenn zwei oder vier Nachbarn den Zustand 1 besitzen ist die Zelle im nächsten Zeitintervall (also die Zelle unterhalb) in der nächsten Generation auf 1 gesetzt, andererseits bleibt ihr Zustand 0.

Der Assistent für Stephen Wolframs Raum-Zeit Universum in celmac 2.0 erlaubt allgemeinere Nachbarschaftsdefinitionen und Zustandsübergangsfunktionen als es in der ursprünglichen Form des zellularen Automaten vorgesehen ist.

2.2.4 Greenberg-Hastings Automat

Der Greenberg-Hastings Automat ist als Epedemiemodell zu verstehen. Die Zellen können einen von folgenden Zuständen annehmen.

• a erregte Zustände
• g refraktäre Zustände
• Ruhezustand

Die Anzahl der möglichen Zustände beträgt demnach a+g+1. Als Nachbarschaftsdefinition ist die Von-Neumann-Nachbarschaft (mit vier Nachbarn zuzüglich der Zelle selbst) oder die Moore-Nachbarschaft (mit acht Nachbarn zuzüglich der Zelle selbst) möglich. Im Assistenten für Greenberg-Hastings Automaten in celmac können Sie diese Unterscheidung im Gruppenfeld Nachbarschaft treffen.
Hat nun eine Zelle im Ruhezustand mindestens s erregte Nachbarn wird sie selbst erregt und durchläuft zuerst alle erregten und dann alle refraktäre Zustände bis sie wieder in den Ruhezustand verfällt. Eine ruhende Zelle mit weniger als s erregten Nachbarn bleibt im Ruhestadium.

Der Versuch, a und g als ABC-Parameter zu behandeln, wird scheitern, da die in celmac 2.0 zur Laufzeit unveränderbare Zustandsmenge von a und g abhängen. s kann man im Assistenten für Greenberg-Hastings Automaten durch das Deaktivieren des Häckchens neben der entsprechenden Beschriftung als ABC-Variable deklarieren lassen.

3. Softwareimplementation celmac 2.0

3.1 Begrifflichkeiten in celmac

3.1.1 CAP

CAP steht für CA-Protocol. Dieses Protokoll nutzen sämtliche Dateien, die von celmac erzeugt werden. Da Sie bei normaler Bedienung von celmac nicht direkt mit CAP in Berührung kommen, dient dieses Kapitel nur Hintergrundinformationen.

CAP erinnert entfernt an Protokolltypen wie HTTP oder FTP. Sie bestehen alle aus einem Header und einem Body. Diese beiden Teile werden mit einem doppelten Zeilenumbruch getrennt. Im Header kann man verschiedene Informationen mitgeben, von denen einige Pflicht, andere optional sind. Die Syntax hier lautet wie bei HTTP oder FTP auch folgendermaßen.

Ein Zeilenumbruch schließt eine Information ab. CAP ist Case-Sensitive, also muss Groß- und Kleinschreibung beachtet werden. Ein Beispiel.

Folgende Werte sind möglich:

Hier finden Sie ein Beispiel für ein vollständiges und typisches CAP-Protokoll.

3.1.2 ABC

Da celmac möglichst allgemeine zellulare Automaten simulieren können soll, muss auch die Definition der Zustandsübergangsfunktion möglichst flexibel sein. Dies kann in celmac durch die Sprachen ABC ( a bit C ) und CAL geschehen. Wir wenden uns zunächst ABC zu.

ABC ist eine sehr schlanke Sprache, deren Syntax an C angelehnt ist. Jedoch, wie am Namen schon abzulesen, ist C sehr viel mächtiger als ABC weil auch die Anforderung sehr viel höher sind. Mit ABC können wir eine Zustandsübergangsfunktion für zellulare Automaten schreiben, es ist nicht dafür ausgelegt ganze Programme zu schreiben. Mehr zur praktischen Umsetzung von Schreiben einer Zustandsübergangsfunktion finden Sie in dem Kapitel Programmierung mit ABC.

Besonderheiten

ABC ist eine sehr primitive Programmiersprache, die über keinerlei objektorientierten Ansatz verfügt. Es existieren weiterhin keine Strukturen, Funktionen oder Prozeduren. Es gibt nur einen Datentyp, den 1-Byte Integer. Der Umgang mit komplexen Anweisungen ist in ABC gewöhnungsbedürftig. ABC besteht aus nur vier Sprachelementen.

1. Deklarationen von Variablen
2. Zuweisungen
3. Kontrollstrukturen
4. Schleifen

Bei drei der vier Sprachelemente sind Ausdrücke ein zentraler Bestandteile, darum werden wir uns zunächst mit ihnen beschäftigen und uns dann den anderen Punkten zuwenden.

Zusätzlich ist zu sagen, dass es in ABC ausnahmslos keinen syntaxrelevanten Whitespace gibt. Dies ist ein wichtiger Unterschied zu vielen anderen Programmiersprachen. Die Auswirkungen dessen werden wir nachfolgend erläutern.

Ausdrücke

Den Ausdruck kann man als elementaren Grundbaustein von ABC bezeichnen. Sollte man ABC mit einem Satz charakterisieren wollen, könnte man sagen, dass es sich um eine ausdrucksorientierte Sprache handelt. Noch deutlicher wird dieser Aspekt, wenn wir uns mit CAL beschäftigen, in die ABC letztlich übersetzt wird. CAL arbeitet ausschließlich mit Ausdrücken.

Ein Ausdruck ist allgemein gesagt eine Aneinanderreihung von Zeichen unter Beachtung einer vorgegebenen Syntax. In ABC darf ein Ausdruck nur aus Integerkonstanten, Variablennamen und Operatoren bestehen. Das wichtigste Charakteristik um eines Ausdrucks ist, dass er immer einen Wert besitzt.

Ausdrücke dienen in ABC entweder Zuweisungen an Variablen oder Bedingungen von Kontrollstrukturen oder Schleifen.

Variablen

In ABC gibt es, angepasst an die Anforderung an diese Sprache, nur einen Datentypen. Es können nur 1 Byte Integer Variablen deklariert werden. 1 Byte entsprechen 8 Bit von denen das höchstwertigste Bit als Vorzeichenbit benutzt wird. Der Wert -127 ist für TARITH_IDENTIFIER als reservierter Wert für die Umsetzung auf Quelltextebene nötig. Integer in ABC können also lediglich den Zahlenbereich von -126 bis +127 abdecken, was aber für den Einsatzbereich von ABC ausreichend ist.

Die Namen von Variablen müssen in ABC den üblichen Konventionen für Namensvergaben in Programmiersprachen wie C folgen.

• Ein Variablenname darf aus beliebigen Buchstaben, Ziffern und Unterstrichen bestehen.
• ABC ist Case-Sensitive, das heißt zwischen Groß- und Kleinschreibung wird unterschieden.
• Die für CAL reservierte Variable LC darf nicht verwendet werden.
• Variablennamen dürfen keine Leerzeichen enthalten.

Die Deklaration von Variablen verläuft in ABC aus Gründen, die nachfolgend erklärt werden, anders als in C.

Da es in ABC keinen syntaxrelevanten Whitespace gibt würde beim Parsen dieses Quelltextes als ABC-Quelltext dieser Befehl entstehen.

Dieser Befehl ist in ABC syntaktisch falsch. Stattdessen verfügt ABC ähnlich wie Perl über eine eigene Funktion (die einzige Funktion die es in ABC gibt) namens mk().

So wird die in ABC überflüssige Angabe des Datentypen umgangen und es ist kein syntaxrelevanter Whitespace von Nöten. Leider ist es bei dieser Syntax nicht möglich einen vorgegebenen Initalisierungswert anzugeben, die Variablen werden standardmäßig mit Null initialisiert. Folglich ist in ABC anders als in C / C++ kein undefiniertes Verhalten möglich.

Die Deklaration durch mk() ist nicht zwingend notwendig. Sollte eine Variable nicht durch mk() deklariert worden sein, wird sie es, wiederum ähnlich wie in Perl, bei ihrer ersten Verwendung. Zur besseren Übersicht ist jedoch die Deklaration durch mk() empfehlenswerter.

Zuweisungen

Bei einer Zuweisung weißt man einer Variable einen Wert zu. Dieser Wert ist immer ein Wert eines Ausdrucks. Die Syntax ist hier mit der von C identisch, jedoch ist die Umsetzung anders. Das Zeichen = wird in ABC nicht als Operator gesehen, also ist eine Zuweisung nie ein Ausdruck. Zuweisungen besitzen in ABC keinen Wert, also kann man sie auch nicht an einer Stelle einsetzen wo ein Wert erwartet wird. Folgendes Beispiel sollte diesen Unterschied verdeutlichen.

Kontrollstrukturen

In ABC steht jediglich die if-Abfrage, optional gekoppelt mit einem else-Zweig, als Kontrollstruktur zur Verfügung. Die Syntax erinnert sehr an C, es sei hier jedoch auf eine Eigenart von ABC hingewiesen, die auf der Nichtexistenz von syntaxrelevanten Whitespace begründet sind. Es wird ein Codebeispiel vorgestellt, das in ABC im Gegensatz zu C unerwartete Auswirkung hat.

Wird in ABC wie folgt geparst.

Verhindern kann man diesen Trugschluß von ABC durch Klammersetzung. Mehr über Klammersetzung bei komplexen Anweisungen finden Sie weiter hinten im Kapitel.

Schleifen

Schleifen dienen dazu, bestimmten Quelltext sooft zu wiederholen, bis ein bestimmter Ausdruck wahr wird. Es gibt in ABC zwei unterschiedliche Schleifen.

while-Schleife

Bei einer while-Schleife wird der Ausdruck eingangs geprüft. Der Quelltext wird ausgeführt solange der Ausdruck wahr ist.

repeat-until-Schleife

Hier wird der Ausdruck erst nach der Ausführung der Zuweisungen geprüft. Der Quelltext wird ausgeführt bis der Ausdruck wahr ist.

Komplexe Anweisungen

Dieses Kapitel beschäftigt sich mit den Problemen, die der Übersetzer von celmac für ABC in CAL mit C-gewohntem Weglassen von { und } in Kombination mit verschachtelten Anweisungen hat. Oben haben wir uns ein Beispiel angeschaut wo es auch ohne Verschachtelung zu Problemen kommen kann. Generell gilt, dass man im Zweifelsfall immer geschweifte Klammern setzen sollte, zu viele Klammern schaden nicht. In einigen Fällen erhöht es jedoch die Performance des erzeugten CAL-Quelltextes, die geschweiften Klammern wegzulassen. Hier sind folgende Regeln zu beachten.

1. Nach else muss immer eine öffnende geschweifte Klammer.
2. In einem Anweisungsblock, bei dem die Klammern weggelassen wurden, darf kein weiterer Anweisungsblock stehen. Folgender Quelltext ist ungültig
   if(a==5) while(a<20)a=a+1; if(a==5) while(a<20){ a=a+1; }
   Ungültiges ABC.
   Diese Einschränkung kommt daher, dass der ABC->CAL Übersetzer ein Anweisungsblock ohne geschweifte Klammern nicht als Anweisungsblock ansieht um performanteres CAL erzeugen zu können (Mehr dazu finden Sie im Kapitel Umsetzung auf Quelltextebene unter Übersetzung von ABC in CAL). Wie folgt können wir das Problem umgehen.
   if(a==5){ while(a<20)a=a+1; }
   Gültiges ABC.

3.1.3 CAL

CAL (CA-Language) ist eine sehr einfache Sprache, die jedoch für den Simulator von celmac verständlich ist und aus der er logische Hierarchien von Ausdrücken und eine Anweisungsliste im Arbeitsspeicher des Computers erstellen kann. Die Beziehung zwischen ABC, CAL und celmac ist vergleichbar mit der zwischen C, Assembler und Computer. C wird zunächst in Assembler übersetzt ehe es kompiliert werden kann. Sie müssen sich nicht mit CAL beschäftigen, um celmac benutzen zu können. Dieses Kapitel dient nur für Hintergundinformationen und Aufdeckung von Möglichkeiten, das aus ABC erzeugte CAL performanter und flexibler zu machen.

Variablen

CAL-Variablen stimmen bezüglich ihrer Wertemenge mit ABC-Variablen überein. Es gibt jedoch eine reservierte CAL-Variable namens LC, die nicht neu deklariert werden darf (auch nicht in ABC, da die Namen von Variablen in ABC und CAL gleich sind). Diese Variable hat den Wert 1 oder 0, je nachdem, ob der letzte Befehl ausgeführt wurde oder nicht. Gebraucht wird sie für performantere Umsetzung von ABC typische if-else-Strukturen in CAL. Wir werden später auf diese Variable bei der Übersetzung von ABC in CAL nochmals zurückkommen.

Kommentare

Bei der Auswertung des CAL-Quelltextes wird jede Zeile übersprungen, in der das erste Zeichen ein Doppelkreuz (#) ist. Auf diese Weise ist eine einfache Kommentarfunktion gewährleistet.

Der CAL-Befehl

CAL ist anders als ABC zeilenorientiert. Jede Zeile ist ein Befehl. Ein Befehl besteht aus mindestens zwei Gliedern, jedes Glied ist mit einem Leerzeichen von dem Nächsten getrennt. Whitespace ist nicht erlaubt. Einen gültigen CAL Befehl finden wir zum Beispiel hier.

Die ersten beiden Buchstaben (das erste Glied) geben an, wie das Argument verwendet werden soll. Das zweite Glied des CAL-Befehls ist eine Bedingung (ein ABC-Ausdruck) und gibt an, ob der Befehl ausgeführt werden soll. Das dritte Glied benötigen manche CAL-Befehle als Argument. Hier finden Sie eine Übersicht über alle CAL-Befehle und eine kurze Beschreibung, wie das Argument genutzt wird.

3.1.4 PBML

PBML (Portable Bitmap Like) ist das Format, das in celmac zum Speichern von Feldern oder Feldausschnitten genutzt wird. Es erinnert an das etwas weiter verbreitete Format PBM (Portable Bitmap - siehe bwinf 2005). In celmac kommt PBML wie alle andere in Dateien gespeicherte Daten nur eingebettet in CAP mit dem Content-Type PBML vor.

Das PBML-Format

Die Speicherstruktur von PBML ist sehr einfach. Jede Zeile in PBML steht für eine Zeile auf dem Feld, jede Spalte für eine Spalte. Die ASCII-Werte der einzelnen Zeichen in den Zeilen entsprechen den Zuständen der einzelnen Zellen subtrahiert mit vier. Die Subtraktion von vier ist notwendig, da das Zeilenumbruchzeichen \n mit dem ASCII-Wert drei nicht als Beschreibung eines Zustandes einer Zelle, sondern in seiner ursprünglichen Funktion, nämlich als Zeilenumbruchzeichen, verwendet wird. Nachfolgend wird ein Beispiel eines PBML-Formats vorgestellt (Die Zahlen stehen im Beispiel für die Zeichen des entsprechenden ASCII-Wertes, nicht für die ASCII-Werte der Zahlen als Zeichen).

3.1.5 SPG

Ein wesentlicher Bestandteil von celmac sind die statistischen Auswertungsmöglichkeiten. Um frühere aufgezeichnete Statistiken wieder aufgreifen oder wichtige Ergebnisse ablegen zu können, ist ein Format nötig, das diese Informationen in einer Datei speichern kann. celmac benutzt hier das Format SPG (Statistics Per Generation), das in Dateien mit der Endung *.spg vorkommt, auch selbstverständlich wie alle von celmac erzeugten Dateien innerhalb von CAP.

Das SPG-Format

Das SPG-Format erinnert in den Grundzügen an HTML, wenn man die eckigen Klammern durch spitze Klammern ersetzt. Die eckigen Klammern, die das Schlüsselwort generation umfassen, können als Tag angesehen werden, der mit [/generation] wieder geschlossen wird. Innerhalb des Tags befinden sich beliebig viele Standalone-Tags, eingeleitet mit dem Schlüsselwort combi. Sie geben hinter dem Doppelpunkt die Anzahl der gezählten Kombination an, die direkt nach combi definiert wurde. Zur näheren Erläuterung zu Kombinationen und deren Zählungen lesen Sie bitte das Kapitel Statistische Auswertung mit celmac 2.0. Nachfolgend wurden über drei Generationen die Kombinationen 1;0;1 und 0;2;1 überwacht, nachdem der CA schon 22 Geneationen iteriert hat.

Im SPG-Format ist Whitespace wie in ABC erlaubt und wird ignoriert.

3.2 Bedienung von celmac

Die Bedienung von celmac 2.0 ist recht komplex. Das kommt daher, dass celmac 2.0 möglichst allgemein zellulare Automaten simulieren kann und so viele Performanceeinbußen einstecken muss. Um dem entgegen zu wirken, gibt es zahlreiche Optimierungstechniken, die je nach CA unterschiedlich effektiv sind. Wir blenden diese Funktionen zunächst aus und machen uns mit der Grundstruktur des Programms vertraut.

3.2.1 Generator und Player

Die offensichtlichste (siehe Startdialog) und auch zugleich tiefgreifendste Strukturierung des Programms ist die Unterteilung in Player und Generator.

Der Generator erstellt zellulare Automaten. Mit ihm definiert man im Wesentlichen die Zustandsübergangsfunktion, das Charakteristikum jedes CAs. Außerdem kann man hier Dynamik und Anzahl der Dimensionen des CAs vorschlagen, da eine Zustandsübergangsfunktion meist hier mit festen Werten rechnet.

Der Player ermöglicht uns die praktische Anwendung des vom Generator erzeugten CAs. Hier können wir Iterationen beobachten, Zufallsversuche starten und mit der vorgegebenen Zustandsübergangsfunktion experimentieren. Es wird deutlich, dass in celmac 2.0 das Feld und der CA strikt getrennt sind, um viele verschiedene Kombinationsmöglichkeiten (z.B. Langton's Ameise auf einem von Game Of Life erzeugten Feld laufen lassen) zu ermöglichen.

3.2.2 Der Generator

Die Menüführung

Rechts sehen Sie das Fenster, das Sie erwartet, wenn Sie im Startdialog auf Generator klicken. Es besteht aus einer Menüleiste und drei Karteikarten.

Die erste Karteikarte Head beinhaltet alle Informationen außer die Zustandsübergangsfunktion. Hier kann die Wertemenge definiert werden (Standardwert1) und die Dynamik festgelegt werden. Um die Wertemenge richtig bestimmen zu können lesen Sie bitte das Kapitel Programmierung mit ABC.Wenn Sie die Checkbox vollständig synchrone Dynamik nicht ausgewählt haben, erscheint das Gruppenfeld Sequientielle Aufteilung in Blöcken.... Hier können wir die Ausmaße der Blöcke, die für die asynchrone Dynamik nötig sind, definieren.
In der zweiten Karteikarte ABC finden Sie ein Textfeld, in dem Sie die Zustandsübergangsfunktion schreiben können.
Nach einem Klick auf die Karteikarte CAL übersetzt celmac den ABC-Code in CAL-Code und gibt ihn aus. Hier können Sie nun Veränderung direkt an der systemnäheren Sprache CAL durchführen.

Die Menüführung ist in Datei, Tabs und Hilfe unterteilt. Da die beiden Letzteren keiner weiteren Erklärung bedürfen, wenden wir uns dem Submenü unter Datei zu.

Unter Neu... können Sie einen neuen zellularen Automaten definieren. Es erwartet Sie ein Dialogfeld, das ihnen anbietet, Assistenten zu benutzen, um einfacher geläufige CAs erstellen zu können. Möchten Sie keinen Assistenten benutzen wählen Sie die erste Option.

Die nächsten drei Menüpunkte Öffnen..., Speichern und Speichern unter... dienen zur Dateiverwaltung von Dateien, die im CAP-Format mit ABC-Quelltext gespeichert sind (*.abc). Diese Dateien können noch nicht vom Player verwendet werden, jedoch können Sie sie zu einem späteren Zeitpunkt mit dem Generator wieder editieren.

Unter CA-Datei erzeugen... erzeugen Sie eine Datei im CAP-Format mit CAL-Quelltext. Mit dieser Datei kann der Player umgehen, jedoch können Sie diese Datei nicht mehr mit dem Generator verändern, da die Übersetzung von CAL in ABC nicht möglich ist.

Mit CA-Player... wechseln Sie zum Player und mit Beenden beenden Sie celmac 2.0.

Programmierung mit ABC

Die Programmiersprache ABC ist in celmac 2.0 zum Erstellen der Zustandsübergangsfunktion vorgesehen. Nachdem wir uns mit der Sprachsyntax von ABC beschäftigt haben, gehen wir jetzt auf die praktische Umsetzung ein.

Auch wenn ABC eigentlich keine Arrays kennt, wird der Zugriff auf die Eingabevariablen durch ein zweidimensionales Array namens Cell[x][y] realisiert, wobei x und y Integerkonstanten sein müssen. Auch der Rückgabewert der Zustandsübergangsfunktion wird durch die Zuweisung an die Variable Cell[0][0] festgelegt. Folgendes Beispiel eines binären CAs setzt den Zustand der Zelle auf 1, wenn ihr linker Nachbar den Zustand 0 und ihr rechter Nachbar den Zustand 1 besitzen.

Augenscheinlich ist folgende Zuweisung aus syntaktischer Sicht zulässig..

Laut der Theorie von CAs ist diese Zuweisung nicht möglich. ABC speichert den Wert trotzdem in diesem Feld, er verfällt jedoch, nachdem die Zustandsübergangsfunktion beendet wurde. Alle anderen selbst deklarierten Variablen in ABC sind statisch und behalten ihren Wert solange der CA geöffnet ist.

Zu beachten ist weiterhin das Handling von celmac 2.0 mit der Zustandsmenge. Im Generator kann man eine Zustandsmenge angeben, jedoch hat dieser Wert nicht die Bedeutung, von der man wahrscheinlich intuitiv ausgeht.
Dieser Wert z bestimmt den Höchstwert des Betrages eines Zustandes. In der Zustandsübergangsfunktion dürfen auch höhere Werte für Cell[0][0] erreicht werden (das allgemeine Maximum für Variablen in ABC bleibt natürlich weiterhin bestehen), nach dem Durchlauf der Zustandsübergangsfunktion jedoch wird der Wert in Cell[0][0] Modulo z genommen. Daraus folgt, dass celmac 2.0 keine "echten" binären CAs simulieren kann (auch bei z=2 beträgt die Zustandsmenge {-1;0;1} ), jedoch hat das keinen Einfluß auf die übliche Arithmetik.

Dieses Beispiel eines binären CAs wechselt den Zustand der Zelle, wenn ihr unterer Nachbar den Wert 1 besitzt. Sollte Cell[0][0] nämlich anfangs den Wert 0 besitzen nimmt die Zelle nach der Durchführung der Zustandsübergangsfunktion den Wert 1 an (1mod2=1). Wenn die Zelle anfangs den Wert 1 besitzt hat Cell[0][0] nach der Zustandsübergangsfunktion den Wert 2. Im ZR hat die Zelle jedoch den Wert 0 (2mod2=0).

Abschließend wollen wir uns eine komplette Zustandsübergangsfunktion eines bekannten CAs in ABC ansehen. Als Beispiel nehmen wir das klassische Game Of Life des Mathematikers John Horton Conway (Regelwelt 23/3).

3.2.3 Der Player

Klickt man nach dem Start von celmac im Startdialog auf Player, so erscheint ein relativ leer aussehendes Fenster. Das Menü bietet im Wesentlichem das Öffnen der Hilfe und das Öffnen eines CAs an.

CAs öffnen

Nach dem Klick auf das Ordnersymbol oder auf den Menüpunkt CA öffnen... erscheint das Dialogfeld CA öffnen.

Dieses Dialogfeld bietet zunächst die Angabe der CA-Datei an (*.ca), die vorher vom Generator erzeugt werden muss. Im zweiten Textfeld sind zwei unterschiedliche Angaben möglich. Entweder man gibt eine PBML-Datei an, um einen schon vorhandenen ZR zu laden, oder man lässt durch die Eingabe der Zeichenkette Leeres Feld oder dem Selektieren des nebenstehenden Speedbuttons ein neues Feld erzeugen. Sollte die zweite Möglichkeit gewählt worden sein, ist das Gruppenfeld Neues Feld zu sehen. Hier ist es möglich, die Ausmaße und die Topologie des zu erzeugenden ZRs zu definieren, die jedoch später nochmals geändert werden können. Die Topologie des ZRs wird definiert, indem man für jede Dimension festsetzt, wie und ob die Enden des ZRs miteinander verbunden werden. Es sind drei verschiedene Werte möglich.

• Nicht verbunden: Die Enden des ZRs sind in dieser Dimension nicht miteinander verbunden
• Parallel verbunden: Die am häufigsten verwendete Option. Die Enden werden einfach parallel verbunden. Eine Zelle am rechten Rand hat beispielsweise die Zelle auf gleicher Höhe am linken Rand als rechten Nachbar
• Antiparallel verbunden: Die Enden des ZRs werden gegenläufig verbunden. Eine Zelle am rechten Rand im oberen Drittel hat dann eine Zelle am linken Rand im unterem Drittel als rechten Nachbar

Mit einem Klick auf Bestätigen schließt sich das Fenster und es erscheint ein für MDI-Anwendungen charakteristische untergeordnete MDI-Kindfenster.

Die Unterfenster

Je ein Fenster steht für einen geladenen CA. Das Fenster an sich dient dazu, den ZR anzeigen und ihn verändern zu können. Die Zellen sind abhängig ihres Zustandes eingefärbt. Die Farben sind unter CA->Einstellungen... zu definieren. Beschäftigen wir uns mit den aktiven Möglichkeiten von einem Unterfenster.

Per Rechtsklick gelangt man zum gezeigten Popup-Menü, dessen Menüführung bis auf den ersten Menüpunkt Beim Klicken keiner weiteren Erklärung bedarf. Unter Beim Klicken wird festgesetzt, was bei einem Linksklick ins Fenster mit der angeklickten Zelle geschieht. So kann man mit der linken Maustaste den Zustand einzelner Zellen verändern. Den Zustand mehrerer Zellen aufeinmal kann man verändern, indem man einen Ausschnitt einer anderen Datei in den ZR lädt. Dieser muss im PBML-Format vorliegen.

Das Hauptmenü

Hat man nun einen CA geöffnet vergrößert sich auch das Hauptmenü des Players.

Wir wenden uns zunächst den Speed - Buttons in der Tool - Leiste zu. Mithilfe des Ordnersymbol kann man wie zuvor einen CA öffnen. Die folgenden drei Buttons ermöglichen es, die untergeordneten MDI-Fenster auf verschiedene Arten zu ordnen. Ein Klick auf den grünen Pfeil, die Taste F9, der Menüpunkt Simulation->Simulation starten oder der Button OK im Iterationsassitenten haben alle die selbe Funktion, nämlich eine Simulation mit der im Iterationsassistenten festgelegten Anzahl von Iterationen zu starten. Die restlichen Speed - Buttons stehen für die verschiedenen Assistenten des Players, die später im Kapitel behandelt werden, nachdem der Menüpunkt CA erläutert wurde.

Der Menüpunkt CA

Das CA Menü des Players bezieht sich meist auf die untergeordneten MDI-Fenster. Das Untermenü Feld ähnelt dem PopUp-Menü der Unterfenster und bedarf somit keiner weiteren Erklärung. Unter Statistische Auswertung gelangt man zum entsprechendem Fenster, das später im Kapitel Statistische Auswertung näher erläutert wird. CA Schließen schließt einen CA und somit ein MDI-Fenster. CA-Generator... wechselt zum Generator. Unter Einstellungen kann man verschiedene Einstellungen vornehmen, die auf Quelltextebene meist in der Klasse TSettings abgelegt werden. celmac Beenden beendet das Programm.

Assistenten

Assistenten steuern im Player die gesamte Simulation. Sie sind entweder über das Hauptmenü des Players, über die Speed - Buttons in der Tool - Leiste oder durch die Tasten F4 bis F8 ein- und auszublenden. Es gibt fünf Assistenten.

• Der Simulationsassistent
• Der Iterationsassitent
• Der Parameterassistent
• Der Statistikassistent
• Der Optimierungsassitent

Der Simulationsassistent

Der Simulationsassistent ermöglicht genaue und differenzierte Angaben über die gewünschte Genauigkeit der verschiedener Anzeigen einerseits und die Performance der ganzen Simulation andererseits. Der Simulationsassistent differenziert zwischen Feld, Generationsanzeige und Statistiken. Sollte kein Häckchen neben einer dieser Bereiche gemacht worden sein, wird dieser Bereich erst nach dem Ablauf der gesamten Simulation aktualisiert. Da das Neuzeichnen auf dem Bildschirm sehr rechenaufwendig ist, kann man so sehr viel Rechenzeit sparen, es empfiehlt sich jedoch, die Generationsanzeige nicht gar nicht aktualisieren zu lassen, da dies der rechenunaufwendigste Bereich ist und an ihm sich erkennen lässt, ob celmac erwartungsgemäß arbeitet.

Der Iterationsassistent

Jede Simulation wird direkt oder indirekt (per Shortcuts) über den Iterationsassistenten gestartet. Mit der Bemerkung, dass im Textfeld die Zahl der Iterationen, die auf einmal ausgeführt werden sollen, eingetragen wird, erschöpft sich der Erklärungsbedarf der Bedieneroberfläche des Iterationsassistenten mangels Komplexität derselben.

Der Parameterassistent

Die Tabelle im Parameterassistent zeigt alle ABC-Variablen des aktuellen CAs an. So ist es möglich, mit ABC Zustandsübergangsfunktionen zu schreiben, die auf Änderungen einzelner Parameter reagieren, wie es sich beispielsweise bei der Programmierung des Greenberg-Hastings Automaten für s anbietet. Die Variablen im Parameterassistent können direkt in der Tabelle verändert werden. Änderungen sind jedoch erst nach dem Defokusieren des Parameterassistenten sichtbar.

Der Statistikassistent

Der Statistikassistent hat wie leicht zu erkennen zwei verschiedene Zustände: eingeklappt und ausgeklappt. Da der eingeklappte Zustand nur zum Zwecke des Platzsparens sinnvoll ist, beschäftigen wir uns mit dem ausgeklapptem Zustand, da nur da der Statistikassistent sein Möglichkeiten entfaltet. Der Statistikassistent bezieht sich immer auf die aktuelle Generation des aktuellen CAs. Er zeigt die überwachten Kombinationen und deren absolute Häufigkeit an. Er bietet weiterhin die Möglichkeit, die überwachten Kombinationen zu beabeiten, zu löschen oder neue Kombinationen hinzuzufügen. Im Menü Datei erhält der Benutzer die Möglichkeit, aktuelle Ergebnisse in eine SPG-Datei zu speichern. Es können auch SPG-Dateien geladen werden, jedoch verfallen dann sämtliche gemachte Aufzeichnungen und werden durch die Werte der SPG-Datei ersetzt.

Äußert wichtig ist hier die Checkbox Statistische Aufzeichnung. Sollte diese Checkbox nicht aktiviert sein, werden keinerlei Kombinationen überwacht und keine Werte gesammelt, wenn der CA iteriert wird.

Die Spalte Platz ist in der Beta-Version überflüssig und ohne Bedeutung.

Der Optimierungsassistent

Im Optimierungsassistenten kann zwischen Echtzeitinterpretierung von CAL und Zustandsübergangstabelle gewählt werden. Dabei handelt es sich um zwei verschiedene Methoden, die Zustandsübergangsfunktion anzuwenden, die je nach Anzahl der Nachbarn und Größe der Wertemenge unterschiedlich performant sind. Nähere Erklärung finden Sie im Kapitel Umsetzungen auf Quelltextebene unter Zwei Optimierungsmethoden. Änderungen im Optimierungsassistenten sind sofort wirksam.

3.2.4 Statistische Auswertung

Dieses Kapitel könnte eigentlich dem Player zugeordnet werden, da jedoch die Auswertung unabhängig der MDI-Fenster geschehen kann und der Bereich der Statistik einen besonderen Stellenwert einnimmt, ist ihm dieses Kapitel gewidmet.

Um auch diesen Bereich von celmac 2.0 bedienen zu können, müssen wir uns klarmachen, welche statistischen Möglichkeiten celmac 2.0 hat. Eine zentrale Rolle spielt dabei der Begriff der Kombination.

Kombinationen

Sollte im Statistikassistenten die Checkbox Statistische Aufzeichnung aktiviert sein, werden nach jeder Generationen die im Selbigem festgelegten Kombinationen im ZR ausfindig gemacht. Dabei wird der ZR als eine Reihe von Zahlen gesehen, und innerhalb dieser Zahlenfolge werden andere Zahlenfolgen (Kombinationen genannt), gesucht, gezählt und gespeichert. Kombinationen können eine beliebige Länge erreichen. Kombinationen sind das Werkzeug von celmac 2.0, um statistische Ergebnisse zu erhalten .Mit ihrer Hilfe können bestimmte Muster herausgefiltert werden, Zufallsreihen generiert werden und Vergleiche zwischen unterschiedlichen CAs angestellt werden.

Das Auswertungsfenster

Zum Auswertungsfenster gelangt man über CA->Statistische Auswertung im Hauptmenü des Players oder durch einen entsprechenden Button im Statistikassistenten.

3.3 Umsetzungen auf Quelltextebene

3.3.1 Die Klasse TGlobal

Die Klasse TGlobal nimmt in celmac eine Sonderstellung ein. Zur gesamten Laufzeit referenziert immer nur ein Zeiger die eine TGlobal-Instanz (Diese Instanz wird im Konstruktor von TMainForm erzeugt). Diese Klasse ist einerseits als eine Zusammenfassung allgemeingültiger Informationen (Elemente), anderseits als Sammlung nützlicher und immer wieder gebrauchten Routinen (Elementfunktionen) zu verstehen. So wird deutlich, dass die Klasse TGlobal nicht als klassische Klasse im objektorientierten Sinne zu verstehen ist, sondern eher mit einer C typischen Struktur zu vergleichen ist. Somit wurde auch keinen Wert auf objektorientierten Techniken wie Kapselung etc. gelegt.

Wichtige Elemente

Das Element MyDir

MyDir speichert, wie aus dem Kommentar ersichtlich, das Arbeitsverzeichnis beim Start von celmac, also den Dateipfad zur EXE-Datei. Dieser Pfad wird zum Beispiel bei der Speicherung von Dateien wie settings.dat gebraucht. Ermittelt wird dieser Pfad mithilfe eines Objektes von Borland C++ Builder namens TDirectoryListBox (Element von TMainForm), dessen Eigenschaft Directory standardmäßig die gesuchte Pfadangabe enthält. Beim Erzeugen von TMainForm wird nun dieser Wert in TGlobal::MyDir geschrieben. Zu sehen ist auch das Erzeugen des TGlobal-Objektes.

Andere Elemente

celmac 2.0 ist eine MDI-Anwendung. Für jedes Fenster gibt es eine eigene Instanz von TMDIChild, TCA und TWorld. In TGlobal finden wir Zeiger, die die zu dem aktuellem (aktivem) Fenster gehörigen Instanzen oben genannter Klassen referenzieren. Sollte kein Fenster aktiv sein, zeigen diese Zeiger auf NULL.

Wichtige Elementfunktionen

Die Funktion Split(...) zerschneidet eine gegebene Zeichenkette (String Text) an jedem Vorkommen eines gegebenen Zeichens (char Seperator) und gibt das Ergebnis als TStringList zurück.

GetParam(...) wird bei der Auswertung von CAP-Headern gebraucht. In einem gegebenem String (String Source) wird nach einem Doppelpunkt gesucht und der Teilstring vor und der nach diesem Zeichen als zwei Referenzen (&Key und &Value) zurückgegeben.

Mit NewActWin(...) werden die Elemente MDIChild, CA und Field aktualisiert, sollte sich das aktuelle Fenster ändern.

Die Unterklasse TSettings

Diese Klasse ist wie TGlobal auch eher als C typische Struktur, nicht als eine objektorientierte Klasse anzusehen. TSettings besitzt Elemente, die Einstellungen speichern, die nach Beenden von celmac nicht verloren gehen sollen. Daher werden diese Daten durch den Konstruktor aus der Datei settings.dat geladen und durch den Destruktor wieder dort hinein geschrieben. Zur Laufzeit können diese Daten verändert werden, meist geschieht das explizit durch den Benutzer, indem er im Player über den Menüpunkt CA->Einstellungen... das Formular von TSetForm öffnet (settings.h), das seinerseits wiederum die Elemente von TSettings verändern kann, da sie alle öffentlich deklariert sind.

Die Datei settings.dat

Die Syntax von settings.dat schwer ohne Erläuterungen zu durchschauen. Die Datei ist durch vier verschiedene Kategorien strukturiert. Die Namen dieser Kategorien stehen in eckigen Klammern allein in einer Zeile und leiten so den jeweiligen Abschnitt ein, der dann nach einer festgelegten Zeilenzahl durch eine andere Kategorie abgelöst wird. Jede Kategorie hat ihre eigene Syntax.
Anmerkung: In der Syntaxdarstellung werden die originalen Variablennamen aus TSettings verwendet. In Klammern hinter jeder Zeile finden sie den Datentypen, wie er in settings.dat verwendet wird.

3.3.2 Aufgabenfeld Generator

Der Generator ist programmiertechnisch außer in zwei Bereichen nicht sehr interressant.

• ABC - Highlighting
• Übersetzung von ABC in CAL

Da die Umsetzung des ABC - Highlighting in der Betaversion von celmac 2.0, mit der sich diese Arbeit auseinandersetzt, aufgrund akutem Zeitdrucks derartig schlecht umgesetzt ist, dass es leider kaum verwendbar ist, werden wir uns nur der Übersetzung von ABC in CAL widmen.

Übersetzung von ABC in CAL

Ich werde an dieser Stelle meinen eigenen Gedankengang, soweit ich ihn noch reflektieren kann, darlegen, der mich auf meine Lösung gebracht hat, wie ABC in CAL zu übersetzen ist. Zunächst übersetzte ich verschiedene ABC-Strukturen per Hand (vor der CAL-Befehlszeile steht in geschweiften Klammern die Zeilennummer, um die jp-Befehle besser nachvollziehen zu können.

Zur Strukturierung sind drei Zeichen in ABC ausschlaggebend. Die öffnende geschweifte Klammer ( { ) leitet einen Anweisungsblock ein, die schließende geschweifte Klammer ( } ) schließt ihn wieder. Das dritte Zeichen ist der Strichpunkt ( ; ), der einen ABC-Befehl abschließt. Ein Block wird durch eine Instanz der Klasse TBlock [gen_main.h] dargestellt. Um diese Klasse zu verstehen müssen wir uns jedoch ersteinmal mit der Funktion TGenMainForm::AnalyzeABC(..) auseinandersetzen. Ohne sich weiter mit dem Quelltext dieser Funktion auseinanderzusetzen sei hier ihre Funktionsweise erklärt.

Das letzte Argument source ist eine Zeichenkette, die der Syntax

oder der Syntax

entspricht. AnalyzeABC(..) filtert nun die einzelnen Teile heraus und gitb sie als Referenzen zurück. Da von key später nur der erste Buchstabe benötigt wird genügt es auch jetzt nur den ersten Buchstaben als Referenz zurück zu liefern.

Die Klasse TBlock [gen_main.h]

Folgende Elemente besitzt diese Klasse.

• pCondition (String)
• pKey (char)
• pLine (int)
• pPrev (TBlock *)

Die Elemente pCondition und pKey sind von TGenMainForm::AnalyzeABC(..) ermittelt worden. pLine speichert die Zeilennummer der geschweiften öffnenden Klammer, die ja einen Block einleitet. Da die Blöcke auch verschachtelt vorkommen ist noch ein Verweis auf den nächst höheren Block nötig, der durch pPrev realisiert ist.

Die Funktion Abc2Cal(..) [gen_main.cpp]

Kommen wir nun zur praktischen Umsetzung des Übersetzungsvorgangs. Sie geht in der Funktion Abc2Cal [gen_main.cpp] vonstatten. Da ihr Quelltext jedoch umfangreich, gleichzeitig aber nicht sehr kompliziert ist wird hier darauf verzichtet, quelltextnah diese Funktion zu erklären. Stattdessen soll es hier um die logischen gedanklichen Schritte gehen , die Grundlage dessen sind.

Zunächst wird der ABC-Quelltext von Whitespace entfernt. Anschließend wird der ABC-Quelltext Zeichen für Zeichen durchsucht. Wird eines der oben genannten strukturgebenen Zeichen ( '{', '}' oder ';' ) gefunden wird gestoppt und der Teilstring zwischen dem letztem gefundenem strukturgebenen Zeichen und der aktuellen Position von AnalyzeABC(..) verarbeitet. Bei '}' ist dieser Teilstring immer leer und so ist hier die Verarbeitung durch AnalyzeABC(..) nicht notwendig. Bei eingehender Untersuchung des ABC-Quelltextes, des von Hand ermittelten entsprechenden CAL-Quelltextes und unter Zuziehung der bis jetzt abgeschlossenen Gedankenschritte ergibt sich folgender Entscheidungsbaum. Man kann dieses Diagram auch als grobes Programmablaufprotokoll der Funktion Abc2Cal(..) sehen.

CAL-Quelltext ist grau unterlegt. Rauten kennzeichnen Entscheidungen und Rechtecke symbolisieren Anweisungen. In den Kreisen steht die Bedingung, die erfüllt werden muss, um diesen Weg zu gehen. In den Kreisen der zweiten Entscheidungsebene stehen immer nur einzelne Buchstaben, da ja key ein Character ist. Sie ersetzen folgende vollständige ABC-Schlüsselwörter.

• i steht für if
• e steht für else
• w steht für while
• r steht für repeat
• u steht für until
• m steht für mk

3.3.3 Aufgabenfeld Player

Handling von CAL

CAL ist die Sprache, in die ABC übersetzt wird um von dem Player verwendet zu werden. Hier soll die genaue Umsetzung dargelegt werden, wie celmac mit CAL den Zustand des CAs bei jeder Iteration neu berechnet. Ausgehend von der Klasse TInterpreter [interpret.h] werden sämtliche Aufgaben bezüglich der Umsetzung von CAL gesteuert.

Lösungsidee

Um CAL zu verwenden, müssen ersteinmal die einzelnen Bestandteile der Sprache analysiert und auf einen möglichst kleinen gemeinsamen Nenner gebracht werden. Schauen wir uns die verschiedenen CAL-Befehle einmal genau an. Ausgenommen von mk kann jeder Befehl als Zuweisung gewertet werden. Bei st wird einer Variable ein Wert zugewiesen, bei jp wird der Zeilennummer ein Wert zugewiesen. Der vd Befehl kann als leere st Anweisung gewertet werden. Eine Zuweisung besteht aus einer Variablen, der etwas zugewiesen wird, und einem Wert (ein Ausdruck), der zugewiesen wird. Folglich kann man eine Liste von Zuweisungen (nichts anderes ist ja CAL, wie oben festgestellt, wenn man mk gesondert behandelt) auf Quelltextebene durch eine Liste von Zeigern auf 1-Byte Integer für die Variable und eine Liste von Zeigern auf eine Klasse für Ausdrücke (konkret: die Klasse TArith [ausdruck.h]) für den zuzuweisenden Wert realisiert werden. Ein Ausdruck kann jedoch auch aus einer Integerkonstante bestehen, deshalb wird in dieser Liste generische Zeiger verwendet. Zusätzlich ist noch eine weitere Liste notwendig, um das zweite Glied eines CAL-Befehls, die Bedingung, ob diese Befehlszeile ausgeführt werden soll, zu beachten. Eine Liste von Zeigern wird durch die Klasse TPtrList realisiert, drei Instanzen dieser Klasse werden in TInterpreter [interpret.h] deklariert.

Eine ausführliche Beschreibung von TPtrList und TInterpreter folgt weiter hinten im Kapitel.

Die Klasse TArith

Mit der Klasse TArith ist celmac 2.0, wie oben bereits erwähnt, in der Lage, Ausdrücke von einer Aneinanderreihung von Zeichen in ein hierarchisch aufgebautes Speichermodell zu verwandeln, das mithilfe von Rekursion bestimmte Arten von Ausdrücken auswerten kann. Operator speichert die Rechenart und op1 und op2 zeigen auf die zwei Operanten. Es wird deutlich, dass eine Instanz von TArith nur für eine Rechenoperation stehen kann. Beliebig komplexe Ausdrücke kann man nun konstruieren, indem man die Operantenzeiger auf weitere TArith - Instanzen zeigen lässt. op1 und op2 dürfen folglich nur auf 1-Byte Integer oder auf weitere TArith - Instanzen zeigen.

Bevor wir die Funktionsweise von TArith an einem Beispiel nachvollziehen können müssen wir noch auf die Methode Calc() eingehen. Dabei klären wir auch die Bedeutung der konstanten Variable TArith::Identifier.

Auffällig ist hier, dass op1 und op2 hier die Funktion Calc() aufrufen, obwohl sie generische Zeiger sind , also nicht zwangsweise auf TArith-Instanzen zeigen. Um dies herauszufinden wird der this-Zeiger verwendet . Das Schlüsselwort this steht für eine lokale Variable, die in jeder Nicht-statischen Elementfunktion vorhanden ist. Sie wird beim Funktionsaufruf verborgen mit übergeben und zeigt auf das aufrufende Klassenobjekt, in unserem Fall möglicherweise auch auf den integrierten Datentyp __int8. Nimmt man nun die von this referenzierte Adresse und castet sie als __int8, werden die ersten 8 Bit als __int8 gewertet. Die ersten 8 Bit eines TArith-Objekts nimmt TArith::Identifier ein, folglich hat *this, sollte es auf eine TArith-Instanz zeigen, immer den Wert TARITH_IDENTIFIER bzw. den Wert -127. Da dieser Wert für ABC-Variablen nicht zulässig ist, kann hier eine eindeutige Unterscheidung getroffen werden. Sollte this eine TArith-Instanz referenzieren, wird Calc() einmal durch op1 und einmal durch op2 aufgerufen. Es entsteht Rekursion, die solange fortgesetzt wird, bis this den Datentyp __int8 referenziert. Dann wird der entsprechende Wert zurückgegeben.

Verdeutlichen wir dies nun an einem Beispiel. Folgender Ausdruck soll abgelegt werden.

Nachfolgend sehen sie die schematische Darstellung der dazu notwendigen hierarchische Speicherstruktur.

Sollte nun von der obersten TArith-Instanz die Funktion Calc() aufgerufen werden, wird insgesamt sieben mal die Funktion TArith::Calc() aufgerufen, jedoch zeigt this jedesmal auf eine andere Speicheradresse.

Die Klasse TArithList

Um aus der Zeichenkette, bestehend aus Operatoren, Variablennamen und Integerkonstanten, solch eine Struktur zu generieren benötigen wir eine eigene Klasse, die Klasse TArithList.

Wie an den Zeigern Next und Before zu erahnen wird hier mit zweifach verketteten Listen gearbeitet. In einer zweifach verketteten Liste enthält jede Instanz einen Zeiger auf den Vorgänger und einen Zeiger auf den Nachfolger. Zusätzlich besitzt die Klasse TArithList einen Zeiger auf eine TArith-Instanz und einen 16-Bit Integer namens OrderIndex. Folglich kann man mit einer zweifach verketteten Liste aus TArithList-Instanzen eine Liste von gleichberechtigten TArith-Objekten darstellen, denen eine bestimmte Zahl zugeordnet ist.

Die eigentliche Übersetzung des Strings in eine Speicherstruktur geschieht in der Funktion TInterpreter::StringToArith(String Term) in der Datei [interpret.cpp]. Ohne die einzelnen Quelltextzeilen dieser Funktion zu erläutern beschränke ich mich auf die groben Vorgänge. Zunächst wird wie für die Auswertung von C++ Ausdrücken eine feste Rangfolge der Operatoren festgelegt (Die entsprechenden ABC-Operatoren finden Sie im Anhang).

Anders als in C++ wird jedoch keine operatorenspezifische Assozitivität festgelegt, die Abarbeitungsfolge geht immer von links nach rechts. Referenziert also nun der Zeiger einer TArithList-Instanz eine TArith-Instanz, so wird der Rangfolgeplatz von TArith::Operator in TArithList::OrderIndex geschrieben. Sollte diese TArith-Instanz eine in Klammern stehende Rechenoperation repräsentieren wird zu TArithList::OrderIndex der Wert OP_COUNT*z addiert, wobei z die Anzahl der Klammern darstellt. So erhalten wir also eine Liste aus TArithList-Instanzen, in der die referenzierte TArith-Instanz mit dem höchsten TArithList::OrderIndex Wert zuerst ausgewertet werden muss. Die Grundlage für die Schaffung der oben beschriebenen hierarchischen Struktur unter verschiedenen TArith-Instanzen ist gegeben. Wir verfolgen die weitere Entwicklung dieser Speicherstrukturen an unserem ursprünglichen Beispiel.

Um nun aus diesem Gebilde eine hierarchische Struktur zu machen ist hauptsächlich die Funktion TArithList::LevelUp() verantwortlich. Sie wird zunächst von dem Klassenobjekt aufgerufen, das den höchsten Wert in TArithList::OrderIndex gespeichert hat, in unserem Falle das Mittlere.

Die Funktion löscht das aufrufende Klassenobjekt, sorgt jedoch dafür, dass die entstehende Lücke in der zweifach verketteten Liste geflickt wird. Außerdem wird die vom aufrufenden Klassenobjekt referenzierte TArith-Instanz zu dem Ziel von Before->Arith->op2 und Next->Arith->op1. Wir erhalten nach der Ausführung dieser Funktion folgendes verändertes Schaubild.

Nun wird nochmals die Funktion TArithList::LevelUp() durch das Klassenobjekt mit dem höchsten TArithList::OrderIndex aufgerufen, sooft, bis nur noch eine TArithList-Instanz vorhanden ist. Diese referenziert dann die hierarchisch höchste TArith-Instanz. Nun haben wir die oben angestrebte Speicherstruktur erreicht. Empfohlen zum leichteren Verständnis sei hier das beigelieferte Hilfsprogramm HowWorkTArithList.

Ablegung von Variablen

Nachdem wir uns mit der Umsetzung von Ausdrücken auf Quelltextebene beschäftigt haben wenden wir uns nun den verschiedenen Möglichkeiten zur Ablegung von Variablen zu. Zwischen folgenden Kategorien, denen je eine Klasse zugeordnet werden kann, ist hier zu unterscheiden.

• Konstanten (TByteList)
• Parameter (TVarList)
• Nachbarn (TCellDB)
• reservierte Variablen (TInterpreter)

Für all diese Kategorien existieren auch Verweise in der Klasse TInterpreter, die ja, wie oben erwähnt, die gesamte Umsetzung von CAL steuert. Die Kategorie reservierte Variablen bezieht sich auf die Elemente TInterpreter::LC und TInterpreter::ActLine.

Gehen wir zunächst auf die für das Verständniss nötigen Klassen TByteList, TVarList und TCellDB ein.

Die Klasse TByteList [intlist.h]

Mithilfe von TByteList werden zum Beispiel die Konstanten von CAL abgelegt. TByteList stellt eine Liste von Elementen des integrierten Typs __int8 dar, auf die durch TByteList::Items[int] zugegriffen werden kann.

Da sich TByteList aus Sicht der Speicherreservierung und Speicherfreigabe an C-Syntax hält ist diese Klasse auch geeignet, um an ihr die Funktionsweise von Zeigern kurz zu erklären und kurz auf Zeigerarithmetik einzugehen. Zunächst müssen jedoch die Schnittstellen der Klasse erläutert werden.

Schnittstellen von TByteList

Die einzigen Eigenschaften, auf den von außen zugegriffen werden kann, sind Items[int], mit dem auf die einzelnen Elemente zugegriffen werden kann, und Count, das die Anzahl der Elemente angibt.

Mit Add(..) und Delete(..) können Elemente hinzugefügt bzw. entfernt werden. GetPtrByValue(..) und GetPtrByIndex(..) geben Speicheradressen diverser Elemente zurück. Diese Funktionen werden gebraucht, wenn TByteList durch TInterpreter zur Ablegung von CAL-Konstanten benutzt wird. Clear() löscht alle Elemente der Liste und der Destruktor kümmert sich um saubere Speicherfreigabe.

Interne Funktionsweise von TByteList

Die theoretische Grundlage zum Verständniss der nun im Folgenden vorgestellten internen Funktionsweise von TByteList finden Sie im Anhang unter Zeiger in C++.

Der Zeiger auf 1-Byte-Integer StartPtr zeigt immer auf das erste Element der Liste. Die Adresse des zweiten Elements der Liste enthält man, wenn man zu StartPtr ein Byte (eine __int8 Adresse weiter) addiert.

So sind nun auch einige Funktionen von TByteList zu erklären. In GetItem(..) und SetItem(..) wird auf das Element durch folgenden Ausdruck zugegriffen.

Zu StartPtr wird Index (der Index des aufzurufende Elements) addiert um die korrekte Adresse zu erhalten. Nun wird auf den Inhalt dieser Adresse mit dem Inhaltsoperator * zugegriffen. Diese beiden Funktionen sind nicht ausnahmesicher, könnten also undefiniertes Verhalten hervorrufen. Da diese Klasse jedoch nicht in anderen Projekten verwendet werden soll ist hier zugunsten von Performance auf eine Kontrolle, ob Index kleiner als Count ist, verzichtet worden. GetPtrByIndex(..) arbeitet analog, jedoch ohne Inhaltsoperator *.

Die Funktion Add(..) fügt ein Element der Liste hinzu, sie kümmert sich also auch um die Reservierung neuen Speicherplatzes und der Anpassung von pCount.

Zunächst wird die Zahl der Elemente angepasst. In der zweiten Zeile wird mithilfe von realloc(..) der neue Speicherplatz reserviert und von StartPtr referenziert. Damit die schon vorhandenen Elemente der Liste nicht verloren gehen kopiert realloc(..) den gesamten Inhalt des alten Speicherblock in den neuen Speicherblock. Schließlich wird das noch uninitalisierte letzte Element mit ToAdd initalisiert.

Um Elemente zu löschen benötigt man die Funktion Delete(..), der man den Index des ersten zu löschenden Elements und die Anzahl der zu löschenden Elemente übergibt. Delete(..) verschiebt alle Elemente nach Index um Count nach vorn und passt dann die Größe des Speicherblocks an.

Zur kompletten Freigabe des von StartPtr referenzierten Speicherblocks wird wie im Destruktor oder in Clear() die C-Funktion free(..) wie folgt benutzt.

Die Klasse TVarList [intlist.h]

TVarList übernimmt die Ablegung von CAL-Variablen, also Variablen, die mit dem CAL-Befehl mk erstellt wurden oder mit ihm hätten erstellt werden können. TVarList stellt wie TByteList eine Liste aus 1-Byte-Integer zur Verfügung, zusätzlich können jedoch den Elementen dieser je ein Name zugeordnet werden. Der Parameterassistent des Players zeigt ein genaues Abbild von TVarList::Names und TVarList::Values.

Diese Klasse tut im Grunde nichts weiter als Verweise auf zwei verschiedene Listen zu speichern, eine für die Namen und eine für die Werte. Zusätzlich bietet die Klasse einen internen Zeiger an, der mit Reset() zurückgesetzt werden kann. Dieser Zeiger ist notwendig, damit man beispielsweise mit folgender while-Schleife bequem alle vorhandenen Variablen abfragen kann (Im Beispiel ist VarList ein Zeiger auf eine initalisierte TVarList-Instanz).

Die Klasse TCellDB [celldb.h]

Eine ähnliche und gleichnamige Funktion bietet auch die Klasse TCellDB an. Im Gegensatz zu TVarList ordnet sie jedoch nicht Namen sondern Punkte bestimmten Werten zu. Da TCellDB wie oben angedeutet für die Ablegung der Nachbarn zuständig ist verfügt sie zusätzlich über die Funktion TCellDB::ActValues(..).

Wird TCellDB zur Ablegung der Nachbarn benutzt (wie durch TInterpreter), beinhalten TCellDB::x und TCellDB::y die relative Lage zur Ursprungszelle, übernommen aus der ABC-Variable Cell[][] (siehe Kapitel Programmierung mit ABC). Folglich ändern sich alle Werte in TCellDB::Values, sollte nun die Zustandsübergangsfunktion auf eine andere Zelle angewendet werden. Diese Änderung übernimmt die Funktion TCellDB::ActValues(..).

Standartmäßig ist der Punkt (0|0) vorhanden. Da der Rückegabewert der Zustandsübergangsfunktion ja in ABC durch Zuweisung an die Variable Cell[0][0] realisiert wird ist diese Zelle unerlässlich.

Mit der Funktion TCellDB::GetCombi() beschäftigen wir uns später im Kapitel Die Klasse TInterpreter.

Die Funktion TArithList::InitOp(..) [ausdruck.cpp]

Hier laufen alle Stränge wieder zusammen. Die statische Funktion TArithList::InitOp(..) entscheidet, in welche der oben aufgelisteten Kategorie eine Variable gehört.

Zunächst wird die reservierte Variable LC mit einer if-Abfrage abgefangen. Folgend wird geprüft, ob Name eine Ganzzahl und somit eine Integer-Konstante ist, die dann zu ConstList hinzugefügt wird, sollte sie noch nicht vorhanden sein. Handelt es sich nicht um eine Integer-Konstante ist es entweder eine ABC-Variable oder ein Nachbar der Form Cell[][]. Die Funktion TCellDB::Add(String) liefert einen NULL-Zeiger zurück, sollte der übergebene String nicht der Form entsprechen. Sollte dies der Fall sein ist durch Ausschlussverfahren erwiesen, dass es sich um eine ABC-Variable handelt. Diese wird dann VarList hinzugefügt, sollte ihr Name noch nicht vorhanden sein.

In jedem Fall gibt TArithList::InitOp(..) einen Zeiger auf ein initalisierten 1-Byte Integer zurück.

Die Klasse TPtrList [ptrlist.h]

Diese sehr schlanke Klasse stellt eine Liste von generischen Zeigern da. Obwohl ansonsten bei der Programmierung von celmac 2.0 bei der Speicherverwaltung aus im Vorwort genannten Gründen C-Syntax verwendet wurde macht hier TPtrList durch die Verwendung von new und delete eine Ausnahme. Alle Schnittstellen von TPtrList haben analoge Bedeutung zu den gleichnamigen Schnittstellen von TByteList und werden hier nicht weiter erläutert.

Das Laden einer CA-Datei

Wie anfangs festgestellt wird die gesamte Interpretierung von CAL durch die Klasse TInterpreter realisiert. Wenn eine CA-Datei geladen wird, sind jedoch weitaus mehr Klassen beteiligt. Um die Aufgaben der einzelnen Klassen klar abgrenzen zu können verfolgen wir schrittweise die Mechanismen, die greifen, wenn eine Datei (CAP mit content-type:CAL) geöffnet wird.

Klicken wir in NewChildForm auf den Button Bestätigen, um einen CA zu laden, wird zunächst die Funktion TNewChildForm::OKBClick(...) aufgerufen. Diese Funktion verarbeitet die gegebenen Informationen und ruft passende Konstruktor der Klasse TMDIChild auf.

Die Konstruktoren der Klasse TMDIChild [ChildWin.cpp]

Beide Konstruktoren rufen ihrerseits die Konstruktoren von TCA und TWorld auf und legen die Verweise CA und Field an. So ist festgelegt, welche TCA - und TWorld - Instanzen zu welchem untergeordneten MDI-Fenster, also zu welcher TMDIChild - Instanz gehören. TWorld definiert den ZR.

Die Klasse TWorld [field.h]

Die Klasse TWorld ist im Wesentlichen in der Lage, PBML-Dateien zu laden und zu speichern (auch Ausschnitte) und den Zustand des ZRs über die Eigenschaft Cell[][] abrufbar zu halten.

TWorld ist programmiertechnisch gesehen nicht sehr interessant (ausgenommen der Zeigerarithmethik, die jedoch schon anhand der Klasse TByteList erläutert wurde) und die Schnittstellen sind m.E. intuitiv erfassbar, darum werden wir uns nun der Klasse TCA zu.

Die Klasse TCA [ca.h]

Ausgenommen der Interpretierung von CAL (realisiert durch TInterpreter) und dem Handling des ZRs (realisiert durch TWorld) fällt alles andere zur Definition eines CAs Nötige der Klasse TCA zu. Dazu gehört:

• Der Dateiname ( pFileName )
• Die Wertemenge der Zellen ( ValueCount )
• Die Dynamik ( Synchron, bWidth, bHeight )

Um die Dynamik des CAs zu definieren stehen die Variablen Synchron, bWidth und bHeight zur Verfügung. Sollte Synchron auf true gesetzt sein wird der CA komplett synchron iteriert, andererseits definieren bWidth und bHeight die Ausmaße der Blöcke, die intern synchron, unter sich aber asynchron in Leserichtung abgearbeitet werden (wie im Generator festgelegt).

Kehren wir wieder zurück zu unserem Ausgangsbeispiel. Der Konstruktor verlangt einen Dateinamen, folglich gibt es keine TCA - Instanz, die nicht aus einem CAP-Protokoll mit CAL geladen wurde. Der Ladevorgang wird durch die Prozedur TCA::LoadFromFile(...) durchgeführt. Sie verarbeitet die CAP-Header Informationen und schreibt den CAL-Quelltext in TInterpreter::CAL (TStringList).

Die Klasse TInterpreter [interpret.h]

Nun hat TInterpreter den CAL-Quelltext, mit dessen Hilfe wir nun zur eigentlichen Umsetzung der Lösungsidee zu kommen. In der Klasse TInterpreter laufen alle Stränge wieder zusammen.

Die Zustandsübergangsfunktion kann wie schon oben erwähnt entweder durch Echtzeitinterpretierung von CAL oder durch eine Zustandsübergangstabelle realisiert werden. Wir wenden uns zunächst nur der ersten Möglichkeit zu, da die zweite von der ersten Gebrauch macht und somit auf ihr basiert.

Die Funktion TInterpreter::Prepare(..) [interpret.cpp]

Die Prozedur TCA::LoadFromFile(...) ruft, nachdem sie die CAP-Header Informationen etc. ausgewertet hat, die Funktion TInterpreter::Prepare(..) auf. Diese Funktion übernimmt den eigentlichen Interpretierungsvorgang und wandelt den CAL-Quelltext in die in der Lösungsidee beschriebene Speicherstruktur um.

Auffallend an dieser Prozedur ist, dass zwei ähnliche for-Schleifen aufeinander folgen. Sie beide iterieren eine Schleifenvariable i, um nacheinander alle CAL-Quelltextzeilen, die ja gleichzeitig immer einen CAL-Befehl darstellen, auswerten zu können. In beiden for-Schleifen ist auch eine switch-Anweisung gleichen Aufbaus vorhanden. Sie ermittelt, um welche Befehlsart (mk, st, jp oder vd) es sich in der aktuellen CAL-Quelltextzeile handelt. Ab dieser Stelle unterscheiden sich jedoch die beiden for-Schleifen.

Die erste for-Schleife initalisiert alle Variablen und Integerkonstanten. Dies ist notwendig, da die Ablegung dieser in TByteList - Instanzen geschieht. Ändert sich die Zahl der Einträge einer TByteList - Instanzen , dann ändern sich womöglich auch die Speicheradressen der einzelnen Einträge, da es sein kann, dass realloc(...) den gesamten von TByteList::StartPtr referenzierten Speicherblock verschiebt und somit auch TByteList::StartPtr selbst ändert. Bevor also TInterpreter eine Speicheradresse eines Eintrags einer TByteList - Instanz direkt oder indirekt (über TArith - Instanzen) referenziert muss TByteList:Count festgelegt sein. Um TByteList:Count festzulegen werden alle Variablen und Integerkonstanten zunächst zu einer TByteList - Instanz hinzugefügt, um dann später (in der zweiten for-Schleife) wie in der Lösungsidee vorgesehen in einer Liste refernziert zu werden. Die in der ersten for-Schleife verwendete Funktion TInterpreter::InitOps() filtert alle Variablen und Integerkonstanten aus einem Ausdruck heraus und benutzt TArithList::InitOp(...), um sie in TInterpreter::VarList beziehungsweise TInterpreter::ConstList abzulegen.

Die zweite for-Schleife kann nun die drei Listen AusdruckList, ConditionList und TargetList füllen. Dazu wird die Prozedur TInterpreter::Add(...) verwendet, die wiederum TInterpreter::StringToArith(...) aufruft, um aus Ausdrücken vorliegend als Zeichenkette von den Listen referenzierbare TArith-Instanzen zu machen.

Zwei Optimierungsmethoden

Die Anwendung der Zustandsübergangsfunktion kann auf zwei unterschiedlichen Wegen geschehen; durch Echtzeitinterpretierung von CAL oder durch eine Zustandsübergangstabelle.

Echtzeitinterpretierung von CAL

Der erste Weg geht bei jeder zu berechnenden Zelle alle in den drei Listen gespeicherten Befehle durch, führt sie aus und berechnet so den neuen Zustand der Zelle. Genau dies tut die Funktion TInterpreter::CalcInterpret().

Die for-Schleife benutzt die Variable ActLine, um sie zu iterieren und so von CAL-Befehl zu CAL-Befehl zu gelangen. ActLine und LC gehören zu den reservierten Variablen, sie können also durch CAL-Befehle referenziert und so auch verändert werden. LC (steht für Last Condition) ist eine Variable, die angibt, ob die Bedingung für die Ausführung des letzten CAL-Befehls erfüllt worden ist. Sie wird in CAL zum Beispiel für die Umsetzung einer ABC typischen if-else-Anweisung gebraucht.

Zustandsübergangstabelle

Der zweite Weg zur Anwendung der Zustandsübergangsfunktion ist die Zustandsübergangstabelle. Hier werden alle möglichen Nachbarschaftskonstellationen durchgespielt und das Ergebnis der Zustandsübergangsfunktion in einer Tabelle gespeichert. Soll nun eine Zelle iteriert werden wird in der Tabelle nachgeschlagen. Dies tut die Funktion TInterpreter::CalcTable().

Die Funktion SetCalcMode(..)

Die Funktion TInterpreter::SetCalcMode(..) definiert die gewählte Optimierungsmethode und kann zwischen ihnen hin und her schalten.

Um bequem mit dem Befehl

die Zustandsübergangsfunktion anzuwenden zeigt der Zeiger TInterpreter::Calc vom Typ Zeiger auf Funktion entweder auf TInterpreter::CalcInterpret() (bei Echtzeitinterpretierung von CAL ) oder auf TInterpreter::CalcTable() (bei Zustandsübergangstabelle). Sollte Zustandsübergangstabelle gewählt worden sein erstellt SetCalcMode(..) diese im else-Zweig. Dort werden erst einmal alle Nachbarn (sprich: Alle Einträge von TCellDB::Values) auf den kleinsten Wert der Wertemenge gesetzt und dann CalcList mit der korrekten Größe initalisiert.CalcList stellt die Zustandsübergangstabelle dar (Als TByteList-Instanz), die dann durch die Befehlszeile

mit Werten gefüllt wird.

Die Funktion InitCombi(..)

Bei InitCombi(..) handelt es sich um eine rekursive Funktion, die alle möglichen Kombinationen der Werte in pNeighbours->Values durchgeht, die Zustandsübergangsfunktion anwendet und das Ergebnis in CalcList ablegt.

Die for-Schleife geht für den Eintrag in pNeighbours->Values, der an der mit Index bezeichneten Stelle steht, alle möglichen Werte durch und wendet die Zustandsübergangsfunktion an. Damit auch alle Einträge von in pNeighbours->Values sich dieser Prozedur unterziehen ruft InitCombi(..) sich zum Ende rekursiv selbst auf, jedoch mit dekreminiertem Argument.

Abschließend sei gesagt, dass TCellDB::GetCombi() aus allen Werten in TCellDB::Values eine Ganzzahl generiert, die dann in TInterpreter::CalcList als Index fungiert. TCellDB::SetCombi() kann aus der generierten Ganzzahl wieder die Werte von TCellDB::Values ermitteln, um nicht den rekursiven Durchlauf aller möglichen Nachbarschaftskonstellationen durch Zuweisungen an die ABC-Variable Cell[][] zu behindern.

Iteration eines CAs

Kommen wir nun zur praktischen Anwendung der im letztem Kapitel aufgezeigten Speicherstrukturen und Mechanismen. Während das vorherige Kapitel auf die Abläufen einging, die eintreten, wenn ein neuer CA geladen wird, beschäftigt sich dieses Kapitel mit den Vorgängen, die in Gang gesetzt werden, wenn der Benutzer eine Simulation startet.

Die Funktion TChildWin::Iteration(..)

Wenn eine Simulation gestartet wird wird die Funktion TChildWin::Iteration(..) aufgerufen. Sie benötigt als Argument die Anzahl der Iterationen, die ausgeführt werden sollen.

Im vorliegenden Quelltext wurde der Programmcode für asynchrone Dynamik weggeschnitten, da er dem der synchronen Dynamik sehr ähnlich ist. Alle wesentlichen Mechanismen greifen bei synchroner und asynchroner Dynamik auf gleiche Weise, ein Unterschied ist jediglich im Schleifenalgorithmus, der den ZR abtastet, zu finden.

Auffällig im Quelltext sind zunächst drei ineinander verschachtelte for-Schleifen. Die äußerste Schleife ist für die Anzahl der Iterationen zuständig. i bezeichnet demnach die Anzahl der Iterationen, die schon gemacht wurden. Die beiden inneren Schleifen inkreminieren jeweils die Schleifenvariablen x und y, um jede einzelne Zelle zu erreichen. Im Inneren der beiden Schleifen liegt also der Programmcode, der auf jede Zelle angewandt wird. Wir wollen ihn Zeile für Zeile durchgehen, da hier der zentrale Punkt bei der Simulation allgemeiner CAs liegt.

Wir erinnern uns, dass TCellDB relative Bezüge speichert, um die Nachbarschaft zu simulieren, gleichzeitig jedoch TInterpreter feste Speicheradressen zum Rechnen braucht. Existieren nun Verweise in einer der drei Listen von TInterpreter, die die Interpretierung von CAL organisieren, geht TInterpreter davon aus, dass sich hinter diesen Verweisen die Zustände der Nachbarn befinden. Da jedoch bei jeder Zelle auch die Nachbarn unterschiedlich sind, müssen diese Werte vor jedem Anwenden der Zustandsübergangsfunktion aktualisiert werden. Dies geschieht durch die Funktion TCellDB::ActValues(..) in der Programmtextzeile oben.

Nun kann die Zustandsübergangsfunktion angewendet werden. Da Calc ein Zeiger vom Typ Zeiger auf Funktion ist und immer auf die Funktion der derzeit verwendeten Optimierungsmethode zeigt ist hier keine weitere Unterscheidung dahingehend nötig.

Jede TCellDB-Instanz hat automatisch die Zelle Cell[0][0] in ihren Listen. Schon im Konstruktor wird diese Zelle hinzugefügt, so ist sie also auch immer gleichzeitig der erste Eintrag. Diesen Eintrag kann man mithilfe von TCellDB::GetValue() abrufen. Da der Rückgabewert der Zustandsübergangsfunktion, wie wir uns erinnern, durch Zuweisung an die Zelle Cell[0][0] realisiert wird, ist also jetzt in NewStatus der neue Zustand der Zelle Cell[x][y] gespeichert.

Nun wird überprüft, ob sich der Zustand der Zelle geändert hat. Die Zustandsübergangsfunktion hat keinen direkten Zugriff auf den ZR, und so ist folglich auch noch der alte Wert in Field->Cell[x][y] gespeichert. Wenn der Zustand der Zelle sich geändert hat wird diese mitsamt ihrem neuen Zustand in PointsToChange gespeichert. PointsToChange ist ein TValuePointList-Objekt [intlist.h]. Die Klasse TValuePointList stellt eine Liste von Punkten dar, denen je ein Wert zugeordnet wird. Wenn der neue Zustand der Zelle gleich in den ZR übertragen werden würde wäre eine synchrone Dynamik nicht mehr möglich. Stattdessen beinhaltet PointsToChange so alle Koordinaten der bei einer Iteration veränderte Zellen zuzüglich den neuen Werten. Diese Werte werden dann erst nach dem Anwenden der Zustandsübergangsfunktion auf jede Zelle in den ZR mithilfe einer while-Schleife übertragen.

Die Funktion IsInFieldRect(x,y) stellt fest, ob die Zelle Cell[x][y] in dem Ausschnitt des ZRs zu sehen ist, der durch das untergeordnete MDI-Fenster gezeigt wird. Wenn ja, wird diese Zelle zu PointsToDraw hinzugefügt. PointsToDraw ist ein Objekt der Klasse TUniquePointList [intlist.h], die eine einfache Liste von Punkten darstellt, doppelte Einträge aber von vornerein ausschließt. In PointsToDraw sind jene Zellen verzeichnet, deren Zustand sich von ihrem momentanen Erscheinungsbild unterscheidet und so neugezeichnet werden muss, sollte die Anzeige des Feldes aktualisiert werden.

Nach dem Abtasten des ZRs durch die besprochenen verschachtelten Schleifen folgt eine auch schon angesprochene while-Schleife, die die Veränderungen in den ZR überträgt. Die Variable ActStatistics gibt an, ob Statistiken protokolliert werden können und sollen. Die restlichen Programmtextzeilen innerhalb der großen äußeren for-Schleife, die i inkreminiert, kümmern sich um die korrekte Aktualisierung der Anzeige verschiedener Bereiche, wie es im Simulationsassistent eingestellt wurde.

3.3.4 Aufgabenfeld Statistik

In diesem Kapitel soll es um die Umsetzungen der statistischen Möglichkeiten von celmac 2.0 gehen. Vorraussetzung für dieses Kapitel ist die Kentniss über den Begriff der Kombination, das Sie im Kapitel Bedienung von celmac 2.0 bei der Abhandlung der Anwendung des statistischen Möglichkeiten von celmac im Kapitel Kombination erhalten.

Die Klasse TStatistics [stats.h]

Eine zentrale Rolle bei der Verwaltung von Statistiken spielt die Klasse TStatistics. Eine Instanz dieser Klasse steht genau für eine Statistik. Als Statistik wird eine Sammlung von mehreren Auszählungen immer gleicher Kombinationen bezeichnet, wie sie zum Beispiel in einer SPG-Datei abgelegt werden kann.

Im vorliegenden Quelltext wurden die für die mit dem Schlüsselwort __property versehenden Elemente nötigen Funktion (Getter und Setter) sowie Konstruktoren und der Destruktor entfernt, da diese für die Erläuterung der Klasse nicht nötig sind.

Zentrale Elemente Klasse TStatistics sind die gleich im Konstruktor initalisierten Zeiger CombiPtr und EntriesPtr, die Instanzen von TPtrList referenzieren. Elemente der von CombiPtr referenzierten Instanz zeigen auf TByteList-Objekte. Somit stellt CombiPtr eine Liste von TByteList-Instanzen dar. Da man mithilfe von TByteList eine Kombination ablegen kann handelt es sich hier also um eine Liste von Kombinationen; die Kombinationen, die in dieser Statistik überwacht werden. Elemente der von EntriesPtr referenzierten TPtrList-Instanz zeigen auf TStatEntry-Instanzen, die später genauer erläutert wird. Hier sei jediglich gesagt, dass TStatEntry die Auszählungen einer Generation speichert, sodass also TEntriesPtr eine Liste von Auszählungen darstellt.

Wir haben also nun die Möglichkeit, beliebig viele Kombinationen und beliebig viele Auszählungen zu speichern, die mit Combis[int] und Entries[int] abgerufen werden können. Nichts anderes ist eine Statistik, wie wir sie oben definiert haben. Darüber hinaus besitzt TStatistics eine Vielzahl von Möglichkeiten, Kombinationen und Auszählungen hinzuzufügen (AddCombi(..) und AddEntry(..)) oder zu löschen (DelCombi(..) und DelEntry(..)). CombiCount und EntryCount geben jeweils die Größe der beiden Listen an. Die Variable TPtrList gibt an, ob aktuell Statistiken mitprotokolliert werden sollen, also ob das Häckchen neben Statistische Aufzeichnung im Statistikassistenten gesetzt ist. CombiToStr(..) ist in der Lage, die Kombination an einer bestimmten Stelle in der von CombiPtr referenzierten TPtrList-Instanz in für Menschen lesbarer Form auszugeben.

Oben konstatierten wir, dass eine TStatistics-Instanz immer für eine Statistik steht. Eine Statistik hat ihrem Ursprung entweder in einer SPG-Datei oder in einem aktuell geöffnetem CAs, bei dessen Iterationen statistische Aufzeichnungen gemacht wurden. Sollte Ersteres eingetreten sein wird in pFileName der Dateiname gespeichert. In diesem Fall ist Field ein NULL-Zeiger. Sollte jedoch der zweiteres der Fall sein wird von Field die entsprechende TWorld-Instanz referenziert. Auch in TWorld befindet sich der Zeiger Statistics, der in diesem Fall die TStatistics-Instanz referenziert. Aufgrund dieser gegenseitigen Beziehung befindet sich notwendigerweise am Anfang von [stats.h] bzw. [field.h] eine unvollständige Deklaration der Klasse TWorld bzw. TStatistics. Wenn durch den Statistikassistenten eine Statistik gespeichert oder durch ihn eine neue Statistik geladen worden sein bezieht sich diese TStatistics-Instanz immernoch auf den aktuell geöffneten CA, hat jedoch einen Dateinamen zu referenzieren. In diesem Fall greifen beide oben aufgezeigten Mechanismen.

Die Funktion SaveToFile legt eine SPG-Datei an und speichert den Dateinamen in pFileName. LoadFromFile(..) ist im private-Teil deklariert, da diese Funktion nur vom Konstruktor aufgerufen werden darf. Lädt also der Statistikassistent eine Datei erstellt er eine neue TStatistics-Instanz, die die Datei lädt, und ersetzt sie durch die alte Statistik.

Die Klasse TStatEntry [stats.h]

Wir stellten bereits fest, dass die Klasse TStatEntry Auszählungen speichert. Sie verfügt so über eine Liste von Ganzzahlen (StrtItems), die die Auszählungen an sich speichert, und der Variable pGeneration, die, wie leicht zu erahnen, die Generation ablegt, in der diese Auszählungen vonstatten gingen. Die Auszählungen werden in der Funktion TStatistics::AddEntry() (ohne Argumente) gemacht.

Der Statistikassistent

Wie leicht feszustellen ist (siehe Konstruktoren von TWorld) verfügt nicht jeder im Player geöffnete CA über eine TStatistics-Instanz. Diese ist auch solange nicht nötig, bis ein Bedarf an einer Statistik entsteht. Dies ist frühstens dann, wenn der Statistikassistent geöffnet wird. Der Statistikassistent benötigt eine TStatistics-Instanz um funktionieren zu können, es muss also gewährleistet sein, dass jeder aktive CA, bei dem der Statistikassistent geöffnet ist, über eine TStatistics-Instanz verfügt. Wird der Statistikassistent eingeblendet oder ändert sich der aktive CA (d.h. wechselt der Fokus zwischen den untergeordneten MDI-Fenster) wird die Funktion TStatForm::InitValues() aufgerufen.

Die Funktion TStatForm::InitValues()

Richten wir unser Augenmerk zunächst auf die erste if-Anweisung. Hier wird, sollte noch keine TStatistics-Instanz vorhanden sein, wie oben beschrieben eine neue initalisiert. Die zweite if-Anweisung veranlasst eine Auszählung der aktuellen Generation, falls dies nicht schon geschehen ist. Dieses Vorgehen ist darin begründet, dass sonst unaktuelle Werte ausgegeben werden könnten, wie es dann in der dritten if-Anweisung unter der Bedingung getan wird, dass Kombinationen schon verzeichnet sind.

Statistische Auswertung

Das grafische Benutzerinterface für die statistische Auswertung ist in [stat_calc.dfm] zu finden. Die in der entsprechenden H-Datei deklarierte Klasse TStatCalcForm beinhaltet jedoch nicht allen Quelltext, der für die Visualisierung einer Statistik (sprich einer TStatistics-Instanz) nötig ist.

Die Klasse TGraphBar [graphbar.h]

Mit einer Instanz der Klasse TGraphBar und einer Instanz der Klasse TImage [ExtCtrls.hpp] kann ein Liniendiagramm mit beliebig vielen Graphen dargestellt werden.

Der Zeiger Image verweist auf die nötige TImage-Instanz. Es folgen die Objekte x und y der Unterklasse TAxis. TGraphBar definiert die Wertemenge der Achsen und besitzt die Funktion GetCoord(..), die absolute Werte mit einer festgelegten Skala verrechnet, sodass diese in die TImage-Komponente passen. TGraphBar geht davon aus, dass die TGraphBar-Komponente nicht höher oder breiter als 5000 Pixel wird, was eine sehr realistische Annahme ist. Diese Höchstgrenze wurde gesetzt, um mögliche Integer-Überläufe abfangen zu können ohne die Funktionalität merklich zu beeinflussen.

Darauf folgen die beiden Zeiger GraphStatistics und GraphIndexes definieren die angezeigten Graphen. Es handelt sich beide Male um Listen. Die erste Liste zeigt auf TStatistics-Instanzen der anzuzeigenden Graphen, während GraphIndexes den Index der anzuzeigenden Kombination in dieser TStatistics-Instanz ablegt. Auf diese Listen kann man mittels der im public-Teil deklarierten Eigenschaften Statistics[int] und CombiIndexes[int] zugreifen. Alle Elementfunktion von TGraphBar außer SearchGrapH(..) und ActDisp(..) dienen dem Editieren dieser Listen. Mittels SearchGraph(..) ist es möglich, festzustellen, ob sich ein Graph (sprich das übergebene Paar einer TStatistics-Instanz und einer Ganzzahl) in der Liste der anzuzeigenden Graphen befindet.

Die Funktion TGraphBar::ActDisp(..) [graphbar.cpp]

Diese Funktion zeichnet die Graphen in einem übergebenen Intervall in die TImage-Komponente. Hier sei die grobe Funktionsweise beschrieben.

Zunächst werden Minimal und Maximalwerte für die y-Achse ermittelt. Dies ist bei der x-Achse nicht nötig, da hier die Grenzen ja Funktionsargumente sind und somit als gegeben betrachtet werden können. Die ermittelten Werte werden mit der Höhe bzw Breite der TImage-Komponente verrechnet und so eine Umrechnungsskala festgesetzt (TGraphBar::TAxis::Scale), die absolute Werte passend zur Breite und Höhe der TImage-Komponente skaliert. Anschließend werden die Achsen sinnvoll beschriftet. Erst danach werden die Graphen nacheinander gezeichnet, indem eine for-Schleife alle TStatEntry-Instanzen, die in den entsprechenden Bereich fallen, nacheinander durchgeht und die daraus resultierenden Punkte (x ist die Generation, während y die Auszählung der entsprechenden Kombination darstellt) zu einem Graphen verbindet.

3.4 Anwendung der statistischen Möglichkeiten von celmac 2.0

3.4.1 Grundlegendes

Eine meiner Ambitionen, celmac 2.0 zu schreiben, rüherte daher, ausprobieren zu wollen, in wie weit sich CAs als Zufallszahlengeneratoren eignen. Dieses Kapitel beschäftigte sich mit diesem Thema. Leider konnte ich aufgrund Zeitdrucks nicht soviele Zufallsversuche starten, wie ich es für nötig gehalten hätte, um ein klares Bild des Sachverhalts zu erhalten. Dennoch sind die hier aufgezeigten Ergebnisse m.E. als Grundlage weiterer Untersuchungen brauchbar. Ich startete verschiedene Zufallsversuche mit den CAs Greenberg-Hastings Automat, Stephen Wolframs Universum und Game Of Life.

3.4.2 Greenberg-Hastings Automat

Der Greenberg-Hastings Automat ist für das Erstellen einer Zufallszahlenkette ungeeignet, da es sich hier um eine Art Epidemiemodell handelt. Jede Zelle durchläuft, sobald sie angeregt ist, eine bestimmte Reihe von Zuständen und kehrt wieder in den Ausgangszustand zurück. Dies hat ein bestimmtes Verhalten des ZRs zu Folge. Bei den meisten Ausgangskonstellationen der Träger (Träger nennt man die Zellen, die am Anfang der Simulation nicht den Zustand 0 haben) ist ein sich wellenförmig ausbreitendes Muster zu erkennen, das sich natürlich nicht sehr gut als Grundlage einer Zufallszahlenkette verwenden lässt.

3.4.3 Stephen Wolframs Universum

Stephen Wolfram entwickelte diesen CA, um Vorgänge nach dem Urknall in einem Modell visualisieren zu können. Demnach stellt dieser CA eine Entwicklung dar. Allein dieser Fakt macht ihn für die Generation von Zufallszahlen unbrauchbar. Weiterhin lassen sich nach einem Urknall in Stephen Wolframs Universum nach einer kurzen Eliminierungsphase entweder oszillierende oder konstante Strukturen feststellen. Beides ist für die Erstellung von Zufallszahlen kontraproduktiv.

3.4.4 Game Of Life

Unter den untersuchten CAs liefert Game Of Life das beste Ergebnis. Zwei charakteristische Zufallsversuche seien hier behandelt.

Regelwelt 23/3

Zunächst untersuchte ich die ursprüngliche Spielvariante 23/3. In dieser Welt gibt es viele statische, oszillierende und symmetrische Muster, deshalb versprach ich mir mit dieser Variante wenig Erfolg. Ich wußte jedoch, dass in dieser Welt das sogenannte Chaos Pentomino existiert, das, trotz seiner leicht erkennbaren Einfachheit, erstaunlich komplexe Vorgänge veranlasst. Der ZR war ein 100x100 Zellen großer Torus (d.h. die Enden beider Dimensionen des ZRs waren miteinander verbunden). Einziger Träger stellte das Pentomino dar.

Ergebnisse

Nach 1100 Iterationen existieren nur noch statische und oszillierende Objekte in dem ZR, sodass ich die Beobachtung auf die ersten 1100 Generationen beschränke. Verschiedene Kombinationen wurden überwacht, deren Kurven jedoch sehr der der Kombination 1 ähneln und diese nun stellvertretend für die anderen Kombinationen untersucht wird.

Dieser Verlauf sieht auf den ersten Blick im mittleren Teil recht zufällig aus. Generiert man nun jedoch aus den gesammelten Daten Zufallszahlenketten (Möglich in celmac 2.0 im Fenster Statistische Auswertung unter Datei->Zufallszahlenkette erstellen...) zeigt sich jedoch ein anderes Bild. In celmac ist es möglich, bei der Erstellung einer Zufallszahlenkette nur jewails die letzten Ziffern der Auszählungen zu benutzen. Wieviele Ziffern einer Auszählung benutzt wurden, ist in der folgenden Tabelle in den Titeln der Spalten zu sehen. Diese Tabelle zeigt die absolute Häufigkeit der Ziffern in der generierten Zufallszahlenkette in Abhängigkeit der Anzahl der verwendeten Ziffern pro Auszählung.

Es ist hier ein deutliches Übergewicht der Ziffer 1 zu erkennen, unabhängig davon, wieviel Ziffern einer Auszählung verwendet werden. Dies zu begründen fällt mir schwer, eine Vermutung habe ich dennoch. Im Laufe dieser 1100 Generationen erstehen immer wieder oszillierende und stabile Objekte, die jedoch dann durch Gleiter oder Chaos wieder zerstört werden. Diese Objekte könnten die Zufallskette negativ beeinflussen. Weiterhin gibt es in der Regelwelt 23/3 Strukturen, die sich ausdehnen, und Strukturen, die sich auflösen. Nun kann es sein, dass die Anzahl der lebenden Zellen in der einen Strukturart sich über längere Zeit hinweg von der Anzahl der lebenden Zellen in der anderen Strukturart unterscheidet und dadurch dieses Missverhältniss in der Zufasllszahlenkette entsteht.

Hierbei handelt es sich jediglich um Vermutungen, die jedoch auch wenn sie zutreffen nicht vollständig das Übergewicht der Ziffer 1 begründen können.

Regelwelt 125/125

Nach einigen Experimenten stellte sich die Regelwelt 125/125 als brauchbar heraus. In dieser Welt lebt eine Zelle mit eins, zwei oder fünf Nachbarn, andernfalls stirbt sie. Träger war eine einzige lebende Zelle, da dies als Auslöser sehr komplexen Verhaltens genügt. Ein 200x200 Zellen großer Torus stellte den ZR dar.

Ergebnisse

Es wurden mehrere Kombinationen überwacht, von denen alle relativ unterschiedliche Kurven darstellten. Von den überwachten Kombinationen sind folgende hier gezeigt.

Es entstehen drei Graphen, die nach circa 100 Iterationen in einem gewissen Wertebereich chaotisches Verhalten aufweisen. Schauen wir uns die erzeugte Zufallszahlenkette an, wie wir es in der Regelwelt 23/3 getan haben.

Je mehr Ziffern der Auszählung verwendet werden desto mehr sinkt auch die Qualität der Zufallszahlen. Dies ist wahrscheinlich darin zu begründen, dass der Graph eben nur in einem bestimmten Wertebereich chaotisches Verhalten aufzeigt, hier etwa zwischen 16000 und 18500. Die meisten Werte liegen jedoch in einem noch enger gesteckten Wertebereich, sodass hier die ersten Ziffern der Auszählungen immer gleich bleiben. Brauchbar ist jedoch die Zufallszahlenreihe, wenn man nur die letzte Ziffer jeder Auszählung benutzt. Hier beträgt die Abweichung der Häufigkeiten der verschiedenen Ziffern nur ca. 10 %.

3.4.5 Fazit

Auch eine Abweichung von 10 % kennzeichnet eine schlechtere Qualität von Zufallszahlen als die üblichen Algorithmen zur Zufallszahlengewinnung. Ferner sind bei genauerer Betrachtung auch dieser Zufallszahlenkette vereinzelt Muster zu erkennen (wie die häufige Wiederholung einer Ziffer), was gegen eine hohe Qualität dieser Kette spricht. Das Argument des vermehrten Rechenaufwands sollte auch nicht vernachlässigt werden. Abschließend ist zu sagen, dass die Tests, wie sie hier in diesem Umfang gemacht wurden, nicht zu einem befriedigenem Ergebnis geführt haben, dass jedoch damit nicht die Idee als solches verworfen werden muss. Ich persönlich bin der Meinung, dass es möglich ist, wesentlich qualitativ hochwertigere Zufallszahlenketten als die hier aufgezeigten mittels CAs generieren zu können.

4. Anhang

4.1 Changelog

Hier das Changelog seit der ersten Beta-Version.

• improve ABC-Highlighting (yeah, it is allready not acceptable, but I think it isn't important)
• fix topology issues
• choosing topology by popup-menu was broken
• several bugs if the base space is smaller than the window
• fix few spelling bugs in _german_ help :)
• decrementing cellstate by clicking on the base space was broken
• remove assistant for langton's ant (maybe I'll add it in further versions)
• close all opened assistants when you close a CA
• add "randomize field"
• celmac 2.0 in english is avaiable!
• german and english doc is valid xhtml again

4.2 Interne Darstellung der ABC-Operatoren

Da die teilweise zwei Zeichen langen ABC-Operatoren in TArith::Operator (Character) gespeichert werden sind Ersatzdarstellungen für diese Operatoren nötig. Hier finden Sie eine Liste aller ABC-Operatoren und ihren Entsprechungen im Arbeitsspeicher.

4.3 Zeiger in C++

C++ ist eine sehr zeigerorientierte Programmiersprache. Gerade in celmac 2.0, wo ja sehr hardwarenahes Programmieren erforderlich war, sind Zeiger ein unerlässliches Instrument. Hier kann nur ein kleiner Überblick gegeben werden, um eine Idee von dem Zeigerkonzept in C++ zu erhalten.

Man unterscheidet zwischen Zeiger auf Funktionen und Zeiger auf Objekte. Da in celmac 2.0 hauptsächlich nur Zeiger des zweiten Types verwendet werden beschäftigen wir uns ausschließlich mit dieser Kategorie.

Jede Variable ist im Hauptspeicher des Computers bei einer bestimmten Speicheradresse abgelegt. Ein Zeiger in C++ ist eine normale Variable, die jedoch nicht den Wert an sich, sondern die Speicheradresse, wo der Wert abgelegt ist, beinhaltet. Wir werden uns nun mit der theoretischen Grundlage befassen und dann diese an einem Beispiel anwenden.

4.3.1 Adressen

Wird nun also einem Zeiger ein Wert zugewiesen, ist dieser Wert eine Adresse. Das heißt der Wert an sich, der bei dieser Adresse gespeichert ist, bleibt davon unberühert, auch seine Adresse ändert sich nicht. Jediglich wird er nicht mehr von dem Zeiger referenziert, weil dieser jetzt auf eine neue Adresse zeigt. Der Umkehrschluss dieser Aussage, dass also der Zeiger konstant bleibt, wenn sich der referenzierte Wert ändert, gilt zusätzlich.

4.3.2 Operatoren

Um Zeiger verwenden gibt es zwei wichtige Operatoren in C++, den Adressoperator & und der Inhaltsoperator *. Der Adressoperator gibt die Adresse einer Variable an. Durch den Inhaltsoperator kann man durch einen Zeiger auf den referenzierten Wert zugreifen.

Es folgt ein stark kommentierter Quelltext zur Veranschaulichung des bis jetzt vermittelten Inhalts.

4.3.3 Zeigerarithmetik

Die praktische Anwendung von Zeigern kann eigentlich nur durch die Verwendung von Rechenoperationen erreicht werden. Zeiger kann man, wie auch schon oben im Quelltextbeispiel zu sehen, zuweisen. Weiterhin ist der Vergleich sowie die Addition und Subtraktion von Zeigern möglich.

Nach der Addition von 3 zu ptr enthält ptr nun eine um 6 Bytes höhere Adresse, da ein short-Element den Platz von 2 Bytes einnimmt (2*3=6). Von Zeigerarithmetik wird in celmac 2.0 zum Beispiel in der Klasse TByteList stark Gebrauch gemacht.

Glossar

Quellen

Alle URIs wurden am 05.06.2006 abgerufen

1. Hilfe von der Entwicklungsumgebung Borland C++ Builder 6 Enterprise, vorzugsweise die VCL Reference (Visual Component Libary Reference)
2. Scott Meyers: Effektiv C++ programmieren, 3. Auflage, ISBN: 3-8273-2297-9
3. Borland Turbo C++ 3.0 Programmierhandbuch
4. Oliver Böhm: C++ echt einfach, ISBN: 3-7723-7525-1
5. Technische Universität Darmstadt: Studienarbeit zum dem Thema Effiziente Implementierung zellularer Automaten in Software vorgelegt von Patrick Röder
6. Ian Stewart: Pentagonien, Andromeda und die gekämmte Kugel, ISBN: 3-8274-1548-9
7. http://www.uni-tuebingen.de/uni/bcm/schoenfisch/green.html
8. http://www.fim.uni-linz.ac.at/lva/rus/CellulareAutomaten/
9. Wikipedia

Hiermit erkläre ich, dass ich keine weiteren als die oben aufgezeigten Quellen benutzt habe.