In der letzten Zeit habe ich mich ein wenig mit einer möglichen Umsetzung des UML-Reasoner beschäftigt. Um ein Gefühl für den "Artenreichtum" eines Klassendiagramms auf der Objektebene (der Instanzebene) zu bekommen, spielte ich ein wenig rum. Zwei Klassen und eine eingerichtete Assoziation bildeten meine Ausgangsbasis. Maximal fünf Instanzen zu jeder Klasse sollte es geben. Ich schrieb mir einfache Routinen, die mir aus zwei Mengen ({a1, a2, a3, ...} und {b1, b2, b3, ...}) mit je fünf Elementen alle möglichen Relationen von der einen zur anderen Menge erzeugten -- unter jeweils unterschiedlichen Annahmen. Beispielsweise kann man das Paar (a1,b1) als gleichwertig mit (a2,b2) betrachten. Schließlich geht es ja nur um den Link von einer Instanz aus der ersten Menge zu einer Instanz aus der zweiten Menge. Man kann jedoch auch anders argumentieren, wenn man Instanz-Relationen über die Zeit betrachtet. Dann kann (a1,b1) die Folge einer anderen Konstellation sein als (a2,b2) und auch eine andere Fortsetzung finden. Wirklich? Bisweilen verstieg ich mich in haarigen Argumentationsketten.
Wie auch immer, eines wurde mir klar: Je nach Annahme explodiert mein Raum an Möglichkeiten enorm und nimmt fast erschreckende Ausmaße an. Wie soll da noch in sinnvoller Zeit der ganze Raum an Möglichkeiten generiert und auf Design-Beschränkungen überprüft werden. Gibt es einen anderen Ansatz?
Ich wandte mich Prolog zu, einer logischen Programmiersprache. Aber irgendwie überzeugte mich das nicht. Prolog geht ähnlich vor: es wird der gesamte Suchraum generiert und dann werden logische Beschränkungen überprüft. Das ist der so genannte "generate and test"-Ansatz. Damit kommt man auch nicht weiter.
Also begann ich Constraint Programming zu studieren, der nächste, naheliegende Ansatz. Es gibt dazu ein erfreulich dünnes und gutes Buch von Thom Frühwirth und Slim Abdennadher, "Essentials of Constraint Programming" (Springer, 2003) mit dem man sich innerhalb von ein, zwei Stunden in das Thema einarbeiten kann, vorausgesetzt man überspringt die Mathematik. Constraint Programming arbeitet nach der "constraint and generate"-Methodik. Der Ansatz ist sehr schön beschrieben in dem Buch "Concepts, Techniques, and Models of Computer Programming" von Peter Van Roy und Seif Haridi (MIT Press, 2004) -- das nächste Buch, das ich zu Rate zog. Sie können das mit der Programmiersprache Oz mit Hilfe von Mozart auch selber ausprobieren. Das Buch von Roy und Haridi basiert auf Oz.
Um Constraint Programming (CP) zu betreiben brauchen Sie jedoch keine spezielle Programmiersprache. Im Grunde kann CP als Bibliothek "nachgeladen" werden, sofern eine solche Bibliothek für Ihre Programmiersprache verfügbar ist. Es geht aber auch gänzlich ohne Bibliothek, wenn man das Prinzip verstanden hat. Per Zufall bin ich auf einen Artikel von Peter Norvig (übrigens Director of Research bei Google) gestoßen, der die Idee des Constraint Programming mit dem Wechselspiel aus Constraint Propagation and Search am Beispiel eines Sudoku-Lösers demonstriert; siehe "Solving Every Sudoku Puzzle". Der Code ist in Python geschrieben, verblüffend kurz und erweist sich als effizient für selbst "schwere" Sudokus.
Wenn Sie sich durch das Norvig-Beispiel gearbeitet haben, erahnen Sie es vielleicht auch: Ich glaube, hier ist der Schlüssel zu einer praktikablen Umsetzung des UML-Reasoners verborgen.
Wie auch immer, eines wurde mir klar: Je nach Annahme explodiert mein Raum an Möglichkeiten enorm und nimmt fast erschreckende Ausmaße an. Wie soll da noch in sinnvoller Zeit der ganze Raum an Möglichkeiten generiert und auf Design-Beschränkungen überprüft werden. Gibt es einen anderen Ansatz?
Ich wandte mich Prolog zu, einer logischen Programmiersprache. Aber irgendwie überzeugte mich das nicht. Prolog geht ähnlich vor: es wird der gesamte Suchraum generiert und dann werden logische Beschränkungen überprüft. Das ist der so genannte "generate and test"-Ansatz. Damit kommt man auch nicht weiter.
Also begann ich Constraint Programming zu studieren, der nächste, naheliegende Ansatz. Es gibt dazu ein erfreulich dünnes und gutes Buch von Thom Frühwirth und Slim Abdennadher, "Essentials of Constraint Programming" (Springer, 2003) mit dem man sich innerhalb von ein, zwei Stunden in das Thema einarbeiten kann, vorausgesetzt man überspringt die Mathematik. Constraint Programming arbeitet nach der "constraint and generate"-Methodik. Der Ansatz ist sehr schön beschrieben in dem Buch "Concepts, Techniques, and Models of Computer Programming" von Peter Van Roy und Seif Haridi (MIT Press, 2004) -- das nächste Buch, das ich zu Rate zog. Sie können das mit der Programmiersprache Oz mit Hilfe von Mozart auch selber ausprobieren. Das Buch von Roy und Haridi basiert auf Oz.
Um Constraint Programming (CP) zu betreiben brauchen Sie jedoch keine spezielle Programmiersprache. Im Grunde kann CP als Bibliothek "nachgeladen" werden, sofern eine solche Bibliothek für Ihre Programmiersprache verfügbar ist. Es geht aber auch gänzlich ohne Bibliothek, wenn man das Prinzip verstanden hat. Per Zufall bin ich auf einen Artikel von Peter Norvig (übrigens Director of Research bei Google) gestoßen, der die Idee des Constraint Programming mit dem Wechselspiel aus Constraint Propagation and Search am Beispiel eines Sudoku-Lösers demonstriert; siehe "Solving Every Sudoku Puzzle". Der Code ist in Python geschrieben, verblüffend kurz und erweist sich als effizient für selbst "schwere" Sudokus.
Wenn Sie sich durch das Norvig-Beispiel gearbeitet haben, erahnen Sie es vielleicht auch: Ich glaube, hier ist der Schlüssel zu einer praktikablen Umsetzung des UML-Reasoners verborgen.